第一篇 数理逻辑 1
第一章 命题演算 2
1-1 命题及联结词 2
1-2 命题变元与命题公式 8
1-3 命题演算的关系式 10
1-3-1 命题之间的等价关系 10
1-3-2 命题的蕴函关系 14
1-3-3 对偶法则 16
1-4 其他联结词 18
1-5 范式 21
1-5-1 析取范式和合取范式 21
1-5-2 主析取范式和主合取范式 23
1-6 命题演算的推理 30
1-6-1 真值表技术 31
1-6-2 直接推演 33
1-6-3 间接推演 37
第二章 谓词演算 38
2-1 谓词演算的基本概念 38
2-1-1 谓词与个体 39
2-1-2 量词 41
2-1-3 谓词演算公式 42
2-1-4 自由变元与约束变元 43
2-2 谓词演算的关系式 46
2-2-1 基本定义 46
2-2-2 关系式 47
2-3 前束范式 53
2-4 谓词演算的推理 54
习题一 59
学习提要一 66
第二篇 集合论 79
第三章 集合 80
3-1 集合的基本概念 80
3-1-1 集合及其表示 80
3-1-2 集合间的关系 81
3-1-3 几种特殊集合 84
3-2 集合的运算及基本公式 85
3-3 幂集 93
3-4 包含排斥原理 95
3-5 集合的直积(笛卡儿乘积) 97
第四章 关系 101
4-1 关系及其运算 101
4-2 关系的有关性质 108
4-3 关系的闭包运算 111
4-4 等价关系和相容关系 115
4-4-1 集合的覆盖与划分 115
4-4-2 等价关系 116
4-4-3 相容关系 119
4-5 偏序关系 121
第五章 映射与无限集 129
5-1 映射 129
5-1-1 映射的基本概念 129
5-1-2 复合映射 134
5-1-3 逆映射 135
5-1-4 由映射产生的等价关系 137
5-2 无限集 141
5-2-1 自然数 141
5-2-2 等势 142
5-2-3 可列集 143
5-2-4 不可列无限集 145
5-2-5 势的比较 147
习题二 150
学习提要二 158
第三篇 图论 167
第六章 图论 168
6-1 图的基本概念 168
6-1-1 基本术语 168
6-1-2 路与回路 177
6-1-3 欧拉图与哈密顿图 183
6-2 树 190
6-2-1 树的特征 190
6-2-2 生成树与割集 192
6-2-3 有向树 197
6-3 图的矩阵表示 201
6-3-1 关联矩阵与基本关联矩阵 201
6-3-2 回路矩阵 203
6-3-3 割集矩阵 204
6-3-4 邻接矩阵 205
6-3-5 有向图的矩阵表示 207
6-4 平面图 212
6-4-1 平面图的概念 212
6-4-2 连通平面图的欧拉公式 214
6-4-3 库拉托斯基定理 215
6-4-4 对偶图与着色 217
6-5 二分图与匹配 219
6-5-1 二分图 219
6-5-2 匹配 221
习题三 226
学习提要三 233
第四篇 代数结构 241
第七章 代数结构的基本知识 242
7-1 代数系统的基本概念 242
7-2 同构与同态 249
第八章 半群与群 260
8-1 半群、循环半群与幺半群 260
8-2 群 264
8-3 置换群与对称群 267
8-4 循环群 271
8-5 陪集与拉格朗日定理 275
第九章 环与域 279
9-1 环与幺环 279
9-2 整环与除环 280
9-3 域 284
第十章 格与布尔代数 287
10-1 格与代数系统 287
10-2 布尔格与布尔代数 294
10-3 布尔代数的另一理论体系 299
10-4 布尔表达式与布尔函数 303
习题四 309
学习提要四 316
第五篇 离散数学在计算机科学技术中的应用 325
第十一章 用计算机化简逻辑函数 326
11-1 自动化简逻辑函数的算法 326
11-2 用对合法寻找逻辑函数基本项 327
11-3 用覆盖法寻找必需项 329
11-4 用(准)必需项选拔法选取基本项 330
11-5 逻辑函数化简实例 332
12-1-1 语言的表示 335
第十二章 形式语言与自动机 335
12-1 语言的概念及运算 335
12-1-2 字母表和串 336
12-1-3 语言的概念及运算 338
12-2 文法及语言 342
12-2-1 文法(语法) 342
12-2-2 文法的类型 347
12-2-3 上下文(前后文)有关文法及语言(1型) 348
12-2-4 上下文(前后文)无关文法及语言(2型) 349
12-2-5 有限状态文法及语言 356
12-3 有限自动机 359
12-3-1 自动机与形式文法的关系 359
12-3-2 有限自动机的基本概念 360
12-3-3 有限自动机及其表示法 362
12-3-4 有限自动机的等价 364
12-3-5 状态赋值自动机 365
12-3-6 有限自动机的简化 369
12-3-7 有限识别器 374
12-3-8 确定的有限识别器与不确定的有限识别器 375
12-3-9 有限识别器与有限状态文法 378
12-3-10 有限识别器的另一形式 379
12-4 下推自动机 381
12-4-1 下推自动机的概念 381
12-4-2 下推自动机的例子 383
12-5 线性有界自动机 385
12-5-1 线性有界自动机的概念 385
12-5-2 线性有界自动机的例子 386
12-6-1 五重组图灵机 390
12-6 图灵机 390
12-6-2 波斯特—图灵机 395
12-6-3 图灵机用于计算 401
12-6-4 图灵识别器 406
12-6-5 通用图灵机与图灵停机问题 409
习题五 410
学习提要五 414
习题答案与提示 420
符号表 445
参考文献 450