第一篇 数理逻辑 1
第一章 命题演算 1
1.1 引言 1
1.2 基本概念 1
1.3 逻辑联词与命题公式 2
1.4 永真复合命题的刻画 5
1.5 简化真值表法 10
1.6 对偶定律 13
1.7 命题公式的范式 15
第二章 命题演算的推理理论 17
2.1 命题演算的语义推理与语法推理 17
2.2 命题演算的公理化方法 18
2.3 命题演算的性质 23
第三章 一阶谓词 30
3.1 谓词、客体和变元 30
3.2 量词、约束变元和自由变元 33
3.3 谓词代数 38
第四章 一阶谓词演算的推理理论 40
4.1 谓词公式的语义解释 40
4.2 语义学的论证 41
4.3 一阶谓词演算的公理化方法 44
4.4 一阶谓词演算的性质 49
4.5 例题 52
4.6 包含等关系的一阶谓词演算公理系统 61
第五章 机器推理技术 67
5.1 命题演算的归结法原理 67
5.2 合式谓词公式的斯科林范式 68
5.3 谓词演算的归结法 70
5.4 归结法与人工智能 73
参考文献 78
第二篇 集合论 80
第一章 集合论的基本概念 80
1.1 集合及其有关概念 80
1.2 集合的相等和包含 87
1.3 幂集 89
1.4 集合的运算 92
1.5 集合运算的定理和关系式 98
1.6 有穷集合基数的运算 105
1.7 有序偶和笛卡尔乘积 109
第二章 关系 114
2.1 关系及其性质 114
2.2 关系的运算 123
2.3 等价关系及其它 135
2.4 偏序关系及其它 143
第三章 函数 149
3.1 函数的基本概念 149
3.2 逆函数及函数的复合 154
3.3 特征函数和模糊子集 161
第四章 自然数和基数 165
4.1 自然数与数学归纳法 165
4.2 基数 170
4.3 基数的比较 175
第五章 递归函数 178
5.1 递归函数及其特点 178
5.2 初始函数和算子 180
5.3 递归函数 183
5.4 递归集合及递归谓词 189
参考文献 193
第三篇 图论 194
第一章 基本术语 194
1.1 引言 194
1.2 有向图及无向图 196
1.3 图的基本结构 197
1.3 子图 200
第二章 连通性 203
2.1 可达性 203
2.2 连通类 205
2.3 顶点基和强分图 208
2.4 块 211
第三章 有向图的矩阵表示 214
3.1 邻接矩阵 214
3.2 可达性矩阵 216
第四章 树 220
4.1 树的一般定义 220
4.2 根树与有序树 222
4.3 二元树 223
4.4 生成树 227
4.5 割集 229
第五章 穿程问题 233
5.1 欧拉图 233
5.2 哈密顿图 236
第六章 二分图的匹配问题 240
6.1 基本概念 240
6.2 二分图的最大匹配 242
6.3 从X到Y的匹配 243
第七章 平面图及色数 247
7.1 平面图 247
7.2 色数 252
第八章 通路问题 256
8.1 最短通路 256
8.2 最优通路 260
8.3 关键通路 267
参考文献 267
第四篇 有限自动机理论 269
第一章 有限自动机与基本概念 269
1.1 独异半群 269
1.2 有限自动机的定义 270
1.3 有限自动机的等价性 275
1.4 mealy机与moore机 276
第二章 有限自动机的简化 278
2.1 最小自动机的定义及性质 278
2.2 S划分和格LM 280
2.3 FA的最小化 286
第三章 有限自动机的分析与综合 293
3.1 关于有限自动机的功能 293
3.2 正则序列集与正则表达式 294
3.3 正则序列集与FA的关系 297
3.4 非确定性FA 300
3.5 由正则表达式构造FA的算法 304
3.6 FA的综合 311
第四章 FA理论在计算机科学中的应用 315
4.1 FA理论与形式语言理论的关系 315
4.2 FA理论在算法综合中的应用 319
参考文献 323
第五篇 代数系统 324
第一章 基本概念 324
1.1 代数系统 324
1.2 同态和同构 327
1.3 子代数和商代数 328
2.1 半群的概念 332
第二章 半群和群 332
2.2 子半群和半群同态 333
2.3 商半群和半群直积 334
2.4 群的概念 336
2.5 子群和群的同态 338
2.6 变换群、置换群和循环群 339
2.7 不变子群和商群 341
3.1 环和域的概念 346
第三章 环和域 346
3.2 子环和环的同态 348
3.3 理想和商环 349
第四章 抽象数据类型代数规范初步 352
4.1 标记、项和代数规范 352
4.2 Σ-代数和范畴 357
4.3 代数规范的初始语义 358
参文考献 361