本书从算法分析和问题求解的角度，全面系统地介绍了离散数学的基础概念及相关知识，并在其前一版的基础上进行了修改与扩展。书中通过大量实例，深入浅出地讲解了数理逻辑、组合算法、图论、Boole代数、网络模型、形式语言与自动机理论、计算几何等与计算机科学密切相关的前沿课题，既着重于各部分内容之间的紧密联系，又深入探讨了相关的概念、理论、算法和实际应用。本书内容叙述严谨、推演详尽，各章配有相当数量的习题与书后的提示和答案，为读者迅速掌握相关知识提供了有效的帮助。
本书抛开了以往离散数学教材从数学角度出发，讲解基本概念和方法，而是按照计算机专业课程设置的特点，从计算机应用的角度来讲解离散数学，特点鲜明，非常有针对性，可以帮助计算机专业的教师有效地开展教学，并让学生深刻理解离散数学知识在计算机技术中的关键作用。
译者序
离散数学以研究离散量的结构和相互间的关系为主要目标， 包括数理逻辑、集合论、数论、图论、组合学和计算几何等，是计算机科学与技术专业的一门重要基础课。
本书的第一版出版于上个世纪80年代，那时许多大学需要一门涉及组合数学、算法和图论等内容的课程来拓宽学生的数学知识和处理抽象概念的能力。该书的出版满足了这种需求，并对以后离散数学课程的发展产生了深远的影响。本版本的离散数学教材，不仅包括了算法、组合数学、集合、函数、数学归纳法等内容，同时还涉及证明的理解和构造技术，通过学习，学生可提高数学涵养，能更好理解后序课程的内容。
自本书第4版引进国内，本书译者就一直使用该教材于离散数学课程的教学。从内容上看，这是一本深入浅出的好教材，不要求学生具备任何预备知识，可广泛应用于普通高 译者序
离散数学以研究离散量的结构和相互间的关系为主要目标， 包括数理逻辑、集合论、数论、图论、组合学和计算几何等，是计算机科学与技术专业的一门重要基础课。
本书的第一版出版于上个世纪80年代，那时许多大学需要一门涉及组合数学、算法和图论等内容的课程来拓宽学生的数学知识和处理抽象概念的能力。该书的出版满足了这种需求，并对以后离散数学课程的发展产生了深远的影响。本版本的离散数学教材，不仅包括了算法、组合数学、集合、函数、数学归纳法等内容，同时还涉及证明的理解和构造技术，通过学习，学生可提高数学涵养，能更好理解后序课程的内容。
自本书第4版引进国内，本书译者就一直使用该教材于离散数学课程的教学。从内容上看，这是一本深入浅出的好教材，不要求学生具备任何预备知识，可广泛应用于普通高等院校、成人教育、远程教育和高等专科学校计算机相关专业的离散数学教学。可以说这是国内目前可见的最明了、简单的离散数学教材，可适用于任何层次的学生以不同的途径学习，包括自学和网络教学。
本书由上海交通大学计算机系的黄林鹏教授、陈俊清博士和王欣博士共同翻译，由黄林鹏审校。此外还要感谢彭冲、王德俊、徐小辉、伍建焜、张迎春、冯志宇、杨欢和林海源等的帮助。
这里还要提一下我的研究生导师左孝凌教授，他在上个世纪80年代撰写的离散数学教材曾再版30余次，影响了几代学子。译者在1986至1988年间作为他的研究生，在他指导下开始学习离散数学知识，再此饮水思源，并表示感谢。
由于译者水平所限，错误难免，译文不当不周之处难免，敬请读者将意见寄到lphuang@sjtu.edu.cn，不胜感激。
这本新版的离散数学书籍，是基于作者多年来的教学经验并根据读者意见修改而成，可作为一个或两个学期的离散数学课程的教材，本书不需要作者先期掌握形式化方法，也不需要具备微积分的知识，当然更不需要计算机科学的前期知识。本书包括例题、练习、图表、问题求解要点，每个章节还包括复习、注释、自测题和上机练习等，这些丰富的材料可帮助读者快速掌握离散数学的基本知识。与本书配套的材料还包括教学参考书和Web站点。
在20世纪80年代初期，几乎没有离散数学入门课程的合适教材。但那时许多大学需要一门涉及组合数学、算法和图论等内容的课程来拓宽学生的数学知识和处理抽象概念的能力。本书第一版（1984）的出版满足了这种需求，并对离散数学课程的发展产生了深远的影响。此后，离散数学课程得到了包括数学和计算机等专业的许多学科的认可。美国数学学会（MAA）的一个专门小组曾提议离散数学应作为一学年的课程讲授。电气和电子工程师协会（IEEE）的教育委员会也建议在大学一年级开设离散数学课程。随后，美国计算机学会（ACM）和IEEE给出了离散数学课程的推荐性大纲。本版和前面各版一样，不仅包括了算法、组合数学、集合、函数、数学归纳法等被这些组织所认可的内容，同时还涉及证明的理解和构造技术，学生通过学习可提高数学上的涵养。
逻辑和证明发方面的修改
本书第7版的修改来自于许多读者对本书先前版本的意见和要求。对第6版的最大修改是第1章到第3章。本书第6版的第1章，逻辑和证明，在第7版中被分为两章，集合与逻辑（第1章）和证明（第2章）。除了集合一节，第6版中的第2章（数学的语言）和第3章（关系）被合并为第7版中的第3章（函数、序列和关系）。从本书预印版已经看出读者对于这些修改的热切期望。
集合一节现在是本书的第一节。这种改变使本书可以自始至终使用与集合相关的术语。现在可以在例子和练习的证明中使用集合的概念，由此可以给出比先前版本更有意思的例子。甚至可以在完整讨论证明和证明技术之前就可以使用集合来引入证明的概念（例如，证明两个集合是相等的，证明一个集合是另一个集合的子集）。
对于证明构造技术的内容也大大拓广了。2.1和2.2节是和数学系统、证明技术相关的新章节。除此之外，还有关于等价性证明和存在性证明（包括构造和非构造存在性证明）的扩展内容。几乎每一个证明都有前导性的讨论章节和/或伴随的图解。问题求解部分包括了如何进行证明，如何书写证明以及证明中常见的错误等额外的建议和例子。有两个新的问题求解段落，一是关于量词的，另一个与证明有关（参见证明实数的若干性质）。
关于证明的论据和规则的讨论则被移到关于命题的讨论之后。与量词有关的推理规则被整合进量词一节。
例子和习题的数量也有了大量的提升。在第6版，前3章大约有1370个例子和习题。而在第7版，前3章大约有1640个例子和习题。当然，不仅数量增加了，质量也得到了提高。对于第6版中的大部分例子，第7版都进行了讨论并增加了分析。
对第6版所进行的其他修改
对第6版所进行的其他修改如下：
* 在本书前头就引入了整数（Z，Z#+，Z#-，Z＃nonneg）、有理数（用Q代替Z）、实数（用R代替Z）的概念描述和记法（见1.1节，集合）。
* 给出定理5.1.17和定理5.1.22的证明，本书第6版只是给出证明概要，这两个定理描述了从给定的两个整数的素因子表示法中得出最大公因子和最小公倍数的过程。
* 给出计算两个整数a和b的最大公因子的递归算法gcd(a,b)，以及如何计算满足gcd(a,b)=sa+tb的整数s和t的算法。
* 6.1节增加了包含排斥原理。
* 6.1节增加了几个实例以说明乘法原理和加法原理的应用。这些例子所处的位置在读者了解该使用何种原理或混合使用两种原理之前。
* 和广义排列组合有关的章节（第6版中的6.6节）现在放在6.1节和6.2节之后（基本原理、排列和组合），因为广义排列组合的概念和6.1节、6.2节中的材料较为相近。
* 在介绍鸽巢（6.9节）之前给出了一些简单、直接的“热身”练习。
* 加入更多的（8.6节）图同构的练习，练习分为3类，一类要求给出两个给定的图是同构的证明，另一类要求给出两个给定的图不是同构的说明，还有一类是要求读者确定是否两个给定的图是同构的并给出证明。
* 9.3节新增了一些使用回溯法的练习，包括流行的数独智力游戏。
* 给出更多的例子和练习以提示常见的错误（例如，在2.1节复习和练习前的“常见错误”部分就给出了一些证明中常见的错误，例6.2.24也说明了一个常见的计数错误）。
* 在参考文献中加入了近期的一些书籍和文章。一些参考书籍被更新为最新的版本。
* 例子的数量增加到650（第6版大概有600个例子）。
* 练习的数量增加到4200左右（第6版大概有4000个例子）。
内容和结构
本书内容包括
* 集合和逻辑（包括量词）。实例包括Google搜索引擎的使用（例 1.2.13）等。本书使用程序逻辑来讨论自然语言到符号表达式的翻译。例1.6.15讨论了逻辑游戏，该游戏给出了一种确定量化命题函数的值是否为真的方法。
* 讨论了证明技术（第2章），包括直接证明、反例、反证法、逆否证明法、分情况证明法、（构造和非构造）存在性证明和数学归纳法。使用循环不变式做为数学归纳法的应用例子之一。包括了一节可选的，简短的对归结证明方法（自动证明技术的基础）的讨论。
* 函数、序列、和与积的记法、串和关系（第3章），包括新的13位国际标准书号（ISBN）的构造、Hash函数和伪随机数发生器（3.1节）的介绍、偏序关系在任务调度中的应用（3.3节）和关系数据库（3.6节）等。
* 详细讨论了算法、递归算法和算法分析技术（第4章）。在说明“大O”和相关记法之前列举了若干例子（4.1节和4.2节），对引入该记法的动机进行了简要的介绍。算法的使用将贯穿全书。本书将提到许多现代算法可能没有传统算法的许多特征（如许多现代算法不是通用、确定的、甚至有的不是有限的）。为了说明这点，本章给出了一个随机算法作为例子（例4.2.4）。算法以伪代码的灵活形式书写，其和目前流行的程序设计语言如C、C＋＋和Java相似（本书不要求读者预先具有计算机科学的知识，所使用的伪代码的描述在附录C中给出）。本身介绍的算法包括覆盖算法（4.4节）、计算最大公约数的欧几里德算法（5.3节）、RSA公共密钥算法（5.4节）、排列组合生成算法（6.4节）、归并排序算法（7.3节）、Dijkstra最短路径算法（8.4节）、回溯算法（9.3节）、深度优先和广度优先算法（9.3节）、树的遍历算法（9.6节）、博弈树求值算法（9.9节）、网络最大流量算法（10.2节）、寻找最小距点对算法（13.1节）和凸包计算算法（13.2节）等。
* 关于函数增长的“大O”、Ω、Θ记法的讨论（4.3节）。使用这些记法可以准确地描述函数的增长以及算法的时间和空间复杂度问题。
* 数论的介绍（第5章）。包括一些传统的结论（如整除性、素数个数是无限的、基本的算术定理）和数论算法（如寻找最大公约数的欧几里德算法、基于重复平方法计算数的指数的算法，计算满足gcd(a,b)=sa+tb的整数s和t的算法，计算一个整数针对某个模的逆的算法等。本章介绍的方法可应用于RSA公共密钥算法（5.4节）中涉及的计算。
* 排列、组合、离散概率和鸽巢原理（第6章）。可选章节（6.4节和6.5节）介绍了离散概率。
* 递推关系及其在算法分析中的应用（第7章）。
* 图，包括并行计算机体系结构的图型表示和映射、骑士旅行、Hamilton回路、图的同构、平面图（第8章）等。定理8.4.3给出了Dijkstra算法正确性的简短优美的证明。
* 树，包括二叉树、树的遍历、最小生成树、决策树、排序的时间下界、树的同构（第9章）等。
* 网络最大流量算法和匹配问题（第10章）。
* Boole代数，重点是Boole代数与组合电路的关系（第11章）。
* 介绍了基于有限自动机的建模技术和应用（第12章）。例12.1.11讨论了SR触发电路。例12.3.19以von Koch雪花为例，给出了分形的语法描述。
* 第13章介绍
Richard Johnsonbaugh是美国芝加哥Depaul大学计算机科学、通信和信息系统学院的教授。他分别在俄亥俄州立大学、耶鲁大学和伊利诺斯大学芝加哥分校获得计算机科学和数学的学士、硕士与博士学位。他多本计算机专著的作者，其中包括C for Scientists and Engineers）、Applications Programming in C++、Object Oriented Programming in C++以及Applications Programming in ANSI C系列。Johnsonbaugh教授有近30年讲授离散数学课程和编程语言课程的教学经验。
第1章 集合与逻辑.
1.1 集合
1.2 命题
1.3 条件命题与逻辑等价
1.4 论证和推理规则
1.5 量词
1.6 嵌套量词
注释
本章复习
本章自测题
上机练习
第2章 证明
2.1 数学系统、直接证明和反例
2.2 更多的证明方法
2.3 归结证明 第1章 集合与逻辑.
1.1 集合
1.2 命题
1.3 条件命题与逻辑等价
1.4 论证和推理规则
1.5 量词
1.6 嵌套量词
注释
本章复习
本章自测题
上机练习
第2章 证明
2.1 数学系统、直接证明和反例
2.2 更多的证明方法
2.3 归结证明
2.4 数学归纳法
2.5 强数学归纳法和良序性
注释
本章复习
本章自测题
.上机练习
第3章 函数、序列和关系
3.1 函数
3.2 序列和串
3.3 关系
3.4 等价关系
3.5 关系矩阵
3.6 关系数据库
注释
本章复习
本章自测题
上机练习
第4章 算法
4.1 简介
4.2 算法举例
4.3 算法的分析
4.4 递归算法
注释
本章复习
本章自测题
上机练习
第5章 数论简介
5.1 因子
5.2 整数的表示和整数算法
5.3 欧几里得算法
5.4 rsa公钥密码系统
注释
本章复习
本章自测题
上机练习
第6章 计数方法与鸽巢原理
6.1 基本原理
6.2 排列与组合
6.3 广义的排列和组合
6.4 排列组合生成算法
6.5 离散概率简介
6.6 离散概率论
6.7 二项式系数和组合恒等式
6.8 鸽巢原理
注释
本章复习
本章自测题
上机练习
第7章 递推关系
7.1 简介
7.2 求解递推关系..
7.3 在算法分析中的应用
注释
本章复习
本章自测题
上机练习
第8章 图论
8.1 简介
8.2 路径和回路
8.3 hamilton回路和旅行商问题
8.4 最短路径算法
8.5 图的表示
8.6 图的同构
8.7 平面图
8.8 顿时错乱问题
注释
本章复习
本章自测题
上机练习
第9章 树
9.1 简介
9.2 树的术语和性质
9.3 生成树
9.4 最小生成树
9.5 二叉树
9.6 树的遍历
9.7 决策树和最短时间排序
9.8 树的同构
9.9 博弈树
注释
本章复习
本章自测题
上机练习
第10章 网络模型
10.1 简介
10.2 最大流算法
10.3 最大流最小割定理
10.4 匹配
注释
本章复习
本章自测题
上机练习
第11章 boolo代数与组合电路
11.1 组合电路
11.2 组合电路的性质
11.3 boole代数
11.4 boole函数与电路合成
11.5 应用
注释
本章复习
本章自测题
上机练习
第12章 自动机、文法和语言
12.1 时序电路和有限状态机.
12.2 有限状态自动机
12.3 语言和文法
12.4 不确定有限状态自动机
12.5 语言和自动机之间的关系
注释
本章复习
本章自测题
上机练习
第13章 计算几何
13.1 最小距点对问题
13.2 计算凸包的一种算法
注释
本章复习
本章自测题
上机练习
附录a 矩阵
附录b 代数学复习
附录c 伪代码
部分习题答案
参考文献
符号表
书单推荐
