A Solution to Quiz #1
CS 205: Discrete Structures I, Fall 2019 (Sections 4,5,6)
Name:
NetID:
Instructions:
1. Make sure you write your solutions ONLY in the space provided below each question. No
extra material is allowed.
2. If you are caught cheating, or it is later suspected that your answers were copied from someone
else, you will be given a zero on the quiz, and possibly reported to the department.
Question 1 (20%) Show that the following proposition is a tautology in two ways: using a truth
table, and using boolean algebra (justify each step!).
(¬p)→ (p→ q)
1 p q ¬p p→ q (¬p)→ (p→ q)
2 T T F T T
3 T F F F T
4 F T T T T
5 F F T T T
6
1 ≡ (¬(¬p)) ∨ (p→ q) (implication law)
2 ≡ p ∨ (p→ q) (double negation law)
3 ≡ p ∨ (¬p ∨ q) (implication law)
4 ≡ (p ∨ ¬p) ∨ q (associative law)
5 ≡ T ∨ q
6 ≡ T
Question 2 (10%) Write the following proposition in disjunctive normal form (DNF):
(¬(p ∧ q ∧ ¬r)) ∨ (¬p ∧ ¬q ∧ r)
1 ¬p ∨ ¬q ∨ r ∨ (¬p ∧ ¬q ∧ r) (or an even better answer: ¬p ∨ ¬q ∨ r)
Question 3 (20%) Denote by P (x) the predicate “x2 = 2x” with the domain being the real
numbers. Determine the truth value for each the following propositions, and prove your answers:
(1) ∀xP (x) (2)∃xP (x) (3)∀x¬P (x) (4) ∃x¬P (x)
1 (1) F: counter-example: x = 1 (as 12 6= 2 · 1)
2 (2) T: example: x = 0 (as 02 = 2 · 0)
3 (3) F: counter-example: x = 0 ((3) is the negation of (2))
4 (4) T: example: x = 1 ((4) is the negation of (1))
Name:
NetID:
Question 4 (50%) Prove the following propositions:
(i) For all positive integers c and n, c is even if and only if cn is even.
(Hint: recall that, by distributivity, when expanding (x+ y)n, every summand is of the form
xiyj for some 0 ≤ i, j ≤ n.)
1 (c is even → cn is even) Let c be even, meaning c = 2k for some integer k.
2 Then cn = (2k)n = 2 · (2n−1kn).
3 Since 2n−1kn is an integer, this proves cn is even.
4
5 (cn is even → c is even) We prove the contrapositive: “c is odd → cn is odd”.
6 Let c be odd, meaning c = 2k + 1 for some integer k.
7 Then cn = (2k + 1)n, and when expanding, each term is of the form (2k)i for some 0 ≤ i ≤ n.
8 The only odd term is (2k)0 = 1, which implies cn is odd.
(ii) Prove that log2 3 is irrational. (Hint: use (i).)
1 Suppose for contradiction log2 3 is rational, meaning log2 3 = a/b for some integers a, b
2 with a, b > 0 (without loss of generality as log2 3 > 0).
3 Then 3 = 2a/b, or equivalently, 3b = 2a.
4 By (i), the LHS is odd and the RHS is even, so the equality is a contradiction.
5
6
7
(iii) Find two irrational numbers x, y such that xy is rational (that is, give a constructive existence
proof). Use the fact that
√
2 is irrational together with (ii).
1 Take x =
√
2 and y = 2 log2 3. Then x
y = 2log2 3 = 3.
2 Since 3 is rational and
√
2 is irrational, it remains to show that 2 log2 3 is irrational.
3 Suppose for contradiction 2 log2 3 = a/b for some integers a, b with b 6= 0.
4 Then log2 3 = a/2b, meaning log2 3 is rational. This contradicts (ii).
5
6
7