Discrete Mathematics Problem Solving Techniques and Solutions
Discrete Mathematics Problem Set Solutions
1. (d) Constructing Venn Diagrams for Set Expressions
Illustrate the following set expressions using Venn diagrams:
- \( \bar{A} \) (Complement of A)
- \( A \Delta B \) (Symmetric Difference)
Solution Instructions:
- For \( \bar{A} \): Shade the region outside set \( A \) in a single circle diagram.
- For \( A \Delta B \) (Symmetric Difference): Shade the regions in two circles representing \( A \) and \( B \) that are exclusively in \( A \) or \( B \) (i.e., \( A \cap B’ \) and \( A’ \cap B \)).
(2 marks)
1. (e) Determining the Domain Where Two Functions Are Equal
Find the domain for which the functions \( f(x) = 3x^2 – 1 \) and \( g(x) = 1 – 5x \) are equal.
Solution Steps:
- Set \( f(x) = g(x) \):
\[ 3x^2 – 1 = 1 – 5x \] \[ 3x^2 + 5x – 2 = 0 \]
- Solve using the quadratic formula: \( x = \frac{-b \pm \sqrt{b^2 – 4ac}}{2a} \), where \( a = 3 \), \( b = 5 \), \( c = -2 \).
- Discriminant: \( 5^2 – 4 \cdot 3 \cdot (-2) = 25 + 24 = 49 \)
- Calculate roots: \( x = \frac{-5 \pm \sqrt{49}}{6} = \frac{-5 \pm 7}{6} \)
- Root 1: \( x = \frac{2}{6} = \frac{1}{3} \)
- Root 2: \( x = \frac{-12}{6} = -2 \)
The domain (values of \( x \) where they are equal) is: \( x = -2 \) or \( x = \frac{1}{3} \). (2 marks)
1. (f) Calculating Combinations: Choosing 8 out of 10 Questions
In how many ways can a student choose 8 questions out of 10 questions in an exam?
Calculation:
Use the combination formula \( C(n, r) = \frac{n!}{r!(n-r)!} \):
\[ C(10, 8) = C(10, 2) = \frac{10!}{2!(10-2)!} = \frac{10 \cdot 9}{2 \cdot 1} = 45 \]
The number of ways is 45. (2 marks)
1. (g) Proving Logical Equivalence Using De Morgan’s Laws
Prove the following equivalence: \( \neg (\exists x P(x)) \equiv \forall x (\neg P(x)) \)
Proof:
By applying De Morgan’s laws and logical equivalence:
The expression \( \neg (\exists x P(x)) \) means “it is not the case that there exists an \( x \) such that \( P(x) \) is true.”
This statement is logically equivalent to saying “for all \( x \), \( P(x) \) is false,” which is formally written as \( \forall x (\neg P(x)) \).
Hence, the equivalence is proved. (2 marks)
1. (h) Calculating Sum and Product of Functions
Let \( f(x) = \frac{1}{x} \) and \( g(x) = x^3 + 2 \), where \( x \in \mathbb{R} \). Find \( (f + g)(x) \) and \( (fg)(x) \).
Function Operations:
- Sum: \( (f + g)(x) = f(x) + g(x) = \frac{1}{x} + x^3 + 2 \)
- Product: \( (fg)(x) = f(x) \cdot g(x) = \frac{1}{x} \cdot (x^3 + 2) = \frac{x^3 + 2}{x} = x^2 + \frac{2}{x} \)
Note: The domain for both resulting functions excludes \( x = 0 \). (2 marks)
1. (i) Proof by Mathematical Induction for Sum of Squares
Use mathematical induction to prove: \( 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6} \)
Induction Steps:
- Base Case (\( n = 1 \)):
- Left side = \( 1^2 = 1 \)
- Right side = \( \frac{1 \cdot (1+1) \cdot (2\cdot 1+1)}{6} = \frac{1 \cdot 2 \cdot 3}{6} = 1 \).
The formula holds for \( n=1 \).
- Inductive Step (\( n = k \to n = k + 1 \)):
Assume the formula is true for \( n = k \):
\[ 1^2 + \ldots + k^2 = \frac{k(k+1)(2k+1)}{6} \]
We must show it holds for \( n = k + 1 \):
\[ 1^2 + \ldots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \]
After algebraic manipulation, this simplifies to:
\[ \frac{(k+1)(k+2)(2k+3)}{6} \]
This matches the original formula evaluated at \( n = k + 1 \).
Hence, the formula is proved by induction. (2 marks)
1. (j) Finding Permutations of Letters in “MUST”
How many distinct three-letter words can be formed from the letters of the word “MUST”?
Calculation:
The word “MUST” has 4 distinct letters (M, U, S, T). We are choosing and arranging 3 of them. This requires calculating the permutation \( P(n, r) \).
Number of three-letter words = \( P(4, 3) = \frac{4!}{(4-3)!} = 4 \cdot 3 \cdot 2 = 24 \).
The number of ways is 24. (2 marks)