本书由计算机和数学领域的三位教授联合撰写，是为计算机专业量身定制的离散数学教材。针对初入学的本科生不理解为何要学习高深的数学，授课教师苦于向毫无编程经验的学生讲授繁杂的算法程序的问题，本书打破了传统的课程顺序和教学方法，明确“为何学”和“有何用”，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用启发学生对后续课程的学习兴趣。主要内容涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论等。本书推导严谨、代码清晰、练习丰富，可作为高等学校计算机相关专业的离散数学课程的教材，也可供计算机技术人员学习与参考。
为计算机科学专业量身定制的离散数学课程教材
动机与目标
很多大学都开设离散数学课程。上该课程的学生来自多个专业，其中最多的是来自计算机科学专业的学生。在国家科学基金会一的支持下，作为达特茅斯（Dartmouth）学院跨学科数学项目的一部分，我们提出开设一门离散数学课程来满足计算机科学专业学生的需求。在分析想让计算机科学专业的学生了解哪些离散数学主题，以及为什么想让他们了解这些主题时，我们得到两个结论。
第一，我们认为一些主题对于计算机科学专业很重要，但是没有被充分地纳入传统的离散数学课程中。这些主题包括递归树和解决递推关系的主定理，计算平均运行时间和分析随机算法的概率理论，以及强归纳法和结构归纳法。
第二，我们认为对于计算机科学专业学生很重要的每个离散数学主题，在计算机科学里都有一个很有启发性的主题，上述第一门或者第二门计算机科学入门课程的学生可以理解这些主题。我们感觉这样安排就能回答在应用数学课程中学生经常会问的问题：“为什么我们必须学习这些？”因此，我们决定写一本针对计算机科学专业学生的教科书，目标是为计算机科学专业学生提供必要的数学基础，并且通过学生在计算机科学学习的开始阶段就能够理解的计算机科学问题来启发他们学习这本教科书。
一基金资助号为DUE-9552462。
二我们的大多数学生已经学习过微积分。在一些地方我们会使用初级的导数，并且在概率部分的选修小节中，我们使用自然对数、指数函数和初级的幂级数。如果忽略少数使用导数的证明和问题，以及概率部分的选修小节，教师可以不涉及微积分。
在许多高校的计算机科学系，离散数学是学生的专业必修课之一，甚至是第一门计算机科学课程的先修课。在这种情况下，教师面临一种困境——讲授纯数学的概念，很少或者完全没有显式的计算机应用，或者讲授计算机科学的例子来营造一种针对计算机科学专业学生的语境。对于第一种讲课方式，学生会抱怨在学习第一门计算机科学课程之前被迫学习太多“不相干的”数学知识。对于第二种讲课方式，教师（通常是数学家）要尝试给可能从来没有写过程序的学生解释相当高级的计算机科学主题，比如散列、二叉树和递归程序等。即使在最好的情况下，这种方式也明显降低了数学的深度。基于我们的分析，产生了一种不同的讲课方式，即开设一门学生稍后学习的课程。尽管我们没有明确假定学生已经学过微积分，但是假定学生了解并且能够熟练使用求和符号、对数和指数函数。因此，熟悉微积分知识是很有帮助的二。这意味着学生要在计算机科学的入门课中见过递归程序之后再学习这门课。这门课最好和数据结构课程同时学习或者在其之后学习，不过我们会通过例子解释所使用的数据结构。因此，数据结构课程不是这门课的先导课程。
我们觉得这样安排离散数学课程有很多优势，例如：
?学生已经有了较为深入的问题解决、算法和编程的经验。
?学生已经学习或者准备学习一些重要的计算机科学概念，比如散列、递归、排序和搜索，以及基本的数据结构。
?学生对计算机科学有足够的了解，已经知道一些启发性例子，或者这些例子对于他们而言足够简单易懂。例如：
a散列可以用于启发概率的学习。a分析递归程序，比如归并和快速排序，可以启发学习递推关系和相应的解决方法。
a分析在一个寻找线性表中最小元素的程序中，我们期望多久找到一个新的最小值，可以启发学习期望的线性性质和调和数。
a二叉树可以用于教授结构递归法，也可以作为图的特例启发树的学习。
根据我们自己的授课经验，离散数学课程是算法课的先导课程，学生经常在结束离散数学课程不久后就开始学习算法。这样，他们会发现自己可以直接使用刚学过的离散数学知识。
教学理念
这本教科书是以教学活动为驱动，以练习的形式体现的。教学内容通过说明和教学活动的延伸来形象地呈现。对于学生，使用这本书的最有效方法是认真参与教学活动，而不是只阅读那些教学活动后面的解释。这些教学活动在课堂中以小组的形式完成。因此，我们建议学生形成小组，一起解决安排在课外进行的教学活动。我们希望通过这种设计来帮助学生培养数学思维。通过了解关于本科生怎样学习数学，我们得出以下几个结论。
?那些主动发现自己所学内容的学生（从而参与到所谓的“主动学习”中）比那些不主动学习的学生记住概念的时间要长得多，他们也更有可能在课堂之外运用这些概念。
?当学生在一个小组和同学一起学习，而不是在一个有导师的更大的班级中学习时，他们更有可能提出问题，直到他们理解一个主题。（然而，情况并非如此。很多学生需要适应他们的小组之后再提出问题，因为他们担心会拖慢其他人的进度。我们尝试提高舒适度，允许学生选择学习小组，并且根据出席情况允许或者要求学生更换不同的小组。）
?最后，通过为他人解释概念来帮助学生进一步理解概念，并且让学生熟悉数学语言。
这本书的内容可用于一门四个学期的课程。在达特茅斯学院，我们使用这本书的课程节奏比较快，一周上三天且仅仅上九周，却涵盖了本书除了最后几节和一部分带星号的内容之外的所有内容。
证明的作用
我们编写这本书的目的之一是给学生提供一些关于证明的背景知识，在以后的计算机科学课程中，他们需要理解并且写出证明。我们的观点是用听、看、讨论并且尽量动手证明的方式来学习如何证明。为了方便讨论证明，我们需要用一种共同的语言来区分证明的组成成分，并且提供一个讨论的框架。为此，我们在书中包含一个逻辑的章节，即为学生提供这种语言，并帮助学生思考他们已经看到的证明。为了提供重要的内容在这个章节里讨论，我们在学生看过一些组合和数论的证明之后再安排相关内容。这种方法可以给学生提供一些用来阐述逻辑证明的具体例子。我们意识到，这不是离散数学教材中常用的顺序，而通过具体的例子来讨论重要事实的证明，可以提供一些实用的基础知识，否则这些证明看起来就是一长串的推理规则。
我们把关于逻辑的章节放在数学归纳法章节之前，这样就可以用逻辑语言来讨论和思考数学归纳法。
数学归纳法
计算机科学的归纳证明经常使用不是“更小”的子问题。因此，我们强调强归纳法和弱归纳法，也引入了树和图的结构归纳法。我们尝试让学生用递归的经验来更好地理解归纳证明，并且设计了基于归纳法的证明。特别是，当开始设计归纳证明时，从一个大问题开始并将它递归地分解成小问题，比由小问题开始并组成大问题更加有利。
伪代码的使用
我们同时使用文字和伪代码描述算法。任何使用Java、C或者C++写过程序的人都可以很轻松地读懂伪代码，使用其他语言写过程序的人也能很容易地理解伪代码。我们的终极目标不是给出语法上正确的任何一种语言的代码，而是力求代码的清晰。比如，对于“互换变量x和y的值”，我们会写成“交换x和y”，而不是写成三行的代码。类似地，我们写“如果点i、j和k不共线”，而不用担心其详细的计算过程如何处理。下面给出本书使用的特别约定。
?代码块通过缩进表示，而没有像许多语言那样使用“begin”“end”或者“{”“}”。
?for循环被写成“fori=1ton”来表示变量i的取值范围是从1到n。
?如果while之后的布尔表达式取值为真，while循环的主体会重复执行。
?repeat循环的使用格式为“repeat…until”。repeat和until之间的代码最少执行一次，并且会重复执行，直到until之后的布尔表达式取值为真。
?if语句可以使用以下任意一种格式：
aif（表达式）代码块
aif（表达式）代码块1else代码块2
在第一种格式中，代码块会执行，当且仅当表达式为真。在第二种格式中，如果表达式为真，则代码块1执行，而如果表达式为假，则代码块2执行。
?数组的下标使用“[]”。
?赋值用“=”，等式比较用“==”。
?x递增和递减分别用“x++”和“x??”表示。
?逻辑操作符“not”用“！”表示，所以“!true”是“false”，当x不小于y时，！(x
另一本书名相同、作者相同的书已经由另一家出版社出版，但这家出版社已经从大学教材市场退出。KenBogart是该书的主要作者，在该书出版前不久辞世。我们非常感谢他参与该书编写并为该书出版做出贡献。
本书最明显的变化如下：
?上一本书虽然讨论了等价关系，但只是作为一个集合的划分。等价关系的自反性、对称性和传递性被放到附录中介绍，并且没有讨论偏序和全序关系。本书讨论了关系，将其作为一个连接函数、等价关系、偏序关系和全序关系的概念。本书也解释了为什么利用自反性、对称性和传递性可以推导出等价关系，而利用自反性、反对称性和传递性则可以推导出偏序关系。
?本书包含结构归纳法。同时，对递归和归纳关系的章节进行了扩充，并且使用了一些不同的例子。
?将关于递推关系的章节删除或者放在附录中，这些章节在递推中去掉了下取整和上取整，并将关系的作用域扩展到非同底数幂的数域，主定理仍然有效。我们认为这些内容使章节不太顺畅，并且需要处理一些大多数学生在这个阶段不需要知道的细节。
?在条件概率的章节增加了贝叶斯定理。
?增加了问题来涵盖新的主题。
还有一些小的改变，例如，介绍“乘以x和相减”方法来得到一个几何级数的封闭形式。
教师辅助资料一
本书的教师辅助资料包括：
?教师手册
a教学建议
a课后作业的答案
a上课用的练习
a关于如何让学生采用小组的形式进行课堂练习的讨论
?教学PPT
一关于教辅资源，仅提供给采用本书作为教材的教师用作课堂教学，布置作业，发布考试等用途。如有需要的教师，请直接联系Pearson北京办公室查询并填表申请。联系邮箱：Copub.Hed@pearson.com——编辑注
致谢
很多人对本书的初稿做出了贡献。我们要感谢EddieCheng（奥克兰大学）、AliceDean（斯基德莫学院）、RuthHass（史密斯学院）和ItaloDejter（波多黎各大学），感谢他们对早期书稿的建设性意见。随着书稿的不断改进，我和NealYoung、PasadJayanti、TomShemanske、RoseOrellana、AprilRasala、AmitChakrabarti、CarlPomerance使用本书的初稿在达特茅斯学院教授离散数学。他们都对本书的最终稿产生了影响，甚至是很大的影响，感谢他们提出的建议。我们要特别感谢CarlPomerance在教学过程中有见地和前瞻性的评论。QunLi是我们开始准备书稿时的研究生助教，他完成了准备本书习题答案的工作。在使用初稿教学的时候，其他计算机科学和数学系的研究生助教也给出了很有价值的见解，让我们知道学生学到了什么，没有学到什么，从而能进一步帮助他们解决问题。这些研究生助教是S.Agrawal、ElishivaWerner-Reiss、RobertSavell、VirgiliuPavlu、LiboSong、GeetaChaudhry、KingTan、YurongXu、GabriellaDumitrascu、FlorinConstantin、AlinPopescu和WeiZhang。我们曾经的学生也提供了很有价值的反馈，特别是，EricRobinson认真读了整本书，明确提出了难以理解的章节。
我们也要感谢让这本书顺利出版的人。以下审稿人提供了很有价值的建议：MichaelRothstein（肯特州立大学）、RaviJanardan（明尼苏达大学）、KlausSutner（卡内基·梅隆大学）、DougBaldwin（纽约州立大学）、StuartReges（华盛顿大学）、RichardAnderson（华盛顿大学）、JonathanGoldstine（宾夕法尼亚大学）。SandraHakanson是Pearson的销售代表，她协助我们联系主编MichaelHirsch。他同意出版这本书，并且为本书出版提供了很多帮助，书中的很多改进源自他的建议。对本书的出版做出贡献的出版社人员还有：StephanieSellinger（编辑助理）、JefHolcomb（总编辑）、HeatherMcNally（项目编辑）和ElenaSidorova（封面设计人员）。Laserwords的BruceHobart负责书稿的编辑、排版和校对。
每一个作者都想要感谢另外两位作者从各自的工作中抽出时间完成这个项目。因为需要时间来融合我们的观点，只有在国家科学基金会（资助号DUE-9552462）的支持下，我们才能够承担这个项目。感谢本科生教学部门的老师在构思数学科学项目及其在整个教学课程中的应用时，在满足本科生的需求和解决跨学科课程发展的困难方面展现出来的洞察力。我们感谢这个项目对本科数学教育以及跨学科合作起到的推动作用。
CliffStein
ScotDrysdale
计算机\离散数学
本书由计算机和数学领域的三位教授联合撰写，旨在满足计算机专业对离散数学课程的需求。针对这门课程的困境——初入学的本科生不理解为何要学习高深的数学，以及授课教师难以向毫无编程经验的学生讲授繁杂的算法程序——本书明确了“为何学”和“有何用”，打破了传统的课程顺序和教学方法，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用激发学生对后续课程的学习兴趣。
主要内容：涵盖计数、密码编码学与数论、逻辑与证明、归纳、递归、概率以及图论，推导严谨、代码清晰、练习丰富。
教学模式：提倡参与式教学，鼓励学生加入小组讨论，主动探索，通过提问、讨论和报告来掌握概念，找到解决方案。
课程建议：建议学生掌握微积分知识，了解递归。
自 2016 年下半年起翻译 Clifford Stein、Robert L. Drysdale 和 Kenneth Bogart 三位教授合著的这本书，至今已经过去 4 年多了。翻译伊始，我们就认为这是一项非常有挑战的工作，但万万没有想到的是，前前后后竟然用了 4 年多的时间才完成翻译工作。一方面，翻译这本教学理念新颖的离散数学教材颇有难度，另一方面我们希望保证翻译质量，而不是追求翻译的速度。
如果说数学是所有理工科专业的基础，那么离散数学就是计算机专业的基础。离散数学一直被认为是计算机专业的核心课程之一，而这本书正是从计算机专业的角度出发，面向计算机专业学生的直接需求，以教学活动为驱动，辅以大量的习题来讲解离散数学的知识，易于读者深入理解和掌握。特别是，本书覆盖了传统的离散数学教材没有涉及但对于计算机专业又很重要的内容，如密码学、递归树、主定理、概率计算，以及强归纳法和结构归纳法等。译者相信，系统地学习和掌握这些内容对于一个计算机专业的学生（甚至是研究人员）的职业生涯将会产生深远的影响。
本书的翻译工作是由北京航空航天大学和中国人民大学的四位老师合作完成的。其中，马帅翻译前言、第 5 章、第 6 章及相应的索引和附录，秦波和伍前红翻译第 1 章、第 2 章及相应的索引和附录，罗杰翻译第 3 章、第 4 章及相应的索引和附录。此外，在本书的翻译过程中，蒋浩谊、王罡、张振宇、郑海彬、冯翰文、李雅楠、刘航、刘少凡、黄飞、王益飞、赵飞等同学也对初稿做了大量辅助工作。编辑朱劼在本书的翻译过程中始终给予译者高度的理解和信任，在此表示感谢。
由于译者水平所限，尽管已经竭尽全力地保证翻译质量，但还是难免有不妥甚至错误之处，敬请读者不吝赐教。请将问题发送给 mashuai@buaa.edu.cn，我们将及时给予读者反馈。
译者
北京航空航天大学
中国人民大学
2020 年 11 月于北京
译者序
前言
第1章 计数 1
1.1 基本计数 1
1.1.1 加法原理 1
1.1.2 抽象化 2
1.1.3 连续整数求和 3
1.1.4 乘法原理 3
1.1.5 二元子集 5
重要概念、公式和定理 5
习题 6
1.2 序列、排列和子集 7
1.2.1 使用加法和乘法原理 7
1.2.2 序列和函数 9
1.2.3 双射原理 10
1.2.4 集合的 k 元素排列 11
1.2.5 集合子集的计数 12
重要概念、公式和定理 14
习题 15
1.3 二项式系数 16
1.3.1 帕斯卡三角形 16
1.3.2 使用加法原理的证明 18
1.3.3 二项式定理 19
1.3.4 标记与三项式系数 21
重要概念、公式和定理 22
习题 22
1.4 关系 24
1.4.1 什么是关系 24
1.4.2 函数关系 24
1.4.3 关系的性质 25
1.4.4 等价关系 27
1.4.5 偏序和全序 29
重要概念、公式和定理 30
习题 31
1.5 在计数中运用等价关系 32
1.5.1 对称原理 32
1.5.2 等价关系 34
1.5.3 商原理 34
1.5.4 等价类计数 35
1.5.5 多重集 36
1.5.6 书柜安排问题 37
1.5.7 n 元集合的 k 元多重集的数目 38
1.5.8 使用商原理解释商 39
重要概念、公式和定理 39
习题 40
第2章 密码编码学与数论 43
2.1 密码编码学和模算法 43
2.1.1 密码编码学导论 43
2.1.2 私钥密码 43
2.1.3 公钥密码体制 46
2.1.4 模 n 算术 47
2.1.5 使用模 n 加法的密码编码 49
2.1.6 使用模 n 乘法的密码编码 50
重要概念、公式和定理 51
习题 52
2.2 逆元和最大公因子 54
2.2.1 方程的解和模 n 的逆元 54
2.2.2 模 n 的逆元 55
2.2.3 将模方程转化为普通方程 57
2.2.4 最大公因子 58
2.2.5 欧几里得除法定理 59
2.2.6 欧几里得最大公因子算法 61
2.2.7 广义最大公因子算法 62
2.2.8 计算逆元 64
重要概念、公式和定理 65
习题 66
2.3 RSA 密码体制 67
2.3.1 模 n 的指数运算 67
2.3.2 指数运算的规则 68
2.3.3 费马小定理 70
2.3.4 RSA 密码体制 71
2.3.5 中国剩余定理 74
重要概念、公式和定理 75
习题 76
2.4 RSA 加密体制的细节 78
2.4.1 模 n 指数运算的实用性 78
2.4.2 使用 RSA 算法会花费多长时间 79
2.4.3 因式分解有多难 80
2.4.4 找大素数 80
重要概念、公式和定理 83
习题 83
第3章 关于逻辑与证明的思考 85
3.1 等价和蕴含 85
3.1.1 语句的等价 85
3.1.2 真值表 87
3.1.3 德摩根律 89
3.1.4 蕴含 90
3.1.5 当且仅当 91
重要概念、公式和定理 93
习题 94
3.2 变元和量词 95
3.2.1 变元和论域 95
3.2.2 量词 96
3.2.3 量词化的标准记号 98
3.2.4 关于变元的语句 99
3.2.5 重写语句以包含更大的论域 99
3.2.6 证明量词语句的真假 100
3.2.7 量词语句的否定 101
3.2.8 隐式量词化 102
3.2.9 量词语句的证明 103
重要概念、公式和定理 104
习题 105
3.3 推理 106
3.3.1 直接推理（演绎推理）和证明 106
3.3.2 直接证明的推理规则 108
3.3.3 推理的逆否（对换）规则 109
3.3.4 反证法 110
重要概念、公式和定理 112
习题 113
第4章 归纳、递归和递推式 115
4.1 数学归纳法 115
4.1.1 最小反例 115
4.1.2 数学归纳法原理 118
4.1.3 强归纳法 120
4.1.4 归纳法的一般形式 121
4.1.5 从递归视角看归纳法 123
4.1.6 结构归纳法 126
重要概念、公式和定理 128
习题 128
4.2 递归、递推式和归纳法 130
4.2.1 递归 130
4.2.2 一阶线性递推式举例 132
4.2.3 迭代递推式 133
4.2.4 等比级数 134
4.2.5 一阶线性递推式 137
重要概念、公式和定理 140
习题 141
4.3 递推式解的增长率 142
4.3.1 分治算法 142
4.3.2 递归树 144
4.3.3 三种不同的行为 149
重要概念、公式和定理 151
习题 152
4.4 主定理 153
4.4.1 主定理基础 153
4.4.2 求解更一般的递推式 156
4.4.3 扩展主定理 156
重要概念、公式和定理 158
习题 158
4.5 更一般的递推式 159
4.5.1 递推不等式 159
4.5.2 不等式主定理 160
4.5.3 归纳法的一个窍门 161
4.5.4 更多归纳证明的窍门 163
4.5.5 处理 nc 以外的函数 165
重要概念、公式和定理 166
习题 167
4.6 递推式和选择 168
4.6.1 选择的理念 168
4.6.2 一种递归选择算法 169
4.6.3 中位数未知情况下的选择 170
4.6.4 一种查找中间一半中元素的算法 171
4.6.5 对修改后的选择算法的分析 174
4.6.6 不均匀划分 175
重要概念、公式和定理 177
习题 178
第5章 概率 179
5.1 概率导论 179
5.1.1 为什么学习概率 179
5.1.2 概率计算举例 181
5.1.3 互补概率 182
5.1.4 概率与散列法 182
5.1.5 均匀概率分布 184
重要概念、公式和定理 186
习题 187
5.2 并集和交集 188
5.2.1 并集事件的概率 188
5.2.2 概率的容斥原理 190
5.2.3 计数的容斥原理 195
重要概念、公式和定理 196
习题 197
5.3 条件概率和独立性 198
5.3.1 条件概率 198
5.3.2 贝叶斯定理 201
5.3.3 独立性 201
5.3.4 独立试验过程 203
5.3.5 树形图 204
5.3.6 素数测试 207
重要概念、公式和定理 208
习题 209
5.4 随机变量 210
5.4.1 什么是随机变量 210
5.4.2 二项式概率 211
5.4.3 体验生成函数 212
5.4.4 期望值 213
5.4.5 期望值的求和与数值乘法 216
5.4.6 指示器随机变量 218
5.4.7 第一次成功的尝试次数 219
重要概念、公式和定理 220
习题 222
5.5 散列中的概率计算 223
5.5.1 每个位置上元素的期望个数 224
5.5.2 空位置的期望个数 224
5.5.3 冲突的期望个数 225
5.5.4 元素在散列表的一个位置上的最大期望个数 227
重要概念、公式和定理 231
习题 231
5.6 条件期望、递推和算法 234
5.6.1 当运行时间不仅依赖输入的大小时 234
5.6.2 条件期望值 236
5.6.3 随机算法 237
5.6.4 重温选择算法 239
5.6.5 快速排序 240
5.6.6 随机选择的更详细分析 243
重要概念、公式和定理 244
习题 245
5.7 概率分布和方差 247
5.7.1 随机变量的分布 247
5.7.2 方差 250
重要概念、公式和定理 255
习题 256
第6章 图论 259
6.1 图 259
6.1.1 顶点的度 261
6.1.2 连通性 263
6.1.3 环 264
6.1.4 树 265
6.1.5 树的其他性质 265
重要概念、公式和定理 267
习题 269
6.2 生成树和根树 270
6.2.1 生成树 270
6.2.2 广度优先搜索 272
6.2.3 根树 275
重要概念、公式和定理 278
习题 279
6.3 欧拉图和哈密顿图 281
6.3.1 欧拉环游和迹 281
6.3.2 寻找欧拉环游 284
6.3.3 哈密顿路径和回路 285
6.3.4 NP 完全问题 289
6.3.5 证明问题是 NP 完全的 291
重要概念、公式和定理 293
习题 294
6.4 匹配定理 296
6.4.1 匹配的概念 296
6.4.2 使得匹配更大 299
6.4.3 二部图的匹配 301
6.4.4 搜索二部图的增广路径 302
6.4.5 增广覆盖算法 304
6.4.6 高效算法 308
重要概念、公式和定理 309
习题 310
6.5 着色与平面性 311
6.5.1 着色的概念 311
6.5.2 区间图 313
6.5.3 平面性 315
6.5.4 平面画法的面 316
6.5.5 五色定理 319
重要概念、公式和定理 322
习题 322
附录 A 更一般的主定理推导 324
附录 B 习题答案和提示 332
参考文献 347
索引 349
