计算理论与符号逻辑PDF电子书下载

第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