第一部分 形式语言与自动机理论 1
第一章 语言与正规语言 1
符号、符号串及其运算 1
文法与语言的形式定义 3
正规表达式 12
正规文法与正规式 16
第二章 有限自动机 20
有限自动机的定义与构造 20
确定的有限自动机（DFA） 22
不确定的有限自动机（NFA） 23
NFA的确定化 25
DFA的最小化 28
正规集与有限自动机的等价性 31
双向有限自动机 33
具有输出的有限自动机 36
第三章 正规集的性质 39
正规集的泵作用引理 39
正规集的封闭性质 41
正规集的一些判定算法 47
第四章 上下文无关语言 50
上下文无关文法 50
上下文无关文法的简化 52
Chomsky范式 56
Greibach范式 57
先天歧义的上下文无关语言的存在 60
第五章 下推自动机 64
非形式的描述 64
下推自动机的定义 65
下推自动机和上下文无关语言 68
第六章 上下文无关语言的性质 74
对CFL的泵作用引理 74
上下文无关语言的封闭性质 78
CFL的某些判定算法 82
第二部分 可计算理论 86
第七章 图灵机 86
图灵机模型 86
可计算语言和函数 89
图灵机的构造技术 90
图灵机的修改 94
Church假设 99
图灵机作为枚举器 100
等价于基本模型的受限图灵机 102
第八章 短语结构语言与上下文有关语言 106
短语结构语言与图灵机 106
上下文有关语言与线性有界自动机 108
上下文无关语言与递归集合 110
上下文有关语言类的性质 111
第九章 可判定性 114
递归语言和递归可枚举语言的性质 114
通用图灵机和一个不可判定问题 116
RICE定理和某些其他的不可判定问题 118
POST对应问题的不可判定性 124
图灵机的有效计算和无效计算 129
Greibach定理 132
圣人计算 134
第十章 可计算理论 138
原始递归函数 138
递归函数与部分递归函数 142
图灵机与部分递归函数的等价性 145
第三部分 逻辑学 148
第十一章 命题逻辑与一阶逻辑 148
命题逻辑的自然推理 148
命题演算的公理系统 150
PC的可靠性与一致性 153
PC的完备性 154
一阶逻辑 155
第十二章 直觉主义逻辑 173
直觉主义的一些基本观点 173
一阶直觉主义逻辑的形式化 174
完全性定理 192
第十三章 模态逻辑 198
模态词“必然”与“可能” 198
模态命题逻辑系统 199
模态狭义谓词逻辑 219
第十四章 非单调逻辑 223
单调性与非单调性 223
非单调逻辑 224
缺省推理 225
非单调逻辑系统 230
限定理论 235
第十五章 模糊逻辑 241
逻辑与不确定性的研究 241
模糊集 242
模糊逻辑的代数模型——De-Morgan代数 247
模糊变量与模糊逻辑公式（函数） 249
模糊逻辑真值表与范式 253
模糊逻辑公式的极小化 255
似然推理 255
模糊归纳推理 258
第十六章 多值逻辑 260
三值逻辑 260
多值命题逻辑 262
三值逻辑代数系统 264
n值逻辑代数系统 266
阈值逻辑 268
第四部分 程序设计理论 271
第十七章 程序的指称语义 271
把程序看作函数 271
序列程序结构的程序函数 273
分支程序结构的程序函数 274
循环程序结构的程序函数 276
循环程序的正确性证明 281
第十八章 程序的公理语义 284
程序的公理语义 284
霍尔公理系统 286
最弱前置谓词与程序的公理语义 290
第十九章 程序的形式推导 299
程序形式推导的基本思想 299
选择语句的设计 300
循环程序的设计 302
不变式与界函数的构造 306
第二十章 递归程序理论 313
递归的基本概念 313
递归数据结构 317
递归程序的证明 319
习题 325
参考文献 343