Discrete mathematics with applications

Title Page......Page 2
Copyright Page......Page 3
Contents......Page 6
Preface......Page 14
1.1: Variables......Page 24
1.2: The Language of Sets......Page 29
1.3: The Language of relations and functions......Page 38
1.4: The Language of Graphs......Page 47
2.1: Logical Form and Logical Equivalence......Page 60
2.2: Conditional Statements......Page 76
2.3: Valid and Invalid Arguments......Page 89
2.4: Application: Digital Logic Circuits......Page 102
2.5: Application: Number Systems and Circuits for Addition......Page 116
3.1: Predicates and Quantified Statements I......Page 131
3.2: Predicates and Quantified Statements II......Page 145
3.3: Statements with Multiple Quantifiers......Page 154
3.4: Arguments with Quantified Statements......Page 169
Chapter 04: Elementary Number theory and Methods of Proof......Page 183
4.1: Direct Proof and Counterexample I: Introduction......Page 184
4.2: Direct Proof and Counterexample II: writing Advice......Page 196
4.3: Direct Proof and Counterexample III: Rational Numbers......Page 206
4.4: Direct Proof and Counterexample IV: Divisibility......Page 213
4.5: Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem......Page 223
4.6: Direct Proof and Counterexample VI: Floor and Ceiling......Page 234
4.7: Indirect argument: Contradiction and Contraposition......Page 241
4.8: Indirect Argument: Two Famous Theorems......Page 251
4.9: Application: The Handshake Theorem......Page 258
4.10: Application: Algorithms......Page 267
5.1: Sequences......Page 281
5.2: Mathematical Induction I: proving Formulas......Page 298
5.3: Mathematical Induction II: Applications......Page 312
5.4: Strong Mathematical Induction and the Well-Ordering principle for the Integers......Page 324
5.5: Application: Correctness of Algorithms......Page 337
5.6: Defining Sequences Recursively......Page 348
5.7: Solving Recurrence Relations by Iteration......Page 363
5.8: Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients......Page 375
5.9: General Recursive Definitions and Structural Induction......Page 387
6.1: Set Theory: Definitions and the Element Method of Proof......Page 400
6.2: Properties of Sets......Page 414
6.3: Disproofs and Algebraic Proofs......Page 430
6.4: Boolean Algebras, Russell’s Paradox, and the Halting Problem......Page 437
7.1: Functions Defined on General Sets......Page 448
7.2: One-to-One, Onto, and Inverse Functions......Page 462
7.3: Composition of functions......Page 484
7.4: Cardinality with Applications to Computability......Page 496
8.1: Relations on Sets......Page 510
8.2: Reflexivity, Symmetry, and Transitivity......Page 518
8.3: Equivalence Relations......Page 528
8.4: Modular Arithmetic with Applications to Cryptography......Page 547
8.5: Partial Order relations......Page 569
9.1: introduction to Probability......Page 587
9.2: Possibility Trees and the Multiplication rule......Page 596
9.3: Counting elements of Disjoint Sets: The Addition rule......Page 612
9.4: The Pigeonhole Principle......Page 627
9.5: Counting Subsets of a Set: Combinations......Page 640
9.6: r-Combinations with repetition Allowed......Page 657
9.7: Pascal’s Formula and the Binomial Theorem......Page 665
9.8: Probability Axioms and expected Value......Page 678
9.9: Conditional Probability, Bayes’ Formula, and independent events......Page 685
10.1: Trails, Paths, and Circuits......Page 700
10.2: Matrix Representations of Graphs......Page 721
10.3: isomorphisms of Graphs......Page 736
10.4: Trees: Examples and Basic Properties......Page 743
10.5: Rooted Trees......Page 755
10.6: Spanning Trees and a Shortest Path Algorithm......Page 765
11.1: Real-Valued Functions of a Real Variable and Their Graphs......Page 783
11.2: Big-O, Big-Omega, and Big-Theta Notations......Page 792
11.3: Application: Analysis of Algorithm Efficiency I......Page 810
11.4: Exponential and Logarithmic Functions: Graphs and Orders......Page 823
11.5: Application: Analysis of Algorithm Efficiency II......Page 836
Chapter 12: Regular Expressions and Finite-State Automata......Page 851
12.1: Formal Languages and Regular Expressions......Page 852
12.2: Finite-State Automata......Page 864
12.3: Simplifying Finite-State Automata......Page 881
Appendix A: Properties of the real Numbersp......Page 895
Appendix B: Solutions and Hints to Selected Exercises......Page 898
Index......Page 1036