本书凝聚了作者多年的研究成果和实践经验，是一本优秀的离散数学入门教材。本书充分考虑到了初学者的需要，内容、例题和习题都进行了精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。
　　本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书。

本书特点：
　　● 注重算法，且算法描述独立于某种具体的编程语言。
　　● 各章内容独立性强，教师可根据学生的水平和课程的需要来灵活选择主题。
　　● 习题安排错落有致，灵活性强。每节后都有大量简单的计算题和算法题，每章末有一组补充习题和计算机题，并在书后给出了奇数号习题的答案。

无

如今，数学的应用越来越多地涉及离散而非连续的模型，其主要原因是现代社会越来越多地用到计算机。本书适用于一学期的离散数学入门课程。
　　预备知识
　　虽然按照本书讲授的课程只要求很少的数学预备知识，但还是要求学生至少达到修读过两年高中数学所应具有的水平，包括解题和运算的技能以及抽象思维的能力。
　　方法
　　本书强调算法并以此贯穿全书。算法用文字表述，不需要具体编程语言的知识。
　　主题的选择
　　本书主题的选择基于多个专业组织的建议，包括MAA（美国数学协会）一年级和二年级离散数学课程制定工作组的建议、NCTM（National Council of Teachers of Mathematics，美国数学教师理事会）的“学校数学教育的原则与标准”和CBMS（Conference Board of the Mathematical Sciences，美国数学科学联合会）对数学教学的建议等。
　　灵活性
　　虽然本书是针对一学期的课程设计的，但是本书所包含的材料多于一个学期所能覆盖的内容。因此，教师可以根据学生的特定需求和兴趣方便地选择主题。本书以前的版本在从计算机科学专业的一年级课程到数学专业的高年级课程等许多课程中用过，并得到了良好的反映。现在的这个版本仍然为教师提供了灵活性，以适于各种不同专业学生的课程。
　　第5版的变动
　　第5版的主要变动是新增了一章—第3章，讨论同余、欧几里得算法及相关的数论方面的内容、RSA公钥密码技术、检错码和纠错码（包括矩阵码）。本书其余内容与这一章不相关，所以可由教师根据需要进行取舍。学习矩阵码的内容要求熟悉矩阵，所以在学习编码理论这一章之前，不熟悉矩阵的学生需要先阅读附录B。（详见下面的“章节独立性”和“课程设置建议”。）
　　另外，新版本在表述的清晰性方面有所改进，对离散数学的新进展也给予了关注。
　　习题
　　本书的习题安排错落有致，灵活性强。每节后都有大量简单的计算题和算法题，其中大多数习题有助于学生针对离散数学的概念和算法进行全面练习，这对数学基础较弱的学生尤其重要；另一些习题拓展了正文中的材料，或者引入了正文中未论述过的新概念。带*号的习题是更具挑战性的问题。教师应根据课程和学生水平从中挑选。奇数号计算题的答案附在本书末尾。在每一章的末尾，有一组补充习题，用来温习各章最重要的概念和技术，以及探讨正文中未讨论的新概念。
　　章节独立性
　　在采用本书进行教学时，各章的顺序可以灵活地安排。下图显示了各章的依赖关系。其中，虚线表示第6章仅与第4章的前几节内容相关。本书只假定读者具有高中几何课程对于逻辑与证明的熟练程度，而对那些偏好更形式化处理的读者提供了一个附录（附录A），可以将它作为独立的单元在任何时候讲授，也可以与第9章一起讲授。仅在3.5～3.6节和第4章讨论邻接矩阵时，要求熟悉矩阵（附录B）。
　　第1章和第2章实质上是导论。第1章给出本书所处理的离散问题的样例，应很快讲授完。该章只是提出某些问题，而在本书的后面才给出解答。1.4节包含对复杂性的讨论，可以略过它，或者推迟到学生有更多算法经验时再讲授。在这一节中，教师可以只讲解与学生关系最密切的示例算法。
　　第2章复习各种基本主题，包括集合、关系、函数和数学归纳法。该章可以讲授得稍快些，这取决于学生的数学背景和课程的层次。对于数学背景较好的学生，第2章的很多内容应该可以让他们自学。如上图所示，除了第5章和第7章依赖于第4章，以及第6章与第4章前几节的内容相关外，其余各章均彼此独立。
　　为配合新的第3章，同余的内容从第2章中移出。与第4版一样，这个内容（见第5版的3.1节）可以在讲完2.2节（等价关系）以后的任何时候学习。
　　课程设置建议
　　下面的表格给出了三个课程设置范例。课程A的重点是图论及其应用，涵盖了第4～7章的大部分内容。课程B涉及图论较少，更强调计数技术。课程C的重点是计算机科学专业的学生所感兴趣的论题。
　　　课程A 课程B 课程C
　　章 课时数 章 课时数 章 课时数
　　1 4 1（跳过1.4节） 3 1 4
　　2 5 2 5 2 5
　　4 6 4 6 附录B 1
　　5 7 5 6 3 6
　　6 6 8 8 4 6
　　7 4 9 5 5 6
　　8 8 附录A 3 9 5
9 4 附录A 3
10 4
　　本书适用于各种层次的“离散数学”课程。比如，计算复杂性是一个很重要的主题，本书对许多算法的复杂性给予了关注。但是，这是一个较难的主题，其论述深度应当与课程的层次和学生的基础相吻合。
　　计算机题
　　各章结尾均给出一组计算机题，这些计算机题与该章的内容、算法等相关。本书刻意用普通的术语来叙述计算机题，以便适应使用各种计算系统和语言的学生。
致谢
　　我们衷心地感谢下列审阅本书的数学家：米勒斯维尔大学的Dorothee Blum、威斯康星大学麦迪逊分校的Richard Brualdi、佛罗里达州立大学的John L. Bryant、波特兰州立大学的 Richard Crittenden、乔治梅森大学的Klaus Fischer、东得克萨斯州立大学的Dennis Grantham、Clemson大学的William R. Hare、东密歇根大学的Christopher Hee、佛罗里达大西洋大学的Frederick Hoffman、佛罗里达国际大学的Julian L. Hook、Broome社区学院的Carmelita Keyes、 Macalester学院的Richard K. Molnar、普度大学Calumet分校的Catherine Murphy、佛罗里达大学的Charles Nelson、迈阿密大学的Fred Schuurmann、Charles S. Mott社区学院的Karen Sharp和新汉普郡大学的Donovan H. Van Osdol。为本书第2版的改进提出有益意见的有我们的同事Saad El-Zanati、Michael Plantholt和Shailesh Tipnis, 本书的使用者，以及伯米吉州立大学的Elaine Bohanon、常青藤州立学院的George Dimitroff、威斯康星-怀特沃特大学的Richard Enstad、西密歇根大学的Donald Goldsmith、肯塔基教育网络的Thomas R. Graviss、威斯康星-怀特沃特大学的Gary Klatt、Kings学院的Mark Michael、Shepherd学院的Peter Morris、密苏里大学的Dix H. Pettey、Puget Sound大学的Matt Pickard、田纳西大学的Terry Walters、南密西西比大学的Porter Webster、Frostburg州立大学的Richard Weimer、威斯康星-伊奥克莱尔大学的Thomas Weininger和佛门大学的Mark Woodard。本书第3版作了进一步改进，这得益于本书的使用者的意见，以及下列同行的评论意见：威斯康星-伊奥克莱尔大学的Veena Chadha、西密歇根大学的Gary Chartrand、东南路易斯安那大学的Tilak de Alwis、东华盛顿大学的Ron Dalla、 Evergreen 州立学院的George Dimitroff、佐治亚州立大学的Gayla S. Domke、得克萨斯大学阿灵顿分校的Jerome Eisenfeld、富劳斯特堡州立大学的Kathleen Elder、乔治梅森大学的Klaus Fischer、北维吉尼亚社区学院的Donald A. Goral、南佛罗里达大学的Natasa Jonoska、 乔治梅森大学的Thomas Kiley、圣玛丽学院的Theresa D. Magnus、田纳西大学的Chris Mawata、北卡罗来纳A&T州立大学的Robert C. Mers、普度大学Calumet分校的Catherine M. Murphy、宾夕法尼亚爱丁堡大学的Anne Quinn、莱特州立大学的Steen Pedersen、密苏里大学哥伦比亚分校的Dix H. Pettey、Bemidji州立大学的James L. Richards、Washburn大学的A. Allan Riveland、中密歇根大学的Mohan Shrikhande和西密歇根大学的Allan Schwenk，以及我们的同事Roger Eggleton。
　　我们要对伊利诺伊州立大学的Michael Plantholt和Dean Sanders表示特别的感谢，他们独立地审核了第3版中所有算法的正确性和可读性，根据他们的建议对算法进行了实质性的修正和改进。　
　　本书第4版的更改源于下列同行的评论意见：中西部州立大学的Mark Ferris、佐治亚州立大学的Johanne Hattingh、圣玛丽学院的Colleen Hoover、杜鲁门州立大学的Jason Miller和太平洋联合学院的Richard Rockwell。
　　本书第5版的更改源于下列审阅者：旧金山城市学院的Glen Aguiar、The Citadel的Stephen Comer、黑鹰学院的Lowell Doerder、黑斯廷斯学院的Mark Hall、太平洋联合学院的George Hilton、布卢姆菲尔德学院的Kenneth Myers、维吉尼亚工学院和州立大学的Charles Parry、大瀑布大学的Richard Schoyen、西密歇根大学的Allen Schwenk和伊利诺伊中心学院的Fereja Tahir。
　　此外，在本书的出版过程中，我们还要感谢Jami Darby、Emily Portwood和Bill Hoffman出色的编辑工作，以及资深作者支持和技术专家Joe Vetere的大力协助。

　　John A. Dossey
　　Albert D. Otto
　　Lawrence E. Spence
　　Charles Vanden Eynden

离散数学纪年表
译者序
译者简介
前言
致学生
离散数学纪年表
第1章　 组合问题与组合技术引论 1
1.1　 工程完成时间的问题 1
1.1.1　 问题 1
1.1.2　 分析 2
1.1.3　 关键路径分析 3
1.1.4　 一个建筑的例子 4
1.2　 匹配问题 7
1.2.1　 问题 7
1.2.2　 分析 7
1.2.3　 排列 8
1.2.4　 航空公司问题解决方案的实用性 9
1.3　 背包问题 11
1.3.1　 问题 11
1.3.2　 分析 12
1.3.3　 回顾实验问题 14
1.4　 算法及其效率 15
1.4.1　 算法的比较 15
1.4.2　 多项式求值 16
1.4.3　 子集生成算法 19
1.4.4　 冒泡排序 21
历史注记 24
补充习题 25
计算机题 27
推荐读物 27
第2章　 集合、关系和函数 28
2.1　 集合运算 28
2.2　 等价关系 32
*2.3　 偏序关系 37
2.3.1　 偏序和全序 37
2.3.2　 哈斯图 40
2.3.3　 拓扑排序 41
2.4　 函数 44
2.5　 数学归纳法 52
2.6　 应用 58
历史注记 65
补充习题 66
计算机题 69
推荐读物 69
第3章　 编码理论 70
3.1　 同余 70
3.2　 欧几里得算法 75
3.2.1　 最大公约数 75
3.2.2　 欧几里得算法 75
3.2.3　 欧几里得算法的效率 77
3.2.4　 扩展的欧几里得算法 77
3.3　 RSA方法 79
3.3.1　 指数取模 80
3.3.2　 RSA方法的解密 83
3.3.3　 RSA方法的可行性 85
3.4　 检错码和纠错码 86
3.5　 矩阵码 93
3.5.1　 矩阵码 93
3.5.2　 编码的校验矩阵 94
3.6　 单纠错矩阵码 99
3.6.1　 校验矩阵行译码法 100
3.6.2　 汉明码 101
历史注记 105
补充习题 106
计算机题 109
推荐读物 109
第4章　 图 110
4.1　 图及其表示 110
4.1.1　 图的概念和表示 110
4.1.2　 图的其他表示 112
4.1.3　 同构 113
4.2　 通路和回路 117
4.2.1　 多重图、通路和回路 117
4.2.2　 欧拉回路和欧拉通路 119
4.2.3　 哈密顿回路和哈密顿通路 122
4.3　 最短通路和距离 129
4.3.1　 广度优先搜索算法 129
4.3.2　 带权图 131
4.3.3　 通路的数目 134
4.4　 图着色 138
4.5　 有向图和有向多重图 144
4.5.1　 有向图 145
4.5.2　 有向图的表示 145
4.5.3　 有向多重图 146
4.5.4　 有向欧拉回路和有向欧拉通路 148
4.5.5　 有向哈密顿回路和有向哈密顿
通路 149
历史注记 155
补充习题 156
计算机题 160
推荐读物 161
第5章　 树 162
5.1　 树的性质 162
5.2　 生成树 168
5.2.1　 生成树 169
5.2.2　 广度优先搜索法 169
5.2.3　 最小生成树和最大生成树 171
5.2.4　 普里姆算法的证明 174
5.3　 深度优先搜索 179
5.3.1　 深度优先搜索法 179
5.3.2　 回溯 183
5.4　 根树 188
5.5　 二叉树和遍历 193
5.5.1　 表达式树 193
5.5.2　 前序遍历 195
5.5.3　 后序遍历 197
5.5.4　 中序遍历 199
5.6　 最优二叉树和二叉搜索树 202
5.6.1　 最优二叉树 202
5.6.2　 二叉搜索树 208
历史注记 215
补充习题 216
计算机题 219
推荐读物 220
第6章　 匹配 221
6.1　 相异代表系 221
6.1.1　 相异代表系 221
6.1.2　 霍尔定理 222
6.2　 图中的匹配 225
6.2.1　 匹配 225
6.2.2　 偶图的矩阵 227
6.2.3　 覆盖 227
6.3　 匹配算法 231
6.3.1　 独立集算法的应用示例 231
6.3.2　 将算法运用于最大独立集 233
6.3.3　 独立集算法 234
6.3.4　 课程分配 235
6.4　 算法的应用 239
6.4.1　 柯尼希定理 240
6.4.2　 霍尔定理的证明 241
6.4.3　 瓶颈问题 242
6.5　 匈牙利方法 245
6.5.1　 匈牙利算法 245
6.5.2　 匈牙利算法的证明 247
6.5.3　 不是方阵的矩阵 248
6.5.4　 最大和独立集 249
历史注记 250
补充习题 251
计算机题 252
推荐读物 253
第7章　 网络流 254
7.1　 流和割 254
7.2　 流增广算法 261
7.3　 最大流最小割定理 269
7.4　 流和匹配 274
历史注记 280
补充习题 280
计算机题 283
推荐读物 283
第8章　 计数技术 284
8.1　 帕斯卡三角形和二项式定理 284
8.2　 3个基本原理 287
8.3　 排列和组合 293
8.4　 允许重复的排列和组合 297
8.5　 概率 302
*8.6　 容斥原理 306
*8.7　 排列和r组合的生成 315
8.7.1　 排列的词典序枚举 315
8.7.2　 r组合的词典序枚举 317
历史注记 320
补充习题 321
计算机题 323
推荐读物 324
第9章　 递推关系与生成函数 325
9.1　 递推关系 325
9.2　 迭代法 333
9.3　 常系数线性差分方程 341
9.3.1　 一阶常系数线性差分方程 341
9.3.2　 二阶线性齐次差分方程 344
*9.4　 用递推关系分析算法的效率 350
9.4.1　 顺序查找算法和冒泡排序算法
的效率… 350
9.4.2　 分治算法的效率 352
9.4.3　 排序算法的效率 357
9.5　 用生成函数计数 359
9.5.1　 生成函数 360
9.5.2　 形式幂级数 361
9.6　 生成函数的代数 365
历史注记 372
补充习题 373
计算机题 375
推荐读物 376
第10章　 组合电路和有限状态机 377
10.1　 逻辑门 377
10.2　 构造组合电路 383
10.3　 卡诺图 388
10.4　 有限状态机 397
10.4.1　 奇偶校验机 398
10.4.2　 有限状态机 399
10.4.3　 带输出的有限状态机 400
历史注记 404
补充习题 405
计算机题 407
推荐读物 408
附录A　 逻辑和证明简介 409
附录B　 矩阵 425
附录C　 本书中的算法 432
参考文献 436
奇数号习题答案 440

计算机在其诞生至今短短的几十年间，得到了令人瞩目的飞速发展，它在很多方面都深刻地改变了人类的活动方式和思维习惯。然而，现代数字计算机的理论模型依然是20世纪30年代提出的图灵机，这是一种“离散”的机器，可用来处理“离散”的对象。当然，正如大多数计算机的早期应用那样，通过近似计算等手段，计算机也可以处理“连续”的对象，但本质上，现代的数字计算机仍然是一种“离散”的机器。事实上，目前计算机已经越来越多地用于处理各种“离散”的对象。
离散数学研究离散对象的数量和空间关系，它包括多个数学分支，如本书所涉及的集合论、图论、组合数学、经典概率、自动机理论等，是计算机科学的理论基础，也是计算机应用的有力工具。18世纪以前的数学基本上都属于离散数学的范畴，之后，天文学、物理学等的发展极大地推动了连续数学（如微积分）的发展，直到20世纪中期，尤其是20世纪80年代以后，随着计算机日益渗透到现代社会的几乎各个方面，离散数学再次得到高度重视。当然，离散数学涉及的内容极其广泛，其应用全然不是仅局限于计算机科学，而是涉及我们生活的方方面面。
　　离散数学是计算机专业重要的必修课程之一，它是许多计算机专业课程的基础，国内外已经出版了大量的离散数学教科书和参考书，那么为什么还要引进出版这本书呢？
　　对大多数计算机专业的学生而言，囿于有限的数学素养，要学好这门课程不太容易。他们的困难主要表现在两个方面：一是看不懂或不理解某些内容；二是尽管看懂了有关的内容，但是不会应用，面对习题无从着手。另一个常常困惑学生的问题是：离散数学是否真的如教师所说的那样在计算机科学中起着关键的作用？本书针对这些问题作了很好的处理。它不仅是一本很好的离散数学教材或参考书，还可以启发我们的思路，以便编写出更适合我国国情的教材。这就是我们要翻译此书、把它引荐给读者的原因。
　　本书充分考虑到计算机专业的学生和初学者的数学素养，对内容、例题、习题都作了精心的挑选和组织，叙述方式力求深入浅出。对离散数学中出现的大量定义、定理和证明，不是简单地罗列，而是采用浅显易懂的语言娓娓道来，循序渐进地展开，并辅以足够的由易到难的例子，而且这些例子往往十分贴近日常生活或计算机应用。本书所提供的大量习题也是为了使读者在完成习题的过程中不知不觉地巩固和深化所学的知识和技能。本书的另一个特点是强调算法，这使读者很容易就把离散数学和计算机科学联系起来。
　　本书的第一作者John A. Dossey教授长期从事各个层次的数学教学研究和实践，著有大量数学教科书和科研论文，多次获得美国各种数学教学奖项，具有极其丰富的数学教学的理论和实践经验。本书凝聚了作者多年的研究成果和实践经验，是一本成功的离散数学入门教材，为美国众多大学所采用。事实上，它也是一本很好的自学教材。相信本书也一定会给国内的读者以莫大的帮助。
　　章炯民、王新伟和曹立曾经共同协作完成了本书第4版的翻译，在此基础上，第5版的翻译工作主要由章炯民完成。此外，万英杰、张钰、左文英等也参与了第5版的部分翻译工作。译者本着尊重原著的原则，力求准确、严谨地翻译，同时也更正了原著中的少量错误。由于译者水平所限，难免有错误和欠妥之处，敬请读者批评指正。

　　译　 者　
　　2006年11月于华东师范大学