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
... [Show More] 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). [Show Less]