Discrete Structure Exam Questions: 1. (a) (i) Identify whether the following propositions are logically equivalent: ¬(p ∨ q) and ¬p ∧ ¬q (ii) Use a truth table to check whethe... Discrete Structure Exam Questions: 1. (a) (i) Identify whether the following propositions are logically equivalent: ¬(p ∨ q) and ¬p ∧ ¬q (ii) Use a truth table to check whether the following proposition is a tautology or contradiction: (p ∧ q) ∨ R → p ∧ (q ∨ R) (b) A computer company receives 360 applications. 210 majored in computer science, 147 in business, and 51 in both. How many majored in neither? 2. (a) A person deposits 100,000 PKR. The bank yields 11% per year with interest compounded annually. Evaluate the amount that his son will get after 10 years. (b) Illustrate a closed formula for the recursive relation: a_k = a_{k-1} + 2 for k = 1, 2, 3, ..., a_0 = 1 (c) Use induction to prove: 1 + 3 + 6 + ... + n(n+1)/2 = n(n+1)(n+2) / 6 3. (a) Let X = {a, b, c} and Y = {w, x, y, z}. Define function K with the arrow diagrams. Is K one-to-one? Why or why not? Is it onto? Why or why not? (b) Let A = {0, 1, 2, 3} and define relation R = {(0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0), (3,3)}. Check if R is reflexive, symmetric, and transitive. Read more

Steps to Solve

1. Question 1(a)(i): Logical Equivalence

To determine if $\neg(p \lor q)$ and $\neg p \land \neg q$ are logically equivalent, we can use DeMorgan's Law, which states that $\neg(p \lor q) \equiv \neg p \land \neg q$. Therefore, they are logically equivalent.

2. Question 1(a)(ii): Tautology or Contradiction Using a Truth Table

We need to construct a truth table for $(p \land q) \lor R \rightarrow p \land (q \lor R)$.

Since the last column is not all True or all False, the proposition is neither a tautology nor a contradiction.

3. Question 1(b): Applicants Majoring Neither in Computer Science Nor Business

Let $C$ be the set of applicants who majored in computer science, and $B$ be the set of applicants who majored in business. We are given:

• $|C| = 210$
• $|B| = 147$
• $|C \cap B| = 51$
• Total applicants $= 360$

We want to find the number of applicants who majored in neither subject, which can be represented as $360 - |C \cup B|$.

Using the principle of inclusion-exclusion, we have: $|C \cup B| = |C| + |B| - |C \cap B| = 210 + 147 - 51 = 306$

Therefore, the number of applicants who majored in neither subject is: $360 - 306 = 54$

4. Question 2(a): Compound Interest Calculation

We are given the principal amount $P = 100,000$ PKR, the interest rate $r = 11% = 0.11$, and the number of years $t = 10$. The interest is compounded annually, so we can use the formula:

$A = P(1 + r)^t$

$A = 100,000(1 + 0.11)^{10} = 100,000(1.11)^{10} \approx 100,000 \times 2.8394 = 283,942$ PKR

5. Question 2(b): Closed Formula for Recursive Relation

The recursive relation is given by $a_k = a_{k-1} + 2$ for $k = 1, 2, 3, ...$ and $a_0 = 1$. We can find the first few terms: $a_0 = 1$ $a_1 = a_0 + 2 = 1 + 2 = 3$ $a_2 = a_1 + 2 = 3 + 2 = 5$ $a_3 = a_2 + 2 = 5 + 2 = 7$

We can observe that this is an arithmetic sequence with a common difference of 2. The general formula for an arithmetic sequence is $a_n = a_0 + nd$, where $a_0$ is the initial term and $d$ is the common difference. In this case, $a_0 = 1$ and $d = 2$.

So, the closed formula is: $a_k = 1 + 2k$

6. Question 2(c): Proof by Induction

We want to prove that $1 + 3 + 6 + ... + \frac{n(n+1)}{2} = \frac{n(n+1)(n+2)}{6}$ for all positive integers $n$.

• Base Case (n=1): For $n = 1$, the left-hand side (LHS) is $\frac{1(1+1)}{2} = 1$. The right-hand side (RHS) is $\frac{1(1+1)(1+2)}{6} = \frac{1(2)(3)}{6} = 1$. Thus, the base case holds.

• Inductive Hypothesis: Assume that the formula holds for some positive integer $k$. That is, assume $1 + 3 + 6 + ... + \frac{k(k+1)}{2} = \frac{k(k+1)(k+2)}{6}$

• Inductive Step: We want to prove that the formula also holds for $n = k+1$. That is, we want to show that: $1 + 3 + 6 + ... + \frac{k(k+1)}{2} + \frac{(k+1)(k+2)}{2} = \frac{(k+1)(k+2)(k+3)}{6}$

  Starting with the LHS and using the inductive hypothesis: $1 + 3 + 6 + ... + \frac{k(k+1)}{2} + \frac{(k+1)(k+2)}{2} = \frac{k(k+1)(k+2)}{6} + \frac{(k+1)(k+2)}{2}$

  Now, we simplify the expression: $\frac{k(k+1)(k+2)}{6} + \frac{3(k+1)(k+2)}{6} = \frac{(k+1)(k+2)(k+3)}{6}$

Thus, the formula holds for $n = k+1$.

• Conclusion: By the principle of mathematical induction, the formula holds for all positive integers $n$.

7. Question 3(a)(i): One-to-one Function

A function is one-to-one (injective) if each element in the codomain is mapped to by at most one element in the domain. From the arrow diagram, we see that $K(a) = w$, $K(b) = x$ and $K(c) = x$. Since both $b$ and $c$ map to $x$, the function is not one-to-one.

8. Question 3(a)(ii): Onto Function

A function is onto (surjective) if every element in the codomain is mapped to by at least one element in the domain. The codomain is ${w, x, y, z}$. From the arrow diagram, we see that $w$ and $x$ are mapped to, but $y$ and $z$ are not. Therefore, the function is not onto.

9. Question 3(b): Relation Properties

$A = {0, 1, 2, 3}$ and $R = {(0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0), (3,3)}$

• Reflexive: A relation is reflexive if $(a, a) \in R$ for all $a \in A$. Since $(0,0), (1,1), (2,2), (3,3) \in R$, the relation is reflexive.

• Symmetric: A relation is symmetric if $(a, b) \in R$ implies $(b, a) \in R$ for all $a, b \in A$. $(0,1) \in R$ and $(1,0) \in R$. Also, $(0,3) \in R$ and $(3,0) \in R$. The remaining elements of $R$ of the form $(a, a)$ don't violate symmetry. So, the relation is symmetric.

• Transitive: A relation is transitive if $(a, b) \in R$ and $(b, c) \in R$ implies $(a, c) \in R$ for all $a, b, c \in A$.

  • $(0,1) \in R$ and $(1,0) \in R$, we need $(0,0) \in R$, which is true.
  • $(0,1) \in R$ and $(1,1) \in R$, we need $(0,1) \in R$, which is true.
  • $(0,3) \in R$ and $(3,0) \in R$, we need $(0,0) \in R$, which is true.
  • $(0,3) \in R$ and $(3,3) \in R$, we need $(0,3) \in R$, which is true.
  • $(1,0) \in R$ and $(0,1) \in R$, we need $(1,1) \in R$, which is true.
  • $(1,0) \in R$ and $(0,3) \in R$, we need $(1,3) \in R$. But $(1,3) \notin R$

Therefore, the relation is not transitive.