and A ∪ B. Based on your drawings, do you think it’s true that A ∩ B = A ∪ B?
The diagrams for A ∩ B and A ∪ B look exactly
U
alike. In either case the diagram is the shaded
region illustrated on the right. Thus we would
A
B
expect that the equation A ∩ B = A ∪ B is true
for any sets A and B.
9. Draw a Venn diagram for (A ∩ B) − C.
C
A
B
11. The simplest answer is (B ∩ C) − A.
13. One answer is (A ∪ B ∪ C) − (A ∩ B ∩ C).
246
Solutions
Section 1.8
1. Suppose A1 = {a, b, d, e, g, f }, A2 = {a, b, c, d}, A3 = {b, d, a} and A4 = {a, b, h}.
4
4
(a) [ A
i = {a, b, c, d, e, f , g, h}
(b)
Ai = {a, b}
i=1
i=1
3. For each n ∈ N, let An = {0,1,2,3,..., n}.
(a) [ Ai = {0} ∪ N
(b) Ai = {0,1}
i∈N
i∈N
5. (a) [ [i, i + 1] =[1,∞)
(b) [i, i + 1] =;
i∈N
i∈N
7. (a) [ R × [i, i + 1] = {(x, y) : x, y ∈ R, y ≥ 1}
(b) R × [i, i + 1] = ;
i∈N
i∈N
9. (a)
[
X = N
(b)
X = ;
X ∈P(N)
X ∈P(N)
11. Yes, this is always true.
13. The first is true, the second is false.
Chapter 2 Exercises
Section 2.1
Decide whether or not the following are statements. In the case of a statement,
say if it is true or false.
1. Every real number is an even integer. (Statement, False)
3. If x and y are real numbers and 5x = 5y, then x = y. (Statement, True)
5. Sets Z and N are infinite. (Statement, True)
7. The derivative of any polynomial of degree 5 is a polynomial of degree 6.
(Statement, False)
9. cos(x) = −1
This is not a statement. It is an open sentence because whether it’s true or
false depends on the value of x.
11. The integer x is a multiple of 7.
This is an open sentence, and not a statement.
13. Either x is a multiple of 7, or it is not.
This is a statement, for the sentence is true no matter what x is.
15. In the beginning God created the heaven and the earth.
This is a statement, for it is either definitely true or definitely false. There is
some controversy over whether it’s true or false, but no one claims that it is
neither true nor false.
247
Section 2.2
Express each statement as one of the forms P ∧ Q, P ∨ Q, or ∼ P. Be sure to also
state exactly what statements P and Q stand for.
1. The number 8 is both even and a power of 2.
P ∧ Q
P: 8 is even
Q: 8 is a power of 2
Note: Do not say “Q: a power of 2,” because that is not a statement.
3. x 6= y
∼ (x = y)
(Also ∼ P where P : x = y.)
5. y ≥ x
∼ (y < x)
(Also ∼ P where P : y < x.)
7. The number x equals zero, but the number y does not.
P∧ ∼ Q
P : x = 0
Q : y = 0
9. x ∈ A − B
(x ∈ A)∧ ∼ (x ∈ B)
11. A ∈ ©X ∈ P(N) : |X | < ∞ª
(A ⊆ N) ∧ (|A| < ∞).
13. Human beings want to be good, but not too good, and not all the time.
P∧ ∼ Q∧ ∼ R
P : Human beings want to be good.
Q : Human beings want to be too good.
R : Human beings want to be good all the time.
Section 2.3
Without changing their meanings, convert each of the following sentences into a
sentence having the form “If P , then Q . ”
1. A matrix is invertible provided that its determinant is not zero.
Answer: If a matrix has a determinant not equal to zero, then it is invertible.
3. For a function to be integrable, it is necessary that it is continuous.
Answer: If function is integrable, then it is continuous.
5. An integer is divisible by 8 only if it is divisible by 4.
Answer: If an integer is divisible by 8, then it is divisible by 4.
7. A series converges whenever it converges absolutely.
Answer: If a series converges absolutely, then it converges.
9. A function is integrable provided the function is continuous.
Answer: If a function is continuous, then that function is integrable.
11. You fail only if you stop writing.
Answer: If you fail, then you have stopped writing.
13. Whenever people agree with me I feel I must be wrong.
Answer: If people agree with me, then I feel I must be wrong.
248
Solutions
Section 2.4
Without changing their meanings, convert each of the following sentences into a
sentence having the form “P if and only if Q . ”
1. For a matrix to be invertible, it is necessary and sufficient that its determinant
is not zero.
Answer: A matrix is invertible if and only if its determinant is not zero.
3. If xy = 0 then x = 0 or y = 0, and conversely.
Answer: x y = 0 if and only if x = 0 or y = 0
5. For an occurrence to become an adventure, it is necessary and sufficient for
one to recount it.
Answer: An occurrence becomes an adventure if and only if one recounts it.
Section 2.5
1. Write a truth table for P ∨ (Q ⇒ R)
5. Write a truth table for (P∧ ∼ P) ∨ Q
P
Q
R
Q ⇒ R
P ∨ (Q ⇒ R)
P
Q
(P∧ ∼ P)
(P∧ ∼ P) ∨ Q
T
T
T
T
T
T
T
F
T
T
T
F
F
T
T
F
F
F
T
F
T
T
T
F
T
F
T
T
F
F
T
T
F
F
F
F
F
T
T
T
T
7.
F
T
F
F
F
Write a truth table for (P∧ ∼ P) ⇒ Q
F
F
T
T
T
P
Q
(P∧ ∼ P)
(P∧ ∼ P) ⇒ Q
F
F
F
T
T
T
T
F
T
3. Write a truth table for ∼ (P ⇒ Q)
T
F
F
T
F
T
F
T
P
P ⇒ Q
∼ (P ⇒ Q)
F
F
F
T
T
T
T
F
T
F
F
T
F
T
T
F
F
F
T
F
9. Write a truth table for ∼ (∼ P∨ ∼ Q).
P
Q
∼ P
∼ Q
∼ P∨ ∼ Q
∼ (∼ P∨ ∼ Q)
T
T
F
F
F
T
T
F
F
T
T
F
F
T
T
F
T
F
F
F
T
T
T
F
249
11. Suppose P is false and that the statement (R ⇒ S) ⇔ (P ∧ Q) is true. Find the
truth values of R and S. (This can be done without a truth table.)
Answer: Since P is false, it follows that (P ∧Q) is false also. But then in order
for (R ⇒ S) ⇔ (P ∧ Q) to be true, it must be that (R ⇒ S) is false. The only way
for (R ⇒ S) to be false is if
R is true and S is false.
Section 2.6
A. Use truth tables to show that the following statements are logically equivalent.
1. P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)
P
Q
R
Q ∨ R
P ∧ Q
P ∧ R
P ∧ (Q ∨ R)
(P ∧ Q) ∨ (P ∧ R)
T
T
T
T
T
T
T
T
T
T
F
T
T
F
T
T
T
F
T
T
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
F
F
F
F
T
F
T
F
F
F
F
F
F
T
T
F
F
F
F
F
F
F
F
F
F
F
F
Thus since their columns agree, the two statements are logically equivalent.
3. P ⇒ Q = (∼ P) ∨ Q
P
Q
∼ P
(∼ P) ∨ Q
P ⇒ Q
T
T
F
T
T
T
F
F
F
F
F
T
T
T
T
F
F
T
T
T
Thus since their columns agree, the two statements are logically equivalent.
5. ∼ (P ∨ Q ∨ R) = (∼ P) ∧ (∼ Q) ∧ (∼ R)
P
Q
R
P ∨ Q ∨ R
∼ P
∼ Q
∼ R
∼ (P ∨ Q ∨ R)
(∼ P) ∧ (∼ Q) ∧ (∼ R)
T
T
T
T
F
F
F
F
F
T
T
F
T
F
F
T
F
F
T
F
T
T
F
T
F
F
F
T
F
F
T
F
T
T
F
F
F
T
T
T
T
F
F
F
F
F
T
F
T
T
F
T
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
T
T
T
T
T
Thus since their columns agree, the two statements are logically equivalent.
250
Solutions
7. P ⇒ Q = (P∧ ∼ Q) ⇒ (Q∧ ∼ Q)
P
Q
∼ Q
P∧ ∼ Q
Q∧ ∼ Q
(P∧ ∼ Q) ⇒ (Q∧ ∼ Q)
P ⇒ Q
T
T
F
F
F
T
T
T
F
T
T
F
F
F
F
T
F
F
F
T
T
F
F
T
F
F
T
T
Thus since their columns agree, the two statements are logically equivalent.
B. Decide whether or not the following pairs of statements are logically equivalent.
9. By DeMorgan’s law, we have ∼ (∼ P∨ ∼ Q) =∼∼ P∧ ∼∼ Q = P ∧ Q. Thus the
two statements are logically equivalent.
11. (∼ P) ∧ (P ⇒ Q) and ∼ (Q ⇒ P)
P
Q
∼ P
P ⇒ Q
Q ⇒ P
(∼ P) ∧ (P ⇒ Q) ∼ (Q ⇒ P)
T
T
F
T
T
F
F
T
F
F
F
T
F
F
F
T
T
T
F
T
T
F
F
T
T
T
T
F
The columns for the two statements do not quite agree, thus the two state-
ments are not logically equivalent.
Section 2.7
Write the following as English sentences. Say whether the statements are true
or false.
1. ∀ x ∈ R, x2 > 0
Answer: For every real number x, x2 > 0.
Also: For every real number x, it follows that x2 > 0.
Also: The square of any real number is positive. (etc.)
This statement is FALSE. Reason: 0 is a real number, but it’s not t
rue that
02 > 0.
3. ∃ a ∈ R,∀ x ∈ R, ax = x.
Answer: There exists a real number a for which ax = x for every real number x.
This statement is TRUE. Reason: Consider a = 1.
5. ∀ n ∈ N,∃ X ∈ P(N),|X | < n
Answer: For every natural number n, there is a subset X of N with |X | < n.
This statement is TRUE. Reason: Suppose n ∈ N. Let X = ;. Then |X | = 0 < n.
251
7. ∀ X ⊆ N,∃ n ∈ Z,|X | = n
Answer: For any subset X of N, there exists an integer n for which |X | = n.
This statement is FALSE. For example, the set X = {2, 4, 6, 8, . . .} of all even
natural numbers is infinite, so there does not exist any integer n for which
|X | = n.
9. ∀ n ∈ Z,∃ m ∈ Z, m = n + 5
Answer: For every integer n there is another integer m such that m = n + 5.
This statement is TRUE.
Section 2.9
Translate each of the following sentences into symbolic logic.
1. If f is a polynomial and its degree is greater than 2, then f 0 is not constant.
Translation: (P ∧ Q) ⇒ R, where
P : f is a polynomial,
Q : f has degree greater than 2,
R : f 0 is not constant.
p
3. If x is prime then
x is not a rational number.
Translation: P ⇒∼ Q, where
P : x is prime,
p
Q :
x is a rational number.
5. For every positive number ε, there is a positive number δ for which |x − a| < δ
implies | f (x) − f (a)| < ε.
Translation: ∀ ε ∈ R, ε > 0,∃ δ ∈ R, δ > 0,(|x − a| < δ) ⇒ (|f (x) − f (a)| < ε) 7. There exists a real number a for which a + x = x for every real number x.
Translation: ∃a ∈ R,∀x ∈ R, a + x = x
9. If x is a rational number and x 6= 0, then tan(x) is not a rational number.
Translation: ((x ∈ Q) ∧ (x 6= 0)) ⇒ (tan(x) ∉ Q)
11. There is a Providence that protects idiots, drunkards, children and the United
States of America.
One translation is as follows. Let R be union of the set of idiots, the set of
drunkards, the set of children, and the set consisting of the USA. Let P be the
open sentence P(x): x is a Providence. Let S be the open sentence S(x, y): x
protects y. Then the translation is ∃ x,∀ y ∈ R, P(x) ∧ S(x, y).
(Notice that, although this is mathematically correct, some humor has been
lost in the translation.)
13. Everything is funny as long as it is happening to somebody else.
Translation: ∀ x,(∼ M(x) ∧ S(x)) ⇒ F(x),
where M(x): x is happening to me, S(x): x is happening to someone, and F(x) : x
is funny.
252
Solutions
Section 2.10
Negate the following sentences.
1. The number x is positive, but the number y is not positive.
The “but” can be interpreted as “and.” Using DeMorgan’s law, the negation is:
The number x is not positive or the number y is positive.
3. For every prime number p there, is another prime number q with q > p.
Negation: There is a prime number p such that for every prime number q ,
q ≤ p .
Also: There exists a prime number p for which q ≤ p for every prime number q .
(etc.)
5. For every positive number ε there is a positive number M for which |f (x)− b| < ε
whenever x > M.
To negate this, it may be helpful to first write it in symbolic form. The statement
is ∀ ε ∈ (0, ∞), ∃M ∈ (0, ∞), (x > M) ⇒ (| f (x) − b| < ε).
Book of Proof Page 35