第一篇 数理逻辑 3
第1章 命题逻辑 3
1.1 命题与联结词 3
1.2 命题公式、翻译和真值表 8
1.3 公式分类与等价式 11
1.4 对偶式与蕴涵式 15
1.5 联结词的扩充与功能完全组 19
1.6 逻辑运算应用举例 22
1.7 公式标准型——范式 26
1.8 公式的主范式 28
1.9 命题逻辑的推理理论 33
1.10 命题逻辑的归结推理 39
习题 42
第2章 谓词逻辑 46
2.1 谓词逻辑中基本概念与表示 46
2.2 谓词公式与翻译 49
2.3 约束变元与自由变元 50
2.4 谓词逻辑的解释与其赋值 53
2.5 真与逻辑有效 56
2.6 谓词逻辑中的等价式 59
2.7 变换规则 61
2.8 谓词逻辑的蕴涵式 62
2.9 谓词逻辑中公式范式 64
2.10 谓词逻辑的推理理论 67
2.11 谓词逻辑的归结推理 71
习题 75
第二篇 集合论 81
第3章 集合论的公理系统 81
3.1 公理导出和基本概念 81
3.2 外延公理与子集公理 83
3.3 集合的表示法 86
3.4 偶集公理与联集公理 87
3.5 极小元与正则公理 91
3.6 无穷公理 92
3.7 幂集公理 93
习题 96
第4章 关系与函数 99
4.1 有序对 99
4.2 笛卡儿积 100
4.3 二元关系及其矩阵表示 101
4.4 关系的性质 107
4.5 等价关系与划分 113
4.6 函数 115
4.7 递归定义函数 118
4.8 序关系 119
4.9 代换公理 124
习题 126
第5章 序数与基数 130
5.1 序数 130
5.2 基数 135
习题 140
第6章 选择公理与无穷集合 141
6.1 选择公理 141
6.2 良序定理 142
6.3 无穷集合 144
习题 147
第三篇 计数 151
第7章 计数原理与技术 151
7.1 基本计数原理 151
7.2 鸽洞原理 153
7.3 容斥原理 155
7.4 排列与组合 156
7.5 递推关系 160
习题 163
第8章 离散概率 166
8.1 随机事件及事件的关系 166
8.2 离散集合上的概率 168
8.3 事件组合的概率 170
8.4 条件概率 172
8.5 伯努利试验与二项分布 175
8.6 随机变量及其数字特征 176
习题 181
第四篇 数论与算法 185
第9章 整数与整除 185
9.1 因数和倍数 185
9.2 素数和合数 186
9.3 最大公因数和最小公倍数 188
9.4 整数分解唯一性定理 191
9.5 模运算与同余 192
9.6 剩余类和剩余系 195
习题 198
第10章 整数与算法 200
10.1 算法的基本概念 200
10.2 欧几里得算法 203
10.3 整数的基底b展开算法 204
10.4 整数的计算机算术运算算法 205
习题 206
第11章 数论应用 208
11.1 一次同余式 208
11.2 一次同余式组 210
11.3 二次同余式和勒让德符号 213
11.4 雅可比符号 220
11.5 数论在计算机科学中的应用 221
习题 224
第五篇 代数结构 229
第12章 代数结构基本概念及性质 229
12.1 代数结构的定义与例 229
12.2 代数结构的基本性质 230
12.3 同态与同构 237
12.4 同余关系 244
12.5 商代数 246
12.6 积代数 248
习题 249
第13章 半群与群 251
13.1 半群和独异点的定义及性质 251
13.2 半群和独异点的同态与同构 254
13.3 积半群 257
13.4 群的基本定义与性质 258
13.5 置换群和循环群 261
13.6 子群与陪集 267
13.7 群的同态与同构 274
习题 278
第14章 环和域 281
14.1 环 281
14.2 子环与理想 283
14.3 环同态与环同构 287
14.4 域 289
14.5 有限域 290
习题 292
第15章 布尔代数 295
15.1 布尔代数的基本定义与性质 295
15.2 格 300
15.3 子布尔代数、积布尔代数和布尔代数同态 303
15.4 布尔代数的原子表示 304
15.5 布尔代数B r 2 307
15.6 布尔表达式及其范式定理 309
习题 312
第六篇图 论 317
第16章 图的基本概念及其矩阵表示 317
16.1 图的基本概念 317
16.2 链（或路）与圈（或回路） 323
16.3 最短链与关键路 329
16.4 图的矩阵表示 332
习题 344
第17章 几类重要的图 348
17.1 欧拉图与哈密顿图 348
17.2 二部图 356
17.3 树 360
17.4 图的生成树 373
17.5 平面图 377
17.6 图的色数问题 384
17.7 图的其他一些参数 387
习题 390
第18章 超图 394
18.1 超图的基本概念与术语 394
18.2 源于数据库理论的超图 396
习题 400
参考文献 401