Discrete mathematics for computer scientists and mathematicians

목차 (Table of Contents)

• CONTENTS
• Preface = ⅶ
• Acknowledgments = xiii
• A Note to the Reader = xiv
• 1. Foundations = 1
• 1.1. Basics = 1
• 1.2. Sets and Operations of Sets = 2
• 1.3. Relations and Functions = 9
• 1.4. Some Methods of Proof and Problem - Solving Strategies = 17
• 1.5. Fundamentals of Logic = 33
• 1.6. Logical Inferences = 45
• 1.7. Methods of Proof of an Implication = 60
• 1.8. First Order Logic and Other Methods of Proof = 79
• 1.9. Rules of Inference for Quantified Propositions = 97
• 1.10. Mathematical Induction = 103
• 2. Elementary Combinatorics = 125
• 2.1. Basics of Counting = 126
• 2.2. Combinations and Permutations = 143
• 2.3. Enumeration of Combinations and Permutations = 147
• 2.4. Enumerating Combinations and Permutations with Repetitions = 162
• 2.5. Enumerating Permutations with Constrained Repetitions = 172
• 2.6. Binomial Coefficients = 189
• 2.7. The Binomial and Multinomial Theorems = 201
• 2.8. The Principle of Inclusion - Exclusion = 211
• 3. Recurrence Relations = 237
• 3.1. Generating Functions of Sequences = 237
• 3.2. Calculating Coefficients of Generating Functions = 247
• 3.3. Recurrence Relations = 264
• 3.4. Solving Recurrence Relations by Substitution and Generati : Functions = 280
• 3.5. The Method of Characteristic Roots = 300
• 3.6. Solutions of Inhomogeneous Recurrence Relations = 306
• 4. Relations and Digraphs = 331
• 4.1. Relations and Directed Graphs = 331
• 4.2. Special Properties of Binary Relations = 339
• 4.3. Equivalence Relations = 349
• 4.4. Ordering Relations, Lattices, and Enumerations = 362
• 4.5. Operations on Relations = 379
• 4.6. Paths and Closures = 388
• 4.7. Directed Graphs and Adjacency Matrices = 395
• 4.8. Application : Sorting and Searching = 415
• 4.9. Application : Topological Sorting = 428
• 5. Graphs = 437
• 5.1. Basic Concepts = 437
• 5.2. Isomorphisms and Subgraphs = 449
• 5.3. Trees and Their Properties = 468
• 5.4. Spanning Trees = 480
• 5.5. Directed Trees = 498
• 5.6. Binary Trees = 507
• 5.7. Planar Graphs = 523
• 5.8. Euler's Formula = 530
• 5.9. Multigraphs and Euler Circuits = 535
• 5.10. Hamiltonian Graphs = 452
• 5.11. Chromatic Numbers = 558
• 5.12. The Four - Color Problem = 569
• 6. Boolean Algebras = 577
• 6.1. Introduction = 577
• 6.2. Boolean Algebras = 578
• 6.3. Boolean Functions = 588
• 6.4. Switching Mechanisms = 595
• 6.5. Minimization of Boolean Functions = 605
• 6.6. Applications to Digital Computer Design = 613
• 7. Network Flows = 631
• 7.1. Graphs as Models of Flow of Commodities = 631
• 7.2. Flows = 636
• 7.3. Maximal Flows and Minimal Cuts = 645
• 7.4. The Max Flow - Min Cut Theorem = 659
• 7.5. Applications : Matching and Hall's Marriage Theorem = 686
• 8. Representation and Manipulation of Imprecision = 699
• 8.1. Fuzzy Sets = 699
• 8.2. Possibility Theory = 715
• 8.3. Application of Fuzzy Set Theory to Expert Systems = 720
• Bibliography = 735
• Index = 739