前言 1
第一章 可计算性 3
引言 3
1-1 有穷自动机 4
1-1·1 正则表达式 6
1-1·2 有穷自动机 10
1-1·3 转换图 12
1-1·4 Kleene定理 15
1-1·5 等价定理 22
1-2 Turing机 25
1-2·1 Turing机 26
1-2·2 Post机 30
1-2·3 具有下推存贮？有穷机 35
1-2·4 不确定性 42
1-3 作为接收？的Turing机 45
1-3·1 递归可？集合 45
1-3·2 递归集合 47
1-3·3 形式语言 48
1-4 作为发生？的Turing机 52
1-4·1 原始递归函数 54
1-4·2 部分递归函数 61
1-5 作为算法的Turing机 65
1-5·1 是／否问题类的可解性 66
1-5·2 Turing机的停机问题 68
1-5·3 半Thue系统的字问题 70
1-5·4 Post对应问题 73
1-5·5 是／否问题类的部分可解性 78
文献评论，文献目录，习题 83
第二章 谓词演算 97
引言 97
2-1 基本概念 102
2-1·1 句法 102
2-1·2 字义（说明） 108
2-1·3 真确的良构式 116
2-1·4 良构式的等价性 125
2-1·5 良构式的正则形式 132
2-1·6 真确性问题 137
2-2 自然演绎法 140
2-2·1 连词法则 143
2-2·2 ？词法则 152
2-2·3 算符法则 160
2-3 分解的方法 164
2-3·1 子句形式 165
2-3·2 Herband过程 171
2-3·3 联合法则 178
2-3·4 分解法则 183
文献评论，文献目录，习题 189