目 录 1
第一章预备知识 1
§1-1字符串、字母表和语言 1
§1-2图和树 2
§1-3集合表示法和关系 4
§1-4经典逻辑 5
第二章有穷自动机与正规语言 12
§2-1确定型有穷自动机 12
§2-2非确定型有穷自动机 16
§2-3正规表达式 20
§2-4双向有穷自动机 25
§2-5泵作用引理 27
§2-6正规集合的性质 28
第三章图灵机 31
§3-1可计算性与可计算函数 31
§3-2图灵机的定义和例子 34
§3-3专用图灵机 37
§3-4通用图灵机 45
§3-5图灵可计算性 49
第四章部分递归函数及其与图灵机的等价性 61
§4-1三类递归函数 61
§4-2原始递归谓词与递归谓词 68
§4-3哥德尔编码 72
§4-4图灵机与部分递归函数的等价性 74
§4-5递归语言与递归可枚举语言 78
§5-1计算复杂度及图灵机的资源 82
第五章计算复杂性 82
§5-2巡迥、空间与时间复杂度之间的关系 90
§5-3计算模型间的相似性 93
§5-4理论复杂性量度与加速定理 96
第六章程序正确性证明 101
§6-1预备知识 101
§6-2部分正确性证明 104
§6-3终止性证明 114
§6-4完全正确性证明 117
§6-5递归程序的正确性 120
第七章 定理的机器证明 123
§7-1海尔勃朗特定理 124
§7-2归结原理 127
§7-3归结原理的改进 132
§7-4 自然推导法 139
§7-5重写规则法 142
§7-6 B-M定理证明系统 145
§7-7几何定理机器证明 151
第八章非标准逻辑 156
§8-1 引言 156
§8-2算法逻辑 157
§8-3二阶逻辑 170
§8-4模态逻辑 175
§8-5时态逻辑 181
§8-6动态逻辑 189
§8-7 3-值逻辑、无穷值逻辑和模糊逻辑 195
§8-8直觉主义逻辑 203
§8-9非单调逻辑 209
§8-10开放逻辑 214
第九章推理方法 219
§9-1推理方法的分类、演绎推理和归纳推理 219
§9-2概率推理 221
§9-3不确定性推理 227
§9-4非单调推理 235
§9-5模糊推理 237
§9-6其它推理方法 241
第十章按自然法则计算——研究非图灵模型的途径之一 250
§10-1遗传算法 253
§10-2模拟退火算法 258
§10-3人工神经网络 263
§10-4混沌 273
§10-5分形 277
主要参考文献 281