第一篇 数理逻辑 3
第1章 命题逻辑 3
1.1 命题与联结词 3
1.1.1 命题基本概念 3
1.1.2 命题联结词 4
1.1.3 复合命题 6
1.2 命题公式 9
1.2.1 定义 9
1.2.2 赋值 10
1.2.3 真值表技术 11
1.3 等值演算 14
1.3.1 基本等值式 14
1.3.2 等值演算过程 15
1.3.3 对偶公式和内否公式 17
1.4 命题公式的范式 20
1.4.1 析取范式和合取范式 20
1.4.2 主范式 21
1.5 联结词的功能完全集 25
1.5.1 真值函数 25
1.5.2 功能完全集 26
1.6 永真蕴涵式 29
1.6.1 基本永真蕴涵式 29
1.6.2 证明永真蕴涵式的方法 31
1.7 命题逻辑推理 34
1.8 命题逻辑归结推理法 37
1.9 命题逻辑推理的机械化方法 39
第2章 谓词逻辑 45
2.1 谓词逻辑的基本概念 45
2.1.1 谓词的概念 45
2.1.2 量词的概念 46
2.2 谓词逻辑公式 49
2.2.1 合式公式 49
2.2.2 约束变元和自由变元 50
2.2.3 赋值 51
2.2.4 换名规则和替换规则 53
2.3 谓词逻辑的等值演算与前束范式 55
2.3.1 基本等值式 55
2.3.2 前束范式 57
2.4 Skolem标准型 59
2.4.1 ？前束范式 59
2.4.2 无？前束范式 61
2.5 谓词逻辑的推理理论 63
2.5.1 基本永真蕴涵式 63
2.5.2 推理规则 63
2.5.3 推理实例 64
2.6 谓词逻辑的归结推理法 69
2.6.1 归结证明过程 69
2.6.2 归结证明实例 70
第二篇 集合论 75
第3章 集合 75
3.1 集合的定义 75
3.2 集合的基本运算 79
3.3 有限集合的计数 88
3.4 集合表达式的相等与包含 92
3.5 集合的特征函数 96
第4章 关系 99
4.1 二元关系 99
4.2 二元关系的表示及按性质分类 101
4.2.1 二元关系的关系矩阵和关系图表示 101
4.2.2 二元关系的按性质分类 103
4.3 二元关系的运算 107
4.4 二元关系的合成 111
4.5 关系的闭包 116
4.6 等价关系和偏序关系 120
4.6.1 等价关系 121
4.6.2 偏序关系 123
第5章 函数 128
5.1 函数的基本概念 128
5.2 函数的性质 129
5.3 函数的复合与反函数 133
5.4 可逆函数集与置换 136
5.5 二元运算 138
5.6 基数 141
第三篇 代数系统 147
第6章 半群、语言和自动机 147
6.1 半群与语言 147
6.2 语言和文法 150
6.3 有限状态机 154
6.4 有限状态自动机 155
6.5 语言与自动机的关系 159
第7章 群、环和域 163
7.1 群的基本概念 163
7.2 子群 165
7.3 群的同态与同构 167
7.4 子群的陪集 169
7.5 对称群、置换群、正规性与商群 171
7.6 群在集合上的作用 174
7.7 同态基本定理与同构定理 177
7.8 环的基本概念 178
7.9 子环、理想与商环 181
7.10 交换环中的因子分解 183
7.11 多项式环 186
7.12 多项式环的因子分解 187
7.13 域的基本概念 189
7.14 分裂域 191
7.15 有限域 193
第8章 格与布尔代数 196
8.1 格的概念 196
8.2 分配格 199
8.3 有补格 201
8.4 布尔代数 202
8.5 布尔表达式 204
8.6 数字电路与最小化 205
第四篇 组合分析与算法数论 211
第9章 组合分析 211
9.1 计数 211
9.2 排列与组合 213
9.3 递推序列 216
9.4 抽屉原理 222
9.5 生成函数 226
第10章 算法数论 232
10.1 整数论 232
10.2 与整数有关的典型算法 240
10.3 素性测试、因数分解与公钥密码学 245
10.3.1 素性测试 245
10.3.2 因数分解 248
10.3.3 公钥密码 252
10.4 有限域上的椭圆曲线算术和ECC 255
10.5 配对和基于身份的公钥密码体制 259
10.5.1 双线性配对 260
10.5.2 基于身份的密码 263
第五篇 图论 267
第11章 无向图 267
11.1 无向图的基本概念 267
11.2 无向图的表示 271
11.3 无向图的连通性 273
11.4 欧拉图与哈密顿图 277
11.4.1 欧拉图 277
11.4.2 哈密顿图 279
11.5 最短通道问题 282
第12章 平面图与图着色 287
12.1 平面图的基本概念 287
12.2 欧拉公式和极大平面图 288
12.3 平面图的对偶图 292
12.4 图着色 293
第13章 有向图 296
13.1 有向图的基本概念 296
13.2 有向图的连通性 298
第14章 树 302
14.1 基本定义和性质 302
14.2 生成树与最小生成树 304
14.3 有根树 307
14.4 二叉树和哈夫曼树 310
参考文献 313