离散数学

本书是编者在多年离散数学教学实践经验的基础上，针对应用型本科教学的特点，参考了国内外多种教材编写而成的。应用型本科注重理论，以够用为限，重点突出，加强理论与实际的联系。本书力求理论体系完整、科学严谨，内容叙述深入浅出、简明扼要，概念尽量用例子加以说明。本书强化基本概念的理解，注重基本理论的证明方法。书中配有典型例题，各章后面配有适量典型习题供学生练习。

离散数学是现代数学的一个重要分支，它的研究对象是各种离散量的结构及离散量之间的关系，在数据结构、编译系统、程序设计语言、数据库原理、操作系统、人工智能、计算机图形学、软件工程、网络与分布式计算以及计算机体系结构等领域中都得到广泛的应用。因此，离散数学是计算机专业学生的一门重要的专业基础课程。

通过对离散数学的学习，不仅能使学生掌握进一步学习其他课程所必需的数学基础知识，还可以培养学生的抽象思维能力和严密的逻辑推理能力，同时也可以提高学生发现问题、分析问题和解决问题的能力。

本书是编者在多年离散数学教学实践经验的基础上，针对应用型本科教学的特点，参考了国内外多种教材编写而成的。应用型本科注重理论，以够用为限，重点突出，加强理论与实际的联系。本书力求理论体系完整、科学严谨，内容叙述深入浅出、简明扼要，概念尽量用例子加以说明。本书强化基本概念的理解，注重基本理论的证明方法。书中配有典型例题，各章后面配有适量典型习题供学生练习。

全书共分11章，主要内容有：

第1章和第2章分别介绍命题逻辑和谓词逻辑的基本概念、等值演算和推理理论。第3章至第6章为集合论，介绍了集合的基本概念和运算、二元关系、函数、基数等内容。第7章至第9章为图论，介绍了图的基本概念、图的矩阵表示、欧拉图、哈密尔顿图、树、平面图等内容。第10章和第11章为代数系统，介绍了代数系统、半群、独异点、群、环、域、格、有补格、分配格和布尔代数等内容。

本书第1章至第3章由贾振华编写，第4章由贾振华和李新荣共同编写；第5章和第6章由李瑛编写；第7章和第8章由李新荣编写；第9章至第11章由黄中升编写。赵辉、李杰、崔玉宝、赵丽艳等同志参加了部分章节的习题编写和校对工作。

在编写过程中，作者参考了大量的离散数学教材和相关的文献资料，从中汲取了许多好的思想，引用了不少有用的素材，在此一并向有关作者表示感谢。还要感谢中国水利水电出版社的编辑和领导以及院系领导对教材出版的支持和帮助。

由于作者水平有限，书中难免出现一些错误和不妥之处，敬请读者不吝指正。作者电子邮箱：jiazhenhualf@163.com。

编 者

2006年10月

序
前言
第一部分 数理逻辑
 第1章 命题逻辑 2
本章学习目标 2
1.1 命题和命题联结词 2
1.1.1 命题 2
1.1.2 命题联结词 3
1.2 命题公式与解释 7
1.2.1 命题公式 7
1.2.2 命题公式的解释 9
1.3 真值表与等价公式 10
1.3.1 真值表 10
1.3.2 命题公式的分类 11
1.3.3 等价公式 12
1.3.4 代入规则和替换规则 15
1.4 对偶定理 19
1.5 范式 20
1.5.1 合取范式和析取范式 20
1.5.2 主析取范式和主合取范式 22
1.6 公式的蕴涵 27
1.6.1 蕴涵的概念 27
1.6.2 蕴涵式的证明方法 28
1.6.3 基本蕴涵式 29
1.7 其他联结词与最小联结词组 29
1.7.1 其他联结词 29
1.7.2 最小联结词组 32
1.8 命题逻辑推理理论 33
1.8.1 命题逻辑推理理论 33
1.8.2 推理规则 35
1.8.3 判断有效结论的常用方法 36
本章小结 39
习题一 40
 第2章 谓词逻辑 43
本章学习目标 43
2.1 谓词逻辑命题的符号化 43
2.1.1 个体词与谓词 43
2.1.2 量词 45
2.1.3 谓词逻辑中命题的符号化 45
2.2 谓词逻辑公式与解释 47
2.2.1 谓词逻辑的合式公式 47
2.2.2 谓词的约束和替换 49
2.2.3 谓词逻辑公式的解释 50
2.3 谓词逻辑公式的等价与蕴涵 52
2.3.1 谓词逻辑的等价公式 52
2.3.2 谓词逻辑的蕴涵公式 55
2.3.3 多个量词的使用 56
2.4 前束范式 57
2.5 谓词逻辑的推理理论 59
本章小结 63
习题二 63
第二部分 集合论
 第3章 集合 68
本章学习目标 68
3.1 集合的概念与表示 68
3.1.1 集合的基本概念 68
3.1.2 集合的表示 68
3.1.3 集合之间的关系 69
3.2 集合的运算 72
3.2.1 集合的交运算 72
3.2.2 集合的并运算 73
3.2.3 集合的补 74
3.2.4 集合的对称差 75
3.3 包含排斥原理 76
本章小结 79
习题三 79
 第4章 关系 82
本章学习目标 82
4.1 序偶与笛卡儿积 82
4.1.1 有序n元组 82
4.1.2 笛卡儿积的概念 83
4.1.3 笛卡儿积的性质 83
4.2 二元关系及其表示 85
4.2.1 二元关系的概念 85
4.2.2 二元关系的表示 86
4.3 关系的运算 88
4.3.1 关系的交、并、差、补运算 88
4.3.2 关系的复合运算 89
4.3.3 关系的逆运算 92
4.4 关系的性质 93
4.4.1 自反性和反自反性 93
4.4.2 对称性和反对称性 94
4.4.3 传递性 94
4.4.4 关系性质的判定 95
4.5 关系的闭包 100
4.6 等价关系与集合的划分 105
4.6.1 等价关系 105
4.6.2 等价类 106
4.6.3 集合的划分 106
4.7 相容关系 109
4.7.1 相容关系 109
4.7.2 覆盖 110
4.8 偏序关系 112
4.8.1 偏序关系 112
4.8.2 哈斯图 113
4.8.3 全序关系 114
4.8.4 良序关系 116
本章小结 117
习题四 117
 第5章 函数 120
本章学习目标 120
5.1 函数的概念 120
5.2 函数的性质 121
5.3 复合函数和逆函数 124
5.3.1 复合函数 124
5.3.2 逆函数 125
5.4 置换 127
本章小结 128
习题五 128
 第6章 集合的基数 130
本章学习目标 130
6.1 基数的概念 130
6.2 可数集和不可数集 132
6.2.1 可数集 132
6.2.2 不可数集 134
6.3 基数的比较 134
本章小结 136
习题六 136
第三部分 图论
 第7章 图 140
本章学习目标 140
7.1 图的基本概念 140
7.1.1 图论的发展 140
7.1.2 图的基本概念 141
7.2 通路与回路 146
7.3 图的连通性 148
7.3.1 无向图的连通性 148
7.3.2 有向图的连通性 150
7.4 图的矩阵表示 153
7.4.1 图的邻接矩阵 153
7.4.2 图的关联矩阵 155
7.4.3 有向图的可达矩阵 156
7.5 图的应用 158
7.5.1 带权图的最短通路 158
7.5.2 带权图的关键路径 161
本章小结 162
习题七 163
 第8章 欧拉图与哈密尔顿图 166
本章学习目标 166
8.1 欧拉图 166
8.1.1 欧拉图的定义 166
8.1.2 欧拉图的判定 167
8.1.3 求欧拉回路的算法 168
8.1.4 欧拉图的应用 169
8.2 哈密尔顿图 170
8.2.1 哈密尔顿图 170
8.2.2 哈密尔顿图的判定 170
本章小结 171
习题八 172
 第9章 特殊图 173
本章学习目标 173
9.1 树 173
9.1.1 无向树 173
9.1.2 生成树与最小生成树 175
9.1.3 有向树与根树 177
9.2 二部图 180
9.3 平面图 182
9.3.1 平面图的定义 182
9.3.2 欧拉公式 183
9.3.3 库拉托夫斯基定理 185
9.3.4 平面图的对偶图 186
本章小结 188
习题九 188
第四部分 代数系统
 第10章 代数结构 192
本章学习目标 192
10.1 二元运算及其性质 192
10.1.1 二元运算 192
10.1.2 二元运算的性质 194
10.2 代数系统 196
10.3 群的定义 198
10.3.1 半群 198
10.3.2 群 199
10.3.3 群的性质 200
10.4 子群 202
10.4.1 子群 202
10.4.2 子群的判定 203
10.5 阿贝尔群和循环群 204
10.5.1 阿贝尔群 204
10.5.2 循环群 205
10.6 置换群与伯恩赛德定理 206
10.6.1 置换群 206
*10.6.2 伯恩赛德定理（Burnside） 209
10.7 陪集与拉格朗日定理 211
10.7.1 陪集 211
10.7.2 正规子群和商群 213
10.7.3 拉格朗日定理 214
10.8 群的同态与同构 215
本章小结 217
习题十 218
 第11章 格与布尔代数 221
本章学习目标 221
11.1 格的定义和性质 221
11.1.1 格的定义 221
11.1.2 格的对偶原理 222
11.1.3 格的性质 222
11.1.4 子格和格的同态 225
11.2 分配格和有补格 227
11.2.1 模格 227
11.2.2 分配格 227
11.2.3 有界格 229
11.2.4 有补格 229
11.3 布尔代数 230
11.3.1 布尔代数的定义及性质 230
11.3.2 布尔代数的同构与同态 231
11.3.3 布尔代数的表示理论 234
本章小结 235
习题十一 236
参考文献 238

1. 工程数学 [主编 郭立娟 王海]
2. 应用数学 [梁玮 蔡超 高志]
3. 大学应用数学 [主编 郭立娟]
4. 高等数学导学篇（下册） [主编 李文婧 胡雷 尹金生]
5. 高等数学导学篇（上册） [主编 李文婧 胡雷 尹金生]
6. 高等数学（下册） [主编 李爱芹 胡雷 尹金生]
7. 高等数学（上册） [主编 李爱芹 胡雷 尹金生]
8. 高等数学（下册） [秦红兵]
9. 应用数学 [主编 刘东海 刘丽瑶]
10. 高等数学（上册） [主编 白莉 秦红兵]
11. 高等数学（下册）（第二版） [主编 何春江]
12. 高等数学（上册）（第二版） [主编 何春江]
13. 高等数学 [主编 刘彦辉 张 静]
14. 应用数学（第二版） [主编 刘丽瑶]
15. 数学（下册） [单凤娟 刘艳平 李杨 马秀芬 ]
16. 数学（上册） [单凤娟 刘艳平 李杨 马秀芬 ]
17. 应用数学基础 [主编 刘彦辉 李先明]
18. 高等数学学习辅导与习题解答（第三版） [主编 翟秀娜]
19. 离散数学（第二版） [主编 贾振华]
20. 数学（二）职业模块 [李丽君 吴白旺 杨勇]
21. 高等数学（下册） [何春江]
22. 数学（一）职业模块 [主编 杨勇 海敏娟 禇丽娜]
23. 高等数学（上册） [何春江]
24. 应用数学（第二版•下册） [主 编 孙振营 徐自立]
25. 应用数学（第二版•上册） [主编 孙振营 夏云青]
26. 数学（一）职业模块 [主编 杨勇 海敏娟 禇丽娜]
27. 计算机数学基础（第二版） [主编 何春江]
28. 高等数学（下册）课后习题详解及考研题型解析 [何红洲]
29. 高等数学学习指导与习题解答（经管、文科类） [主 编 郭照庄]
30. 高等数学（下册） [何红洲]