前　　言


这本新版离散数学教材是基于作者多年来的教学经验并根据读者意见修改而成的，可作为一个或两个学期离散数学课程的教材。本书尽可能地减少了对预先掌握数学方法的要求，不需要具备微积分知识，也不需要预先掌握计算机科学的相关知识。本书包括例题、练习、图表、问题求解和相关提示，以及章节复习、注释、自测题和上机练习等，用以帮助读者掌握离散数学的基本知识。此外，与本书配套的资料还包括教师手册和网站资源。
在20世纪80年代初，几乎没有离散数学入门课程的合适教材。但当时许多大学需要一门涉及组合数学、算法和图论等内容的课程，来拓宽学生的数学知识和处理抽象概念的能力。本书第一版（1984年）的出版满足了这种需求，并对离散数学课程的发展产生了深远影响。此后，离散数学课程得到了包括数学和计算机等专业许多学科的认可。美国数学学会（MAA）的一个专门小组曾提议离散数学应作为讲授一学年的课程。电气与电子工程师协会（IEEE）的教育委员会也建议在大学一年级开设离散数学课程。随后，美国计算机学会（ACM）和IEEE给出了离散数学课程的推荐性大纲。本书第八版和前面各版本一样，不仅包括了算法、组合数学、集合、函数、数学归纳法等被以上组织所认可的内容，同时还涉及证明的理解和构造技巧，学生通过学习可提高数学素养。
本版更新内容
本书第八版的修改来自于许多读者对本书先前版本的意见和要求。在第七版的基础上，本版做了如下修改：
第七版中的网站图标修改为短URL地址，以便于快速访问正确的网页，例如使用便携式设备。
每一章中的自测题不再与章节内容紧密相关，这使得自测题更像是真正的考试题（这些自测题的提示与章节内容仍然紧密相关）。
例题解答的开始及结束位置更加清晰。
前三章（集合与逻辑；证明；函数、序列与关系）的习题数量从第七版的大约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）作为质因数分解不成立代数系统的例子。
使用二项定理的一个应用来证明Fermat小定理（6.7节，习题40和41）。
给出了一种在给定图中寻找 Hamilton 回路的随机算法（算法8.3.10）。
原第13章中的最小距点对问题（第七版的13.1节）被整合进第7章（递推关系）。因为该算法是基于归并排序的，而归并排序在第7章中进行讨论和分析。第八版删去了第七版第13章的剩余内容。
参考文献中补充了一些最近出版的书籍和论文，原有书籍的一些信息在本版中也进行了更新。
习题的数量增加到近4500个（第七版中大约有4200个）。
内容和结构
内容概述
第1章　集合与逻辑
内容涵盖量化并分析Google搜索引擎的实例（例1.2.13）。利用程序逻辑讨论了英语与符号表达式之间的相互转换。例1.6.15讨论了逻辑游戏，该游戏给出了一种确定量化命题函数的值是否为真的方法。
第2章　证明
讨论了证明方法（第2章），包括直证法、反例、反证法、逆否证明法、分情况证明法、（构造和非构造）存在性证明和数学归纳法。使用循环不变式作为数学归纳法的应用例子之一。其中包括了一节简短可选读的对消解原理（一种可自动化的证明方法）的讨论。
第3章　函数、序列与关系
本章包括串、和与积的记法以及启发性的例子，例如本章开篇介绍的计算信用卡校验位的 Luhn算法。其他例子包括，hash函数的介绍（例3.1.15）、伪随机数生成器（例3.1.16）、函数复合在应用于价格比较时的实例（例3.1.45）、偏序集在任务调度中的应用（3.3节）和关系数据库（3.6节）。
第4章　算法
本章详细讨论了算法、递归算法及算法分析的技术。在说明“大O”和相关记号之前，给出了若干例子（4.1节和4.2节），对引入这些记法的动机进行了说明。之后，本章详细讨论了描述函数增长的“大O”、Omega和Theta记号（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节）以及鸽巢原理。应用问题包括互联网编址（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）。
特别强调证明细节的理解和证明的构造。多数定理的证明带有插图注释并（或）有专门的讨论。有独立的小节（问题求解部分）向学生讲解如何进行问题求解及定理证明。一些章节后的问题求解要点则对本章节涉及的主要技术和方法进行总结。
大量的应用问题，特别是计算机领域中的应用问题。
图和表。利用图表描述概念、表示算法的工作原理、对定理进行阐释，从而使内容讲解更加生动。有些定理的证明辅以图示，从而对证明进行进一步的解释。
教材结构
每一章都按照下面的方式组织：
Chapter X Overview
Section X.1
Section X.1 Review Exercises
Section X.1 Exercises
Section X.2
Section X.2 Review Exercises
Section X.2 Exercises
?
Chapter X Notes
Chapter X Review
Chapter X Self-Test
Chapter X Computer Exercises
此外，多数章节都有“Problem-Solving Corners”部分（参考后文“本书亮点”部分给出的更为详细的说明。）
“Review Exercises”部分帮助学生复习本章节的重要概念、定义、定理和求解技巧等，书后附有部分章节练习的答案。尽管章节练习是为复习章节准备的，但也可作为课后作业或考试题目。
“Notes”部分给出了进一步学习的建议。“Review”部分给出每章的基本概念。在“Self-Tests”部分中，对应每节给出4道练习，相关的答案在书后给出。
“Computer Exercises”部分包括项目、一些算法的实现及其他与程序设计有关的活动。本书不要求读者具备程序设计的能力，也没有给出程序设计内容的介绍，因而这些练习只是为那些具有程序设计基础并愿意利用计算机来分析离散数学概念的读者准备的。
本书亮点
习题
书中包括4500多个习题，其中150个是上机练习。超过一般难度的习题用“*”标出。部分习题（约占三分之一）在书后有提示或答案。其他习题的答案可以在教师手册中找到。有少数习题明确标出需要微积分知识，但书中的主要章节不涉及微积分的概念。因此除了那些有标识的习题之外，其他习题是不需要用到微积分知识的。
例题
本书包括650多个例题。这些例题向学生展示如何使用离散数学解决问题、介绍理论的应用、阐述证明过程，从而使相关内容的讲解更加生动。
问题求解
问题求解部分（即“Problem-Solving Corners”部分）旨在帮助学生对一些问题进行研究和探索，展示如何给出一个问题的证明。这部分的结构不同于本书的正文，是对一个问题进行讨论之后出现的独立一节，其目的是展示另一种求解问题的方法、讨论如何寻找问题的答案、说明问题求解和证明的技巧，而不是简单地给出一个问题的证明和答案。
问题求解部分由问题陈述开始，接着是讨论解决问题的方法。在得出求解方法以后，进一步说明该如何正确地书写形式化的求解过程。最后，再对使用的求解技巧进行总结。此外，有的问题求解部分还包括注释，并讨论其与数学和计算机科学的其他内容的联系，有的给出问题的背景和进一步阅读的参考文献目录，有的则以练习作为结束。
补充资料和技术支持
教师手册
ISBN-10: 0-321-98309-2　ISBN-13: 978-0-321-98309-1
作者编写的教师手册包含了本书中的多数练习的解答。购买本书的教师可以从 Pearson 教师资源中心（www.pearsonhighered.com/irc）下载相关文件①。
网站支持
学生可以通过点击正文中给出的短URL链接获得
对于较难掌握材料的补充讲解，以及与离散数学相关的其他网站。
计算机程序（用C或C++编写）。
URL地址goo.gl/f03Crh 给出了上述全部资源以及一个额外列表的地址。
致谢
向为本次改版提供了大量有益建议的审稿人致以特别的感谢：
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