第1篇 预备知识 1
第1章 集合基础 1
1.1 集合与子集 1
1.1.1 集合 1
1.1.2 集合的表示 2
1.1.3 集合与元素的关系 3
1.1.4 外延性原理 3
1.1.5 集合之间的关系与子集 4
1.2 集合的运算 6
1.3 无限集的基本概念 9
1.3.1 自然数集合与可列集合 9
1.3.2 不可数集合 12
1.4 有限集合的计数 12
1.4.1 鸽笼原理 12
1.4.2 容斥原理 13
1.5 习题 14
第2章 序列（有序组） 18
2.1 序列与子序列 18
2.2 序列的运算 19
2.3 习题 20
第3章 整数中的除法 21
3.1 整除 21
3.2 最大公因子 22
3.3 最小公倍数 24
3.4 习题 25
第4章 矩阵的基础知识 27
4.1 矩阵的定义 27
4.2 矩阵的运算及性质 28
4.3 布尔矩阵及运算 30
4.4 习题 32
第2篇 数理逻辑 33
第5章 命题逻辑 33
5.1 命题与命题联结词 34
5.1.1 命题 34
5.1.2 命题联结词 35
5.2 命题公式、解释与真值表 40
5.2.1 命题公式 40
5.2.2 公式的解释与真值表 41
5.2.3 一些特殊的公式 43
5.2.4 等价公式 45
5.3 联结词的完备集 50
5.3.1 联结词的扩充 50
5.3.2 与非、或非和异或的性质 51
5.3.3 全功能联结词集合 52
5.4 范式 53
5.4.1 析取范式和合取范式 53
5.4.2 主析取范式和主合取范式 54
5.5 命题逻辑的推理理论 61
5.5.1 推理的基本概念和推理形式 61
5.5.2 判断有效结论的常用方法 62
5.6 习题 69
第6章 谓词逻辑 73
6.1 谓词逻辑中的基本概念与表示 73
6.1.1 谓词 74
6.1.2 量词 76
6.1.3 谓词的语言翻译 79
6.2 谓词公式与解释 80
6.2.1 谓词的合适公式 80
6.2.2 自由变元和约束变元 82
6.2.3 公式的解释 84
6.2.4 一些特殊的公式 85
6.2.5 等价关系与蕴涵关系 87
6.3 范式 91
6.3.1 前束范式 91
6.3.2 Skolem标准形 92
6.4 谓词演算的演绎与推理 93
6.4.1 推理规则 93
6.4.2 谓词演算的综合推理方法 95
6.5 习题 100
第7章 数理逻辑在计算机科学中的应用 105
7.1 命题逻辑在计算机科学中的应用 105
7.2 谓词逻辑在计算机科学中的应用 108
7.2.1 谓词逻辑与数据子语言 108
7.2.2 谓词逻辑与逻辑程序设计语言 110
第3篇 二元关系 119
第8章 二元关系 119
8.1 二元关系及其表示法 119
8.1.1 序偶与笛卡儿积 119
8.1.2 关系的引入 121
8.1.3 关系的定义 121
8.1.4 二元关系 122
8.1.5 关系的表示法 123
8.2 关系的运算 125
8.2.1 关系的交、并、补、差运算 125
8.2.2 关系的复合运算 125
8.2.3 关系的逆运算 126
8.2.4 关系运算的性质 127
8.3 关系的性质 130
8.3.1 自反性与反自反性 130
8.3.2 对称性与反对称性 131
8.3.3 传递性 133
8.3.4.关系性质的证明 135
8.3.5 利用集合运算来判断关系的性质 136
8.3.6 关系性质的保守性 137
8.4 关系的闭包运算 138
8.4.1 关系的限制与扩充 138
8.4.2 关系的闭包 140
8.5 习题 143
第9章 特殊关系 147
9.1 等价关系 147
9.1.1 集合的划分 147
9.1.2 等价关系 148
9.1.3 等价类与商集 149
9.1.4 等价关系与划分 150
9.2 次序关系 152
9.2.1 次序关系的定义 152
9.2.2 偏序集的哈斯图 153
9.2.3 偏序集中的特殊元素 154
9.2.4 全序与良序 156
9.3 习题 157
第10章 函数 160
10.1 函数的基本概念 160
10.2 函数的性质 161
10.3 函数的复合运算 163
10.4 函数的逆运算 165
10.5 置换 166
10.6 习题 167
第11章 关系在计算机科学中的应用 169
11.1 关系在关系数据库中的应用 169
11.2 关系代数与数据子语言 172
11.3 关系及闭包与计算机程序 177
11.4 划分在计算机中的应用 177
第4篇 图论 180
第12章 图 180
12.1 图的基本概念 180
12.1.1 图的定义 180
12.1.2 结点的度数 182
12.1.3 子图与补图 184
12.1.4 图的同构 185
12.1.5 图的操作 186
12.2 通路与回路 186
12.3 无向图的连通性 188
12.4 有向图的连通性 190
12.5 图的矩阵表示 192
12.5.1 邻接矩阵 192
12.5.2 可达性矩阵 197
12.6 习题 199
第13章 特殊图 204
13.1 欧拉图 204
13.2 哈密尔顿图 207
13.3 树 211
13.3.1 无向树 211
13.3.2 生成树 213
13.3.3 最小生成树 214
13.3.4 有向树 216
13.4 偶图 222
13.5 平面图 225
13.5.1 观察法 226
13.5.2 欧拉公式 227
13.5.3 库拉托夫斯基定理 229
13.5.4 对偶图 230
13.6 图的着色 231
13.6.1 结点着色 231
13.6.2 边着色 233
13.7 习题 234
第14章 图论在计算机科学中的应用 240
14.1 计算机鼓轮设计 240
14.2 巡回售货员问题 241
14.2.1 最邻近算法 241
14.2.2 抄近路算法 242
14.3 中国邮路问题 243
14.4 前缀码 245
14.5 波兰符号法与逆波兰符号法 246
14.6 网络 248
14.6.1 运输网络 248
14.6.2 关键道路法 252
14.6.3 通信网络 254
第5篇 代数系统与布尔代数 255
第15章 代数系统 255
15.1 代数系统 255
15.1.1 代数运算 255
15.1.2 代数运算的性质 257
15.1.3 代数系统 260
15.2 同态与同构 264
15.2.1 同态与同构 264
15.2.2 同态的性质 266
15.3 习题 267
第16章 群论 271
16.1 半群与含幺半群 271
16.1.1 半群与含幺半群 271
16.1.2 循环半群与循环独异点 273
16.2 群的基本概念与性质 275
16.2.1 群的定义和基本性质 277
16.2.2 元素的周期 278
16.2.3 子群 281
16.2.4 群的同态 284
16.3 特殊群 285
16.3.1 交换群（阿贝尔群） 285
16.3.2 循环群 286
16.4 陪集与拉格朗日定理 288
16.4.1 陪集 288
16.4.2 拉格朗日定理 291
16.5 不变子群与商群 291
16.5.1 不变子群（正规子群） 291
16.5.2 商群 293
16.6 习题 295
第17章 环与域 298
17.1 环 298
17.2 域 299
17.3 习题 300
第18章 格与布尔代数 301
18.1 格 301
18.1.1 格的定义 301
18.1.2 格的另一定义 303
18.1.3 格的性质 306
18.1.4 子格 307
18.1.5 格的同态与同构 308
18.2 特殊格 310
18.2.1 分配格 310
18.2.2 模格 312
18.2.3 有界格 312
18.2.4 有补格 313
18.3 布尔代数 315
18.3.1 布尔代数 315
18.3.2 布尔表达式 317
18.4 习题 319
第19章 代数系统的应用 322
19.1 有限自动机 322
19.2 计数问题 323
19.2.1 理论基础 323
19.2.2 图的计数问题 325
19.2.3 开关线路的计数问题 326
19.3 纠错码 328
19.3.1 纠错码简介 328
19.3.2 纠错码的纠错能力 329
19.3.3 纠错码的选择 330
19.3.4 群码的校正 334
19.4 开关电路 336
19.4.1 开关函数 336
19.4.2 逻辑门 339
19.4.3 全加器的逻辑设计 341