How To Prove It: A Structured Approach Third Edition Solutions Manual

. . . . . . . . . . . . . . . . . 137 — − — − √ √ ∧ ∧ ∨ ∧ ¬ ∧ ∧ ∨ ¬ ∨ ∨ ∧ ¬ ∧ INTRODUCTION 1 Introduction 1. We use the formula 2 ab − 1 = (2b − 1)(1 + 2 b + 2 2b + ····+ 2 (a− 1)b ) from the proof of Conjecture 2. (a) 2 15 − 1 = 2 3 · 5 − 1 = (25 − 1) · (1 + 2 5 + 2 10) = 31 · 1057. (b) 2 32,767−1 = 2 1057 · 31−1 = (2 31−1)(1+2 31 +· · ·+2 1056 · 31 ). The first factor is 2 31−1 = 2,147,483,647. 2. When n = 1, 3n 1 = 2, which is prime. For all n > 1, 3n 1 is an even integer larger than 2, so it is not prime. If n is not prime, then 3n 2 n is not prime. If n is prime, then 3n 2 n may be either prime or composite. 3. (a) The method gives m = 2 · 3 · 5 · 7 + 1 = 211, which is prime. (b) The method gives m = 2 · 5 · 11 + 1 = 111 = 3 · 37; 3 and 37 are both prime. 4. Using the method of the proof of Theorem 4, with n = 5, we get x = 6! + 2 = 722. The five consecutive composite numbers are 722 = 2 · 361, 723 = 3 · 241, 724 = 2 · 362, 725 = 5 · 145, and 726 = 2 · 363. 5. 2 5 − 1 = 31 and 27 − 1 = 127 are Mersenne primes. Therefore, by Euclid’s theorem, 24 (25 − 1) = 496 and 2 6 (27 − 1) = 8128 are both perfect. 6. No. The remainder when any integer n > 3 is divided by 3 will be either 0, 1, or 2. If it is 0, then n is divisible by 3, so it is composite. If it is 1, then n + 2 is divisible by 3 and therefore composite. If it is 2, then n + 4 is divisible by 3 and composite. Thus, the numbers n, n + 2, and n + 4 cannot all be prime. 7. The positive integers smaller than 220 that divide 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110, and 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284. The positive integers smaller than 284 that divide 284 are 1, 2, 4, 71, and 142, and 1 + 2 + 4 + 71 + 142 = 220. Chapter 1 Section 1.1 1. (a) (R H) (H T ), where R stands for the statement “We’ll have a reading assignment,” H stands for “We’ll have homework problems,” and T stands for “We’ll have a test.” (b) ¬G ∨ (G ∧ ¬S), where G stands for “You’ll go skiing,” and S stands for “There will be snow.” (c) ¬[( 7 < 2) ∨ ( 7 = 2)]. 2. (a) (J B) (J B), where J stands for “John is telling the truth” and B stands for “Bill is telling the truth.” (b) (F C) (F P ), where F stands for “I’ll have fish,” C stands for “I’ll have chicken,” and P stands for “I’ll have mashed potatoes.” (c) S N F , where S stands for “6 is divisible by 3,” N stands for “9 is divisible by 3,” and F stands for “15 is divisible by 3.” 3. Let A stand for the statement “Alice is in the room” and B for “Bob is in the room.” (a) ¬(A ∧ B). (b) ¬A ∧ ¬B. (c) ¬A ∨ ¬B; this is equivalent to the formula in (a). (d) ¬(A ∨ B); this is equivalent to the formula in (b). 4. Let P stand for “Ralph is tall,” Q for “Ed is tall,” R for “Ralph is handsome,” and S for “Ed is handsome.” (a) (P ∧ Q) ∨ (R ∧ S). 2 SOLUTIONS (b) (P ∨ R) ∧ (Q ∨ S). (c) ¬(P ∨ R) ∧ ¬(Q ∨ S). (d) ¬[(P ∧ R) ∨ (Q ∧ S)]. 5. (a) and (c) are well-formed formulas. 6. (a) I won’t buy the pants without the shirt. (b) I won’t buy the pants and I won’t buy the shirt. (c) Either I won’t buy the pants or I won’t buy the shirt. 7. (a) Either Steve or George is happy, and either Steve or George is not happy. (b) Either Steve is happy, or George is happy and Steve isn’t, or George isn’t happy. (c) Either Steve is happy, or George is happy and either Steve or George isn’t happy. 8. (a) Either taxes will go up or the deficit will go up. (b) Taxes and the deficit will not both go up, but it is not the case that taxes won’t go up and the deficit also won’t go up. (c) Either taxes will go up and the deficit won’t, or the deficit will go up and taxes won’t. 9. See exercise 7 in Section 1.2 for the determination of whether these arguments are valid. (a) Let J stand for “Jane will win the math prize,” P for “Pete will win the math prize,” and C for “Pete will win the chemistry prize.” The premises are: ¬(J ∧ P), P ∨ C, J. The conclusion is C. (b) Let B stand for “The main course will be beef,” F for “The main course will be fish,” P for “The vegetable will be peas,” and C for “The vegetable will be corn.” The premises are: B ∨F , P ∨C, ¬(F ∧ C). The conclusion is ¬(B ∧ P ). (c) Let J stand for “John is telling the truth,” B for “Bill is telling the truth,” and S for “Sam is telling the truth.” The premises are J ∨ B, ¬S ∨ ¬B. The conclusion is J ∨ ¬S. (d) Let S stand for “Sales will go up,” E for “Expenses will go up,” and B for “The boss will be happy.” There is only one premise: (S ∧ B) ∨ (E ∧ ¬B). The conclusion is ¬(S ∧ E). Section 1.2 1. (a) P Q ¬P ∨ Q F F T F T T T F F T T T (b) SG (S ∨ G) ∧ (¬S ∨ ¬G) F F F F T T T F T T T F 2. (a) P Q ¬[P ∧ (Q ∨ ¬P )] F F T F T T T F T T T F ∧ ¬ ∨ ∧ ¬ ∨ ∧ ¬ ∧ CHAPTER 1 3 (b) PQ R (P ∨ Q) ∧ (¬P ∨ R)F F F F F F T F F T F T F T T T T F F F T F T T T T F F T T T T 3. (a) P Q P + Q F F F F T T T F T T T F (b) Here are two possibilities: (P Q) (Q P ), or (P Q) (P Q). The truth table is the same as in part (a). 4. ¬(¬P ∧ ¬Q). The truth table is the same as the truth table for P ∨ Q. 5. (a) P Q P ↓ Q F F T F T F T F F T T F (b) ¬(P ∨ Q). (c) ¬P is equivalent to P ↓ P , P ∨ Q is equivalent to (P ↓ Q) ↓ (P ↓ Q), and P ∧ Q is equivalent to (P ↓ P ) ↓ (Q ↓ Q). 6. (a) P Q P | Q F F T F T T T F T T T F (b) ¬(P ∧ Q). (c) ¬P is equivalent to P | P , P ∨ Q is equivalent to (P | P ) | (Q | Q), and P ∧ Q is equivalent to (P | Q) | (P | Q). 7. We use the premises and conclusions identified in exercise 9 of Section 1.1. (a) Valid: premises are all true only in line 6 of the following truth table, and the conclusion is also true in that line. Premises Conclusion J P C ¬(J ∧ P) (P ∨ C) J C F F F T F F F F F T T T F T F T F T T F F F T T T T F T T F F T F T F T F T T T T T T T F F T T F T T T F T T T 4 SOLUTIONS (b) Invalid. Here is a line of the truth table in which all premises are true but the conclusion is false: Premises Conclusion B F P C B ∨ F P ∨ C ¬(F ∧ C) ¬(B ∧ P ) T T T F T T T F (c) Valid: premises are all true in lines 3, 5, 6, and 7 of the following truth table, and the conclusion is also true in all of those lines. Premises Conclusion J B S J ∨ B ¬S ∨ ¬B J ∨ ¬S F F F F T T F F T F T F F T F T T T F T T T F F T F F T T T T F T T T T T T F T T T T T T T F T (d) Invalid. Here is a line of the truth table in which the premises are all true but the conclusion is false: Premise Conclusion S E B (S ∧ B) ∨ (E ∧ ¬B) ¬(S ∧ E) T T T T F 8. The following truth table shows that (a) and (c) are equivalent, as are (b) and (e): (a) (b) (c) (d) (e) P Q (P ∧ Q) ∨ (¬P ∧ ¬Q) ¬P ∨ Q (P ∨ ¬Q) ∧ (Q ∨ ¬P ) ¬(P ∨ Q) (Q ∧ P ) ∨ ¬P F F T T T T T F T F T F F T T F F F F F F T T T T T F T 9. The following truth table shows that (b) is a contradiction and (c) is a tautology: (a) (b) (c) P Q (P ∨ Q) ∧ (¬P ∨ ¬Q) (P ∨ Q) ∧ (¬P ∧ ¬Q) (P ∨ Q) ∨ (¬P ∨ ¬Q) F F F F T F T T F T T F T F T T T F F T Formula (d) is also a tautology, as the following truth table shows: P Q R [P ∧ (Q ∨ ¬R)] ∨ (¬P ∨ R) F F F T F F T T F T F T F T T T T F F T T F T T T T F T T T T T CHAPTER 1 5 10. (a) P Q ¬(P ∨ Q) ¬P ∧ ¬Q F F T T F T F F T F F F T T F F (b) PQ R P ∧ (Q ∨ R) (P ∧ Q) ∨ (P ∧ R) P ∨ (Q ∧ R) (P ∨ Q) ∧ (P ∨ R) F F F F F F F F F T F F F F F T F F F F F F T T F F T T T F F F F T T T F T T T T T T T F T T T T T T T T T T T 11. (a) ¬(¬P ∧ ¬Q) is equivalent to ¬¬P ∨ ¬¬Q (De Morgan’s law), which is equivalent to P ∨ Q (double negation law). (b) (P ∧ Q) ∨ (P ∧ ¬Q) is equivalent to P ∧ (Q ∨ ¬Q) (distributive law), which is equivalent to P (tautology law). (c) ¬(P ∧ ¬Q) ∨ (¬P ∧ Q) is equivalent to (¬P ∨ ¬¬Q) ∨ (¬P ∧ Q) (De Morgan’s law), which is equivalent to (¬P ∨ Q) ∨ (¬P ∧ Q) (double negation law), which is equivalent to ¬P ∨ (Q ∨ (¬P ∧ Q)) (associative law), which is equivalent to ¬P ∨ (Q ∨ (Q ∧ ¬P )) (commutative law), which is equivalent to ¬P ∨ Q (absorption law). 12. (a) ¬(¬P ∨ Q) ∨ (P ∧ ¬R) is equivalent to (¬¬P ∧ ¬Q) ∨ (P ∧ ¬R) (De Morgan’s law), which is equivalent to (P ∧ ¬Q) ∨ (P ∧ ¬R) (double negation law), which is equivalent to P ∧ (¬Q ∨ ¬R) (distributive law), which is equivalent to P ∧ ¬(Q ∧ R) (De Morgan’s law). (b) ¬(¬P ∧ Q) ∨ (P ∧ ¬R) is equivalent to (¬¬P ∨ ¬Q) ∨ (P ∧ ¬R) (De Morgan’s law), which is equivalent to (P ∨ ¬Q) ∨ (P ∧ ¬R) (double negation law), which is equivalent to (¬Q ∨ P ) ∨ (P ∧ ¬R) (commutative law), which is equivalent to ¬Q ∨ (P ∨ (P ∧ ¬R)) (associative law), which is equivalent to ¬Q ∨ P (absorption law). (c) (P ∧ R) ∨ [¬R ∧ (P ∨ Q)] is equivalent to (P ∧ R) ∨ [(¬R ∧ P ) ∨ (¬R ∧ Q)] (distributive law), which is equivalent to (P ∧ R) ∨ [(P ∧ ¬R) ∨ (Q ∧ ¬R)] (commutative law), which is equivalent to [(P ∧ R) ∨ (P ∧ ¬R)] ∨ (Q ∧ ¬R) (associative law), which is equivalent to [P ∧ (R ∨ ¬R)] ∨ (Q ∧ ¬R) (distributive law), which is equivalent to P ∨ (Q ∧ ¬R) (tautology law). ∧ − ∧ ∧ ∨ ∨ ∧ ∨ ∈ ∧ − ∧ ∧ ∧ ¬ ∨ ∧ ¬ 6 SOLUTIONS 13. ¬(P ∨ Q) is equivalent to ¬(¬¬P ∨ ¬¬Q) (double negation law), which is equivalent to ¬¬(¬P ∧ ¬Q) (first De Morgan’s law), which is equivalent to ¬P ∧ ¬Q (double negation law). 14. We use the associative law for ∧ twice: [P ∧ (Q ∧ R)] ∧ S is equivalent to [(P ∧ Q) ∧ R] ∧ S which is equivalent to (P ∧ Q) ∧ (R ∧ S). 15. 2 n . 16. P ∨ ¬Q. (You can check this by making the truth table.) 17. (P ∧ ¬Q) ∨ (Q ∧ ¬P ). (You can check this by making the truth table.) 18. If the conclusion is a tautology, then the argument is valid. If the conclusion is a contradiction and there is at least one line of the truth table in which all the premises are true, then the argument is not valid. If one of the premises is a tautology, then you can delete that premise without affecting the validity of the argument. If one of the premises is a contradiction, then the argument is valid. Section 1.3 1. (a) D(6) ∧ D(9) ∧ D(15), where D(x) means “x is divisible by 3.” (b) D(x, 2) ∧ D(x, 3) ∧ ¬D(x, 4), where D(x, y) means “x is divisible by y.” (c) N (x) N(y) [(P (x) P (y)) (P (y) P (x))], where N(x) means “x is a natural number” and P(x) means “x is prime.” 2. (a) M(x) M(y) [(T (x, y) T (y, x)], where M(x) means “x is a man” and T (x, y), means “x is taller than y.” (b) (B(x) B(y)) (R(x) R(y)), where B(x) means “x has brown eyes” and R(x) means “x has red hair.” (c) (B(x) ∧ R(x)) ∨ (B(y) ∧ R(y)), where the letters have the same meanings as in part (b). 3. (a) {x | x is a planet}. (b) {x | x is an Ivy League school}. (c) {x | x is a state in the United States}. (d) {x | x is a province or territory in Canada}. 4. (a) {x | x is the square of a positive integer}. (b) {x | x is a power of 2}. (c) {x | x is an integer and 10 ≤ x < 20}. 5. (a) (−3 ∈ R) ∧ (13 − 2(−3) > 1). Bound variables: x; no free variables. This statement is true. (b) (4 ∈ R)∧ (4 < 0)∧ (13 − 2(4) > 1). Bound variables: x; no free variables. This statement is false. (c) ¬[(5 ∈ R) ∧ (13 − 2(5) > c)]. Bound variables: x; free variables: c. 6. (a) (w ∈ R) ∧ (13 − 2w > c). Bound variables: x; free variables: w, c. (b) (4 R) (13 2(4) is a prime number). Bound variables: x, y; no free variables. This statement is true. (c) (4 is a prime number) (13 2(4) > 1). Bound variables: x, y; no free variables. This statement is false. 7. (a) {−1, 1/2}.