第一篇 数理逻辑 5
第一章 命题逻辑 5
1.1命题和联结词 5
1.2公式和真值赋值 8
1.3等值演算 12
1.4对偶定理 15
1.5联结词的完全集 16
1.6范式 19
1.7逻辑推论 22
习题一 23
第二章 谓词逻辑 29
2.1谓词和量词 29
2.2项和公式 33
2.3解释和赋值 36
2.4永真式 42
2.5等值演算 45
2.6逻辑推论 49
习题二 50
第三章 公理系统 54
3.1命题逻辑的公理系统 54
3.2谓词逻辑的公理系统 59
习题三 63
第四章 归结法原理 65
4.1命题逻辑的归结法 65
4.2前束范式与斯科伦范式 69
4.3谓词逻辑的归结法 71
习题四 81
参考文献 83
第二篇 集 合论 87
第五章 集合的基本概念及其运算 87
5.1集合与元素 87
5.2集合间的相等和包含关系 89
5.3幂集 91
5.4集合的运算 92
5.5有穷集的计数原理 99
5.6集合的归纳定义法 101
5.7有序偶和笛卡儿乘积 105
习题五 106
第六章 关系 110
6.1关系及其性质 110
6.2关系的运算 113
6.3次序关系 119
6.4等价关系、划分及其他 123
习题六 127
第七章 函数 131
7.1基本概念 131
7.2函数的复合 135
7.3特殊性质的函数 138
7.4集合的特征函数 142
习题七 143
第八章 自然数和基数 146
8.1自然数及数学归纳法 146
8.2基数 149
习题八 155
参考文献 156
第三篇 图论 159
第九章 基本概念 159
9.1有向图及无向图 159
9.2图的基本结构 161
9.3子图 163
9.4连通性 166
9.5顶点基和强分图 171
习题九 174
第十章 通路问题 177
10.1最短通路 177
10.2关键通路 180
习题十 183
第十一章 图的矩阵表示 184
11.1邻接矩阵 184
11.2有向图的可达性矩阵 186
11.3关联矩阵 189
习题十一 190
第十二章树 192
12.1树的一般定义 192
12.2根树与有序树 194
12.3二元树 195
12.4生成树 199
12.5割集 202
习题十二 203
第十三章 穿程问题 206
13.1欧拉图 206
13.2哈密顿图 209
习题十三 211
第十四章 二分图的匹配问题 213
14.1基本概念 213
14.2二分图的最大匹配 215
14.3从X到Y的匹配 217
习题十四 219
第十五章 平面图及色数 220
15.1平面图 220
15.2色数 225
习题十五 228
参考文献 230
第四篇 代数系统 233
第十六章 基本概念 233
16.1代数系统 233
16.2同态和同构 236
16.3子代数和商代数 237
习题十六 240
第十七章 半群和群 241
17.1半群的概念 241
17.2子半群和半群同态 242
17.3商半群和半群直积 243
17.4群的概念 245
17.5子群和群的同态 247
17.6变换群、置换群和循环群 249
17.7不变子群和商群 250
习题十七 254
第十八章 环和域 256
18.1环和域的概念 256
18.2子环和环的同态 258
18.3理想和商环 259
习题十八 261
第十九章 格和布尔代数 262
19.1格的定义与基本性质 262
19.2子格和格的同态 264
19.3布尔代数 264
19.4布尔代数的表示 266
习题十九 268
第二十章 抽象数据类型的代数规范 270
20.1标记、项和代数规范 270
20.2 Σ-代数和范畴 275
20.3代数规范的初始语义 277
习题二十 278
参考文献 280
第五篇 有限自动机理论 283
第二十一章 基本概念 283
21.1字符表、字符串及其集合的运算 283
21.2有限自动机的定义 284
21.3有限自动机的等价 288
21.4 Mealy机与Moore机 290
习题二十一 292
第二十二章 有限自动机的简化 294
22.1最小有限自动机的定义及性质 294
22.2状态集的S划分和格LM 296
22.3有限自动机的最小化 302
习题二十二 309
第二十三章 有限自动机和正则表达式 311
23.1有限自动机的识别功能 311
23.2非确定有限自动机 313
23.3正则表达式 316
23.4由正则表达式构造FA的算法 318
23.5有限自动机和正则表达式的等价性 324
23.6正则集合及其性质 327
习题二十三 329
第二十四章 有限自动机的综合与应用 331
24.1有限自动机的综合 331
24.2 FA理论在算法设计中的应用 334
24.3 FA理论与形式语言理论的关系 339
习题二十四 342
参考文献 344
名词索引 345