《计算机、逻辑和集合论》求取 ⇩

第一章 引言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 递归集、递归可枚举集和通用MMCM60

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

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

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 选择公理AC165

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

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

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

练习题181

参考文献187