Discrete_Math_6th_edition.pdf

【核心代码】

Contents
Preface xi
A Word to Students xv
1 Fundamentals 1
1.1 Sets and Subsets 2
1.2 Operations on Sets 5
1.3 Sequences 13
1.4 Properties of the Integers 20
1.5 Matrices 32
1.6 Mathematical Structures 41
2 Logic 50
2.1 Propositions and Logical Operations 51
2.2 Conditional Statements 57
2.3 Methods of Proof 62
2.4 Mathematical Induction 68
2.5 Mathematical Statements 75
2.6 Logic and Problem Solving 78
3 Counting 91
3.1 Permutations 92
3.2 Combinations 96
3.3 Pigeonhole Principle 100
3.4 Elements of Probability 104
3.5 Recurrence Relations 112
4 Relations and Digraphs 122
4.1 Product Sets and Partitions 123
4.2 Relations and Digraphs 127
4.3 Paths in Relations and Digraphs 135
4.4 Properties of Relations 141
4.5 Equivalence Relations 148
4.6 Data Structures for Relations and Digraphs 152
4.7 Operations on Relations 159
4.8 Transitive Closure and Warshall’s Algorithm 169
vii
viii Contents
5 Functions 180
5.1 Functions 181
5.2 Functions for Computer Science 190
5.3 Growth of Functions 200
5.4 Permutation Functions 205
6 Order Relations and Structures 217
6.1 Partially Ordered Sets 218
6.2 Extremal Elements of Partially Ordered Sets 228
6.3 Lattices 233
6.4 Finite Boolean Algebras 243
6.5 Functions on Boolean Algebras 250
6.6 Circuit Design 254
7 Trees 270
7.1 Trees 271
7.2 Labeled Trees 275
7.3 Tree Searching 280
7.4 Undirected Trees 288
7.5 Minimal Spanning Trees 295
8 Topics in Graph Theory 305
8.1 Graphs 306
8.2 Euler Paths and Circuits 311
8.3 Hamiltonian Paths and Circuits 318
8.4 Transport Networks 321
8.5 Matching Problems 329
8.6 Coloring Graphs 334
9 Semigroups and Groups 344
9.1 Binary Operations Revisited 345
9.2 Semigroups 349
9.3 Products and Quotients of Semigroups 356
9.4 Groups 362
9.5 Products and Quotients of Groups 372
9.6 Other Mathematical Structures 377
Contents ix
10 Languages and Finite-State Machines 386
10.1 Languages 387
10.2 Representations of Special Grammars and Languages 394
10.3 Finite-State Machines 403
10.4 Monoids, Machines, and Languages 409
10.5 Machines and Regular Languages 414
10.6 Simplification of Machines 420
11 Groups and Coding 429
11.1 Coding of Binary Information and Error Detection 430
11.2 Decoding and Error Correction 440
11.3 Public Key Cryptology 449
Appendix A: Algorithms and Pseudocode 455
Appendix B: Additional Experiments in
Discrete Mathematics 467
Appendix C: Coding Exercises 473
Answers to Odd-Numbered Exercises 477
Answers to Chapter Self-Tests 515
Glossary G-1
Index I-1
Photo Credits P-1