离散数学

Preface to the Fifth Edition ix
To the Student Especially xiii
 1  Sets, Sequences, and Functions
 1.1   Some Warm-up Questions  1
 1.2   Factors and Multiples  7
 Office Hours  15
 1.3   Some Special Sets  16
 1.4   Set Operations  22
 1.5   Functions  28
 1.6   Sequences  34
 1.7   Properties of Functions  39
 Office Hours  46
 Supplementary Exercises  48
 2  Elementary Logic  50
 2.1   Informal Introduction  50
 2.2   Propositional Calculus  58
 2.3   Getting Started with Proofs  66
 2.4  Methods of Proof 71
 Office Hours  76
 2.5   Logic in Proofs  77
 2.6   Analysis of Arguments  86
 Supplementary Exercises  94
 3  Relations  95
 3.1   Relations  95
 3.2   Digraphs and Graphs  100
 3.3   Matrices  106
 3.4   Equivalence Relations and Partitions  112
 3.5   The Division Algorithm and Integers Mod p  119
 Supplementary Exercises  127
 4  Induction and Recursion  128
 4.1   Loop Invariants  128
 4.2   Mathematical Induction  137
 Office Hours  144
 4.3  Big-Oh Notation  145
 4.4  Recursive Definitions  153
 4.5   Recurrence Relations  160
 4.6   More Induction  167
 4.7   The Euclidean Algorithm  171
 Supplementary Exercises  179
 5  Counting  181
 5.l   Basic Counting Techniques  181
 5.2   Elementary Probability  189
 5.3   Inclusion-Exclusion and Binomial Methods  197
 5.4   Counting and Partitions  204
 Office Hours  212
 5.5   Pigeon-Hole Principle  213
 Supplementary Exercises  220
 6  Introduction to Graphs and Trees
 6.1   Graphs  225
 6.2   Edge Traversal Problems  232
 6.3   Trees  239
 6.4   Rooted Trees  244
 6.5   Vertex Traversal Problems  251
 6.6   Minimum Spanning Trees  257
 Supplementary Exercises  266
 7  Recursion, Trees, and Algorithms
 7.1   General Recursion  269
 7.2   Recursive Algorithms  277
 7.3   Depth-First Search Algorithms  286
 7.4   Polish Notation  298
 7.5   Weighted Trees  304
 Supplementary Exercises  315
 8  Digraphs  318
 8.1   Digraphs Revisited  318
 8.2   Weighted Digraphs and Scheduling Networks  325
 Office Hours  333
 8.3   Digraph Algorithms  333
 Supplementary Exercises  347
 9  Discrete Probability 349
 9.1   Independence in Probability  349
 9.2   Random Variables  359
 9.3   Expectation and Standard Deviation  366
 9.4   Probability Distributions  374
 Supplementary Exercises  387
 10  Boolean Algebra  389
 10.1  Boolean Algebras  389
 10.2  Boolean Expressions  398
 10.3  Logic Networks  405
 10.4  KamaughMaps  412
 10.5  Isomorphisms of Boolean Algebras  417
 Supplementary Exercises  422
 11  More on Relations 424
 11.1 Partially Ordered Sets 424
 11.2  Special Orderings  433
 11.3  Multiplication of Matrices  439
 11.4  Properties of General Relations  446
 11.5  Closures of Relations  452
 Supplementary Exercises  459
 12  Algebraic Structures  462
 12.1  Groups Acting on Sets  462
 12.2  Fixed Points and Subgroups  470
 12.3  Counting Orbits  476
 12.4  Group Homomorphisms  487
 12.5  Semigroups  495
 12.6  Other Algebraic Systems  501
 Supplementary Exercises  512
 13  Predicate Calculus and Infinite Sets
 13.1  Quantifiers and Predicates  515
 13.2  Elementary Predicate Calculus  522
 13.3 Infinite Sets 527
Supplementary Exercises  534
Dictionary 536
Answers and Hints  538
Index 607