计算理论与符号逻辑2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

计算理论与符号逻辑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 最小算术理论Q234

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