绪论 1
第1章 集合论基础 5
1.1可数集 6
1.1.1映射 6
1.1.2可数集的概念 7
1.1.3可数集概念的延伸 9
1.2康拓尔对角线方法 12
1.2.1波尔查诺的无穷观 12
1.2.2康拓尔的证明 13
1.2.3自然数集的幂集P（N） 14
1.3基数 15
1.3.1基数的概念 15
1.3.2基数大小关系性质 16
1.4自然数与有穷集 17
1.4.1集合论观点下的自然数 17
1.4.2有穷集与有穷基数 17
1.5无穷集与？0 18
1.5.1最小的无穷量 18
1.5.2无穷集的肚量 19
1.6更高的超穷基数 19
1.6.1幂集的基数 19
1.6.2关于幂集的康拓尔定理 20
1.6.3其他超穷集的基数 20
1.6.4连续统与连续统假设 22
本章习题 22
第2章 可计算性理论基础 24
2.1计算概念的形成与发展 24
2.1.1计算概念的初识——抽象思维的进步 25
2.1.2计算概念的定义——计算本质的揭示 25
2.1.3计算概念的发展——计算方式的进化 26
2.2算法与能行过程 27
2.2.1算法概念的由来 27
2.2.2算法概念的描述 28
2.2.3能行过程与可计算性 29
2.2.4停机问题 30
2.3可计算性概念的数学描述 31
2.3.1递归函数 31
2.3.2图灵机与图灵可计算函数 34
2.4理想计算机 38
2.4.1 URM模型与指令系统 38
2.4.2 URM可计算函数 41
本章习题 43
第3章 形式命题演算 45
3.1命题与命题演算形式系统 45
3.1.1命题的概念 45
3.1.2命题的表示与翻译 47
3.1.3命题演算形式系统 49
3.2命题演算形式推理 50
3.2.1命题演算形式证明与定理 50
3.2.2相对证明与演绎定理 51
3.3命题公式的等价与替换 58
3.3.1等价命题公式 58
3.3.2等价命题替换定理 59
3.4对偶命题公式 60
3.4.1命题公式的对偶式 60
3.4.2对偶原则 60
3.5形式系统再认识 61
3.5.1形式系统理论 61
3.5.2形式系统L的简化 62
3.6形式系统的进一步讨论 64
3.6.1赋值与重言式 64
3.6.2 L的可靠性定理 66
3.6.3 L的充分性定理 67
本章习题 69
第4章 谓词演算 72
4.1谓词表达式 72
4.1.1谓词与量词 72
4.1.2谓词表达式与翻译 74
4.2一阶语言？ 77
4.2.1一阶语言？与谓词公式 77
4.2.2自由变元与约束变元 78
4.3解释与可满足性 81
4.3.1解释 81
4.3.2可满足性 82
4.4公式的真与假 87
4.4.1公式真假定义 87
4.4.2闭公式及其性质 88
4.4.3逻辑普效与矛盾式 89
4.4.4 ？的重言式 89
本章习题 90
第5章 谓词演算形式系统 92
5.1形式系统K？ 92
5.1.1 K？的定义 92
5.1.2 K？的可靠性证明 93
5.1.3 K？的演绎定理 94
5.2等值与代入 97
5.2.1等值词的定义 97
5.2.2替换定理 98
5.3前束范式 99
5.3.1前束范式的概念 99
5.3.2前束范式定理 100
5.3.3公式分层 101
5.4 K？的充分性定理 102
5.4.1一阶系统的协调完全扩充 102
5.4.2一阶语言？的扩展 103
5.4.3 K？的充分性定理证明 104
本章习题 106
第6章 一阶算术形式系统与哥德尔不完备性定理 107
6.1一阶算术形式系统 107
6.1.1逻辑公理与系统公理 107
6.1.2带等词的一阶系统 109
6.1.3一阶算术系统N 110
6.2哥德尔不完备性定理 117
6.2.1 N的模型与可表示性定理 118
6.2.2哥德尔编码与哥德尔数 120
6.2.3形式系统论断的关系表示 120
6.2.4不完备性定理的证明 121
本章习题 122
附录A习题解答 123
参考文献 136