绪论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  无穷集与018

    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  一阶语言L77

    4.2.1  一阶语言L与谓词公式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  L的重言式89

    本章习题90

第5章  谓词演算形式系统92

  5.1  形式系统KL92

    5.1.1  KL的定义92

    5.1.2  KL的可靠性证明93

    5.1.3  KL的演绎定理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  KL的充分性定理102

    5.4.1  一阶系统的协调完全扩充102

    5.4.2  一阶语言L的扩展103

    5.4.3  KL的充分性定理证明104

    本章习题106

第6章  一阶算术形式系统与哥德尔不完备性定理107

  6.1  一阶算术形式系统107

    6.1.1 逻辑公理与系统公理107

    6.1.2 带等词的一阶系统109

    6.1.3  一阶算术系统N110

  6.2  哥德尔不完备性定理117

    6.2.1  N的模型与可表示性定理118

    6.2.2  哥德尔编码与哥德尔数120

    6.2.3  形式系统论断的关系表示120

    6.2.4  不完备性定理的证明121

    本章习题122

附录A  习题解答123参考文献136