Discrete Mathematics,
7th ed.
Richard Johnsonbaugh
Table of Contents
Preface
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
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
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
2.5 Strong
Form of Induction and the Well-Ordering Property
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
3 Functions, Sequences, and Relations
3.1 Functions
Problem-Solving Corner: Functions
3.2 Sequences
and Strings
3.3 Relations
3.4 Equivalence
Relations
Problem-Solving
Corner: Equivalence Relations
3.5 Matrices
of Relations
3.6 Relational
Databases
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
4 Algorithms
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
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
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
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
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
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
7 Recurrence Relations
7.1 Introduction
7.2 Solving
Recurrence Relations
Problem-Solving
Corner: Recurrence Relations
7.3 Applications
to the Analysis of Algorithms
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
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
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
9 Trees
9.1 Introduction
9.2 Terminology
and Characterizations of Trees
Problem-Solving
Corner: Trees
9.3 Spanning
Trees
9.4 Minimal
Spanning Trees
9.5 Binary
Trees
9.6 Tree
Traversals
9.7 Decision
Trees and the Minimum Time for Sorting
9.8 Isomorphisms
of Trees
9.9 Game
Trees
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
10 Network Models
10.1 Introduction
10.2 A
Maximal Flow Algorithm
10.3 The
Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving
Corner: Matching
Notes
Chapter
Review
Chapter Self-Test
Computer
Exercises
11 Boolean Algebras and Combinatorial
Circuits
11.1 Combinatorial
Circuits
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
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
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
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
13 Computational Geometry
13.1 The
Closest-Pair Problem
13.2 An
Algorithm to Compute the Convex
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
Appendix
A Matrices
B Algebra
Review
C Pseudocode
References
Hints
and Solutions to Selected Exercises
Index