离散数学（第八版）

译  者  序
离散数学是伴随着计算机科学技术一起成长与发展起来的一个研究离散量所具有的结构和相互关系的数学学科，是现代数学的一个重要分支。离散数学的研究包含了来自很多不同学科领域的知识，能够将这些重要的思想组织并整理在一起，并对计算机科学的发展产生巨大的推动作用，确实是一件意义重大的事情。
与任何数学知识的学习一样，离散数学的学习可能也容易让人感到枯燥和冗长。但需要说明的是，这种看似枯燥和冗长的过程恰恰是从事数学研究的多数学者追求极致完美的表现。实际上，也恰恰是这种追求完美的精神，才使得任何数学的分支都成为建立在牢不可破基础上的科学，被全世界的人不断检验并重复研究。
本书作者在对基本数学原理进行介绍的基础上，逐渐展开了离散数学研究的主体部分。其内容组织由浅入深，充分考虑了初学者学习的特点，是一本非常适于初学者使用的入门书籍。本书的读者并不需要过多地掌握微积分等数学方法，也不需要了解过多的计算机科学的相关知识，这丝毫不会影响读者对离散数学相关知识学习的深度和广度。
本书在翻译过程中得到了很多同事的帮助与支持，译者在此对他们表示诚挚的谢意。其中，中国工业与应用数学学会的邢红英女士对所有译文进行了认真的审阅，并给出了很多很有建设性的建议；电子工业出版社高等教育分社的冯小贝女士为本书的顺利出版做出了卓越的贡献。她们的辛勤工作是本书顺利出版的重要保障。
前    言 
这本新版离散数学教材是基于作者多年来的教学经验并根据读者意见修改而成的，可作为一个或两个学期离散数学课程的教材。本书尽可能地减少了对预先掌握数学方法的要求，不需要具备微积分知识，也不需要预先掌握计算机科学的相关知识。本书包括例题、练习、图表、问题求解和相关提示，以及章节复习、注释、自测题和上机练习等，用以帮助读者掌握离散数学的基本知识。此外，与本书配套的资料还包括教师手册和其他资源。
在20世纪80年代初，几乎没有离散数学入门课程的合适教材。但当时许多大学需要一门涉及组合数学、算法和图论等内容的课程，以拓宽学生的数学知识和处理抽象概念的能力。本书版（1984年）的出版满足了这种需求，并对离散数学课程的发展产生了深远影响。此后，离散数学课程得到了包括数学和计算机等专业许多学科的认可。美国数学学会（MAA）的一个专门小组曾提议离散数学应作为讲授一学年的课程。电子与电气工程师协会（IEEE）的教育委员会也建议在大学一年级开设离散数学课程。随后，美国计算机学会（ACM）和IEEE给出了离散数学课程的推荐性大纲。本书第八版和前面各版本一样，不仅包括了算法、组合数学、集合、函数、数学归纳法等被以上组织所认可的内容，同时还涉及证明的理解和构造技巧，学生通过学习可提高数学素养。
第八版更新内容
本书第八版的修改来自许多读者对本书先前版本的意见和要求。在第七版的基础上，本版做了如下修改：

?  每一章中的自测题不再与章节内容紧密相关，这使得自测题更像是真正的考试题目（这些自测题的提示与章节内容仍然紧密相关）。
?  前三章（集合与逻辑；证明；函数、序列与关系）从第七版的大约1640个例题和练习，增加到第八版的1750个以上。
?  对于一些可能会引起歧义的概念，增加了更多的说明（例如，“子集”与“……的元素”，集族，序列命题的逻辑等价，图形的对数标尺）。
?  对于证明某些特定的结论，给出了更多的其他构造证明的方法示例［例如，例2.2.4和例2.2.8；例6.1.3(c)和例6.1.12；例6.7.7，例6.7.8，例6.7.9；例6.8.1和例6.8.2］。
?  修订了一些定义，以便直接应用于证明中［例如，一对一的函数（定义3.1.22）及映上函数（定义3.1.29）］。
?  增加了一些真实的例子。
?  修改了序列的定义（定义3.2.1），使其更加一般化，对子序列的讨论更为自然。
?  增加了一些练习（5.1节，练习40～49），作为素数因子分解不成立代数系统的例子。
?  使用二项式定理的一个应用来证明费马小定理（6.7节，练习40和练习41）。
?  给出了一种在给定图中寻找随机Hamilton回路的算法（算法8.3.10）。
?  原第13章中的小距点对问题（第七版的13.1节）被整合进第7章（递推关系）。因为该算法是基于归并排序的，而归并排序在第7章中进行讨论和分析。第八版删去了第七版第13章的剩余内容。
?  参考文献中补充了一些近出版的书籍和论文，原有书籍的一些信息在第八版中也进行了更新。
?  练习的数量增加到近4500个（第七版中大约有4200个）。

内容和结构
内容概述
第1章　集合与逻辑
本章给出了量化并分析Web搜索引擎的实例（例1.2.13）。利用程序逻辑讨论了英语与符号表达式之间的相互转换。例1.6.15讨论了逻辑游戏，该游戏给出了一种确定量化命题函数的值是否为真的方法。
第2章　证明
本章讨论了证明方法，包括直接证明、反例、反证法、逆否证明法、分情况证明法、（构造和非构造）存在性证明和数学归纳法，使用循环不变式作为数学归纳法的应用例子之一。其中包括了一节可选读的对消解原理（一种可自动化的证明方法）的讨论。
第3章　函数、序列与关系
本章内容包括字符串、和与乘积的记法以及具有启发性的例子，例如本章开篇介绍的计算信用卡校验位的 Luhn算法。其他例子包括Hash函数（例3.1.15）、伪随机数（例3.1.16）、函数复合在应用于价格比较时的实例（例3.1.45）、偏序集在任务调度中的应用（3.3节）和关系数据库（3.6节）。
第4章　算法
本章讨论了算法、递归算法以及算法分析的技术。在讲解“大O”和相关记号之前，给出了若干例子（4.1节和4.2节），对引入这些记法的原因进行了说明。之后，本章详细讨论了描述函数增长的“大O”、Ω和Θ符号（4.3节）。使用这些记法可以准确地描述函数的增长以及算法的时间和空间复杂度问题。
算法的使用将贯穿全书。本书将提到许多现代算法，可能不具备传统算法的多种特征（如许多现代算法不是通用的、确定的，甚至不是有限的）。为了说明这一点，本章给出了一个随机算法作为例子（例 4.2.4）。这些算法都是使用形式灵活的伪代码给出的，伪代码类似于当今的流行语言，例如C、C  以及Java等（本书不要求读者预先具有计算机科学的相关知识，所使用的伪代码的描述在附录C中给出）。本章介绍的算法包括：

?  覆盖算法（4.4节）
?  寻找公约数的欧几里得算法（5.3节）
?  RSA公钥算法（5.4节）
?  排列组合生成算法（6.4节）
?  归并排序算法（7.3节）
?  寻找小距点对算法（7.4节）
?  Dijkstra短路径算法（8.4节）
?  回溯算法（9.3节）
?  深度优先和广度优先算法（9.3节）
?  树的遍历算法（9.6节）
?  博弈树求值算法（9.9节）
?  网络流算法（10.2节）

第5章　数论
本章内容包括一些传统的结论（如整除性、素数的个数是无限的、基本的算术定理）和数论算法［如寻找公约数的欧几里得算法，基于重复平方法计算数的指数算法，计算满足gcd(a, b) = sa   tb的整数s和t的算法，计算整数模的逆的算法等］。本章介绍的方法可应用于RSA公钥算法（5.4节）中涉及的计算。RSA公钥算法的计算量需求使用本章前面给出的算法进行了演示。
第6章　计数方法与鸽巢原理
本章内容包括排列、组合、离散概率（可选读的6.5节和6.6节）以及鸽巢原理。其中的应用实例包括Internet地址（6.1节）、实际的电话拨打中的模式识别问题（例6.6.21）以及利用贝叶斯定理进行的病毒检测（例6.6.22）。
第7章　递推关系
本章内容包括递推关系及其在算法分析中的应用。
第8章　图论
本章内容包括并行计算机体系结构的图形模式、骑士遍历问题、旅行商问题、Hamilton回路、图的同构、平面图等。定理8.4.3给出了Dijkstra算法正确性的证明。
第9章　树
本章内容包括二叉树、树的遍历、小生成树、决策树、排序的时间下界以及树的同构。
第10章　网络模型
本章内容包括网络流算法和匹配问题。
第11章　Boole代数与组合电路
本章重点强调了Boole代数与组合电路之间的关系。
第12章　自动机、文法和语言
本章重点强调模型和应用。SR触发器将在例12.1.11中进行介绍。例12.3.19以von Koch雪花为例，给出了分形的语法描述。
本书其他部分
附录中涵盖了矩阵、基本的代数知识以及伪代码的介绍。本书的参考文献超过160篇，提供了额外的信息资源。本书书末汇总了书中用到的数学和算法符号。
内容特色
?  特别强调不同主题之间的相互关联。例如：
?  数学归纳法与递归算法被紧密结合在一起（4.4节）。
?  使用了Fibonacci序列来分析欧几里得算法（5.3节）。
?  本书中的很多习题都需要使用数学归纳法进行证明。
?  给出了如何通过在图中的顶点集上引入一组等价关系来描述图的分支的方法（参见例8.2.13中的讨论）。
?  计算了n顶点非同构二叉树的个数（定理9.8.12）。
?  特别强调证明细节的理解和证明的构造。多数定理的证明带有插图注释并（或）有专门的讨论。有独立的小节（“问题求解”部分）向学生讲解如何进行问题求解与定理证明。一些章节后的问题求解要点则对本章节涉及的主要技术和方法进行总结。
?  大量的应用问题，特别是计算机领域中的应用问题。
?  图和表。利用图和表描述概念、表示算法的工作原理、对定理进行阐释，从而使内容讲解更加生动。有些定理的证明辅以图示，从而对证明进行进一步的解释。
教材结构
每一章都按照下面的方式组织：

第X章  
本章概览
X.1 
X.1  复习
X.1  练习 
X.2  
X.2  复习
X.2  练习
     
本章注释
本章复习
本章自测题

本书从算法分析和问题求解的角度，全面系统地介绍了离散数学的基础概念及相关知识，并在前一版的基础上进行了修改与扩展。书中通过大量实例，深入浅出地讲解了集合与逻辑，证明，函数、序列与关系，算法，数论，计数方法与鸽巢原理，递推关系，图论，树，网络模型，Boole代数与组合电路，自动机、文法和语言等与计算机科学密切相关的前沿课题，既着重于各部分内容之间的紧密联系，又深入探讨了相关的概念、理论、算法和实际应用。本书内容叙述严谨、推演详尽，各章配有相当数量的练习与书末的提示和答案，为读者迅速掌握相关知识提供了有效的帮助。

Richard Johnsonbaugh是美国芝加哥DePaul大学的计算机科学、通信与信息系统的Emeritus教授，并在DePaul大学的从事了20多年的教学工作，之前曾任莫尔豪斯学院和芝加哥州立大学的数学系教师和系主任一职。Johnsonbaugh教授在耶鲁大学获得数学学士学位、硕士学位，并获得俄勒冈大学的数学博士学位以及伊利诺伊大学的计算机硕士学位。Johnsonbaugh教授近期的研究领域包括模式识别、程序设计语言、算法和离散数学，他也是这些领域众多书籍和文章的作者或合著者。Johnsonbaugh教授的几本专著已被译成各种语言出版，他也是美国数学协会的成员。
张文博，北京邮电大学理学院副教授，现从事计算方法、通信系统的教学与研究工作。迄今为止，发表SCI论文40于篇，EI检索论文20余篇。

目 录 
第1章 集合与逻辑 1 
1.1 集合 1 
1.2 命题 13 
1.3 条件命题与逻辑等价 20 
1.4 论证和推理规则 29 
1.5 量词 35 
1.6 嵌套量词 46 
本章注释 56 
本章复习 56 
本章自测题 58 
上机练习 60 
第2章 证明 61 
2.1 数学系统、直接证明和反例 61 
2.2 更多的证明方法 70 
2.3 归结证明 83 
2.4 数学归纳法 86 
2.5 强数学归纳法和良序性 103 
本章注释 110 
本章复习 110 
本章自测题 111 
上机练习 111 
第3章 函数、序列与关系 112 
3.1 函数 112 
3.2 序列和串 131 
3.3 关系 143 
3.4 等价关系 154 
3.5 关系矩阵 163 
3.6 关系数据库 168 
本章注释 173 
本章复习 173 
本章自测题 175 
上机练习 176 
第4章 算法 178 
4.1 简介 178 
4.2 算法示例 182 
4.3 算法的分析 188 
4.4 递归算法 208 
本章注释 215 
本章复习 216 
本章自测题 217 
上机练习 218 
第5章 数论 219 
5.1 因子 219 
5.2 整数的表示和整数算法 228 
5.3 欧几里得算法 240 
5.4 RSA公钥密码系统 252 
本章注释 254 
本章复习 254 
本章自测题 255 
上机练习 255 
第6章 计数方法与鸽巢原理 256 
6.1 基本原理 256 
6.2 排列与组合 269 
6.3 广义的排列与组合 284 
6.4 排列组合生成算法 289 
6.5 离散概率简介 296 
6.6 离散概率论 300 
6.7 二项式系数和组合恒等式 311 
6.8 鸽巢原理 317 
本章注释 322 
本章复习 323 
本章自测题 324 
上机练习 325 
第7章 递推关系 326 
7.1 简介 326 
7.2 求解递推关系 338 
7.3 在算法分析中的应用 354 
7.4 小距点对问题 368 
本章注释 374 
本章复习 374 
本章自测题 375 
上机练习 376 

第8章 图论 378 
8.1 简介 378 
8.2 路径和回路 388 
8.3 Hamilton回路和旅行商问题 400 
8.4 短路径算法 410 
8.5 图的表示 414 
8.6 图的同构 419 
8.7 平面图 427 
8.8 顿时错乱问题 434 
本章注释 438 
本章复习 439 
本章自测题 440 
上机练习 442 
第9章 树 444 
9.1 简介 444 
9.2 树的术语和性质 451 
9.3 生成树 458 
9.4 小生成树 465 
9.5 二叉树 471 
9.6 树的遍历 478 
9.7 决策树和短时间排序 484 
9.8 树的同构 490 
9.9 博弈树 498 
本章注释 507 
本章复习 508 
本章自测题 509 
上机练习 512 
第10章 网络模型 514 
10.1 简介 514 
10.2 流算法 519 
10.3 流小割定理 527 
10.4 匹配 530 
本章注释 537 
本章复习 538 
本章自测题 539 
上机练习 540 
第11章 Boole代数与组合电路 541 
11.1 组合电路 541 
11.2 组合电路的性质 547 
11.3 Boole代数 553 
11.4 Boole函数与电路合成 560 
11.5 应用 565 
本章注释 573 
本章复习 574 
本章自测题 575 
上机练习 577 
第12章 自动机、文法和语言 578 
12.1 时序电路和有限状态机 578 
12.2 有限状态自动机 584 
12.3 语言和文法 589 
12.4 不确定有限状态自动机 599 
12.5 语言和自动机之间的关系 605 
本章注释 610 
本章复习 611 
本章自测题 611 
上机练习 613 
附录A 矩阵 614 
附录B 代数学复习 618 
附录C 伪代码 628 
部分练习答案 633 
参考文献 746

本书从算法分析和问题求解的角度，全面系统地介绍了离散数学的基础概念及相关知识，并在前一版的基础上进行了修改与扩展。书中通过大量实例，深入浅出地讲解了集合与逻辑，证明，函数、序列与关系，算法，数论，计数方法与鸽巢原理，递推关系，图论，树，网络模型，Boole代数与组合电路，自动机、文法和语言等与计算机科学密切相关的前沿课题，既着重于各部分内容之间的紧密联系，又深入探讨了相关的概念、理论、算法和实际应用。本书内容叙述严谨、推演详尽，各章配有相当数量的练习与书末的提示和答案，为读者迅速掌握相关知识提供了有效的帮助。

Richard Johnsonbaugh是美国芝加哥DePaul大学的计算机科学、通信与信息系统的Emeritus教授，并在DePaul大学的从事了20多年的教学工作，之前曾任莫尔豪斯学院和芝加哥州立大学的数学系教师和系主任一职。Johnsonbaugh教授在耶鲁大学获得数学学士学位、硕士学位，并获得俄勒冈大学的数学博士学位以及伊利诺伊大学的计算机硕士学位。Johnsonbaugh教授近期的研究领域包括模式识别、程序设计语言、算法和离散数学，他也是这些领域众多书籍和文章的作者或合著者。Johnsonbaugh教授的几本专著已被译成各种语言出版，他也是美国数学协会的成员。
张文博，北京邮电大学理学院副教授，现从事计算方法、通信系统的教学与研究工作。迄今为止，发表SCI论文40于篇，EI检索论文20余篇。