计算的数学理论 上PDF电子书下载

前言 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