第1章 绪论 1
1.1 符号逻辑与计算机科学 1
1.2 全书结构 4
第2章 集合、关系和函数 9
2.1 集合的基本概念 9
2.2 集合的笛卡儿积 10
2.3 关系 11
2.3.1 二元关系的定义 11
2.3.2 二元关系的运算 12
2.3.3 二元关系的基本特性 14
2.4 函数 16
2.4.1 函数的定义 16
2.4.2 函数的意义 16
2.4.3 特殊函数类 18
习题 19
第3章 集合的可数性 21
3.1 可数性的基本概念 21
3.2 有结构集合的可数性 23
3.3 不可数性 30
习题 33
第4章 图灵可计算性 34
4.1 能行可计算 34
4.2 图灵可计算性 36
4.3 图灵机的例子 38
4.4 图灵机的多种表示方法 40
4.4.1 状态图表示法 40
4.4.2 状态转换表表示法 42
4.4.3 二元组表示法 42
4.5 对定义4.2的进一步讨论 42
4.6 不可计算性 43
4.6.1 图灵不可计算函数的存在性 43
4.6.2 对角线函数的构造 44
4.6.3 停机函数的引入 44
4.6.4 停机函数图灵不可计算性的直接证明 45
4.7 图灵论题与通用图灵机 46
习题 48
第5章 算盘可计算性 49
5.1 算盘机的定义 49
5.2 算盘机例子程序 50
5.3 算盘可计算性 52
5.4 将算盘机编译为图灵机 53
5.4.1 算盘机内存在读写带上的表示 53
5.4.2 算盘机程序的编译方法 54
习题 58
第6章 递归函数可计算性 59
6.1 递归函数的引入 59
6.2 基本函数 60
6.3 递归算子 60
6.3.1 复合算子 61
6.3.2 原始递归算子 63
6.4 递归函数与函数式程序设计 64
6.5 一般递归算子 70
6.6 递归函数的定义 72
6.7 将递归函数编译为算盘机 73
6.7.1 基本函数的编译 74
6.7.2 Cn的编译，以Cn［f,g1,g1］为例 74
6.7.3 Pr的编译 75
6.7.4 Mn的编译 75
习题 76
第7章 递归函数与递归关系 77
7.1 递归集合和递归关系 77
7.2 基于递归集合和递归关系的程序设计 78
7.3 半递归集合和半递归关系 87
7.4 小结 95
习题 95
第8章 不同计算模型之间的等价性 97
8.1 读写带的表示 97
8.2 图灵机动作的表示 98
8.3 图灵机程序的表示 99
8.4 图灵机配置及执行过程的表示 101
8.5 图灵机停机条件与计算结果的提取 102
8.6 图灵机解释函数的构造 103
8.7 关于可计算性的一组重要结论 104
8.8 第一部分总结与后续部分的引入 108
习题 110
第9章 一阶谓词逻辑的基本概念 111
9.1 符号逻辑的引入 111
9.2 符号、语言、公式、项和解释 113
9.3 一阶谓词逻辑语法的定义 116
9.4 正式写法与常用写法对应关系举例 121
9.5 解释与语义 122
9.6 蕴涵关系与逻辑推理 127
9.7 可满足性原理与蕴涵关系的半可判定过程 133
9.8 小结 138
习题 139
第10章 蕴涵关系的不可判定性 142
10.1 用于形式化图灵机的语言及其标准解释 142
10.2 Γ的构造 143
10.2.1 Γb的构造 143
10.2.2 Γi的构造 147
10.2.3 Γp的构造 147
10.2.4 D的构造 148
10.3 主定理的证明 149
习题 152
第11章 模型 153
11.1 模型及其尺寸 153
11.2 同构与模型的数量 154
11.3 等价关系 162
11.4 Lowenheim-Skolem定理和紧致性定理 167
11.5 非标准模型 169
11.6 小结 171
习题 171
第12章 紧致性定理的证明 174
12.1 获得一个被彻底分解的句子集合Γ 174
12.1.1 足够多的空闲常量 174
12.1.2 用覆盖来刻画“彻底分解” 177
12.1.3 获取已彻底分解集合Γ*的过程 178
12.2 为Γ*构造模型 186
12.3 证明的总体结构 189
12.4 小结 190
习题 190
第13章 形式化推理系统 193
13.1 矢列演算及其合理性 194
13.2 用矢列演算进行推理的例子 201
13.3 矢列演算的完备性 204
13.4 矢列演算小结 211
13.5 算术化与一阶谓词逻辑的计算机实现 212
13.6 什么是理想的数学理论 215
13.7 小结 218
习题 218
第14章 计算行为的逻辑刻画 220
14.1 递归函数算术可定义性 221
14.1.1 算术可定义性 221
14.1.2 递归函数的算术可定义性 222
14.1.3 递归函数的初步性 229
14.2 递归函数的可表示性 232
14.2.1 函数的可表示性 233
14.2.2 最小算术理论Q 234
14.2.3 递归函数在Q中的可表示性 235
14.3 小结 241
习题 241
第15章 Godel不完全性定理 243
15.1 对角线引理与Godel第一不完全性定理 243
15.2 不可判定的句子 248
15.3 Godel第一不完全性定理小结 254
15.4 Godel第二不完全性定理 254
15.5 Lob定理的证明 258
15.6 小结与历史回顾 260
习题 262
参考文献 264
索引 266