Discrete Mathematics
Fifth Edition
Richard Johnsonbaugh
DePaul University
Table of Contents
1 Logic and Proofs
1.1 Propositions
1.2 Conditional Propositions and Logical Equivalence
1.3 Quantifiers
1.4 Proofs
†1.5 Resolution Proofs
1.6 Mathematical Induction
Problem-Solving Corner: Mathematical Induction
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
2 The Language of Mathematics
2.1 Sets
2.2 Sequences and Strings
2.3 Number Systems
2.4 Relations
Problem-Solving Corner: Relations
2.5 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
2.6 Matrices of Relations
†
2.7 Relational Databases2.8 Functions
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
3 Algorithms
3.1 Introduction
3.2 Notation for Algorithms
3.3 The Euclidean Algorithm
3.4 Recursive Algorithms
3.5 Complexity of Algorithms
Problem-Solving Corner: Design and Analysis of an Algorithm
3.6 Analysis of the Euclidean Algorithm
†
3.7 The RSA Public-Key CryptosystemNotes
Chapter Review
Chapter Self-Test
Computer Exercises
4 Counting Methods and the Pigeonhole Principle
4.1 Basic Principles
Problem-Solving Corner: Counting
4.2 Permutations and Combinations
Problem-Solving Corner: Combinations
4.3 Algorithms for Generating Permutations and Combinations
†
4.4 Introduction to Discrete Probability†
4.5 Discrete Probability Theory4.6 Generalized Permutations and Combinations
4.7 Binomial Coefficients and Combinatorial Identities
4.8 The Pigeonhole Principle
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
5 Recurrence Relations
5.1 Introduction
5.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
5.3 Applications to the Analysis of Algorithms
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
6 Graph Theory
6.1 Introduction
6.2 Paths and Cycles
Problem-Solving Corner: Graphs
6.3 Hamiltonian Cycles and the Traveling Salesperson Problem
6.4 A Shortest-Path Algorithm
6.5 Representations of Graphs
6.6 Isomorphisms of Graphs
6.7 Planar Graphs
6.8 Instant Insanity
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
7 Trees
7.1 Introduction
7.2 Terminology and Characterizations of Trees
Problem-Solving Corner: Trees
7.3 Spanning Trees
7.4 Minimal Spanning Trees
7.5 Binary Trees
7.6 Tree Traversals
7.7 Decision Trees and the Minimum Time for Sorting
7.8 Isomorphisms of Trees
†7.9 Game Trees
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
8 Network Models
8.1 Introduction
8.2 A Maximal Flow Algorithm
8.3 The Max Flow, Min Cut Theorem
8.4 Matching
Problem-Solving Corner: Matching
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
9 Boolean Algebras and Combinatorial Circuits
9.1 Combinatorial Circuits
9.2 Properties of Combinatorial Circuits
9.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
9.4 Boolean Functions and Synthesis of Circuits
9.5 Applications
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
10 Automata, Grammars, and Languages
10.1 Sequential Circuits and Finite-State Machines
10.2 Finite-State Automata
10.3 Languages and Grammars
10.4 Nondeterministic Finite-State Automata
10.5 Relationships Between Languages and Automata
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
11 Computational Geometry
11.1 The Closest-Pair Problem
†11.2 A Lower Bound for the Closest-Pair Problem
11.3 An Algorithm to Compute the Convex Hull
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
Appendix
A Matrices
B Algebra Review
References
Hints and Solutions to Selected Exercises
Index