离散数学及其应用(英文版·原书第8版)

本书是经典的离散数学教材，被全球数百所大学广为采用。书中全面而系统地介绍了离散数学的理论和方法，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。

1 The Foundations:Logic and Proofs1
1.1 Propositional Logic1
1.2 Applications of Propositional Logic17
1.3 Propositional Equivalences26
1.4 Predicates and Quantifiers40
1.5 Nested Quantifiers60
1.6 Rules of Inference73
1.7 Introduction to Proofs84
1.8 Proof Methods and Strategy96
End-of-Chapter Material115
2 Basic Structures:Sets,Functions,Sequences,Sums,and atrices121
2.1 Sets121
2.2 Set Operations133
2.3 Functions147
2.4 Sequences and Summations165
2.5 Cardinality of Sets179
2.6 Matrices188
End-of-Chapter Material195
3 Algorithms201
3.1 Algorithms201
3.2 The Growth of Functions216
3.3 Complexity of Algorithms231
End-of-Chapter Materia244
4 Number Theory and Cryptography251
4.1 Divisibility and Modular Arithmetic251
4.2 Integer Representations and Algorithms260
4.3 Primes and Greatest Common Divisors271
4.4 Solving Congruences290
4.5 Applications of Congruences303
4.6 Cryptography310
End-of-Chapter Materia324
5 Induction and Recursion331
5.1 Mathematical Induction331
5.2 Strong Induction and Well-Ordering354
5.3 Recursive Definitions and Structural Induction365
5.4 Recursive Algorithms381
5.5 Program Correctness393
End-of-Chapter Materia398
6 Counting405
6.1 The Basics of Counting405
6.2 The Pigeonhole Principle420
6.3 Permutations and Combinations428
6.4 Binomial Coeficients and Identities437
6.5 Generalized Permutations and Combinations445
6.6 Generating Permutations and Combinations457
End-of-Chapter Materia461
7 Discrete Probability469
7.1 An Introduction to Discrete Probability469
7.2 Probability Theory477
……
8 Advanced Counting Techniques
9 Relations
10 Graphs
11 Trees
12 Boolean Algebra
13 Modeling Computation
Appendices
Suggested Readings B-1
Answers to Odd-Numbered Exercises S-1
Index of Biographies I-1
Index I-2