Discrete Mathematics with Applications (eBook)

Front Cover 1
Discrete Mathematicswith Applications 8
Copyright Page 9
Table of Contents 12
Preface 18
A Word to the Student 26
Chapter 1. The Language of Logic 30
1.1 Propositions 31
1.2 Logical Equivalences 49
1.3 Quantifiers 61
1.4 Arguments (optional) 67
1.5 Proof Methods 78
Chapter Summary 85
Review Exercises 87
Supplementary Exercises 91
Computer Exercises 92
Exploratory Writing Projects 92
Enrichment Readings 93
Chapter 2. The Language of Sets 96
2.1 The Concept of a Set 96
2.2 Operations with Sets 107
2.3 Computer Operations with Sets (optional) 123
2.4 The Cardinality of a Set 127
2.5 Recursively Defined Sets 133
Chapter Summary 138
Review Exercises 140
Supplementary Exercises 142
Computer Exercises 143
Exploratory Writing Projects 143
Enrichment Readings 144
Chapter 3. Functions and Matrices 146
3.1 The Concept of a Function 146
3.2 Special Functions 154
3.3 Properties of Functions 165
3.4 The Pigeonhole Principle 173
3.5 Composition of Functions 179
3.6 Sequences and the Summation Notation 186
3.7 Matrices 193
Chapter Summary 204
Review Exercises 206
Supplementary Exercises 208
Computer Exercises 210
Exploratory Writing Projects 211
Enrichment Readings 212
Chapter 4. Induction and Algorithms 214
4.1 The Division Algorithm 214
4.2 Divisibility Properties 218
4.3 Nondecimal Bases 226
4.4 Mathematical Induction 236
4.5 Algorithm Correctness 253
4.6 The Growth of Functions 266
4.7 Complexities of Algorithms (optional) 276
Chapter Summary 281
Review Exercises 283
Supplementary Exercises 285
Computer Exercises 286
Exploratory Writing Projects 288
Enrichment Readings 288
Chapter 5. Recursion 290
5.1 Recursively Defined Functions 291
5.2 Solving Recurrence Relations 307
5.3 Solving Recurrence Relations Revisited 315
5.4 Generating Functions 327
5.5 Recursive Algorithms 336
5.6 Correctness of Recursive Algorithms 345
5.7 Complexities of Recursive Algorithms (optional) 348
Chapter Summary 362
Review Exercises 363
Supplementary Exercises 367
Computer Exercises 368
Exploratory Writing Projects 370
Enrichment Readings 370
Chapter 6. Combinatorics and Discrete Probability 372
6.1 The Fundamental Counting Principles 373
6.2 Permutations 380
6.3 Derangements 389
6.4 Combinations 394
6.5 Permutations and Combinations with Repetitions 404
6.6 The Binomial Theorem 415
6.7 The Generalized Inclusion–Exclusion Principle (GIEP) (optional) 428
6.8 Discrete Probability (optional) 438
6.9 Additional Topics in Probability (optional) 446
Chapter Summary 456
Review Exercises 458
Supplementary Exercises 461
Computer Exercises 463
Exploratory Writing Projects 463
Enrichment Readings 464
Chapter 7. Relations 466
7.1 Boolean Matrices 467
7.2 Relations and Digraphs 472
7.3 Computer Representations of Relations (optional) 478
7.4 Properties of Relations 483
7.5 Operations on Relations 490
7.6 The Connectivity Relation (optional) 500
7.7 Transitive Closure (optional) 504
7.8 Equivalence Relations 511
7.9 Partial and Total Orderings 522
Chapter Summary 535
Review Exercises 537
Supplementary Exercises 540
Computer Exercises 541
Exploratory Writing Projects 542
Enrichment Readings 543
Chapter 8. Graphs 544
8.1 Graphs 545
8.2 Computer Representations of Graphs (optional) 567
8.3 Isomorphic Graphs 570
8.4 Paths, Cycles, and Circuits 575
8.5 Eulerian and Hamiltonian Graphs 585
8.6 Planar Graphs 605
8.7 Graph Coloring 615
Chapter Summary 627
Review Exercises 630
Supplementary Exercises 633
Computer Exercises 635
Exploratory Writing Projects 542
Enrichment Readings 543
Chapter 9. Trees 638
9.1 Trees 639
9.2 Spanning trees 643
9.3 Minimal Spanning Trees 655
9.4 Rooted Trees 664
9.5 Binary Trees 675
9.6 Binary Search Trees 693
9.7 Huffman Trees (optional) 699
9.8 Decision Trees (optional) 705
Chapter Summary 709
Review Exercises 710
Supplementary Exercises 715
Computer Exercises 716
Exploratory Writing Projects 717
Enrichment Readings 717
Chapter 10.Digraphs 720
10.1 Digraphs 720
10.2 Dags 736
10.3 Weighted Digraphs 744
Chapter Summary 755
Review Exercises 756
Supplementary Exercises 759
Computer Exercises 760
Exploratory Writing Projects 761
Enrichment Readings 761
Chapter 11. Formal Languages and Finite-State Machines 762
11.1 Formal Languages 763
11.2 Grammars 772
11.3 Finite-State Automata 788
11.4 Finite-State Machines 800
11.5 Deterministic Finite-State Automata and Regular Languages 808
11.6 Nondeterministic Finite-State Automata 811
11.7 Automata and Regular Languages 816
Chapter Summary 821
Review Exercises 823
Supplementary Exercises 827
Computer Exercises 829
Exploratory Writing Projects 830
Enrichment Readings 831
Chapter 12. Boolean Algebra and Combinatorial Circuits 832
12.1 Boolean Algebra 833
12.2 Boolean functions 842
12.3 Logic Gates 853
12.4 Combinatorial Circuits 859
12.5 Minimization of Combinatorial Circuits 869
12.6 Don’t Care Conditions 880
Chapter Summary 886
Review Exercises 888
Supplementary Exercises 891
Computer Exercises 892
Exploratory Writing Projects 893
Enrichment Readings 893
Appendix A 896
A.1 ASCII Character Set 896
A.2 Determinants 896
A.3 Exponential and Logarithmic Functions 903
A.4 Generating Permutations and Combinations 912
A.5 The Multinomial Theorem 917
A.6 The Greek Alphabet 923
A.7 Web Sites 924
References 928
Solutions to Odd-Numbered Exercises 936
Credits 1058
Index 1060
List of Biographical Sketches 1072
Application Index 1074
Alogrithms Index 1076
List of Symbols 1077