《离散数学及其应用（原书第7版）》是介绍离散数学理论和方法的经典教材，已经成为采用率最高的离散数学教材，被美国众多名校用做教材，获得了极大的成功。本书中文版也已被国内大学广泛采用为教材。作者罗森参考教师和学生的反馈，并结合自身对教育的洞察，在第7版中做了大量的改进，使其成为更有效的教学工具。本书可作为1～2个学期的离散数学课程教材，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。

KenhH.Rosen，作为位于新泽西州蒙茅斯县的AT＆T实验室杰出技术会员已经拥有一段很长的职业生涯。目前他在蒙茅斯大学任访问研究教授，为研究生讲授计算机科学课程。

Rosen博士于1972年获得位于安娜堡的密歇根大学数学学士学位，1976年获得麻省理工学院数学博士学位，在哈罗德·斯塔克（HaroldStark）的指导下他撰写了数论方面的博士论文。1982年加入贝尔实验室之前，他曾就职于科罗拉多大学博尔德分校；哥伦布市的俄亥俄州立大学；在欧洛诺市的缅因大学任数学副教授。在AT&T工作时，他在蒙茅斯大学任教，教授离散数学、编码理论和数据安全方面的课程。他目前教授算法设计以及计算机安全和密码学方面的课程。

  罗森编著的《离散数学及其应用（原书第7版）》是经典的离散数学教材，为全球多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法，内容涉及数学推理、组合分析、离散结构、算法思想以及应用与建模。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的实例和图表说明、各种练习和题目以及丰富的历史资料和网站资料。第7版在前六版的基础上做了大量的改进，使其成为更有效的教学工具。

本书可作为高等院校数学、计算机科学和计算机工程等专业的教材或参考书。

出版者的话

译者序

前言

配套网站

致学生

关于作者

符号表

第1章　基础：逻辑和证明

　1.1　命题逻辑

　　1.1.1　引言

　　1.1.2　命题

　　1.1.3　条件语句

　　1.1.4　复合命题的真值表

　　1.1.5　逻辑运算符的优先级

　　1.1.6　逻辑运算和位运算

　　练习

　1.2　命题逻辑的应用

　　1.2.1　引言

　　1.2.2　语句翻译

　　1.2.3　系统规范说明

　　1.2.4　布尔搜索

　　1.2.5　逻辑谜题

　　1.2.6　逻辑电路

　　练习

　1.3　命题等价式

　　1.3.1　引言

　　1.3.2　逻辑等价式

　　1.3.3　德摩根律的运用

　　1.3.4　构造新的逻辑等价式

　　1.3.5　命题的可满足性

　　1.3.6　可满足性的应用

　　1.3.7　可满足性问题求解

　　练习

　1.4　谓词和量词

　　1.4.1　引言

　　1.4.2　谓词

　　1.4.3　量词

　　1.4.4　约束论域的量词

　　1.4.5　量词的优先级

　　1.4.6　变量绑定

　　1.4.7　涉及量词的逻辑等价式

　　1.4.8　量化表达式的否定

　　1.4.9　语句到逻辑表达式的翻译

　　1.4.10　系统规范说明中量词的使用

　　1.4.11　选自路易斯卡罗尔的例子

　　1.4.12　逻辑程序设计

　　练习

　1.5　嵌套量词

　　1.5.1　引言

　　1.5.2　理解涉及嵌套量词的语句

　　1.5.3　量词的顺序

　　1.5.4　数学语句到嵌套量词语句的翻译

　　1.5.5　嵌套量词到自然语言的翻译

　　1.5.6　汉语语句到逻辑表达式的翻译

　　1.5.7　嵌套量词的否定

　　练习

　1.6　推理规则

　　1.6.1　引言

　　1.6.2　命题逻辑的有效论证

　　1.6.3　命题逻辑的推理规则

　　1.6.4　使用推理规则建立论证

　　1.6.5　消解律

　　1.6.6　谬误

　　1.6.7　量化命题的推理规则

　　1.6.8　命题和量化命题推理规则的组合使用

　　练习

　1.7　证明导论

　　1.7.1　引言

　　1.7.2　一些专用术语

　　1.7.3　理解定理是如何陈述的

　　1.7.4　证明定理的方法

　　1.7.5　直接证明法

　　1.7.6　反证法

　　1.7.7　归谬证明法

　　1.7.8　证明中的错误

　　1.7.9　良好的开端

　　练习

　1.8　证明的方法和策略

　　1.8.1　引言

　　1.8.2　穷举证明法和分情形证明法

　　1.8.3　存在性证明

　　1.8.4　唯一性证明

　　1.8.5　证明策略

　　1.8.6　寻找反例

　　1.8.7　证明策略实践

　　1.8.8　拼接

　　1.8.9　开放问题的作用

　　1.8.10　其他证明方法

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第2章　基本结构：集合、函数、序列、求和与矩阵

　2.1　集合

　　2.1.1　引言

　　2.1.2　文氏图

　　2.1.3　子集

　　2.1.4　集合的大小

　　2.1.5　幂集

　　2.1.6　笛卡儿积

　　2.1.7　使用带量词的集合符号

　　2.1.8　真值集和量词

　　练习

　2.2　集合运算

　　2.2.1　引言

　　2.2.2　集合恒等式

　　2.2.3　扩展的并集和交集

　　2.2.4　集合的计算机表示

　　练习

　2.3　函数

　　2.3.1　引言

　　2.3.2　一对一函数和映上函数

　　2.3.3　反函数和函数组合

　　2.3.4　函数的图

　　2.3.5　一些重要的函数

　　2.3.6　部分函数

　　练习

　2.4　序列与求和

　　2.4.1　引言

　　2.4.2　序列

　　2.4.3　递推关系

　　2.4.4　特殊的整数序列

　　2.4.5　求和

　　练习

　2.5　集合的基数

　　2.5.1　引言

　　2.5.2　可数集

　　2.5.3　不可数集合

　　练习

　2.6　矩阵

　　2.6.1　引言

　　2.6.2　矩阵算术

　　2.6.3　矩阵的转置和幂

　　2.6.4　0-1矩阵

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第3章　算法

　3.1　算法

　　3.1.1　引言

　　3.1.2　搜索算法

　　3.1.3　排序

　　3.1.4　贪婪算法

　　3.1.5　停机问题

　　练习

　3.2　函数的增长

　　3.2.1　引言

　　3.2.2　大O记号

　　3.2.3　一些重要函数的大O估算

　　3.2.4　函数组合的增长

　　3.2.5　大与大记号

　　练习

　3.3　　算法的复杂度

　　3.3.1　引言

　　3.3.2　时间复杂度

　　3.3.3　矩阵乘法的复杂度

　　3.3.4　算法范型

　　3.3.5　理解算法的复杂度

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第4章　数论和密码学

　4.1　整除性和模算术

　　4.1.1　引言

　　4.1.2　除法

　　4.1.3　除法算法

　　4.1.4　模算术

　　4.1.5　模m算术

　　练习

　4.2　整数表示和算法

　　4.2.1　引言

　　4.2.2　整数表示

　　4.2.3　整数运算算法

　　4.2.4　模指数运算

　　练习

　4.3　素数和最大公约数

　　4.3.1　引言

　　4.3.2　素数

　　4.3.3　试除法

　　4.3.4　埃拉托斯特尼筛法

　　4.3.5　关于素数的猜想和开放问题

　　4.3.6　最大公约数和最小公倍数

　　4.3.7　欧几里得算法

　　4.3.8　gcd的线性组合表示

　　练习

　4.4　求解同余方程

　　4.4.1　引言

　　4.4.2　线性同余方程

　　4.4.3　中国剩余定理

　　4.4.4　大整数的计算机算术

　　4.4.5　费马小定理

　　4.4.6　伪素数

　　4.4.7　原根和离散对数

　　练习

　4.5　同余应用

　　4.5.1　散列函数

　　4.5.2　伪随机数

　　4.5.3　校验码

　　练习

　4.6　密码学

　　4.6.1　引言

　　4.6.2　古典密码学

　　4.6.3　公钥密码学

　　4.6.4　RSA密码系统

　　4.6.5　RSA加密

　　4.6.6　RSA解密

　　4.6.7　用RSA作为公钥系统

　　4.6.8　密码协议

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第5章　归纳与递归

　5.1　数学归纳法

　　5.1.1　引言

　　5.1.2　数学归纳法

　　5.1.3　为什么数学归纳法是有效的

　　5.1.4　数学归纳法的优点与缺点

　　5.1.5　利用数学归纳法证明的例子

　　5.1.6　使用数学归纳法时犯的错误

　　5.1.7　运用数学归纳法证明的原则

　　练习

　5.2　强归纳法与良序性

　　5.2.1　引言

　　5.2.2　强归纳法

　　5.2.3　利用强归纳法证明的例子

　　5.2.4　计算几何学中使用强归纳法

　　5.2.5　利用良序性证明

　　练习

　5.3　递归定义与结构归纳法

　　5.3.1　引言

　　5.3.2　递归地定义函数

　　5.3.3　递归地定义集合与结构

　　5.3.4　结构归纳法

　　5.3.5　广义归纳法

　　练习

　5.4　递归算法

　　5.4.1　引言

　　5.4.2　证明递归算法的正确性

　　5.4.3　递归与迭代

　　5.4.4　归并排序

　　练习

　5.5　程序正确性

　　5.5.1　引言

　　5.5.2　程序验证

　　5.5.3　推理规则

　　5.5.4　条件语句

　　5.5.5　循环不变量

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第6章　计数

　6.1　计数的基础

　　6.1.1　引言

　　6.1.2　基本的计数原则

　　6.1.3　比较复杂的计数问题

　　6.1.4　减法法则（两个集合的容斥原理）

　　6.1.5　除法法则

　　6.1.6　树图

　　练习

　6.2　鸽巢原理

　　6.2.1　引言

　　6.2.2　广义鸽巢原理

　　6.2.3　鸽巢原理的几个简单应用

　　练习

　6.3　排列与组合

　　6.3.1　引言

　　6.3.2　排列

　　6.3.3　组合

　　练习

　6.4　二项式系数和恒等式

　　6.4.1　二项式定理

　　6.4.2　帕斯卡恒等式和三角形

　　6.4.3　其他的二项式系数恒等式

　　练习

　6.5　排列与组合的推广

　　6.5.1　引言

　　6.5.2　有重复的排列

　　6.5.3　有重复的组合

　　6.5.4　具有不可区别物体的集合的排列

　　6.5.5　把物体放入盒子

　　练习

　6.6　生成排列和组合

　　6.6.1　引言

　　6.6.2　生成排列

　　6.6.3　生成组合

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第7章　离散概率

　7.1　离散概率引论

　　7.1.1　引言

　　7.1.2　有限概率

　　7.1.3　事件组合的概率

　　7.1.4　概率的推理

　　练习

　7.2　概率论

　　7.2.1　引言

　　7.2.2　概率指派

　　7.2.3　事件的组合

　　7.2.4　条件概率

　　7.2.5　独立性

　　7.2.6　伯努利试验与二项分布

　　7.2.7　随机变量

　　7.2.8　生日问题

　　7.2.9　蒙特卡罗算法

　　7.2.10　概率方法

　　练习

　7.3　贝叶斯定理

　　7.3.1　引言

　　7.3.2　贝叶斯定理

　　7.3.3　贝叶斯垃圾邮件过滤器

　　练习

　7.4　期望值和方差

　　7.4.1　引言

　　7.4.2　期望值

　　7.4.3　期望的线性性质

　　7.4.4　平均情形下的计算复杂度

　　7.4.5　几何分布

　　7.4.6　独立随机变量

　　7.4.7　方差

　　7.4.8　切比雪夫不等式

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第8章　高级计数技术

　8.1　递推关系的应用

　　8.1.1　引言

　　8.1.2　用递推关系构造模型

　　8.1.3　算法与递推关系

　　练习

　8.2　求解线性递推关系

　　8.2.1　引言

　　8.2.2　求解常系数线性齐次递推关系

　　8.2.3　常系数线性非齐次的递推关系

　　练习

　8.3　分治算法和递推关系

　　8.3.1　引言

　　8.3.2　分治递推关系

　　练习

　8.4　生成函数

　　8.4.1　引言

　　8.4.2　关于幂级数的有用事实

　　8.4.3　计数问题与生成函数

　　8.4.4　使用生成函数求解递推关系

　　8.4.5　使用生成函数证明恒等式

　　练习

　8.5　容斥

　　8.5.1　引言

　　8.5.2　容斥原理

　　练习

　8.6　容斥原理的应用

　　8.6.1　引言

　　8.6.2　容斥原理的另一种形式

　　8.6.3　埃拉托色尼筛

　　8.6.4　映上函数的个数

　　8.6.5　错位排列

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第9章　关系

　9.1　关系及其性质

　　9.1.1　引言

　　9.1.2　函数作为关系

　　9.1.3　集合的关系

　　9.1.4　关系的性质

　　9.1.5　关系的组合

　　练习

　9.2　n元关系及其应用

　　9.2.1　引言

　　9.2.2　n元关系

　　9.2.3　数据库和关系

　　9.2.4　n元关系的运算

　　9.2.5　

　　练习

　9.3　关系的表示

　　9.3.1　引言

　　9.3.2　用矩阵表示关系

　　9.3.3　用图表示关系

　　练习

　9.4　关系的闭包

　　9.4.1　引言

　　9.4.2　闭包

　　9.4.3　有向图中的路径

　　9.4.4　传递闭包

　　9.4.5　沃舍尔算法

　　练习

　9.5　等价关系

　　9.5.1　引言

　　9.5.2　等价关系

　　9.5.3　等价类

　　9.5.4　等价类与划分

　　练习

　9.6　偏序

　　9.6.1　引言

　　9.6.2　字典顺序

　　9.6.3　哈塞图

　　9.6.4　极大元与极小元

　　9.6.5　格

　　9.6.6　拓扑排序

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第10章　图

　10.1　图和图模型

　　10.1.1　图模型

　　练习

　10.2　图的术语和几种特殊的图

　　10.2.1　引言

　　10.2.2　基本术语

　　10.2.3　一些特殊的简单图

　　10.2.4　二分图

　　10.2.5　二分图和匹配

　　10.2.6　特殊类型图的一些应用

　　10.2.7　从旧图构造新图

　　练习

　10.3　图的表示和图的同构

　　10.3.1　引言

　　10.3.2　图的表示

　　10.3.3　邻接矩阵

　　10.3.4　关联矩阵

　　10.3.5　图的同构

　　10.3.6　判定两个简单图是否同构

　　练习

　10.4　连通性

　　10.4.1　引言

　　10.4.2　通路

　　10.4.3　无向图的连通性

　　10.4.4　图是如何连通的

　　10.4.5　有向图的连通性

　　10.4.6　通路与同构

　　10.4.7　计算顶点之间的通路数

　　练习

　10.5　欧拉通路与哈密顿通路

　　10.5.1　引言

　　10.5.2　欧拉通路与欧拉回路

　　10.5.3　哈密顿通路与哈密顿回路

　　10.5.4　哈密顿回路的应用

　　练习

　10.6　最短通路问题

　　10.6.1　引言

　　10.6.2　最短通路算法

　　10.6.3　旅行商问题

　　练习

　10.7　平面图

　　10.7.1　引言

　　10.7.2　欧拉公式

　　10.7.3　库拉图斯基定理

　　练习

　10.8　图着色

　　10.8.1　引言

　　10.8.2　图着色的应用

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第11章　树

　11.1　树的概述

　　11.1.1　有根树

　　11.1.2　树作为模型

　　11.1.3　树的性质

　　练习

　11.2　树的应用

　　11.2.1　引言

　　11.2.2　二叉搜索树

　　11.2.3　决策树

　　11.2.4　前缀码

　　11.2.5　博弈树

　　练习

　11.3　树的遍历

　　11.3.1　引言

　　11.3.2　通用地址系统

　　11.3.3　遍历算法

　　11.3.4　中缀、前缀和后缀记法

　　练习

　11.4　生成树

　　11.4.1　引言

　　11.4.2　深度优先搜索

　　11.4.3　宽度优先搜索

　　11.4.4　回溯的应用

　　11.4.5　有向图中的深度优先搜索

　　练习

　11.5　最小生成树

　　11.5.1　引言

　　11.5.2　最小生成树算法

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第12章　布尔代数

　12.1　布尔函数

　　12.1.1　引言

　　12.1.2　布尔表达式和布尔函数

　　12.1.3　布尔代数恒等式

　　12.1.4　对偶性

　　12.1.5　布尔代数的抽象定义

　　练习

　12.2　布尔函数的表示

　　12.2.1　积之和展开式

　　12.2.2　函数完备性

　　练习

　12.3　逻辑门电路

　　12.3.1　引言

　　12.3.2　门的组合

　　12.3.3　电路的例子

　　12.3.4　加法器

　　练习

　12.4　电路的极小化

　　12.4.1　引言

　　12.4.2　卡诺图

　　12.4.3　无需在意的条件

　　12.4.4　奎因莫可拉斯基方法

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

第13章　计算模型

　13.1　语言和文法

　　13.1.1　引言

　　13.1.2　短语结构文法

　　13.1.3　短语结构文法的类型

　　13.1.4　派生树

　　13.1.5　巴克斯诺尔范式

　　练习

　13.2　带输出的有限状态机

　　13.2.1　引言

　　13.2.2　带输出的有限状态机

　　练习

　13.3　不带输出的有限状态机

　　13.3.1　引言

　　13.3.2　串的集合

　　13.3.3　有限状态自动机

　　13.3.4　有限状态机的语言识别

　　13.3.5　非确定性的有限状态自动机

　　练习

　13.4　语言的识别

　　13.4.1　引言

　　13.4.2　克莱因定理

　　13.4.3　正则集合和正则文法

　　13.4.4　一个不能由有限状态自动机识别的集合

　　13.4.5　一些更强大的机器

　　练习

　13.5　图灵机

　　13.5.1　引言

　　13.5.2　图灵机的定义

　　13.5.3　用图灵机识别集合

　　13.5.4　用图灵机计算函数

　　13.5.5　不同类型的图灵机

　　13.5.6　丘奇图灵论题

　　13.5.7　计算复杂度、可计算性和可判定性

　　练习

　关键术语和结论

　复习题

　补充练习

　计算机课题

　计算和探索

　写作课题

附录A　实数和正整数的公理

附录B　指数与对数函数

附录C　伪代码

推荐读物

参考文献

奇数编号练习答案

本书是根据我多年讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供准确且可读

性很强的教材，清晰地介绍并展示离散数学中的概念和技术。我的目标是向爱怀疑的学生们展示离散数

学的相关性和实用性，希望为学习计算机科学的学生提供一切必需的数学基础，也希望学数学的学生理

解重要的数学概念，以及为什么这些概念对应用来说很重要，最重要的是希望本书既能达到这些目标，

又不含太多的水分。 

对教师而言，我的目的是要利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具，希望为

教师提供能够以最适合特定学生特点的方式高效地教授离散数学的教材。希望本书能够达到这些目标。 

我为本教材在过去所取得的巨大成功而感到非常欣慰。根据北美600多所学校以及全球各地许多大学成功

采用了本书的大批师生的反馈和建议，此次第7版进行了许多改进。 

本教材是为一至两个学期的离散数学入门课程而设计的，适用于数学、计算机科学和工程等各类专业的

学生。虽然唯一的先修课程要求是大学代数，但是要想真正学好离散数学还需要掌握更多的数学知识。 

离散数学课程的目标 

离散数学课程有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用，更重要的是，这样一

门课应培养学生的数学逻辑思维。为此，本教材特别强调数学推理以及用不同的方法解题。本书中五个

重要主题交织在一起：数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程

应该努力使这五个主题相互融合、平衡。 

1.数学推理：学生必须理解数学推理，以便阅读、领会并构造数学论证。本书以数理逻辑开篇，在后面

证明方法的讨论中，数理逻辑是基础。本书描述了构造证明的方法与技巧。本书特别强调数学归纳法，

不仅给出了这种证明的许多不同类型的实例，还详细地解释了数学归纳法为什么是有效的证明技术。 

2.组合分析：一个重要的解题技巧就是计数或枚举对象。本书中，对枚举的讨论从计数的基本技术着手

，重点是用组合分析方法来解决计数问题并分析算法，而不是简单地应用公式。 

3.离散结构：离散数学课程应该教会学生如何处理离散结构，即表示离散对象以及对象之间关系的抽象

数学结构。离散结构包括集合、置换、关系、图、树和有限状态机等。 

4.算法思维：有些问题可以通过详细说明其算法来求解。在清楚地描述算法后，就可以构造一个计算机

程序来实现它。这一过程中涉及的数学部分包括算法的详细说明、正确性验证以及执行算法所需要的计

算机内存和时间的分析等，这些内容在本书中均有介绍。算法是用英语译著中采用汉语。——译者注

和一种易于理解的伪代码来描述的。 

5.应用与建模：离散数学几乎在每个可以想象到的研究领域中都有应用，本书介绍了其在计算机科学和

数据网络中的许多应用，还介绍了在其他各种领域中的应用，如化学、植物学、动物学、语言学、地理

学、商业以及因特网等。这些均是离散数学的实际而又重要的应用，而不是编造的。用离散数学来建模

是十分重要的问题求解技巧，本书中的一些练习让学生有机会通过自己构造模型掌握这一技巧。 

第7版中的变更 

虽然第6版已经是一本非常有效的教材，但许多教师（包括长期使用者）还是提出了使本书更有效的修改

要求。我花了大量的时间和精力来满足这些要求，想方设法使这本书做得更好。 

第7版是一个重大的修订版，其变更基于40多位正式评阅人、学生和教师的反馈以及作者的见解。新版本

改善了主题的组织结构，使本书成为一个更加有效的教学工具。逻辑、算法、数论和图论方面的内容有

许多实质性的增强，使本书更加灵活和全面。第7版中所做的大量变更能帮助学生更容易地掌握这些内容

。增加了额外的解释和例子以便阐述那些学生经常感到有困难的内容。新增了一些常规的和富有挑战性

的习题。还增加了一些与因特网、计算机科学以及数学生物学等密切相关的应用。配套网站得易于广泛

的开发活动，现在所提供的工具使学生可以用来掌握关键概念并探索离散数学世界，正在开发中的许多

新工具也将在本书出版后的来年发布。 

我希望教师仔细阅读这本新版以发现如何来满足他们的需求。尽管要列出本版所有变更是不切实际的，

但基于一些关键变更及其所带来的好处给出一个简要的列表或许是有益的。 

更灵活的组织结构 

　　

命题逻辑的应用分出专门的小节，其中简要介绍了逻辑电路。 递推关系在第2章论述。 扩展了可数性讨

论并在第2章中有专门的一节。 用独立的章节论述算法（第3章）以及数论和密码学（第4章），并增加

了内容。 采用了更多二级、三级标题以便将章节划分成较小的有紧密联系的部分。 

便于学习的工具 

　　

有些难度的讨论和证明已经在页边用布尔巴基著名的“危险弯道”符号警示。 新的页边注解给出一些链

接，增加一些有趣的注解，并为学生提供一些忠告。 在证明以及阐述中引入更多的细节和解释，以帮助

学生更容易地阅读本书。 在对许多原有练习做了一些改进的同时，增加了更多新的练习，包括常规练习

以及富有挑战性的练习。 增强了逻辑、集合和证明所涵盖的内容可满足性问题有了更深入的阐述，并论

述了以可满足性建模的数独（Sudoku）问题。 利用希尔伯特大饭店来解释不可数性。 贯穿全书的证明

通过细化步骤及其背后的原因使之更加易于理解。 增加了一个数学归纳法的证明模板。 在数学归纳法

证明中显式地注明了应用归纳假设的步骤。 

算法 

　　

本书中使用的伪代码已经做了更新。 算法范型做了显式的扩充，提供了包括蛮力算法、贪婪算法以及动

态规划等内容。 增加了对数、幂以及指数函数大O估计的判别规则。 

数论和密码学 

　　

扩展了所涵盖的内容使得教师在课程中可以只选择一小部分或更多的数论内容。 mod函数和同余之间的

关系做了更全面的解释。 对埃拉托斯特尼（Eratosthenes）筛法的介绍在本书中有所提前。 线性同余

式以及模的逆有了更深入的阐述。 深入讨论了数论应用，包括校验码和散列函数。 新一节的密码学集

成了原先的内容，并引入了密码系统的概念。 涵盖了密码协议内容，包括数字签名和密钥共享。 

图论 

　　

增加了结构归纳法在图论中的应用。 更多地关注社交网络的概念。 增加了在生物科学中的应用，还有

图同构和平面性方面很有意思的应用。 增加了二分图的匹配问题，包括Hall定理及其证明。 增加了顶

点连通性、边连通性以及n连通性，使读者对图的连通性有更深入的理解。 

充实的内容 

　　

对许多传记做了扩充和更新，同时新增了贝尔曼、贝祖·比安内梅、卡尔达诺、卡塔兰、柯克斯、库克

、狄拉克、霍尔、希尔伯特、欧尔和陶哲轩的传记。全书历史资料也有所增加。 大量最新发现也做了相

应更新。 

扩展的媒体 

　　

努力为本书开发有价值的网站资源。 在配套网站上为本书主要内容提供了额外的练习。 开发了一些交

互式算法，以及一些探索主题并可用于课堂教学的工具。 2012年秋季新上线一个辅助工具——虚拟离散

数学导师，可以帮助学生解决学习离散数学中的困难。2012年秋季新上线的作业提交系统，可用来提供

自动化的作业，包括数值型和概念型的练习。 针对关键概念的学生评估模块。 开发了供教师使用的

PowerPoint幻灯片。 开发了补充的《探索离散数学》，为配合本书利用MapleTM或MathematicaTM提供广

泛的支持。 提供了一组广泛的外部Web链接。 

本书特色 

易理解性：本书对于初学者来说已被实践证明是易读易懂的。绝大部分内容不需要读者具备比大学代数

更多的数学预备知识。需要额外帮助的学生可以在配套网站找到相应工具将数学水平提升到本书的水准

。本书中少数几个需要参考微积分的地方也已显式注明。大多数学生应该很容易理解书中用来表示算法

的伪代码，无论他们是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。 

每章都是从易于理解和领会的水平开始。一旦详细介绍了基本数学概念，就会给出稍难一些的内容以及

在其他研究领域中的应用。 

灵活性：本书为能灵活使用做了精心设计。各章对其前面内容的依赖程度都降到最低。每章分成长度大

致相等的若干节，每节又根据内容划分成若干小节以方便教学。教师可以根据这些分块灵活地安排讲课

进度。 

写作风格：本书的写作风格是直接而又实用的。使用准确的数学语言，但没有采用过多的形式化与抽象

。在数学命题中的记号和词语表达之间做了精心的平衡。 

数学严谨性和准确性：本书中所有定义和定理的陈述都十分仔细，这样学生可以欣赏语言的准确性和数

学所需的严谨性。证明则先是动机再缓慢展开，每一步都经过了详细论证。证明中用到的公理及其所导

出的基本性质在附录中均有显式描述，这呈现给学生一个清晰的概念，即在一个证明中他们能够作何种

假设。本书解释并大量使用了递归定义。 

实例：超过800多个例子用来阐述概念、建立不同主题之间的关联，并介绍应用。在大部分例子中，首先

提出问题，然后再以适量的细节给出其解。 

应用：本书中所含的应用展示了离散数学在解决现实世界中的问题时的实用性。本书包含的应用涉及广

泛的领域，包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网。 

算法：离散数学的结论常常要用算法来表述，因此本书每章都介绍一些关键算法。这些算法采用文字叙

述，同时也采用一种易于理解的结构化伪代码来描述。伪代码的描述和说明在附录C中给出。简要分析了

书中所有算法的计算复杂性。 

历史资料：本书对许多主题的背景做了简要介绍。83位数学家和计算机科学家的简短传记以脚注的形式

给出。这些传记介绍了他们的生活、事业，以及对离散数学做出过重要贡献的科学家的成就，同时配有

他们的照片（如果有的话）。 

此外，脚注还包含了大量历史资料，作为本书正文中历史资料的补充。我们做了大量努力，使得本书能

够反映最新的发现。 

关键术语和结论：每章最后列出关键术语和结论。关键术语只列出学生必须掌握的那些，而非该章中定

义的每个术语。 

练习：书中包含4000多个练习题，涉及大量不同类型的问题。不仅提供了足够多的简单练习用于培养基

本技能，还提供了大量的中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义，并按难

易程度进行了分级。练习还包含一些特殊的讨论来展开正文中没有涉及的新概念，使得学生能够通过自

己的工作来发现新的想法。 

那些比平均难度稍难的练习用单个星号*标记，而那些相当有挑战性的练习则用两个星号**标记。需要用

微积分来求解的练习也明确指出。而那些其结果要在正文中用到的练习则会明确地用指向右侧的手形符

号来标识。本书最后给出了所有奇数编号练习的答案或解题纲要。解答通常包含那些大多数步骤写得很

清楚的证明。 

复习题：每章最后都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。

要回答这些问题，学生必须写出较长的答案，而不是仅做一些计算或一个简答。 

补充练习：每章后面都有一组丰富而多样的补充练习。这些练习通常比每节后的练习难度更大些。补充

练习强化该章中的概念，并把不同主题更有效地综合起来。 

计算机课题：每章后面还有一组计算机课题。大约150个计算机课题将学生在计算和离散数学中所学到的

内容联系起来。对于那些从数学角度或程序设计角度来看其难度超过平均水平的计算机课题用一个星号*

标记，而那些非常具有挑战性的则用两个星号**标记。 

计算和探索：每章的最后都有一组计算和探索性的问题。完成这些练习（大约有120题）需要借助于现有

的软件工具，如学生或教师自己编写的程序，或MapleTM或MathematicaTM这样的数学计算软件包。大部

分这些练习为学生提供了通过计算来发现一些新事实或想法的机会（其中的一些练习在配套的在线练习

册《探索离散数学》中也有讨论）。 

写作课题：每章后面都有一组写作课题。要完成这类课题学生需要参考数学文献。有些课题本质上是关

于历史的，需要学生查找原始资料。有些课题则是通往新内容和新思想的途径。所有此类练习是要向学

生展示正文中没有深入探讨的想法。这些课题把数学概念和写作过程结合起来，以帮助学生面对未来可

能的研究领域（在线版或印刷版的《学生解题指南》中可以找到为这些课题准备的参考文献）。 

附录：本书有3个附录。附录A介绍实数和正整数的公理，并解释如何利用这些公理直接证明事实。附录B

介绍指数函数和对数函数，复习在课程中常用的一些基本内容。附录C则介绍正文中用来描述算法的伪代

码。 

推荐读物：在附录后还提供了一组针对全书及各章的推荐读物。这些推荐读物包括难度不超过本书的书

籍、更难些的书籍、阐述性的文章，以及发表离散数学新发现的原始文章。其中一些是多年前出版的经

典读物，而另一些是在最近几年内才出版的。 

怎样使用本书 

本书经过精心写作和编排，适用于不同层次以及有不同重点的离散数学课程。下表列出了核心章节和可

选章节。为大学二年级学生开设一学期的离散数学入门课程可以以本书核心章节为基础，其他章节可由

教师取舍。两学期的入门课程可以在核心章节上外加所有可选的数学章节。强调计算机科学的课程则可

以涵盖部分或全部可选的计算机科学章节。教师可以在本书网站上的《教师资源手册》中找到广泛的离

散数学课程教学大纲样本，以及针对本书章节的教学建议。 

　　章核心章节可选的计算机科学章节可选的数学章节 

　　11.1~1.8(视需要) 

　　22.1~2.4、2.6(视需要)2.5 

　　33.1~3.3(视需要) 

　　44.1~4.4(视需要)4.5、4.6 

　　55.1~5.35.4、5.5 

　　66.1~6.36.66.4、6.5 

　　77.17.47.2、7.3 

　　88.1、8.58.38.2、8.4、8.6 

　　99.1、9.3、9.59.29.4、9.6 

　　1010.1～10.510.6～10.8 

　　1111.111.2、11.311.4、11.5 

　　1212.1~12.4 

　　1313.1~13.5 

使用本书的教师可以选用或略去每节最后有挑战性的例题及练习来调整其课程的难度。这里的各章依赖

图展示的是强依赖性。星号表示该章的部分相关小节是学习后续章节必需的。弱依赖关系省略了。更多

详细信息可以在《教师资源手册》中找到。 

辅助资料 

《学生解题指南》：这本可以单独购买的学生手册包含了所有奇数编号练习的完整解答。这些解答解释

了为什么要用某种特定的方法以及为什么这个方法管用。对于有些练习，还给出了一两种其他可能的解

法以说明一个问题可以由多种不同方法来求解。本指南给出了为每章后面的写作课题推荐的参考文献，

还包含撰写证明指南、离散数学学习中学生常犯错误的一般性描述，以及为每章提供的考试样例及解答

以帮助学生准备考试。 

X（ISBN-10∶0-07-735350-1）（ISBN-13∶978-0-07-735350-6） 

《教师资源手册》：本手册在网站上有提供，教师也可以申请印刷版的。手册包含书中所有偶数编号练

习的完整解答。给出了如何讲授本书每章内容的建议，包括每节中应强调的重点以及如何组织内容。手

册还为每章提供了考试样例以及一个可供选择的包含1500多道考试题目的试题库。对于所有考试样例及

试题库中的题目都给出了解答。最后，还给出了针对不同的侧重点以及学生能力水平的课程教学大纲样

本。 

（ISBN-10∶0-07-735349-8）（ISBN-13∶978-0-07-735349-0） 

致谢 

感谢各类学校中使用本书并向我提供有价值的反馈和有益的建议的许多教师和学生，他们的反馈才有可

能使得本书更出色。特别感谢Jerrold Grossman、Jean-Claude Evard和Georgia Mederer，他们作为第7

版的技术审阅，以其“鹰眼”般敏锐的目光确保了本书的准确性。我也很感激那些通过网站提交评论的

人们所提供的帮助。 

感谢第7版以及前六版的评阅人，这些评阅人给予我许多有益的批评和鼓励，希望这一版不会辜负他们的

期望。 

第7版评阅人 

　　Philip Barry美国明尼苏达大学明尼阿波里斯分校 

　　Miklos Bona美国佛罗里达大学 

　　Kirby Brown美国皇后学院 

　　John Carter加拿大多伦多大学 

　　Narendra Chaudhari新加坡南洋理工大学 

　　Allan Cochran美国阿肯色大学 

　　Daniel Cunningham美国布法罗州立学院 

　　George Davis美国佐治亚州立大学 

　　Andrzej Derdzinski美国俄亥俄州立大学 

　　Ronald Dotzel美国密苏里大学圣路易斯分校 

　　T.J.Duda美国哥伦布州立社区学院 

　　Bruce Elenbogen美国密歇根大学迪尔本分校 

　　Norma Elias美国普渡大学卡鲁梅分校（哈蒙德） 

　　Herbert Enderton美国加州大学洛杉矶分校 

　　Anthony Evans美国莱特州立大学 

　　Kim Factor美国马凯特大学 

　　Margaret Fleck美国伊利诺伊大学香槟分校 

　　Peter Gillespie美国费耶特维尔州立大学 

　　Johannes Hattingh美国佐治亚州立大学 

　　Ken Holladay美国新奥尔良大学 

　　Jerry Ianni美国纽约长岛社区学院 

　　Ravi Janardan美国明尼苏达大学明尼阿波里斯分校 

　　Norliza Katuk马来西亚北方大学 

　　William Klostermeyer美国北佛罗里达大学 

　　Przemo Kranz美国密西西比大学 

　　Jaromy Kuhl美国西佛罗里达大学 

　　Loredana Lanzani美国阿肯色大学费耶特维尔分校 

　　Steven Leonhardi美国威诺纳州立大学 

　　Xu Liutong中国北京邮电大学 

　　Vladimir Logvinenko美国迪安萨社区学院 

　　Darrell Minor美国哥伦布州立社区学院 

　　Keith Olson美国犹他谷大学 

　　Yongyuth Permpoontanalarp泰国国王科技大学 

　　Galin Piatniskaia美国密苏里大学圣路易斯分校 

　　Stefan Robila美国蒙特克莱尔州立大学 

　　Chris Rodger美国奥本大学 

　　Sukhit Singh美国得克萨斯州立大学圣马科斯分校 

　　David Snyder美国得克萨斯州立大学圣马科斯分校 

　　Wasin So美国圣何塞州立大学 

　　Bogdan Suceava美国加州州立大学富尔顿分校 

　　Christopher Swanson美国阿什兰大学 

　　Bon Sy美国皇后学院 

　　Matthew Walsh美国印第安那普渡大学韦恩堡分校 

　　Gideon Weinstein美国西部州长办大学 

　　David Wilczynski美国南加州大学 

我要感谢责任编辑Bill Stenquist的倡导、热情和支持，他对这一版的帮助是不可或缺的。我还要感谢

原编辑Wayne Yuhasz，他的洞察力和技能确保了本书的成功。 

我想要对为这一版做出宝贵贡献的RPK编辑部职员表达我的感谢，包括同时担任开发和产品编辑的Rose 

Kernan，还有RPK编辑团队的其他成员——Fred Dahl、Martha McMaster、Erin Wagner、Harlan James

和Shelly Gerger-Knecthl。感谢PreTeX公司的排版人员Paul Mailhot为这一版做了大量的工作，以及他

精湛的LaTex知识。还要感谢Photo Affairs公司的Danny Meldung很巧妙地寻找到新的传记脚注的图片。 

新版的准确性和高质量要归功于Jerry Grossman和Jean-Claude Evard，他们校对了整个手稿的技术准确

性；Georgia Mederer校对了本书最后的答案和《学生解题指南》、《教师资源手册》中题解的准确性。

像往常一样，Jerry Grossman编辑了这两册重要的辅助资料，怎么感谢他都不为过。

我还要对麦格劳希尔高等教育的科学、工程和数学部（SEM）表达感谢，他们对这一版本以及相关的媒体

内容给予了强有力的支持。特别是，感谢麦格劳希尔高等教育SEM总裁Kurt Strand、SEM主编Marty 

Lange、编辑部主任Michael Lange、全球发行主任Raghothaman Srinivasan、责任编辑Bill Stenquist

、市场执行主任Curt Reynolds、项目经理Robin A.Reed、采购员Sandy Ludovissey、内部开发编辑

Lorraine Buczek、设计协调人Brenda Rowles、铅照片研究协调人Carrie K.Burger和媒体项目经理

Tammy Juran。 

Kenneth H.Rosen