Discrete Mathematics and Its Applications

Cover......Page 1
Title Page......Page 2
Copyright Page......Page 3
Contents......Page 4
About the Author......Page 7
Preface......Page 8
Acknowledgments......Page 14
Online Resources......Page 17
To the Student......Page 20
1.1 Propositional Logic......Page 24
1.2 Applications of Propositional Logic......Page 40
1.3 Propositional Equivalences......Page 49
1.4 Predicates and Quantifiers......Page 63
1.5 Nested Quantifiers......Page 83
1.6 Rules of Inference......Page 96
1.7 Introduction to Proofs......Page 107
1.8 Proof Methods and Strategy......Page 119
End-of-Chapter Material......Page 138
2.1 Sets......Page 144
2.2 Set Operations......Page 156
2.3 Functions......Page 170
2.4 Sequences and Summations......Page 188
2.5 Cardinality of Sets......Page 202
2.6 Matrices......Page 211
End-of-Chapter Material......Page 218
3.1 Algorithms......Page 224
3.2 The Growth of Functions......Page 239
3.3 Complexity of Algorithms......Page 254
End-of-Chapter Material......Page 267
4.1 Divisibility and Modular Arithmetic......Page 274
4.2 Integer Representations and Algorithms......Page 283
4.3 Primes and Greatest Common Divisors......Page 294
4.4 Solving Congruences......Page 313
4.5 Applications of Congruences......Page 326
4.6 Cryptography......Page 333
End-of-Chapter Material......Page 347
5.1 Mathematical Induction......Page 354
5.2 Strong Induction and Well-Ordering......Page 377
5.3 Recursive Definitions and Structural Induction......Page 388
5.4 Recursive Algorithms......Page 404
5.5 Program Correctness......Page 416
End-of-Chapter Material......Page 421
6.1 The Basics of Counting......Page 428
6.2 The Pigeonhole Principle......Page 443
6.3 Permutations and Combinations......Page 451
6.4 Binomial Coefficients and Identities......Page 460
6.5 Generalized Permutations and Combinations......Page 468
6.6 Generating Permutations and Combinations......Page 480
End-of-Chapter Material......Page 484
7.1 An Introduction to Discrete Probability......Page 492
7.2 Probability Theory......Page 500
7.3 Bayes’ Theorem......Page 517
7.4 Expected Value and Variance......Page 526
End-of-Chapter Material......Page 543
8.1 Applications of Recurrence Relations......Page 550
8.2 Solving Linear Recurrence Relations......Page 563
8.3 Divide-and-Conquer Algorithms and Recurrence Relations......Page 576
8.4 Generating Functions......Page 586
8.5 Inclusion–Exclusion......Page 602
8.6 Applications of Inclusion–Exclusion......Page 608
End-of-Chapter Material......Page 615
9.1 Relations and Their Properties......Page 622
9.2 n-ary Relations and Their Applications......Page 634
9.3 Representing Relations......Page 644
9.4 Closures of Relations......Page 651
9.5 Equivalence Relations......Page 661
9.6 Partial Orderings......Page 673
End-of-Chapter Material......Page 688
10.1 Graphs and Graph Models......Page 696
10.2 Graph Terminology and Special Types of Graphs......Page 708
10.3 Representing Graphs and Graph Isomorphism......Page 726
10.4 Connectivity......Page 737
10.5 Euler and Hamilton Paths......Page 751
10.6 Shortest-Path Problems......Page 766
10.7 Planar Graphs......Page 776
10.8 Graph Coloring......Page 785
End-of-Chapter Material......Page 794
11.1 Introduction to Trees......Page 804
11.2 Applications of Trees......Page 816
11.3 Tree Traversal......Page 831
11.4 Spanning Trees......Page 844
11.5 Minimum Spanning Trees......Page 858
End-of-Chapter Material......Page 864
12.1 Boolean Functions......Page 870
12.2 Representing Boolean Functions......Page 878
12.3 Logic Gates......Page 881
12.4 Minimization of Circuits......Page 887
End-of-Chapter Material......Page 902
13.1 Languages and Grammars......Page 908
13.2 Finite-State Machines with Output......Page 920
13.3 Finite-State Machines with No Output......Page 927
13.4 Language Recognition......Page 940
13.5 Turing Machines......Page 950
End-of-Chapter Material......Page 961
1 Axioms for the Real Numbers and the Positive Integers......Page 966
2 Exponential and Logarithmic Functions......Page 972
3 Pseudocode......Page 976
Suggested Readings......Page 982
Answers to Odd-Numbered Exercises......Page 990
Index of Biographies......Page 1088
Index......Page 1089