计算机、逻辑和集合论PDF电子书下载

第一章 引言 1

第二章 理想计算机与有穷性原则 8

第一节 递归函数 8

1．1 原始递归函数集 9

1．2 原始递归算子 11

1．3 原始递归函数集的分层 13

1．4 Arckermann函数 15

1．5 递归函数 16

2．1 几个计算实例 17

第二节 理想计算机 17

1．6 递归函数集的分层 17

2．2 计算的分析和理想计算机 19

第三节 Turing机器 21

3．1 Turing机定义 21

3．2 Turing机和递归函数 23

3．3 通用函数和递归定理 32

3．4 通用Turing机 36

3．5 通过Turing机定义的非递归函数 39

3．6 Turing机的子类—有穷自动机 43

3．7 计算复杂性与P？NP问题 46

3．8 Post系统和Turing机 51

第四节 计算机的数学模型（MMCM） 52

4．1 进一步分析Turing机和Post系统 53

4．2 MMCM定义 54

4．3 MMCM和其他理想计算机 58

4．4 MMCM的一般性 59

4．5 递归集、递归可枚举集和通用MMCM 60

4．6 递归可枚举集与递归不可解性 67

4．7 一致可分（简记作US）的MMCM 70

1．1 群的定义和一个定理 78

第一节 数理逻辑和数学 78

第三章 有穷性逻辑和有穷性数学 78

1．2 语言和推理规则 83

1．3 数理逻辑和数学 84

第二节 一阶逻辑 85

2．1一阶语言 86

2．2一阶逻辑语言的语义 88

2．3 一阶逻辑的推理系统 92

2．4 形式推导的正确性和协调性 98

2．5 不含量词公式的合取（析取）范式和含量词公式的前束范式 99

2．6 形式推导的完全性 100

2．7 一阶逻辑的局限性、Gādel不完全定理 104

2．8 二阶逻辑和Q量词逻辑 109

第三节 有穷性逻辑和有穷性数学 112

3．1 有穷性逻辑和有穷性数学 112

3．2 注记和评论 115

第四节 有穷和无穷命题演算 116

4．1 有穷命题演算 116

4．2 无穷命题演算 120

第四章 一般逻辑和一般数学 125

第一节 一般逻辑和一般数学的定义 125

1．2 一般数学？（？）的定义 126

1．1 一般逻辑？的定义 126

第二节 一般逻辑？和一般数学？（？）的解释 129

2．1 公式和推理规则的解释 129

2．2 ？（？）的结构 130

2．3 ？（？）的模型 130

2．4 一般数学？（？）的语义完全性 131

第三节 总结？结论 131

第五章 集合论 136

第一节 朴素集合论 136

1．1 集合之势（基数） 136

1．2 有序集 139

1．3 序型 140

1．4 序型的运算 141

1．5 良序集 142

1．6 序数 144

1．7 可数的超限数 146

1．8 序数和基数 148

1．9 超限归纳法和良序定理 149

第二节 公理集合论（非形式公理系统） 151

2．1 集合论公理 152

2．2 序数 156

2．3 序数和基数 161

2．4 超穷归纳法 164

第三节 ZF系统 164

3．1 公理和说明 165

3．2 选择公理AC 165

3．3集合全域（或称集合的论域） 169

3．4 ZF的可构成模型L，ZF与AC、GCH的协调性 171

3．5 ZF的其他模型，ZF与V≠L，┑AC，┑CH的协调性 178

练习题 181

参考文献 187