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

译 者 序 离散数学是伴随着计算机科学技术一起成长与发展起来的一个研究离散量所具有的结构和相互关系的数学学科，是现代数学的一个重要分支。离散数学的研究包含了来自很多不同学科领域的知识，能够将这些重要的思想组织并整理在一起，并对计算机科学的发展产生巨大的推动作用，确实是一件意义重大的事情。 与任何数学知识的学习一样，离散数学的学习可能也容易让人感到枯燥和冗长。但需要说明的是，这种看似枯燥和冗长的过程恰恰是从事数学研究的多数学者追求极致完美的表现。实际上，也恰恰是这种追求完美的精神，才使得任何数学的分支都成为建立在牢不可破基础上的科学，被全世界的人不断检验并重复研究。 本书作者在对基本数学原理进行介绍的基础上，逐渐展开了离散数学研究的主体部分。其内容组织由浅入深，充分考虑了初学者学习的特点，是一本非常适于初学者使用的入门书籍。本书的读者并不需要过多地掌握微积分等数学方法，也不需要了解过多的计算机科学的相关知识，这丝毫不会影响读者对离散数学相关知识学习的深度和广度。 本书在翻译过程中得到了很多同事的帮助与支持，译者在此对他们表示诚挚的谢意。其中，中国工业与应用数学学会的邢红英女士对所有译文进行了认真的审阅，并给出了很多很有建设性的建议；电子工业出版社高等教育分社的冯小贝女士为本书的顺利出版做出了卓越的贡献。她们的辛勤工作是本书顺利出版的重要保障。 前 言 这本新版离散数学教材是基于作者多年来的教学经验并根据读者意见修改而成的，可作为一个或两个学期离散数学课程的教材。本书尽可能地减少了对预先掌握数学方法的要求，不需要具备微积分知识，也不需要预先掌握计算机科学的相关知识。本书包括例题、练习、图表、问题求解和相关提示，以及章节复习、注释、自测题和上机练习等，用以帮助读者掌握离散数学的基本知识。此外，与本书配套的资料还包括教师手册和其他资源。 在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 练习 本章注释 本章复习 本章自测题 上机练习 此外，多数章节都有“问题求解”部分（参考后文“本书亮点”部分给出的更为详细的说明）。 各节的“练习”部分帮助学生复习本章的重要概念、定义、定理和求解技巧等，书末附有部分练习的答案。尽管“练习”部分是为读者复习准备的，但也可作为课后作业或考试题目。 “本章注释”部分给出了进一步学习的建议。“本章复习”部分给出每章的基本概念。在“本章自测题”部分对应每节给出一些练习，相关的答案在书末提供。 “上机练习”部分包括课题、一些算法的实现及其他与程序设计有关的活动。本书不要求读者具备程序设计的能力，也没有给出程序设计内容的介绍，因而这些练习只是为那些具有程序设计基础并愿意利用计算机来分析离散数学概念的读者准备的。 本书亮点 练习 书中包括近4500个练习，其中约150个是上机练习。超过一般难度的练习用“*”标出。部分练习（约占总数的三分之一）在书末给出了提示或答案。其他练习的答案可以在教师手册中找到。有少数练习明确标出需要微积分知识，但书中的主要章节不涉及微积分的概念。因此，除了那些有标识的练习，其他练习是不需要用到微积分知识的。 例题 本书包括约650个例题。这些例题向学生展示如何使用离散数学解决问题、介绍理论的应用、阐述证明过程，从而使相关内容的讲解更加生动。 问题求解 “问题求解”部分旨在帮助学生对一些问题进行研究和探索，展示如何给出一个问题的证明。这部分的结构不同于本书的正文，是对一个问题进行讨论之后出现的独立一节，其目的是展示另一种求解问题的方法、讨论如何寻找问题的答案、说明问题求解和证明的技巧，而不是简单地给出一个问题的证明和答案。 “问题求解”部分由问题陈述开始，接着是讨论解决问题的方法。在得出求解方法以后，进一步说明该如何正确地书写形式化的求解过程。最后，再对使用的求解技巧进行总结。此外，有的“问题求解”部分还包括注释，并讨论与数学和计算机科学的其他内容的联系，有的给出问题的背景知识和进一步阅读的参考文献，有的则以练习作为结束。 补充资料 教师手册 作者编写的教师手册包含了本书中多数练习的解答。购买本书的教师可以从Pearson教师资源中心（www.pearsonhighered.com/irc）下载相关文件 。 致谢 向为本次改版提供了大量有益建议的审稿人致以特别的感谢： Venkata Dinavahi，芬德利大学 Matthew Elsey，纽约大学 Christophe Giraud-Carrier，杨百翰大学 Yevgeniy Kovchegov，俄勒冈州立大学 Filix Maisch，俄勒冈州立大学 Tyler McMillen，加州州立大学Fullerton 分校 Christopher Storm，艾德菲大学 Donald Vestal，南达科他州立大学 Guanghua Zhao，费耶特维尔州立大学 同时也非常感谢本书的所有读者，他们提供了非常有用的信件和电子邮件。 感谢本书的编审Patricia Johnsonbaugh，她仔细阅读了本书的草稿、改进了行文结构，找出了许多错误并且协助作者完成了很多工作。 本书的出版得到了Pearson团队的持续支持。特别感谢Pearson负责本项目的Lauren Morse，负责设计和排版的SPi Global公司的Jullie Kidd，以及检查了书中相关证明的圣克劳德州立大学的Nick Fiala。 最后，感谢编辑Jeff Weidenaar在本书第八版的准备过程中给予的帮助。他对本书的所有细节都非常关注，给出了大量强化设计的建议，以及提出了很多具体的提高表达和理解能力的建议。 Richard Johnsonbaugh

目 录 第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