Discrete Mathematics

Content: 1 Sets and Logic1.1 Sets1.2 Propositions1.3 Conditional Propositions and Logical Equivalence1.4 Arguments and Rules of Inference1.5 Quantifiers1.6 Nested QuantifiersProblem-Solving Corner: Quantifiers 2 Proofs2.1 Mathematical Systems, Direct Proofs, and Counterexamples2.2 More Methods of ProofProblem-Solving Corner: Proving Some Properties of Real Numbers2.3 Resolution Proofs2.4 Mathematical InductionProblem-Solving Corner: Mathematical Induction2.5 Strong Form of Induction and the Well-Ordering Property Notes Chapter Review Chapter Self-Test Computer Exercises 3 Functions, Sequences, and Relations3.1 FunctionsProblem-Solving Corner: Functions3.2 Sequences and Strings3.3 Relations3.4 Equivalence RelationsProblem-Solving Corner: Equivalence Relations3.5 Matrices of Relations3.6 Relational Databases 4 Algorithms4.1 Introduction4.2 Examples of Algorithms4.3 Analysis of AlgorithmsProblem-Solving Corner: Design and Analysis of an Algorithm4.4 Recursive Algorithms 5 Introduction to Number Theory5.1 Divisors5.2 Representations of Integers and Integer Algorithms5.3 The Euclidean AlgorithmProblem-Solving Corner: Making Postage5.4 The RSA Public-Key Cryptosystem 6 Counting Methods and the Pigeonhole Principle6.1 Basic PrinciplesProblem-Solving Corner: Counting6.2 Permutations and CombinationsProblem-Solving Corner: Combinations6.3 Generalized Permutations and Combinations6.4 Algorithms for Generating Permutations and Combinations6.5 Introduction to Discrete Probability6.6 Discrete Probability Theory6.7 Binomial Coefficients and Combinatorial Identities6.8 The Pigeonhole Principle 7 Recurrence Relations7.1 Introduction7.2 Solving Recurrence RelationsProblem-Solving Corner: Recurrence Relations7.3 Applications to the Analysis of Algorithms  8 Graph Theory8.1 Introduction8.2 Paths and CyclesProblem-Solving Corner: Graphs8.3 Hamiltonian Cycles and the Traveling Salesperson Problem8.4 A Shortest-Path Algorithm8.5 Representations of Graphs8.6 Isomorphisms of Graphs8.7 Planar Graphs8.8 Instant Insanity 9 Trees9.1 Introduction9.2 Terminology and Characterizations of TreesProblem-Solving Corner: Trees9.3 Spanning Trees9.4 Minimal Spanning Trees9.5 Binary Trees9.6 Tree Traversals9.7 Decision Trees and the Minimum Time for Sorting9.8 Isomorphisms of Trees9.9 Game Trees 10 Network Models10.1 Introduction10.2 A Maximal Flow Algorithm10.3 The Max Flow, Min Cut Theorem10.4 MatchingProblem-Solving Corner: Matching 11 Boolean Algebras and Combinatorial Circuits11.1 Combinatorial Circuits11.2 Properties of Combinatorial Circuits11.3 Boolean AlgebrasProblem-Solving Corner: Boolean Algebras11.4 Boolean Functions and Synthesis of Circuits11.5 Applications 12 Automata, Grammars, and Languages12.1 Sequential Circuits and Finite-State Machines12.2 Finite-State Automata12.3 Languages and Grammars12.4 Nondeterministic Finite-State Automata12.5 Relationships Between Languages and Automata  AppendixA MatricesB Algebra ReviewC PseudocodeReferencesHints and Solutions to Selected Exercises Index