《离散数学结构 第3版》

1Fundamentals1

1.1　Sets and Subsets1

1.2　Operations on Sets5

1.3　Sequences14

1.4　Division in the Integers22

1.5 Matrices30

1.6　Mathematical Structures39

2　Logic46

2.1　Propositions and Logical Operations46

2.2　Conditional Statements52

2.3　Methods of Proof58

2.4　Mathematical Induction64

3Counting72

3.1 Permutations72

3.2 Combinations78

3.3 The Pigeonhole Principle82

3.4 Elements of Probability85

3.5 Recurrence Relations95

4Relations and Digraphs101

4.1 Product Sets and Partitions101

4.2 Relations and Digraphs106

4.3 Paths in Relations and Digraphs116

4.4 Properties of Relations124

4.5 Equivalence Relations131

4.6 Computer Representation of Relations and Digraphs136

4.7 Manipulation of Relations146

4.8 Transitive Closure and Warshall's Algorithm157

5Functions167

5.1 Functions167

5.2 Functions for Computer Science177

5.3 Permutation Functions181

5.4 Growth of Functions190

6Topics in Graph Theory197

6.1 Graphs197

6.2 Euler Paths and Circuits204

6.3 Hamiltonian Paths and Circuits213

6.4 Coloring Graphs218

7Order Relations and Structures225

7.1 Partially Ordered Sets225

7.2 Extremal Elements of Partially Ordered Sets239

7.3 Lattices246

7.4 Finite Boolean Algebras259

7.5 Functions on Boolean Algebras266

7.6 Boolean Functions as Boolean Polynomials271

8Trees286

8.1 Trees286

8.2 Labeled Trees292

8.3 Tree Searching299

8.4 Undirected Trees310

8.5 Minimal Spanning Trees321

9Semigroups and Groups329

9.1 Binary Operations Revisited329

9.2 Semigroups334

9.3 Products and Quotients of Semigroups342

9.4 Groups349

9.5 Products and Quotients of Groups361

10Languages and Finite-State Machines368

10.1 Languages368

10.2 Representations of Special Languages and Grammars378

10.3 Finite-State Machines391

10.4 Semigroups，Machines，and Languages398

10.5 Machines and Regular Languages404

10.6 Simplification of Machines412

11Groups and Coding420

11.1 Coding of Binary Information and Error Detection420

11.2 Decoding and Error Correction432

Appendix A Algorithms and Pseudocode444

Appendix B Experiments in Discrete Mathematics458

Answers to Odd-Numbered Exercises477

Index513