前言 1
0 预备知识 1
0.1 集论基本概念 1
引言 3
0.2 Peano自然数公理 3
0.3 可数集 5
1 命题演算 10
1.1 真值函数 10
1.2.1 自由命题代数L(X) 13
1.2 命题演算L 13
1.2.2 命题演算L的建立 17
1.2.3 演绎定理 22
1.2.4 反证律与归谬律 25
1.2.5 析取，合取与等值 30
1.2.6 命题演算的其他系统介绍 32
1.3 命题演算L的语义学 36
1.3.1 L(X)的赋值 37
1.3.2 L的解释 41
1.3.3 公式的真值函数 44
1.3.4 永真式和代换定理 47
1.3.5 等值公式和对偶律 51
1.3.6 析取范式与合取范式 55
1.3.7 运算的完全组 60
1.3.8 语义推论 65
1.4 命题演算L的可靠性和完全性 66
1.5 应用举例 71
2 谓词演算 75
2.1 谓词演算K 76
2.1.1 项与原子公式 76
2.1.2 谓词代数K(Y) 79
2.1.3 谓词演算K的建立 82
2.1.4 等价公式和对偶律 89
2.1.5 前束范式 95
2.2 谓词演算K的语义学 100
2.2.1 K的解释域 101
2.2.2 项解释 103
2.2.3 公式的赋值函数 106
2.2.4 闭式的语义特征 110
2.2.5 语义推论与有效式 115
2.3 K的可靠性 118
2.4 K的完全性 123
3 形式算术与递归函数 132
3.1 带等词的谓词演算 132
3.1.1 等词公理 132
3.1.2 等项替换 135
3.1.3 正规模型 139
3.2 形式算术KN 145
3.3 可表示性 157
3.3.1 可表示函数和关系 157
3.3.2 函数的复合和μ算子保持可表示性 165
3.4 递归函数 171
3.4.1 递归函数的一般定义 171
3.4.2 常用递归函数 173
3.4.3 递归关系和递归集 179
3.5 递归函数的可表示性 182
3.6 可表示函数的递归性 189
3.6.1 唯一读法引理 189
3.6.2 G?del数 192
3.6.3 过程值递归 195
3.6.4 KN的一些递归性质 198
3.6.5 可表示函数的递归性 206
4 不完备性定理 209
4.1 G?del不完备性定理 209
4.1.1 G?del定理 209
4.1.2 G?del-Rosser定理 213
4.1.3 Church论题 216
4.1.4 关于不完备性定理的一些讨论 218
4.1.5 无矛盾性不可证性定理的一种易证形式 222
4.2 形式算术的不可判定性定理 227
4.3.1 可证公式集的递归可枚举性 230
4.3 递归可枚举集和算术集 230
4.3.2 递归可枚举集的算术可定义性 232
4.3.3 真公式集的非算术可定义性(Tarski定理) 235
4.4 Turing论题 238
4.4.1 Turing机 238
4.4.2 Turing可计算函数 244
4.4.3 人与机器 248
练习答案或提示 250
符号汇集 270
参考文献 273