Discrete Mathematics and Its Applications

Cover Page......Page p0001.djvu
Title Page......Page p0002.djvu
Copyright Page......Page p0003.djvu
Contents......Page p0004.djvu
About the Author......Page p0007.djvu
Preface......Page p0008.djvu
The Companion Website......Page p0017.djvu
To the Student......Page p0019.djvu
1.1 Propositional Logic......Page p0022.djvu
1.2 Applications of Propositional Logic......Page p0037.djvu
1.3 Propositional Equivalences......Page p0046.djvu
1.4 Predicates and Quantifiers......Page p0057.djvu
1.5 Nested Quantifiers......Page p0078.djvu
1.6 Rules of Inference......Page p0090.djvu
1.7 Introduction to Proofs......Page p0101.djvu
1.8 Proof Methods and Strategy......Page p0113.djvu
End-of-Chapter Material......Page p0130.djvu
2.1 Sets......Page p0136.djvu
2.2 Set Operations......Page p0148.djvu
2.3 Functions......Page p0159.djvu
2.4 Sequences and Summations......Page p0177.djvu
2.5 Cardinality of Sets......Page p0191.djvu
2.6 Matrices......Page p0198.djvu
End-of-Chapter Material......Page p0206.djvu
3.1 Algorithms......Page p0212.djvu
3.2 The Growth of Functions......Page p0225.djvu
3.3 Complexity of Algorithms......Page p0239.djvu
End-of-Chapter Material......Page p0253.djvu
4.1 Divisibility and Modular Arithmetic......Page p0258.djvu
4.2 Integer Representations and Algorithms......Page p0266.djvu
4.3 Primes and Greatest Common Divisors......Page p0278.djvu
4.4 Solving Congruences......Page p0295.djvu
4.5 Applications of Congruences......Page p0308.djvu
4.6 Cryptography......Page p0315.djvu
End-of-Chapter Material......Page p0327.djvu
5.1 Mathematical Induction......Page p0332.djvu
5.2 Strong Induction andWell-Ordering......Page p0354.djvu
5.3 Recursive Definitions and Structural Induction......Page p0365.djvu
5.4 Recursive Algorithms......Page p0381.djvu
5.5 Program Correctness......Page p0393.djvu
End-of-Chapter Material......Page p0398.djvu
6.1 The Basics of Counting......Page p0406.djvu
6.2 The Pigeonhole Principle......Page p0420.djvu
6.3 Permutations and Combinations......Page p0428.djvu
6.4 Binomial Coefficients and Identities......Page p0436.djvu
6.5 Generalized Permutations and Combinations......Page p0444.djvu
6.6 Generating Permutations and Combinations......Page p0455.djvu
End-of-Chapter Material......Page p0460.djvu
7.1 An Introduction to Discrete Probability......Page p0466.djvu
7.2 Probability Theory......Page p0473.djvu
7.3 Bayes’ Theorem......Page p0489.djvu
7.4 Expected Value and Variance......Page p0498.djvu
End-of-Chapter Material......Page p0515.djvu
8.1 Applications of Recurrence Relations......Page p0522.djvu
8.2 Solving Linear Recurrence Relations......Page p0535.djvu
8.3 Divide-and-Conquer Algorithms and Recurrence Relations......Page p0548.djvu
8.4 Generating Functions......Page p0558.djvu
8.5 Inclusion–Exclusion......Page p0573.djvu
8.6 Applications of Inclusion–Exclusion......Page p0579.djvu
End-of-Chapter Material......Page p0586.djvu
9.1 Relations and Their Properties......Page p0594.djvu
9.2 n-ary Relations and Their Applications......Page p0604.djvu
9.3 Representing Relations......Page p0612.djvu
9.4 Closures of Relations......Page p0618.djvu
9.5 Equivalence Relations......Page p0628.djvu
9.6 Partial Orderings......Page p0639.djvu
End-of-Chapter Material......Page p0654.djvu
10.1 Graphs and Graph Models......Page p0662.djvu
10.2 Graph Terminology and Special Types of Graphs......Page p0672.djvu
10.3 Representing Graphs and Graph Isomorphism......Page p0689.djvu
10.4 Connectivity......Page p0699.djvu
10.5 Euler and Hamilton Paths......Page p0714.djvu
10.6 Shortest-Path Problems......Page p0728.djvu
10.7 Planar Graphs......Page p0739.djvu
10.8 Graph Coloring......Page p0748.djvu
End-of-Chapter Material......Page p0756.djvu
11.1 Introduction to Trees......Page p0766.djvu
11.2 Applications of Trees......Page p0778.djvu
11.3 Tree Traversal......Page p0793.djvu
11.4 Spanning Trees......Page p0806.djvu
11.5 Minimum Spanning Trees......Page p0818.djvu
End-of-Chapter Material......Page p0824.djvu
12.1 Boolean Functions......Page p0832.djvu
12.2 Representing Boolean Functions......Page p0840.djvu
12.3 Logic Gates......Page p0843.djvu
12.4 Minimization of Circuits......Page p0849.djvu
End-of-Chapter Material......Page p0864.djvu
13.1 Languages and Grammars......Page p0868.djvu
13.2 Finite-State Machines with Output......Page p0879.djvu
13.3 Finite-State Machines with No Output......Page p0886.djvu
13.4 Language Recognition......Page p0899.djvu
13.5 Turing Machines......Page p0909.djvu
End-of-Chapter Material......Page p0920.djvu
1 Axioms for the Real Numbers and the Positive Integers......Page p0926.djvu
2 Exponential and Logarithmic Functions......Page p0932.djvu
3 Pseudocode......Page p0936.djvu
Suggested Readings......Page p0942.djvu
Answers to Odd-Numbered Exercises......Page p0950.djvu
Photo Credits......Page p1047.djvu
Index of Biographies......Page p1049.djvu
Index......Page p1050.djvu