Discrete Mathematics with Applications

Description

Front Cover Discrete Mathematicswith Applications Copyright Page Table of Contents Preface A Word to the Student Chapter 1. The Language of Logic 1.1 Propositions 1.2 Logical Equivalences 1.3 Quantifiers 1 .4 Arguments (optional) 1.5 Proof Methods Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 2. The Language of Sets 2.1 The Concept of a Set 2.2 Operations with Sets 2.3 Computer Operations with Sets (optional) 2.4 The Cardinality of a Set 2.5 Recursively Defined Sets Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 3. Functions and Matrices 3.1 The Concept of a Function 3.2 Special Functions 3.3 Properties of Functions 3.4 The Pigeonhole Principle 3.5 Composition of Functions 3.6 Sequences and the Summation Notation 3.7 Matrices Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 4. Induction and Algorithms 4.1 The Division Algorithm 4.2 Divisibility Properties 4.3 Nondecimal Bases 4.4 Mathematical Induction 4.5 Algorithm Correctness 4.6 The Growth of Functions 4 .7 Complexities of Algorithms (optional) Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 5. Recursion 5.1 Recursively Defined Functions 5.2 Solving Recurrence Relations 5.3 Solving Recurrence Relations Revisited 5.4 Generating Functions 5.5 Recursive Algorithms 5.6 Correctness of Recursive Algorithms 5.7 Complexities of Recursive Algorithms (optional) Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 6. Combinatorics and Discrete Probability 6.1 The Fundamental Counting Principles 6.2 Permutations 6.3 Derangements 6.4 Combinations 6.5 Permutations and Combinations with Repetitions 6.6 The Binomial Theorem 6.7 The Generalized Inclusion–Exclusion Principle (GIEP) (optional) 6.8 Discrete Probability (optional) 6.9 Additional Topics in Probability (optional) Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 7. Relations 7.1 Boolean Matrices 7.2 Relations and Digraphs 7.3 Computer Representations of Relations (optional) 7.4 Properties of Relations 7.5 Operations on Relations 7.6 The Connectivity Relation (optional) 7.7 Transitive Closure (optional) 7.8 Equivalence Relations 7.9 Partial and Total Orderings Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 8. Graphs 8.1 Graphs 8.2 Computer Representations of Graphs (optional) 8.3 Isomorphic Graphs 8.4 Paths, Cycles, and Circuits 8.5 Eulerian and Hamiltonian Graphs 8.6 Planar Graphs 8.7 Graph Coloring Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 9. Trees 9.1 Trees 9.2 Spanning trees 9.3 Minimal Spanning Trees 9.4 Rooted Trees 9.5 Binary Trees 9.6 Binary Search Trees 9.7 Huffman Trees (optional) 9.8 Decision Trees (optional) Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 10. Digraphs 10.1 Digraphs 10.2 Dags 10.3 Weighted Digraphs Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 11. Formal Languages and Finite-State Machines 11.1 Formal Languages 11.2 Grammars 11.3 Finite-State Automata 11.4 Finite-State Machines 11.5 Deterministic Finite-State Automata and Regular Languages 11.6 Nondeterministic Finite-State Automata 11.7 Automata and Regular Languages Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Chapter 12. Boolean Algebra and Combinatorial Circuits 12.1 Boolean Algebra 12.2 Boolean functions 12.3 Logic Gates 12.4 Combinatorial Circuits 12.5 Minimization of Combinatorial Circuits 12.6 Don’t Care Conditions Chapter Summary Review Exercises Supplementary Exercises Computer Exercises Exploratory Writing Projects Enrichment Readings Appendix A A.1 ASCII Character Set A.2 Determinants A.3 Exponential and Logarithmic Functions A.4 Generating Permutations and Combinations A.5 The Multinomial Theorem A.6 The Greek Alphabet A.7 Web Sites References Solutions to Odd-Numbered Exercises Credits Index List of Biographical Sketches Application Index Alogrithms Index List of Symbols