离散数学

离散数学是现代数学的一个重要分支，也是计算机科学与技术的理论基础。离散数学是计算机专业的许多专业课程的基础，是数据结构、编译原理、程序设计语言、数据库原理、操作系统、人工智能、算法分析与设计等课程必不可少的前行课程。通过对离散数学的学习，不仅使学生掌握进一步学习其他课程所必需的离散量的结构及其相互关系的数学知识，同时还培养了学生的抽象思维能力和严密的逻辑推理能力，另外还增强了学生使用学过的离散数学知识进行分析问题和解决问题的能力。

本书是在编者多年“离散数学”教学经验的基础上编写而成的。在编写过程中，结合高职高专学生的培养特点和21世纪人才培养需要，不仅考虑了理论体系的完整性与一致性，也很好地体现了高职高专教育的教学要求。本书中的理论以够用为主，不注重理论的推导，有的定理只给出结论，加强了理论与实际的联系，培养学生分析问题、解决问题的能力。在本书的编写过程中，力求通俗易懂、简明扼要，书中除了提供典型实例外，每章后还配有适量的习题供读者练习。

全书共分9章，第1、2章为数理逻辑部分，包括命题逻辑和谓词逻辑等内容。第3～6章为集合论部分，包括集合的基本概念与运算、二元关系、函数、集合的基数等内容。第7章为图论部分，包括图的基本概念、图的矩阵表示、欧拉图、哈密尔顿图、树、平面图等内容。第8、9章为代数系统部分，包括代数系统、半群、独异点、群、环、域、格、有补格、分配格与布尔代数等内容。

本书由贾振华主编，王学军、贾建文、郭辉任副主编。其中，第1章由李建义编写，第2章由贾建文编写，第4，7章由贾振华编写，第3，5，6章由郭辉编写，第8，9章由王学军编写。刘立媛、庄连英、邵温参加了部分章节的习题编写和校对，邹澎涛负责了部分图形的绘制。另外，参加编写的还有李建新、赵辉、李杰、刘俊新等同志。在本书的编写过程中，始终得到安志远教授的帮助，在此表示最真挚的感谢。

在编写本书过程中，我们参考了大量的离散数学教材和资料，在此向有关作者表示衷心的感谢。

由于作者水平有限，书中难免出现一些疏漏和不妥之处，敬请读者批评指正。E-mail：jiazh@nciae.edu.cn。

编者

2003年12月

序
前言
第一部分 数理逻辑
第1章 命题逻辑 1
本章学习目标 1
1.1 命题及其表示法 1
1.1.1 命题的概念 1
1.1.2 命题的表示 3
1.2 命题联结词 3
1.2.1 否定联结词 3
1.2.2 合取联结词 4
1.2.3 析取联结词 4
1.2.4 条件联结词 5
1.2.5 双条件联结词 6
1.2.6 与非联结词 7
1.2.7 或非联结词 8
1.3 命题公式、翻译与解释 8
1.3.1 命题公式 8
1.3.2 命题的翻译 9
1.3.3 命题公式的解释 10
1.4 真值表与等价公式 10
1.4.1 真值表 10
1.4.2 命题公式的分类 12
1.4.3 等价公式 12
1.4.4 置换规则 15
1.5 对偶与范式 17
1.5.1 对偶 17
1.5.2 范式 19
1.5.3 主范式 20
1.6 公式的蕴涵 25
1.6.1 蕴涵的概念 25
1.6.2 基本蕴涵式 26
1.7 其他联结词与最小联结词组 27
1.7.1 其他联结词 27
1.7.2 最小联结词组 28
1.8 命题逻辑推理理论 28
1.8.1 命题逻辑推理理论 28
1.8.2 推理规则 30
1.8.3 推理常用方法 30
本章小结 34
习题 34
第2章 谓词逻辑 37
本章学习目标 37
2.1 谓词逻辑命题的符号化 37
2.2 谓词逻辑公式与解释 41
2.2.1 谓词逻辑的合式公式 41
2.2.2 约束变元与自由变元 42
2.2.3 谓词逻辑公式的解释 43
2.3 谓词逻辑约束公式的等价与蕴涵 44
2.3.1 谓词逻辑的等价公式 44
2.3.2 谓词逻辑的蕴涵公式 48
2.3.3 多个量词的使用 49
2.4 前束范式 50
2.5 谓词演算的推理理论 51
本章小结 55
习题 55
第二部分 集合论
第3章 集合 59
本章学习目标 59
3.1 集合的概念与表示 59
3.1.1 集合的基本概念 59
3.1.2 集合的表示 60
3.2 集合之间的关系 61
3.3 集合的运算 63
3.3.1 集合的并运算 63
3.3.2 集合的交运算 64
3.3.3 集合的补 65
3.3.4 集合的对称差 66
3.4 包含排斥原理 67
本章小结 70
习题 71
第4章 关系 74
本章学习目标 74
4.1 序偶与笛卡儿积 74
4.1.1 有序n元组 74
4.1.2 笛卡儿积的概念 75
4.1.3 笛卡儿积的性质 75
4.2 二元关系及其表示 77
4.2.1 二元关系的概念 77
4.2.2 二元关系的表示 78
4.3 关系的运算 80
4.3.1 关系的交、并、差、补运算 80
4.3.2 关系的复合运算 80
4.3.3 关系的逆运算 84
4.4 关系的性质 85
4.4.1 自反性和反自反性 85
4.4.2 对称性和反对称性 86
4.4.3 传递性 87
4.4.4 关系性质的判定 87
4.5 关系的闭包 93
4.6 等价关系与集合的划分 97
4.6.1 等价关系 97
4.6.2 等价类 98
4.6.3 集合的划分 99
4.7 相容关系 101
4.7.1 相容关系 101
4.7.2 覆盖 103
4.8 偏序关系 105
4.8.1 偏序关系 105
4.8.2 哈斯图 106
4.8.3 全序关系 108
4.8.4 良序关系 110
本章小结 110
习题 110
第5章 函数 114
本章学习目标 114
5.1 函数的概念 114
5.1.1 函数的基本概念 114
5.1.2 几种特殊的函数 115
5.2 复合函数与逆函数 116
5.2.1 复合函数 116
5.2.2 逆函数 117
本章小结 119
习题 119
第6章 集合的基数 120
本章学习目标 120
6.1 基数的概念 120
6.2 可数集和不可数集 121
6.3 基数的比较 123
本章小结 125
习题 125
第三部分 图论
第7章 图论 126
本章学习目标 126
7.1 图的基本概念 127
7.1.1 图的基本类型 127
7.1.2 图中结点的度数 129
7.1.3 完全图 131
7.1.4 图的同构 132
7.1.5 补图 134
7.1.6 子图 138
7.2 路与回路 139
7.2.1 通路与回路 139
7.2.2 图的连通性 140
7.2.3 赋权图的最短通路 144
7.2.4 关键路径 147
7.3 图的矩阵表示 149
7.3.1 图的邻接矩阵表示 149
7.3.2 图的关联矩阵表示 153
7.4 欧拉图 155
7.4.1 欧拉图的定义 155
7.4.2 欧拉图的判定 156
7.5 哈密尔顿图 159
7.5.1 哈密尔顿图 159
7.5.2 哈密尔顿图的判定 160
7.6 树 163
7.6.1 无向树 163
7.6.2 有向树 166
7.6.3 周游算法 169
7.6.4 前缀码与最优树 171
7.7 二部图和平面图 175
7.7.1 二部图 175
7.7.2 平面图 179
本章小结 187
习题 187
第四部分 代数系统
第8章 代数结构 191
本章学习目标 191
8.1 二元运算及其性质 191
8.2 代数系统 196
8.3 半群和独异点 197
8.4 群与子群 199
8.4.1 群 199
8.4.2 群的性质 200
8.4.3 子群 201
8.5 阿贝尔群和循环群 203
8.5.1 阿贝尔群 203
8.5.2 循环群 204
8.6 置换群与伯恩赛德定理 206
8.6.1 置换群 206
8.6.2 伯恩赛德定理（Burnside） 207
8.7 陪集和拉格朗日定理 210
8.7.1 陪集 210
8.7.2 拉格朗日定理 211
8.8 同态与同构 212
本章小结 215
习题 215
第9章 格与布尔代数 220
本章学习目标 220
9.1 格的定义和性质 220
9.1.1 格的定义 220
9.1.2 格的性质 221
9.1.3 格与代数系统的对应 223
9.2 分配格和有补格 224
9.2.1 分配格 224
9.2.2 有补格 226
9.3 布尔代数 228
9.3.1 布尔代数的概念 228
9.3.2 布尔代数的性质 228
9.3.3 布尔表达式 230
本章小结 231
习题 232
参考文献 236

1. 离散数学（第二版） [主编 贾振华]
2. 离散数学（第二版） [主编 邱晓红]
3. 离散数学基础 [主 编 陈华峰 杨 勇]
4. 离散数学 [钟国亮 编著]
5. 离散数学同步辅导及习题全解 [焦艳芳]
6. 离散数学 [邱晓红 主编]
7. 离散数学 [贾振华 主编]