第1章 基础知识 1
1.1 集合的初步知识 1
1.2 数学归纳法 1
1.3 整数的基本性质 2
1.3.1 整除 2
1.3.2 素数 3
1.3.3 带余除法 4
1.3.4 最大公约数 5
1.3.5 最小公倍数 7
1.3.6 模运算 8
1.3.7 同余的应用 10
1.4 序列的基本知识 11
1.4.1 序列 11
1.4.2 典型的整数序列 12
1.4.3 序列求和 13
1.5 计数 15
1.5.1 加法原理和乘法原理 15
1.5.2 排列与组合 17
1.5.3 二项式定理 21
1.5.4 鸽巢原理 22
1.6 矩阵的初步知识 23
1.6.1 矩阵的概念 23
1.6.2 矩阵的加法和数乘 25
1.6.3 矩阵的乘法 26
1.6.4 转置矩阵和逆矩阵 27
1.7 本章小结 28
1.8 习题 28
第2章 命题逻辑 31
2.1 命题与联结词 31
2.1.1 命题 31
2.1.2 逻辑联结词 33
2.1.3 联结词的优先级 37
2.1.4 命题符号化 37
2.1.5 逻辑运算在计算机中的直接运用 39
2.2 命题公式与等价演算 41
2.2.1 命题公式及其层次 41
2.2.2 命题公式的赋值 42
2.2.3 等价式与等价演算 45
2.2.4 等价演算的实际应用 48
2.3 联结词的扩充与联结词完备集 49
2.3.1 联结词的扩充 49
2.3.2 与非、或非、异或的性质 51
2.3.3 联结词完备集 52
2.4 范式 53
2.4.1 析取范式与合取范式 53
2.4.2 主析取范式与主合取范式 57
2.4.3 主范式的作用 62
2.4.4 用主范式解答实际问题 63
2.5 命题逻辑推理 66
2.5.1 推理的形式结构 66
2.5.2 推理的证明方法 68
2.5.3 命题逻辑推理的实际应用 71
2.6 本章小结 72
2.7 习题 73
第3章 谓词逻辑 76
3.1 谓词逻辑的基本概念 76
3.1.1 个体和谓词 76
3.1.2 量词 78
3.1.3 特性谓词 80
3.1.4 谓词逻辑符号化 81
3.2 谓词公式与翻译 82
3.2.1 谓词公式 82
3.2.2 谓词逻辑的翻译 83
3.3 变元的约束 86
3.3.1 约束变元和自由变元 86
3.3.2 约束变元的换名规则 87
3.3.3 自由变元的代替规则 88
3.4 谓词公式的解释与分类 89
3.4.1 谓词公式的解释 89
3.4.2 谓词公式的分类 90
3.5 谓词逻辑的等价式和前束范式 91
3.5.1 谓词逻辑等价式 91
3.5.2 前束范式 94
3.6 谓词逻辑推理 95
3.6.1 推理定律 95
3.6.2 推理规则 97
3.6.3 谓词逻辑推理例题 98
3.7 程序正确性证明 100
3.8 本章小结 102
3.9 习题 102
第4章 集合 106
4.1 集合的基本概念 106
4.1.1 集合及其表示方法 106
4.1.2 集合间的关系 108
4.1.3 特殊集合 109
4.1.4 有限幂集元素的编码表示 110
4.2 集合的基本运算 111
4.3 集合恒等式 113
4.4 集合的划分与覆盖 115
4.5 有穷集合的计数 117
4.6 本章小结 118
4.7 习题 119
第5章 关系 121
5.1 关系的概念与表示 121
5.1.1 笛卡儿积 121
5.1.2 二元关系的概念 123
5.1.3 关系矩阵和关系图 125
5.2 复合关系和逆关系 127
5.2.1 复合关系 127
5.2.2 逆关系 130
5.3 关系的性质 131
5.4 关系的闭包 135
5.5 等价关系和偏序关系 136
5.5.1 等价关系 136
5.5.2 偏序关系 138
5.5.3 字典排序和拓扑排序 141
5.6 函数 143
5.6.1 函数的基本概念 143
5.6.2 复合函数和逆函数 145
5.6.3 几个重要的函数 147
5.7 二元关系的应用 148
5.7.1 等价关系的应用 149
5.7.2 函数的应用 149
5.8 多元关系及其应用 149
5.8.1 多元关系 149
5.8.2 关系数据库 151
5.9 本章小结 153
5.10 习题 153
第6章 代数系统 155
6.1 二元运算及其性质 155
6.1.1 二元运算与一元运算 155
6.1.2 二元运算的性质与特殊元素 157
6.1.3 代数系统简介 162
6.1.4 典型例题分析 163
6.2 半群与群 164
6.2.1 半群、独异点与群 164
6.2.2 幂 167
6.2.3 群的性质 168
6.2.4 典型例题分析 170
6.3 子群、循环群与置换群 170
6.3.1 元素的周期 170
6.3.2 子群 171
6.3.3 循环群 173
6.3.4 置换群 176
6.4 陪集和正规子群 178
6.4.1 陪集 178
6.4.2 正规子群 180
6.4.3 典型例题分析 181
6.5 群的同态与同构 182
6.5.1 基本概念 182
6.5.2 基本性质 183
6.6 环和域 184
6.6.1 环 184
6.6.2 域 187
6.7 格 187
6.7.1 格的定义 187
6.7.2 格的性质 189
6.7.3 几种特殊的格 191
6.8 布尔代数 193
6.8.1 布尔代数及其性质 193
6.8.2 布尔函数与布尔表达式 196
6.9 应用实例 196
6.9.1 门电路 196
6.9.2 逻辑电路设计 197
6.10 本章小结 199
6.11 习题 200
第7章 图论 204
7.1 图的基本概念 204
7.1.1 图的定义 204
7.1.2 特殊的图 207
7.1.3 子图 208
7.1.4 结点的度 209
7.2 图的连通性 211
7.2.1 路径和回路 211
7.2.2 无向图的连通性 212
7.2.3 有向图的连通性 212
7.2.4 欧拉图 213
7.2.5 哈密顿图 217
7.2.6 带权图的最短路 217
7.3 图的矩阵表示 219
7.3.1 无向图的关联矩阵 219
7.3.2 有向图的关联矩阵 220
7.3.3 有向图的邻接矩阵 220
7.3.4 无向图的邻接矩阵 221
7.4 树 222
7.4.1 无向树与生成树 222
7.4.2 有向树 224
7.4.3 最优二元树 226
7.4.4 前缀码 228
7.4.5 树的遍历 230
7.5 本章小结 231
7.6 习题 232
第8章 算法与伪代码 234
8.1 算法概述 234
8.2 判断素数算法 236
8.3 求最大数算法 236
8.4 求最大公约数的欧几里得算法 237
8.5 求拓扑排序的算法 237
8.6 求欧拉路的Fleury算法 239
8.7 求最短路径的Dijkstra算法 240
8.8 求最小生成树的Prim算法 241
8.9 求最优二元树的Huffman算法 243
附录A 离散数学常用符号 245
附录B 中英文名词术语对照表 250
附录C 英中文名词术语对照表 263
附录D 习题答案与提示 275
参考文献 286