EXERCISES CHAPTER 1 Exercise 1 Construct a truth table for each of these compound propositions a) (p ∧ q) → ¬q p q ¬q p∧q (p∧q) → ¬q --- --- ---- ----- ------------ T T F T F T F T F T F T F F T F F T F T b) (p∨r) → (r∨¬p) p r ¬p p∨r r∨¬p (p∨r) → (r∨¬p) --- --- ---- ----- ------ ---------------- T T F T T T T F F T F F F T T T T T F F T F T T c) (p→q) ∨ (q→p) p q p→q q→p (p→q)∨(q→p) --- --- ----- ----- ------------- T T T T T T F F T T F T T F T F F T T T d) (p∨¬q) ∧ (¬p∨q) p q ¬p ¬q p∨¬q ¬p∨q (p∨¬q) ∧ (¬p∨q) --- --- ---- ---- ------ ------ ----------------- T T F F T T T T F F T T F F F T T F F T F F F T T T T T e) (p→¬q) ∨ (q→¬p) p q ¬p ¬q p→¬q q→¬p (p→¬q) ∨ (q→¬p) --- --- ---- ---- ------ ------ ----------------- T T F F F F F T F F T T T T F T T F T F T F F T T T T T f) ¬(¬p∧¬q) p q ¬p ¬q ¬p∧¬q ¬(¬p∧¬q) --- --- ---- ---- ------- ---------- T T F F F T T F F T F T F T T F F T F F T T T F g) (p∨q) → (p⊕q) p q p∨q p⊕q (p∨q) → (p⊕q) --- --- ----- ----- --------------- T T T F F T F T T T F T T T T F F F F T h) (p∧q) ∨ (r⊕q) p q r p∧q r⊕q (p∧q) ∨ (r⊕q) --- --- --- ----- ----- --------------- T T T T F F T T F T T T T F T F T T T F F F F T F T T F F T F T F F T T F F T F T T F F F F F T Exercise 5 Let p, q and r be the propositions p : You have the flu. q : You miss the final examination. r : You pass the course. Express each of these propositions as an English sentence. a) p → q You will miss the final examination if you have the flu. b) ¬q ↔ r If you do not miss the final examination then you will pass the course, and conversely. c) q → ¬r You will not pass the course if you miss the final examination. d) p ∨ q ∨ r You have the flu or you miss the final examination or you pass the course. e) (p → ¬r) ∨ (q → ¬r) You will not pass the course if you have the flu or you miss the final examination. f) (p ∧ q) ∨ (¬q ∧ r) You have the flu and you miss the final examination or you do not miss the final examination and you pass the course. Exercise 9 Show that these compound propositionals are logically equivalent. a) ¬(p ↔ q) and ¬p ↔ q p q ¬p p↔q ¬(p↔q) ¬p↔q --- --- ---- ----- -------- ------ T T F T F F T F F F T T F T T F T T F F T T F F b) (p → q) ∧ (p → r) and p → (q ∧ r) p q r p→q p→r (p→q)∧(p→r) q∧r p→(q∧r) --- --- --- ----- ----- ------------- ----- --------- T T T T T T T T T T F T F F F F T F T F T F F F T F F F F F F F F F T T T T F T F T F T T T F T F T T T T T T T F F F T T T F T c) (p → r) ∧ (q → r) and (p ∨ q) → r p q r p→r q→r (p→r)∧(q→r) p∨q (p∨q)→r --- --- --- ----- ----- ------------- ----- --------- T T T T T T T T T T F F F F T F T F T T T T T T T F F F T F T F F F T T T T F T F T F T F F T F F T T T T T T T F F F T T T F T d) (p → q) ∨ (p → r) and p → (q ∨ r) p q r p→q p→r (p→q)∨(p→r) q∨r p→(q∨r) --- --- --- ----- ----- ------------- ----- --------- T T T T T T T T T T F T F T T T T F T F T T T T T F F F F F F F F F T T T T T T F T F T T T T T F T T T T T T T F F F T T T F T e) ¬p → (q → r) and q → (p ∨ r) p q r ¬p q→r ¬p→(q→r) p∨r q→(p∨r) --- --- --- ---- ----- ---------- ----- --------- T T T F T T T T T T F F F T T T T F T F T T T T T F F F T T T T F F T T T T T T F T F T F F F F F T T T T T T T F F F T T T F T f) p ↔ q and (p → q) ∧ (q → p) p q p↔q p→q q→p (p→q)∧(q→p) --- --- ----- ----- ----- ------------- T T T T T T T F F F T F F T F T F F F F T T T T Exercise 13 You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. Express your answer in terms of g: “You can graduate," m: “You owe money to the university," r: “You have completed the requirements of your major," and b: “You have an overdue library book." g → (r ∧ ¬(m ∧ b)) EXERCISES CHAPTER 2 Exercise 5 Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English. a) ∃xP(x) Some students spend more than five hours every weekday in class. b) ∀xP(x) All students spend more than five hours every weekday in class. c) ∃x¬P(x) Some students do not spend more than five hours every weekday in class d) ∀x¬P(x) All students do not spend more than five hours every weekday in class. Exercise 9 Let L(x, y) be the statement “x loves y," where the domain for both x and y consists of all people in the world. Use quantifiers to express each of these statements. a) Everybody loves Jerry. ∀xL(x,Jerry) b) Everybody loves somebody. ∀x∃yL(x,y) c) There is somebody whom everybody loves. ∃y∀xL(x,y) d) There is somebody whom Lydia does not love. ∃y¬L(Lydia,y) e) There is somebody whom no one loves. ∃y∀xL(x,y) f) There is exactly one person whom everybody loves. ∃y(∀xL(x,y) ∧ ∀z(∀wL(w,z)) → z ≡ y) Exercise 13 What rule of inference is used in each of these arguments? a) Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science major. p ∴ p ∨ q b) Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics major. p ∧ q ∴ p c) If it is rainy, then the pool will be closed. It is rainy. Therefor, the pool is closed. p p → q ∴ q d) If it snows today, then university will close. The university is not closed today. Therefore, it did not snow today. ¬q p → q ∴ ¬p e) If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I will sunburn. Therefore, if I go swimming, then I will sunburn. p → q q → r ∴ p → r Exercise 17 Use a direct proof to show that the product of two odd numbers is odd. Solution Assume that 2n + 1 is an odd number (n is a natural number). We have the product of two number is (2n + 1)² (2n + 1)² = 4n² + 4n + 1 = 2(2n² + 2n)+1 is an odd number. Exercise 21 Use a proof by contradiction to prove that the sum of an irrational number and a rational number is irrational. Solution We have p is a rational number, q is an irrational number so the sum of p and q is r = p + q, then r is an irrational number. Suppose that p is rational, q is irrational and r is rational. We have -p is rational so the sum of r and -p is rational too (r = a/b and p = c/d, b≠0 and d≠0) By algebra we see that r + (-p) = a/b - c/d = (ad - cb)/bd is a rational number. r + (-p) = p + q - p = q. We have q is an irrational number. So r + (-p) is rational is incorrect. In conclusion, r is irrational. Exercise 25 Prove that if n is an integer and 3n + 2 is even, then n is even using a) a proof by contraposition. Solution Assume that “If 3n + 2 is even, then n is even" is fall; We n is odd, so n = 2k + 1, k ∈ ℤ. Substituting 3n + 2 = 3(2k + 1)+2 = 6k + 5 = 2(3k + 2)+1 is odd. Because the negation of the conclusion of the conditional statement implies that the hypothesis is false, Q.E.D b) a proof by contradiction. Solution Let p is the proposition “n is even". Suppose ¬p is true, which means “n is odd". If we add subtract an odd number from an even number, we get an odd number, so 3n + 2 − n = 4n + 2 = 2(2n + 1) is odd. But this is not true. Therefore our supposition was wrong, and the proof by contradiction is complete. Exercise 29 Prove by induction that 1² + 2² + ... + n² = ${6}$ Solution Let P(n) be the proposition that 1² + 2² + ... + n² = ${6}$ + Basis Step: P(1) is true, because 1² = ${6}$ + Inductive Step: Assum that 1² + 2² + ... + k² = ${6}$ Then: 1² + 2² + ... + k² + (k + 1)² = ${6} + (k + 1)^{2}$ $\hspace*{4.45cm}$= $}{6}$ $\hspace*{3.7cm}$= $+7k+6)}{6}$ $\hspace*{3.8cm}$= ${6}$ shows that P (k + 1) is true under the assumption that P (k) is true. Exercise 33 Prove that n!>2n for all n ≥ 1. Solution Let P(n) be the proposition that n!>2n for all n ≥ 1 + Basis Step: