Instructor’s Solutions Manual
for
Discrete Mathematics, 8th
edition
ST
by Richard Johnsonbaugh
U
D
(All Chapters 1-12, 100%
YL
Original Verified, A+ Grade)
AB
, Table of Content
1. Sets and Logic
1.1 Sets
1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers
2. Proofs
2.1 Mathematical Systems, Direct Proofs, and Counterexamples
2.2 More Methods of Proof
Problem-Solving Corner: Proving Some Properties of Real Numbers
2.3 Resolution Proofs
2.4 Mathematical Induction
Problem-Solving Corner: Mathematical Induction
ST
2.5 Strong Form of Induction and the Well-Ordering Property
3. Functions, Sequences, and Relations
3.1 Functions
Problem-Solving Corner: Functions
3.2 Sequences and Strings
U
3.3 Relations
3.4 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
D
3.5 Matrices of Relations
3.6 Relational Databases
4. Algorithms
YL
4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
Problem-Solving Corner: Design and Analysis of an Algorithm
4.4 Recursive Algorithms
AB
5. Introduction to Number Theory
5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
Problem-Solving Corner: Making Postage
5.4 The RSA Public-Key Cryptosystem
6. Counting Methods and the Pigeonhole Principle
6.1 Basic Principles
Problem-Solving Corner: Counting
6.2 Permutations and Combinations
Problem-Solving Corner: Combinations
6.3 Generalized Permutations and Combinations
6.4 Algorithms for Generating Permutations and Combinations
6.5 Introduction to Discrete Probability
6.6 Discrete Probability Theory
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle
7. Recurrence Relations
,7.1 Introduction
7.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms
8. Graph Theory
8.1 Introduction
8.2 Paths and Cycles
Problem-Solving Corner: Graphs
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity
9. Trees
9.1 Introduction
9.2 Terminology and Characterizations of Trees
ST
Problem-Solving Corner: Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
U
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees
D
10. Network Models
10.1 Introduction
10.2 A Maximal Flow Algorithm
YL
10.3 The Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving Corner: Matching
11. Boolean Algebras and Combinatorial Circuits
11.1 Combinatorial Circuits
AB
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
11.5 Applications
12. Automata, Grammars, and Languages
12.1 Sequential Circuits and Finite-State Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between Languages and Automata
Appendices
A. Matrices
B. Algebra Review
C. Pseudocode
, Solutions to Selected Exercises
Section 1.1
ST
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}
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}
U
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
D
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
YL
22 < 10, then x ∈ B. If x = 3, since 3 ∈ Z+ and 32 < 10, then x ∈ B. Thus if x ∈ A, then x ∈ B.
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 ∈
AB
/ A, A 6= B.
38. Since 32 − 1 > 3, 3 ∈
/ B. Since 3 ∈ A, A 6= B. 41. Equal 42. Not equal
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,
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.
for
Discrete Mathematics, 8th
edition
ST
by Richard Johnsonbaugh
U
D
(All Chapters 1-12, 100%
YL
Original Verified, A+ Grade)
AB
, Table of Content
1. Sets and Logic
1.1 Sets
1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers
2. Proofs
2.1 Mathematical Systems, Direct Proofs, and Counterexamples
2.2 More Methods of Proof
Problem-Solving Corner: Proving Some Properties of Real Numbers
2.3 Resolution Proofs
2.4 Mathematical Induction
Problem-Solving Corner: Mathematical Induction
ST
2.5 Strong Form of Induction and the Well-Ordering Property
3. Functions, Sequences, and Relations
3.1 Functions
Problem-Solving Corner: Functions
3.2 Sequences and Strings
U
3.3 Relations
3.4 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
D
3.5 Matrices of Relations
3.6 Relational Databases
4. Algorithms
YL
4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
Problem-Solving Corner: Design and Analysis of an Algorithm
4.4 Recursive Algorithms
AB
5. Introduction to Number Theory
5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
Problem-Solving Corner: Making Postage
5.4 The RSA Public-Key Cryptosystem
6. Counting Methods and the Pigeonhole Principle
6.1 Basic Principles
Problem-Solving Corner: Counting
6.2 Permutations and Combinations
Problem-Solving Corner: Combinations
6.3 Generalized Permutations and Combinations
6.4 Algorithms for Generating Permutations and Combinations
6.5 Introduction to Discrete Probability
6.6 Discrete Probability Theory
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle
7. Recurrence Relations
,7.1 Introduction
7.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms
8. Graph Theory
8.1 Introduction
8.2 Paths and Cycles
Problem-Solving Corner: Graphs
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity
9. Trees
9.1 Introduction
9.2 Terminology and Characterizations of Trees
ST
Problem-Solving Corner: Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
U
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees
D
10. Network Models
10.1 Introduction
10.2 A Maximal Flow Algorithm
YL
10.3 The Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving Corner: Matching
11. Boolean Algebras and Combinatorial Circuits
11.1 Combinatorial Circuits
AB
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
11.5 Applications
12. Automata, Grammars, and Languages
12.1 Sequential Circuits and Finite-State Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between Languages and Automata
Appendices
A. Matrices
B. Algebra Review
C. Pseudocode
, Solutions to Selected Exercises
Section 1.1
ST
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}
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}
U
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
D
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
YL
22 < 10, then x ∈ B. If x = 3, since 3 ∈ Z+ and 32 < 10, then x ∈ B. Thus if x ∈ A, then x ∈ B.
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 ∈
AB
/ A, A 6= B.
38. Since 32 − 1 > 3, 3 ∈
/ B. Since 3 ∈ A, A 6= B. 41. Equal 42. Not equal
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,
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.
