Discrete Mathematics – 8th Edition
ST
INSTRUCTOR’S
UV
SOLUTIONS
IA
_A
MANUAL
PP
RO
Richard Johnsonbaugh
VE
Comprehensive Solutions Manual for Instructors
and Students
D?
© Richard Johnsonbaugh
All rights reserved. Reproduction or distribution without permission is prohibited.
??
©STUDYSTREAM
, Instructor’s Solutions Manual, Discrete Mathematics, 8e
ST
Contents
Chapter 1 1
UV
Chapter 2 14
Chapter 3 39
IA
Chapter 4 56
Chapter 5 77
Chapter 6 85
_A
Chapter 7 115
Chapter 8 136
PP
Chapter 9 158
Chapter 10 182
Chapter 11 187
RO
Chapter 12 196
Appendices 208
VE
D?
??
Copyright © 2018 Pearson Education, Inc. i
,ST
UV
Solutions to Selected Exercises
Section 1.1
IA
2. {2, 4} 3. {7, 10} 5. {2, 3, 5, 6, 8, 9} 6. {1, 3, 5, 7, 9, 10}
8. A 9. ∅ 11. B 12. {1, 4} 14. {1}
_A
15. {2, 3, 4, 5, 6, 7, 8, 9, 10} 18. {n ∈ Z+ | n ≥ 6} 19. {2n − 1 | n ∈ Z+ }
21. {n ∈ Z+ | n ≤ 5 or n = 2m, m ≥ 3} 22. {2n | n ≥ 3} 24. {1, 3, 5}
25. {n ∈ Z+ | n ≤ 5 or n = 2m + 1, m ≥ 3} 27. {n ∈ Z+ | n ≥ 6 or n = 2 or n = 4}
29. 1 30. 3
PP
33. We find that B = {2, 3}. Since A and B have the same elements, they are equal.
34. Let x ∈ A. Then x = 1, 2, 3. If x = 1, since 1 ∈ Z+ and 12 < 10, then x ∈ B. If x = 2, since 2 ∈ Z+ and
22 < 10, then x ∈ B. If x = 3, since 3 ∈ Z+ and 32 < 10, then x ∈ B. Thus if x ∈ A, then x ∈ B.
RO
Now suppose that x ∈ B. Then x ∈ Z+ and x2 < 10. If x ≥ 4, then x2 > 10 and, for these values of x,
x∈/ B. Therefore x = 1, 2, 3. For each of these values, x2 < 10 and x is indeed in B. Also, for each of
the values x = 1, 2, 3, x ∈ A. Thus if x ∈ B, then x ∈ A. Therefore A = B.
37. Since (−1)3 − 2(−1)2 − (−1) + 2 = 0, −1 ∈ B. Since −1 ∈
/ A, A 6= B.
38. Since 32 − 1 > 3, 3 ∈
/ B. Since 3 ∈ A, A 6= B. 41. Equal 42. Not equal
VE
45. Let x ∈ A. Then x = 1, 2. If x = 1,
x3 − 6x2 + 11x = 13 − 6 · 12 + 11 · 1 = 6.
Thus x ∈ B. If x = 2,
D?
x3 − 6x2 + 11x = 23 − 6 · 22 + 11 · 2 = 6.
Again x ∈ B. Therefore A ⊆ B.
46. Let x ∈ A. Then x = (1, 1) or x = (1, 2). In either case, x ∈ B. Therefore A ⊆ B.
??
49. Since (−1)3 − 2(−1)2 − (−1) + 2 = 0, −1 ∈ A. However, −1 ∈
/ B. Therefore A is not a subset of B.
50. Consider 4, which is in A. If 4 ∈ B, then 4 ∈ A and 4 + m = 8 for some m ∈ C. However, the only value
of m for which 4 + m = 8 is m = 4 and 4 ∈ / C. Therefore 4 ∈
/ B. Since 4 ∈ A and 4 ∈
/ B, A is not a
subset of B.
Copyright c 2018 Pearson Education, Inc.
, 2 SOLUTIONS
53.
ST
U
A B
UV
54.
U
A B
IA
_A
56.
A B U
PP
C
RO
57.
U
A
B
C
VE
59.
U
A B
D?
C
62. 32 63. 105 65. 51
??
67. Suppose that n students are taking both a mathematics course and a computer science course. Then
4n students are taking a mathematics course, but not a computer science course, and 7n students are
taking a computer science course, but not a mathematics course. The following Venn diagram depicts
the situation:
Copyright c 2018 Pearson Education, Inc.
ST
INSTRUCTOR’S
UV
SOLUTIONS
IA
_A
MANUAL
PP
RO
Richard Johnsonbaugh
VE
Comprehensive Solutions Manual for Instructors
and Students
D?
© Richard Johnsonbaugh
All rights reserved. Reproduction or distribution without permission is prohibited.
??
©STUDYSTREAM
, Instructor’s Solutions Manual, Discrete Mathematics, 8e
ST
Contents
Chapter 1 1
UV
Chapter 2 14
Chapter 3 39
IA
Chapter 4 56
Chapter 5 77
Chapter 6 85
_A
Chapter 7 115
Chapter 8 136
PP
Chapter 9 158
Chapter 10 182
Chapter 11 187
RO
Chapter 12 196
Appendices 208
VE
D?
??
Copyright © 2018 Pearson Education, Inc. i
,ST
UV
Solutions to Selected Exercises
Section 1.1
IA
2. {2, 4} 3. {7, 10} 5. {2, 3, 5, 6, 8, 9} 6. {1, 3, 5, 7, 9, 10}
8. A 9. ∅ 11. B 12. {1, 4} 14. {1}
_A
15. {2, 3, 4, 5, 6, 7, 8, 9, 10} 18. {n ∈ Z+ | n ≥ 6} 19. {2n − 1 | n ∈ Z+ }
21. {n ∈ Z+ | n ≤ 5 or n = 2m, m ≥ 3} 22. {2n | n ≥ 3} 24. {1, 3, 5}
25. {n ∈ Z+ | n ≤ 5 or n = 2m + 1, m ≥ 3} 27. {n ∈ Z+ | n ≥ 6 or n = 2 or n = 4}
29. 1 30. 3
PP
33. We find that B = {2, 3}. Since A and B have the same elements, they are equal.
34. Let x ∈ A. Then x = 1, 2, 3. If x = 1, since 1 ∈ Z+ and 12 < 10, then x ∈ B. If x = 2, since 2 ∈ Z+ and
22 < 10, then x ∈ B. If x = 3, since 3 ∈ Z+ and 32 < 10, then x ∈ B. Thus if x ∈ A, then x ∈ B.
RO
Now suppose that x ∈ B. Then x ∈ Z+ and x2 < 10. If x ≥ 4, then x2 > 10 and, for these values of x,
x∈/ B. Therefore x = 1, 2, 3. For each of these values, x2 < 10 and x is indeed in B. Also, for each of
the values x = 1, 2, 3, x ∈ A. Thus if x ∈ B, then x ∈ A. Therefore A = B.
37. Since (−1)3 − 2(−1)2 − (−1) + 2 = 0, −1 ∈ B. Since −1 ∈
/ A, A 6= B.
38. Since 32 − 1 > 3, 3 ∈
/ B. Since 3 ∈ A, A 6= B. 41. Equal 42. Not equal
VE
45. Let x ∈ A. Then x = 1, 2. If x = 1,
x3 − 6x2 + 11x = 13 − 6 · 12 + 11 · 1 = 6.
Thus x ∈ B. If x = 2,
D?
x3 − 6x2 + 11x = 23 − 6 · 22 + 11 · 2 = 6.
Again x ∈ B. Therefore A ⊆ B.
46. Let x ∈ A. Then x = (1, 1) or x = (1, 2). In either case, x ∈ B. Therefore A ⊆ B.
??
49. Since (−1)3 − 2(−1)2 − (−1) + 2 = 0, −1 ∈ A. However, −1 ∈
/ B. Therefore A is not a subset of B.
50. Consider 4, which is in A. If 4 ∈ B, then 4 ∈ A and 4 + m = 8 for some m ∈ C. However, the only value
of m for which 4 + m = 8 is m = 4 and 4 ∈ / C. Therefore 4 ∈
/ B. Since 4 ∈ A and 4 ∈
/ B, A is not a
subset of B.
Copyright c 2018 Pearson Education, Inc.
, 2 SOLUTIONS
53.
ST
U
A B
UV
54.
U
A B
IA
_A
56.
A B U
PP
C
RO
57.
U
A
B
C
VE
59.
U
A B
D?
C
62. 32 63. 105 65. 51
??
67. Suppose that n students are taking both a mathematics course and a computer science course. Then
4n students are taking a mathematics course, but not a computer science course, and 7n students are
taking a computer science course, but not a mathematics course. The following Venn diagram depicts
the situation:
Copyright c 2018 Pearson Education, Inc.
