本书是数理逻辑方面的经典教材。书中涵盖了命题逻辑、一阶逻辑、不可判定性以及二阶逻辑等方面的内容，并且包含了与计算机科学有关的主题，如有限模型。本书特点是：内容可读性强；组织结构更灵活，授课教师可根据教学需要节选本书的内容；反映了近几年来理论计算机科学对逻辑学产生的影响；包含较多的示例和说明。本书适合作为计算机及相关专业本科生和研究生数理逻辑课程的教材。

第0章　集合基础　1

第1章　命题逻辑　8

1.0　闲话形式语言　8

1.1　命题逻辑的语言　9

1.2　真值指派　14

1.2.1　真值表　17

1.2.2　典型的重言式　19

习题　19

1.3　解析算法　21

1.3.1　解析算法　22

1.3.2　波兰记法　23

1.3.3　省略括号　23

习题　24

1.4　归纳与递归　24

1.4.1　归纳　24

1.4.2　递归　27

习题　32

1.5　命题联结词　32

1.5.1　0元联结词　37

1.5.2　一元联结词　37

1.5.3　二元联结词　37

1.5.4　三元联结词　37

习题　38

1.6　交换电路　39

习题　42

1.7　紧致性和能行性　43

1.7.1　紧致性　43

1.7.2　能行性及可计算性　44

习题　47

第2章　一阶逻辑　49

2.0　预备知识　49

2.1　一阶语言　50

2.1.1　公式　53

2.1.2　自由变量　55

2.1.3　符号　56

习题　57

2.2　真值与模型　58

2.2.1　逻辑蕴涵　64

2.2.2　结构中的可定义性　65

2.2.3　结构类的可定义性　67

2.2.4　同态　68

习题　72

2.3　解析算法　75

2.3.1　项的解析　76

2.3.2　公式的解析　77

习题　78

2.4　演绎计算　78

2.4.1　形式演绎　79

2.4.2　替换　80

2.4.3　重言式　82

2.4.4　演绎与元定理　83

2.4.5　策略　86

2.4.6　字母变换式　90

2.4.7　相等　92

2.4.8　注记　93

习题　93

2.5　可靠性与完备性理论　94

2.6　理论的模型　107

2.6.1　有限模型　107

2.6.2　模型的大小　110

2.6.3　理论　113

2.6.4　前束范式　117

2.6.5　注记　118

习题　119

2.7　理论之间的解释　119

2.7.1　定义函数　120

2.7.2　解释　121

2.7.3　语法翻译　124

习题　126

2.8　非标准分析　126

2.8.1　*R的构造　127

2.8.2　代数性质　129

2.8.3　收敛性　131

习题　133

第3章　不可判定性　134

3.0　数论　134

3.1　有后继数的自然数　138

习题　142

3.2　数论的其他归约模型　142

习题　149

3.3　数论的子理论　149

3.3.1　公理集AE　149

3.3.2　可表示关系　151

3.3.3　丘奇论题　153

3.3.4　按数字确定的公式　155

3.3.5　可表示函数　156

3.3.6　编目　161

习题　166

3.4　语法的算术化　167

习题　175

3.5　不完全性和不可判定性　175

3.5.1　递归可枚举性　178

3.5.2　弱可表示性　180

3.5.3　算术分层　181

习题　183

3.6　递归函数　184

3.6.1　范式　185

3.6.2　部分递归函数　187

3.6.3　判定问题的归约　193

3.6.4　带寄存的计算器　195

习题　197

3.7　第二不完全性定理　198

3.7.1　集合论的应用　202

3.7.2　集合论中的哥德尔第二不完全性

定理　204

习题　205

3.8　幂乘运算的表示　206

3.8.1　配对函数　207

3.8.2　哥德尔β函数　208

习题　209

第4章　二阶逻辑　211

4.1　二阶语言　211

习题　214

4.2　斯科伦函数　214

习题　219

4.3　多类逻辑　220

4.4　广义结构　222

4.4.1　多类语言　223

4.4.2　二阶语言的广义结构　224

4.4.3　解析模型　226

附录A　推荐读物　228

附录B　符号列表　229

索引　231