Discrete Mathematics with Applications [5th ed.] (without the photoportraits)

Description

Contents......Page 3 Preface......Page 11 1.1: Variables......Page 21 1.2: The Language of Sets......Page 26 1.3: The Language of relations and functions......Page 35 1.4: The Language of Graphs......Page 44 2.1: Logical Form and Logical Equivalence......Page 57 2.2: Conditional Statements......Page 73 2.3: Valid and Invalid Arguments......Page 86 2.4: Application: Digital Logic Circuits......Page 99 2.5: Application: Number Systems and Circuits for Addition......Page 113 3.1: Predicates and Quantified Statements I......Page 128 3.2: Predicates and Quantified Statements II......Page 142 3.3: Statements with Multiple Quantifiers......Page 151 3.4: Arguments with Quantified Statements......Page 166 4 Elementary Number Theory & Methods of Proof......Page 180 4.1: Direct Proof and Counterexample I: Introduction......Page 181 4.2: Direct Proof and Counterexample II: writing Advice......Page 193 4.3: Direct Proof and Counterexample III: Rational Numbers......Page 203 4.4: Direct Proof and Counterexample IV: Divisibility......Page 210 4.5: Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem......Page 220 4.6: Direct Proof and Counterexample VI: Floor and Ceiling......Page 231 4.7: Indirect argument: Contradiction and Contraposition......Page 238 4.8: Indirect Argument: Two Famous Theorems......Page 248 4.9: Application: The Handshake Theorem......Page 255 4.10: Application: Algorithms......Page 264 5.1: Sequences......Page 278 5.2: Mathematical Induction I: proving Formulas......Page 295 5.3: Mathematical Induction II: Applications......Page 309 5.4: Strong Mathematical Induction and the Well-Ordering principle for the Integers......Page 321 5.5: Application: Correctness of Algorithms......Page 334 5.6: Defining Sequences Recursively......Page 345 5.7: Solving Recurrence Relations by Iteration......Page 360 5.8: Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients......Page 372 5.9: General Recursive Definitions and Structural Induction......Page 384 6.1: Set Theory: Definitions and the Element Method of Proof......Page 397 6.2: Properties of Sets......Page 411 6.3: Disproofs and Algebraic Proofs......Page 427 6.4: Boolean Algebras, Russell?s Paradox, and the Halting Problem......Page 434 7.1: Functions Defined on General Sets......Page 445 7.2: One-to-One, Onto, and Inverse Functions......Page 459 7.3: Composition of functions......Page 481 7.4: Cardinality with Applications to Computability......Page 493 8.1: Relations on Sets......Page 507 8.2: Reflexivity, Symmetry, and Transitivity......Page 515 8.3: Equivalence Relations......Page 525 8.4: Modular Arithmetic with Applications to Cryptography......Page 544 8.5: Partial Order relations......Page 566 9.1: introduction to Probability......Page 584 9.2: Possibility Trees and the Multiplication rule......Page 593 9.3: Counting elements of Disjoint Sets: The Addition rule......Page 609 9.4: The Pigeonhole Principle......Page 624 9.5: Counting Subsets of a Set: Combinations......Page 637 9.6: r-Combinations with repetition Allowed......Page 654 9.7: Pascal?s Formula and the Binomial Theorem......Page 662 9.8: Probability Axioms and expected Value......Page 675 9.9: Conditional Probability, Bayes? Formula, and independent events......Page 682 10.1: Trails, Paths, and Circuits......Page 697 10.2: Matrix Representations of Graphs......Page 718 10.3: isomorphisms of Graphs......Page 733 10.4: Trees: Examples and Basic Properties......Page 740 10.5: Rooted Trees......Page 752 10.6: Spanning Trees and a Shortest Path Algorithm......Page 762 11.1: Real-Valued Functions of a Real Variable and Their Graphs......Page 780 11.2: Big-O, Big-Omega, and Big-Theta Notations......Page 789 11.3: Application: Analysis of Algorithm Efficiency I......Page 807 11.4: Exponential and Logarithmic Functions: Graphs and Orders......Page 820 11.5: Application: Analysis of Algorithm Efficiency II......Page 833 12 Regular Expressions & FSA......Page 848 12.1: Formal Languages and Regular Expressions......Page 849 12.2: Finite-State Automata......Page 861 12.3: Simplifying Finite-State Automata......Page 878 Properties of the real Numbers......Page 892 Solutions & Hints......Page 895 Index......Page 1033