本书内容共分5篇：数理逻辑、集合论、组合数学、图论和代数系统。数理逻辑介绍了命题逻辑和谓词逻辑；集合论包括集合、关系和函数；组合数学介绍了组合计数和高级计数方法；图论介绍了图的基本概念、特殊图和树；代数系统介绍了群、环和域等，每部分还包括在计算机中的实际应用，并配有大量典型例题和习题。
离散数学是计算机专业的核心基础课，为数据结构、算法分析、计算机网络等后续课程提供数学理论基础。本书介绍离散数学的核心知识，包括：数理逻辑，集合、关系和函数，组合数学，图论，代数结构五个部分；系统阐述相关理论的分析、证明方法，通过丰富的实例讲解实际离散系统的建模。
本书特色：
重视离散数学在科学领域的应用，培养学生应用理论知识分析问题和解决问题的能力。
配有大量典型例题和难易程度不同的习题，通过实践提高计算思维能力。
深入浅出，使抽象理论变得有趣易学，是一本学术性和可读性都很强的教学参考书。
离散数学研究离散结构及其相互关系，是计算机科学与工程各专业的核心基础课。离散数学充分描述了计算机科学离散性的特点，是数据结构、编译系统、数据库原理、计算机组成原理、算法分析、人工智能、信息安全、计算机网络等计算机专业课程的数学基础。学习离散数学不仅能够帮助学生更好地理解与掌握专业课程的教学内容，同时也可以为学生在将来的计算机科学技术的研究和工程应用中打下坚实的理论基础。
作为计算机专业的重要课程，我们在教学过程中参考了国内外许多优秀的离散数学教材，精心组织教学内容，在强化学生的理论基础的同时，注重理论和实践的结合，培养学生运用基本理论解决问题的能力。本教材按照计算机科学与技术专业对离散数学的教学要求、结合教学组老师多年来的教学实践编写而成。
本书对离散数学的核心知识单元进行系统的理论阐述，对离散数学的分析证明方法进行严谨的介绍，并通过丰富的实际应用实例介绍实际离散系统的建模，帮助读者在掌握坚实的基础理论的同时，理解离散数学理论在科学研究和后续课程中的应用，了解理论是如何解决实际应用问题的，从而提高学生应用理论知识分析问题和解决问题的能力，提高计算思维能力。本书分数理逻辑，集合、关系和函数，组合数学，图论，代数结构五部分，每部分均配有大量典型例题和难易程度不同的习题，并紧密结合实际应用，介绍离散数学在科学领域的应用，使学生对离散数学课程的认识由抽象、枯燥转变为易学、有趣。本书内容翔实，理论与实践相结合、深入浅出，是一本学术性和可读性都很强的教学参考书。
本教材适用于计算机科学、计算机工程、软件工程等不同专业方向和不同学校的离散数学教学。与本教材配套的电子教案和习题解答将陆续推出，以便为使用本教材的学生和教师提供参考。
本书的编写和出版得到机械工业出版社的大力支持，得到许多教师及业界同仁的帮助，收到了许多宝贵的意见，在此我们表示衷心的感谢。编写过程中，我们参考了很多离散数学方面的教材和参考资料，在此也向文献作者表示感谢。由于编著者水平有限，书中难免存在疏漏和不妥之处，敬请读者批评指正。
编者
2014年5月
计算机\离散数学
离散数学是计算机专业的核心基础课，为数据结构、算法分析、计算机网络等后续课程提供数学理论基础。本书介绍离散数学的核心知识，包括：数理逻辑，集合、关系和函数，组合数学，图论，代数结构五个部分；系统阐述相关理论的分析、证明方法，通过丰富的实例讲解实际离散系统的建模。
本书特色
•重视离散数学在科学领域的应用，培养学生应用理论知识分析问题和解决问题的能力。
•配有大量典型例题和难易程度不同的习题，通过实践提高计算思维能力。
•深入浅出，使抽象理论变得有趣易学，是一本学术性和可读性都很强的教学参考书。
前言
教学建议
第一部分 数理逻辑
第1章 命题逻辑2
1.1 命题与联结词2
1.1.1 命题的概念2
1.1.2 联结词3
1.2 命题公式及其分类8
1.3 命题演算的关系式10
1.3.1 等价关系式10
1.3.2 全功能联结词集13
1.3.3 对偶式14
1.4 范式15
1.4.1 析取范式和合取范式15
1.4.2 主析取范式和主合取范式16
1.5 命题演算的推理20
1.5.1 推理理论20
1.5.2 推理证明方法21
习题25
第2章 谓词逻辑29
2.1 谓词逻辑的基本概念29
2.1.1 个体词和谓词29
2.1.2 量词31
2.2 谓词合式公式34
2.3 谓词公式的解释和分类35
2.3.1 谓词公式的解释35
2.3.2 谓词公式的分类36
2.4 谓词演算的关系式37
2.5 前束范式40
2.6 谓词演算的推理41
2.6.1 推理理论41
2.6.2 推理问题的证明43
习题48
第二部分 集合、关系和函数
第3章 集合54
3.1 集合及其表示54
3.2 集合间的关系55
3.3 集合的运算57
3.4 自然数62
3.5 集合的特征函数63
习题64
第4章 关系和函数67
4.1 关系的概念67
4.1.1 有序对和有序n元组67
4.1.2 笛卡儿积67
4.1.3 关系的概念69
4.2 关系的表示法71
4.2.1 用集合表示关系71
4.2.2 用关系图表示关系72
4.2.3 用矩阵表示关系73
4.3 关系的运算73
4.3.1 关系的逆运算74
4.3.2 关系的复合运算75
4.4 关系的性质79
4.5 关系的闭包85
4.6 等价关系和等价类91
4.6.1 等价关系91
4.6.2 等价类92
4.7 偏序关系96
4.8 函数100
4.8.1 函数的定义100
4.8.2 特殊函数101
4.8.3 复合函数103
4.8.4 反函数105
4.8.5 集合的基数106
习题108
第三部分 组合数学
第5章 计数114
5.1 基本计数法则114
5.1.1 加法法则114
5.1.2 乘法法则115
5.2 排列与组合117
5.2.1 排列117
5.2.2 组合118
5.2.3 多重集的排列与组合119
5.2.4 二项式定理120
5.3 容斥原理121
5.4 鸽巢原理125
习题126
第6章 高级计数技术128
6.1 递推方程128
6.1.1 求解递推方程130
6.1.2 常系数线性齐次递推方程的求解130
6.1.3 常系数线性非齐次递推方程的求解133
6.2 生成函数136
6.2.1 牛顿二项式系数与牛顿二项式定理136
6.2.2 生成函数的定义及其性质138
6.2.3 生成函数的应用139
6.2.4 指数型生成函数142
习题144
第四部分 图 论
第7章 图论148
7.1 图的基本概念148
7.1.1 无向图和有向图148
7.1.2 度的概念150
7.1.3 图的分类151
7.1.4 子图与补图155
7.1.5 图的同构157
7.2 通路与回路、连通的概念158
7.2.1 通路与回路158
7.2.2 连通的概念160
7.3 图的表示164
7.3.1 邻接表164
7.3.2 邻接矩阵165
7.3.3 可达矩阵169
7.3.4 关联矩阵169
7.4 图的运算172
习题172
第8章 特殊图176
8.1 欧拉图与哈密顿图176
8.1.1 欧拉图176
8.1.2 哈密顿图178
8.2 带权图182
8.2.1 旅行商问题182
8.2.2 最短路径问题182
8.2.3 中国邮路问题184
8.3 匹配和二分图185
8.3.1 匹配185
8.3.2 二分图186
8.4 平面图189
8.4.1 平面图的定义189
8.4.2 平面图的欧拉公式191
8.4.3 对偶图与着色194
习题197
第9章 树200
9.1 树的定义和特性200
9.2 生成树202
9.2.1 生成树的定义202
9.2.2 最小生成树及其应用203
9.3 根树205
9.3.1 有向根树和有序根树205
9.3.2 有序根树的遍历208
9.4 根树的应用209
9.4.1 前缀码209
9.4.2 最优二元树和赫夫曼编码211
9.4.3 决策树212
习题213
第五部分 代数结构
第10章 代数系统218
10.1 代数系统的概念和性质218
10.1.1 二元运算及其性质218
10.1.2 代数系统和子代数221
10.1.3 代数系统的性质222
10.1.4 代数系统的分类224
10.2 代数系统的同态和同构225
10.3 半群227
10.4 群229
10.4.1 群及其基本性质229
10.4.2 子群232
10.5 循环群和置换群233
10.5.1 循环群233
10.5.2 置换群235
10.6 环和域236
习题238
第11章 格与布尔代数240
11.1 格240
11.1.1 格的基本概念240
11.1.2 分配格243
11.1.3 有界格和有补格245
11.2 布尔代数246
11.2.1 布尔代数的基本概念246
11.2.2 布尔表达式与布尔函数248
11.2.3 布尔代数和数字电路249
习题251
参考文献254
