Discrete Mathematics and Its Applications

Description

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