《数理逻辑》求取 ⇩

前言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 命题演算L13

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 谓词演算K76

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 形式算术KN145

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