第1篇 集合论 1
第1章 集合 1
1.1 集合的基本概念及性质 1
1.1.1 集合的基本概念 1
1.1.2 集合的表示形式 2
1.1.3 集合的基本性质 4
1.1.4 集合之间的关系 4
1.2 集合的运算 6
1.2.1 集合的交运算 6
1.2.2 集合的并运算 6
1.2.3 集合的补运算 7
1.2.4 集合的对称差运算 8
1.2.5 集合的广义交和广义并运算 8
1.3 有限集合的计数 9
1.3.1 鸽巢原理 9
1.3.2 包容排斥原理 9
1.4 集合的运算定律 11
思考与练习题 11
第2章 关系 14
2.1 笛卡尔积概念 14
2.1.1 序偶 14
2.1.2 笛卡尔积 15
2.2 二元关系及其表示方法 17
2.2.1 二元关系的定义 17
2.2.2 二元关系的表示方法 18
2.3 二元关系的运算 19
2.3.1 关系的基本运算 19
2.3.2 关系的复合运算 20
2.3.3 关系的幂运算 25
2.3.4 关系的逆运算 26
2.3.5 关系的限制和像 28
2.4 二元关系的性质 29
2.4.1 自反性与反自反性 29
2.4.2 对称性、反对称性、非对称性 31
2.4.3 传递性 33
2.4.4 关系性质的保持性 35
2.5 二元关系的闭包 37
2.5.1 关系闭包定义 38
2.5.2 关系闭包涉及的定理 39
2.5.3 关系闭包的求解方法总结 42
2.6 等价关系 44
2.6.1 等价关系定义 44
2.6.2 等价类与商集 45
2.6.3 等价类与划分 47
2.7 相容关系与覆盖 49
2.7.1 相容关系与覆盖的定义 49
2.7.2 最大相容类 50
2.8 序关系 52
2.8.1 偏序关系 53
2.8.2 全序关系与良序关系 59
2.8.3 拟序关系 60
思考与练习题 60
第3章 函数 65
3.1 函数的基本概念 65
3.1.1 函数的引入 65
3.1.2 函数的定义及特点 65
3.2 特殊函数 67
3.2.1 单射、满射与双射 67
3.2.2 常用函数 69
3.3 函数的运算 69
3.3.1 函数的复合运算 70
3.3.2 函数的逆运算 72
3.4 集合的基数 74
3.4.1 基数的定义 74
3.4.2 可数集的定义及性质 75
3.4.3 集合基数的比较 76
思考与练习题 77
第2篇 图论 80
第4章 图的基本概念 80
4.1 图的基本概念 80
4.1.1 图的基本概念 81
4.1.2 图中结点的度数 83
4.1.3 可图化的 85
4.1.4 图的同构 86
4.1.5 完全图与正则图 88
4.1.6 子图与补图 89
4.1.7 图的操作与运算 90
4.2 图的通路与图的连通性 91
4.2.1 通略 91
4.2.2 图的连通性 94
4.3 图的矩阵表示 98
4.3.1 图的关联矩阵 98
4.3.2 有向图的邻接矩阵 100
4.3.3 图的可达矩阵 102
思考与练习题 104
第5章 特殊图 107
5.1 欧拉图 107
5.1.1 欧拉图定义 107
5.1.2 欧拉图判定定理 108
5.2 汉密尔顿图 111
5.2.1 汉密尔顿图定义 111
5.2.2 汉密尔顿图判定定理 111
5.3 二部图与匹配 116
5.3.1 二部图 116
5.3.2 匹配 118
5.4 平面图与着色 119
5.4.1 平面图的定义 119
5.4.2 平面图的欧拉公式 122
5.4.3 平面图的判定定理 124
5.4.4 平面图的对偶图 125
5.4.5 平面图的着色 128
思考与练习题 131
第6章 无向树 134
6.1 无向树概念 134
6.1.1 无向树定义 134
6.1.2 无向树性质 135
6.2 生成树与最小生成树 136
6.2.1 生成树 136
6.2.2 最小生成树 138
思考与练习题 144
第7章 有向树 146
7.1 有向树概念 146
7.2 完全有向树与正则有向树 147
7.3 最优二叉树 148
7.3.1 最优二叉树定义 148
7.3.2 最优二叉树求解 149
7.3.3 哈夫曼编码 150
7.4 二叉树的遍历 151
思考与练习题 152
第3篇 数理逻辑 154
第8章 命题逻辑 154
8.1 命题与联结词 154
8.1.1 命题的基本概念 155
8.1.2 联结词 156
8.2 命题公式 159
8.2.1 命题公式定义 159
8.2.2 命题公式的赋值 160
8.2.3 命题公式的类型 161
8.2.4 命题的等价关系 162
8.2.5 命题的蕴涵关系 165
8.3 范式 167
8.3.1 命题的一般范式 167
8.3.2 命题的主范式 169
8.3.3 范式的应用 172
8.4 联结词完备集 175
8.5 命题逻辑的推理理论 179
8.5.1 命题逻辑推理规则 179
8.5.2 命题逻辑推理方法 182
思考与练习题 184
第9章 谓词逻辑 188
9.1 谓词逻辑的基本概念 188
9.1.1 谓词与个体 189
9.1.2 量词 190
9.2 谓词公式 191
9.2.1 谓词公式定义 191
9.2.2 谓词公式的约束变元与自由变元 194
9.2.3 谓词公式的解释 195
9.2.4 谓词公式的类型 196
9.2.5 谓词的等价关系 197
9.2.6 谓词的蕴涵关系 199
9.3 谓词逻辑的范式 200
9.3.1 前束范式 200
9.3.2 Skolem范式 202
9.4 谓词逻辑的推理理论 202
9.4.1 谓词逻辑的推理规则 202
9.4.2 谓词逻辑的推理方法 204
思考与练习题 207
第4篇 代数结构 210
第10章 群 210
10.1 群的定义 210
10.1.1 二元运算 210
10.1.2 代数系统 211
10.1.3 半群和群 211
10.2 交换群、置换群和循环群 213
10.2.1 交换群 213
10.2.2 置换群和循环群 214
10.3 子群、正规子群与商群 214
10.3.1 子群 214
10.3.2 正规子群 215
10.3.3 商群 215
10.4 群的同态与同构 216
思考与练习题 218
第11章 环与理想 219
11.1 基本概念 219
11.2 子环与环的同态 220
11.3 多项式环与欧几里德环 221
11.3.1 多项式环 221
11.3.2 欧几里德环 222
11.4 理想与商环 222
11.4.1 理想 222
11.4.2 商环 223
思考与练习题 224
第12章 域 226
12.1 扩域 226
12.2 代数元与超越元 227
12.3 有限域 229
12.4 本原元与本原多项式 232
思考与练习题 236
第5篇 综合应用 238
第13章 数理逻辑的应用实例 238
13.1 命题逻辑的应用实例 238
13.2 谓词逻辑的应用实例 242
思考与练习题 250
第14章 关系的应用实例 251
14.1 关系及运算在关系数据库中的应用 251
14.1.1 关系数据库简介 251
14.1.2 关系在关系数据库中的应用 252
14.1.3 关系运算在关系数据库中的应用 252
14.2 关系闭包的应用 257
14.3 等价关系与划分的应用 257
14.4 序关系的应用 258
思考与练习题 259
第15章 图论的应用实例 261
15.1 平面图及着色的应用 261
15.1.1 地图的着色 261
15.1.2 交通信号灯问题 262
15.1.3 公共事业问题 262
15.1.4 冰箱分隔问题 263
15.1.5 排课表问题 263
15.2 通路的应用 264
15.2.1 边权为1的两点最短路径——Moore算法 264
15.2.2 单源最短路径——Dijkstra算法 265
15.2.3 所有点对间最短路径——Floyd算法 266
15.2.4 关键道路法 267
15.3 欧拉图的应用实例 272
15.3.1 计算机鼓轮设计问题 272
15.3.2 中国邮路问题 273
15.4 汉密尔顿图的应用实例 273
15.5 树的应用 275
15.5.1 数据压缩问题 275
15.5.2 最优二叉检索树问题 276
15.5.3 决策树与博弈树问题 278
15.6 网络流 283
15.6.1 运输网 283
15.6.2 扩展的运输网 291
15.6.3 匹配问题 291
思考与练习题 292
第16章 有限自动机与语言 294
16.1 单词与语言 294
16.2 正则式和正则语言 296
16.3 有限状态自动机 297
16.4 文法和语言 298
思考与练习题 303
参考文献 307