离散数学

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