第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
1.4 归纳与递归 24
1.4.1 归纳 24
习题 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.0 预备知识 49
第2章 一阶逻辑 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
2.4 演绎计算 78
习题 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 ＊？的构造 127
2.8.2 代数性质 129
2.8.3 收敛性 131
习题 133
3.0 数论 134
第3章 不可判定性 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