MH1812 Discrete Mathematics - Quiz 1
NTU, AY14/15 S2 11 March 2015, 11:30AM - 12:30PM, Exam Hall C
Name: Guo Jian Tutorial Group: not sure NTU Email: guojian@ntu.edu.sg
Note: try ALL 3 questions, you can write on the back of paper if there is not enough space.
Question 1 (40 points)
1. Compute the multiplication table for integers modulo 3 (15 points).
0 1 2
0 0 0 0
Solution:
1 0 1 2
2 0 2 1
2. Using results from (1.), find the inverse of x, i.e., x−1 mod 3, for x = 1, 2. [note: x−1
is an integer modulo 3 such that x−1 · x ≡ 1 mod 3] (5 points).
Solution: From (1.) bold entries, we can see 1 · 1 ≡ 1 mod 3, hence 1−1 ≡ 1 mod 3;
and 2 · 2 ≡ 1 mod 3, hence 2−1 ≡ 2 mod 3.
3. Prove by mathematical induction that 5n − 1 is divisible by 4, for any integer n ≥ 1
[note: for integer a, b, (a + b)(a − b) = a2 − b2 ] (20 points).
Solution:
(a) Basis Step: n = 1, 4|5n − 1 = 4, and this true.
(b) Inductive Step: assume n = k, 4|5k − 1, i.e., 5k − 1 = 4x for some x ∈ Z. when
n = k + 1, 5n − 1 = 5k+1 − 1 = 5(5k − 1) + 5 − 1 = 5 × 4x + 4 = 4(5x + 1), which
is multiple of 4 also.
1
Question 2 (40 points)
1. Decide whether the following argument is valid, justify your answer (20 points).
p→q
q→r
∴ p→r
p q r p→q q→r p→r
1 T T T T T T
2 T T F T F F
3 T F T F T T
Solution: 4 T F F F T F
5 F T T T T T
6 F T F T F T
7 F F T T T T
8 F F F T T T
From the truth table, rows 1, 5, 7, and 8 are critical rows, and p → r are true in all
these rows, hence valid argument.
2. Given sets A = {1, 2, 3}, B = {1, 2, 4}, and P (x, y) denotes “5|(x + y)”, determine the
truth value of the following statement and justify your answer :
(a) ∀x ∈ A, ∃y ∈ B, P (x, y) (10 points).
Solution: FALSE, because negation is true.
¬(∀x ∈ A, ∃y ∈ B, P (x, y)) ≡ ∃x ∈ A, ∀y ∈ B, ¬P (x, y).
∃x = 2 ∈ A, ∀y ∈ B, 5 ̸ |(x + y), i.e., 5 ̸ |(2 + 1) = 3, 5 ̸ |(2 + 2) = 4, 5 ̸ |(2 + 4) = 6.
(b) ∃x ∈ A, ∀y ∈ B, P (x, y) (10 points).
Solution: FALSE, because the negation is true.
¬(∃x ∈ A, ∀y ∈ B, P (x, y)) ≡ ∀x ∈ A, ∃y ∈ B, ¬P (x, y).
For x = 1, ∃y = 1 such that 5 ̸ |(1 + 1) = 2.
For x = 2, ∃y = 1 such that 5 ̸ |(2 + 1) = 3.
For x = 3, ∃y = 1 such that 5 ̸ |(3 + 1) = 4.
2
Question 3 (20 points)
Prove for any two sets A and B, (A − B) ∩ (B − A) = ∅ (showing only the Venn diagram
will not be sufficient).
Solution:
(A − B) ∩ (B − A) ≡ (A ∩ B) ∩ (B ∩ A) (by definition)
≡A∩B∩B∩A (associative law)
≡ A ∩ (B ∩ B) ∩ A (associative law)
≡ A∩∅∩A (by definition)
≡∅∩A (Domination law)
≡∅ (Domination law)
