可计算性与数理逻辑 第4版

目录 2

第—部可计算性理论 2

第1章 可枚举性 2

1.1 可枚举性 2

1.2 可枚举集 5

习题……………………………………………………………1O第2章 对角化 12

2.1 对角化 12

习题 15

第3章 图灵可计算性 17

3.1 图灵可计算性 17

习题 25

第4章 不可计算性 27

4.1 停机问题 27

4.2* 产出函数 31

习题 34

第5章 算盘可计算性 35

5.1 算盘机 35

5.2 用图灵机模拟算盘机 39

5.3 算盘的计算能力 44

习题 48

第6章 递归函数 50

6.1 原始递归函数 50

6.2 极小化 55

习题 57

第7章 递归集与递归关系 58

7.1 递归关系 58

7.2 半递归关系 64

7.3* 其他例子 66

习题 68

8.1 为图灵计算编码 70

第8章 可计算性的等价定义 70

8.2 通用图灵机 74

8.3* 递归可枚举集 76

习题 77

第二部分 基础元逻辑 80

第9章—阶逻辑初阶：语法 80

9.1 一阶逻辑 80

9.2 语法 84

习题 89

第10章 —阶逻辑初阶：语义 91

10.1 语义 91

10.2 元逻辑概念 95

习题 98

第11章 —阶逻辑的不可判定性 100

11.1 逻辑与图灵机 100

11.2 逻辑与原始递归函数 105

习题 107

第12章 模型 110

12.1 模型的规模与数目 110

12.2 等价关系 114

12.3 洛文海姆-斯科伦定理与紧致性定理 117

习题 119

第13章 模型的存在性 123

13.1 证明概述 123

13.2 证明的第一阶段 125

13.3 证明的第二阶段 127

13.4 证明的第三阶段 129

13.5* 不可枚举语言 131

习题 132

第14章 证明与完备性 134

14.1 矢列演算 134

14.2 可靠性与完备性 141

14.3* 其他证明系统与希尔伯特论题 145

习题 150

第15章 算术化 152

15.1 语法的算术化 152

15.2* 哥德尔数 156

15.3* 再论哥德尔数 159

习题 160

第16章 递归函数的可表示性 162

16.1 算术可定义性 162

16.2 极小算术与可表示性 169

16.3 数学归纳 172

16.4* 罗宾逊算术 175

习题 177

第17章 不可定义性、不可判定性和不完全性 180

17.1 对角线引理和局限性定理 180

17.2 不可判定的语句 183

17.3* 不用对角线引理的不可判定语 185

习题 188

第18章 协调性的不可证性 190

18.1 协调性的不可证性 190

18.2 历史评论 194

第三部分 高级专题 198

第19章 范式 198

19.1 析取范式与前束范式 198

19.2 斯科伦范式 201

19.3 赫布兰德定理 207

19.4 消去函数符号和等号 209

习题 211

第20章 Craig内插定理 212

20.1 Craig定理及其证明 212

20.2 罗宾逊联合协调性定理 215

20.3 Beth可定义性定理 216

习题 219

21.1 可解的与不可解的判定问题 221

第21章 一目逻辑与二目逻辑 221

21.2 一目逻辑 223

21.3 二目逻辑 225

习题 228

第22章 二阶逻辑 229

22.1 二阶逻辑 229

习题 233

第23章 算术可定义性 235

23.1 算术可定义性和真 235

23.2 算术可定义性与力迫 237

习题 242

第24章 无乘法算术的可判定性 243

24.1 无乘法算术的可判定性 243

习题 247

25.1 非标准模型中的序 249

第25章 非标准模型 249

25.2 非标准模型中的运算 252

25.3 分析的非标准模型 257

习题 261

第26章 Ramsey定理 263

26.1 Ramsey定理：有限的与无限的 263

26.2 Konig引理 266

习题 268

第27章 模态逻辑与可证性 270

27.1 模态逻辑 270

27.2 可证性逻辑 277

27.3 不动点定理与范式定理 279

习题 282

部分问题提示 283

加注释的参考文献 289