本书专为计算机科学专业的学生而设计，不仅提供学生必需的离散数学知识，而且能够启发后续专业课程的学习兴趣。本书主要内容涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论，推导严谨、代码清晰、练习丰富。本书不仅适合作为高校计算机相关专业离散数学课程的教材，也适合从事计算机行业的技术人员参考。
课程动机与目标很多学院与大学都开设了离散数学这门课程。上这些课程的学生来自多个学科，其中最多的是来自计算机科学的学生。由国家科学基金会支持，作为达特茅斯（Dartmouth）学院跨学科数学项目的一部分，我们提出创建一门离散数学课程来直接解决计算机科学学生的需求。计算机科学的学生需要知道哪些离散数学知识？为什么需要知道这些知识？关于这两个问题，我们的看法如下。
第一，我们认为一些知识对于计算机科学很重要，但是传统的离散数学课程常常不会透彻地讲授这些知识。这些知识包括：递归树和解决递推关系的主定理，计算平均运行时间和分析随机算法的概率理论，以及强归纳法和结构归纳法。
第二，我们认为对于计算机科学的学生而言，那些重要的离散数学知识在计算机科学里对应着一些颇有启发性的问题，并且只具备一两门计算机科学入门课程水平的学生也能够理解。这样有可能回答一届又一届学生在应用数学课程中的疑问：“为什么我们必须学习这个？”因此，我们选择写一本针对计算机科学学生的教科书，为他们提供必要的数学基础，并且通过他们在起步阶段就能够理解的计算机科学问题来启发学习兴趣。
在计算机科学系，离散数学通常是学生的专业首选课之一，甚至是第一门计算机科学课程的先修课。在这种情况下，教师面临着两难困境：是讲授纯数学概念，几乎不涉及计算机应用，还是讲授计算机科学的例子，从而营造一种针对计算机科学学生的教学环境。第一种讲课方式让学生们抱怨在学习第一门计算机科学课程之前，被迫学习太多“不相干的”数学。第二种讲课方式让教授们（通常是数学家）尝试给可能从来没有写过程序的学生解释相当高级的计算机科学知识，比如散列、二叉树和循环程序等。即使在最好的情况，这种方法也明显降低了数学的深度。我们的分析产生了一种不同的讲课方式，创设一门出现在学生稍后学习过程中的课程。尽管我们不强制要求学生已经上过微积分，但是我们假定学生了解并且能够熟练使用加和符号、对数和指数函数，因此对于微积分学前课程的内容有很深的了解是很有帮助的。这意味着要让学生在一门计算机科学的导论课程中先了解递归程序，然后再学习这门课。最好可以和数据结构课程一起或者在其之后学习，不过我们会通过例子解释书中所使用的数据结构，因此数据结构不是这门课的先导课程。
我们觉得这样安排离散数学这门课程有几个优势，下面列举几个特别的例子：学生已经有了较为深入的问题求解、算法和代码的经验。
学生已经学习过或者在准备学习一些重要的计算机科学概念，比如散列、递归、排序、搜索以及基本的数据结构。
学生已经知道足够的计算机科学知识，包括一些启发性的例子，或者其他容易理解的简单例子。例如：m散列可以用于启发关于概率的学习。
m分析递归程序（比如并归和快速排序）可以用于启发关于递归关系及其解决方法的学习。
m在寻找队列中最小元素的过程中，分析我们期望多久找到一个新的最小值，可以用来启发关于期望的线性性质和调和数的学习。
m二叉树可以用来讲解结构递归法，也可以启发作为图的特例的树的学习。
在我们自己的讲课经验中，这门课是算法课的前导，并且学生经常在结束离散数学课程不久后就学习算法。这样，他们会发现自己可以直接使用刚刚学过的离散数学知识。
我们的教育哲学这本教科书是以教学活动为驱动的，并且包含丰富的练习题。通过对这些活动的解释和扩展，教学素材得以不断充实。对于学生最有效的方法是尝试认真完成学生活动，而先不阅读那些教学活动后面的解释。我们最初设计这些教学活动是想让学生在课堂中以小组的形式来完成，因此，如果需要在课外开展教学活动，建议学生组建小组一起完成。我们采用这种方式来设计这门课程以及这本教材，希望借此帮助学生们养成自己的数学思维习惯。我们仔细研究了本科学生应当怎样学习数学，得到了以下几个结论：如果学生能够主动发现他们正在学习的是什么（经常被称为“主动学习”），往往比那些被动学习的学生能够更长久地记住这些概念，也更有可能在学习环境之外运用这些概念。
当学生在一个小组中和同学一起学习，而不是在由导师带领的一个更大的班级中时，他们更有可能提出问题，直到彻底理解某个主题。（然而，这一点不总是成立。很多学生需要在小组中感到舒适之后才敢提出的问题，因为他们担心自己的提问会耽误别人的学习速度。我们尝试提高课程中的舒适度，方法是允许学生自由选择学习小组，并且根据出席模式允许或者要求学生在不同的天数后更换不同的小组。）最后，学生在给别人解释概念的时候能够更有效地组织自己脑中的想法，同时能够熟悉数学语言。
本书内容足够支撑一门四学期学时的课程。在达特茅斯学院，我们使用这本书来上一门快节奏的课程，一周上三天且仅仅上九周，并且覆盖了本书除了最后几个章节和一部分带星号的内容之外的所有内容。
证明的作用我们写这本书的目的之一是给学生们提供一些关于证明的背景知识，在以后的计算机科学课程中，他们将需要理解并且写出证明。
Contents
CHAPTER1 Counting 31
1.1 Basic Counting 31
The Sum Principle 31
Abstraction 33
Summing Consecutive Integers 33
The Product Principle 34
Two-Element Subsets 36
Important Concepts, Formulas, and Theorems 37
Problems 38
1.2 Counting Lists, Permutations, and Subsets 40
Using the Sum and Product Principles 40
Lists and Functions 42
The Bijection Principle 44
k-Element Permutations of a Set 45
Counting Subsets of a Set 46
Important Concepts, Formulas, and Theorems 48
Problems 50
1.3 Binomial Coeffiients 52
Pascal’s Triangle 52
A Proof Using the Sum Principle 54
The Binomial Theorem 56
Labeling and Trinomial Coefficient 58
Important Concepts, Formulas, and Theorems 59
Problems 60
1.4 Relations 62
What Is a Relation? 62
Functions as Relations 63
Properties of Relations 63
Equivalence Relations 66
Partial and Total Orders 69
Important Concepts, Formulas, and Theorems 71
Problems 72
1.5 Using Equivalence Relationsin Counting 73
The Symmetry Principle
Equivalence Relations 75
The Quotient Principle 76
Equivalence Class Counting 76
Multisets 78
The Bookcase Arrangement Problem 80
The Number of k-Element Multisets of an n-Element Set 81
Usingthe Quotient Principle to Explain a Quotient 82
Important Concepts, Formulas, and Theorems 83
Problems 84
CHAPTER2 Cryptography and Number Theory 89
2.1 Cryptography and Modular Arithmetic 89
Introduction to Cryptography 89
Private-Key Cryptography 90
Public-Key Cryptosystems 93
Arithmetic Modulo n 95
Cryptography Using Addition mod n 98
Cryptography Using Multiplication mod n 99
Important Concepts, Formulas, and Theorems 101
Problems 102
2.2 Inverses and Greatest Common Divisors 105
Solutions to Equations and Inverses mod n 105
Inverses mod n 106
Converting Modular Equations to Normal Equations 109
Greatest Common Divisors 110
Euclid’s Division Theorem 111
Euclid’s GCD Algorithm 114
Extended GCD Algorithm 115
Computing Inverses 118
Important Concepts, Formulas, and Theorems 119
Problems 120
2.3 The RSA Cryptosystem 123
Exponentiation mod n 123
The Rules of Exponents 123
Fermat’s Little Theorem 126
The RSA Cryptosystem 127
The Chinese Remainder Theorem 131
Important Concepts, Formulas, and Theorems 132
Problems 134
2.4 Details of the RSA Cryptosystem 136
Practical Aspects of Exponentiation mod n 136
How Long Does It Take to Use the RSA Algorithm? 139
How Hard Is Factoring? 140
Finding Large Primes 140
Important Concepts, Formulas, and Theorems 143
Problems 144
CHAPTER3 Reflectionon Logic and Proof 147
3.1 Equivalence and Implication 147
Equivalence of Statements 147
Truth Tables 150
DeMorgan’s Laws 153
Implication 155
If and Only If 156
Important Concepts, Formulas, and Theorems 159
Problems 161
3.2 Variables and Quantifier 163
Variables and Universes 163
Quantifier 164
Standard Notation for Quantificatio 166
Statements about Variables 168
Rewriting Statements to Encompass Larger Universes 168
Proving Quantifie Statements Trueor False 169
Negation of Quantifie Statements 170
Implicit Quantificatio 173
Proof of Quantifie Statements 174
Important Concepts, Formulas, and Theorems 175
Problems 177
3.3 Inference 179
Direct Inference (Modus Ponens) and Proofs 179
Rules of Inference for Direct Proofs 181
Contrapositive Ruleof Inference 183
Proof by Contradiction 185
Important Concepts, Formulas, and Theorems 188
Problems 189
CHAPTER4 Induction, Recursion, and Recurrences 191
4.1 Mathematical Induction 191
Smallest Counterexamples 191
The Principle of Mathematical Induction 195
Strong Induction 199
Induction in General 201
A Recursive Viewof Induction 203
Structural Induction 206
Important Concepts, Formulas, and Theorems 208
Problems 210
4.2 Recursion, Recurrences, and Induction 213
Recursion 213
Examples of First-Order Linear Recurrences 215
Iteratinga Recurrence 217
Geometric Series 218
First-Order Linear Recurrences 221
Important Concepts,
新书资讯
