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

1 The Foundations: Logic and Proofs....................................1 1.1 Propositional Logic............................................................1 1.2 Applications of Propositional Logic.............................................17 1.3 Propositional Equivalences....................................................26 1.4 Predicates and Quantifiers.....................................................40 1.5 Nested Quantifiers............................................................60 1.6 Rules of Inference.............................................................73 1.7 Introduction to Proofs.........................................................84 1.8 Proof Methods and Strategy....................................................96 End-of-Chapter Material.....................................................115 2 Basic Structures: Sets, Functions, Sequences, Sums, and atrices....................................121 2.1 Sets........................................................................121 2.2 Set Operations...............................................................133 2.3 Functions...................................................................147 2.4 Sequences and Summations...................................................165 2.5 Cardinality of Sets...........................................................179 2.6 Matrices....................................................................188 End-of-Chapter Material.....................................................195 3 Algorithms.........................................................201 3.1 Algorithms..................................................................201 3.2 The Growth of Functions.....................................................216 3.3 Complexity of Algorithms....................................................231 End-of-Chapter Materia.....................................................244 4 Number Theory and Cryptography..................................251 4.1 Divisibility and Modular Arithmetic...........................................251 4.2 Integer Representations and Algorithms........................................260 4.3 Primes and Greatest Common Divisors........................................271 4.4 Solving Congruences.........................................................290 4.5 Applications of Congruences.................................................303 4.6 Cryptography...............................................................310 End-of-Chapter Materia.....................................................324 5 Induction and Recursion............................................331 5.1 Mathematical Induction......................................................331 5.2 Strong Induction and Well-Ordering...........................................354 5.3 Recursive Definitions and Structural Induction..................................365 5.4 Recursive Algorithms........................................................381 5.5 Program Correctness.........................................................393 End-of-Chapter Materia.....................................................398 6 Counting...........................................................405 6.1 The Basics of Counting.......................................................405 6.2 The Pigeonhole Principle.....................................................420 6.3 Permutations and Combinations...............................................428 6.4 Binomial Coeficients and Identities...........................................437 6.5 Generalized Permutations and Combinations...................................445 6.6 Generating Permutations and Combinations....................................457 End-of-Chapter Materia.....................................................461 7 Discrete Probability.................................................469 7.1 An Introduction to Discrete Probability........................................469 7.2 Probability Theory......................................