第1章 集合、映射与运算 1
1.1 集合的有关概念 1
1.1.1 集合 1
1.1.2 子集 3
1.1.3 幂集 4
1.1.4 n元组 4
1.1.5 笛卡儿积 5
习题1.1 5
1.2 映射的有关概念 6
1.2.1 映射的定义 6
1.2.2 映射的性质 8
1.2.3 逆映射 9
1.2.4 复合映射 10
习题1.2 12
1.3 运算的定义及性质 13
1.3.1 运算的定义 13
1.3.2 运算的性质 16
习题1.3 21
1.4 集合的运算 22
1.4.1 并运算 22
1.4.2 交运算 22
1.4.3 补运算 24
1.4.4 差运算 25
1.4.5 对称差运算 26
习题1.4 27
1.5 集合的划分与覆盖 28
1.5.1 集合的划分 29
1.5.2 集合的覆盖 30
习题1.5 31
1.6 集合的对等 31
1.6.1 集合对等的定义 31
1.6.2 无限集合 32
1.6.3 集合的基数 32
1.6.4 可数集合 33
1.6.5 不可数集合 33
1.6.6 基数的比较 34
习题1.6 34
本章小结 35
第2章 关系 37
2.1 关系的概念 37
2.1.1 n元关系的定义 37
2.1.2 2元关系 38
2.1.3 关系的定义域和值域 41
2.1.4 关系的表示 42
2.1.5 函数的关系定义 43
习题2.1 44
2.2 关系的运算 46
2.2.1 关系的集合运算 46
2.2.2 关系的逆运算 46
2.2.3 关系的复合运算 47
2.2.4 关系的其他运算 50
习题2.2 51
2.3 关系的性质 51
2.3.1 自反性 51
2.3.2 反自反性 52
2.3.3 对称性 53
2.3.4 反对称性 54
2.3.5 传递性 55
习题2.3 57
2.4 关系的闭包 58
2.4.1 自反闭包r（R） 58
2.4.2 对称闭包s（R） 59
2.4.3 传递闭包t（R） 60
习题2.4 63
2.5 等价关系 64
2.5.1 等价关系的定义 64
2.5.2 等价类 65
习题2.5 67
2.6 相容关系 68
2.6.1 相容关系的定义 68
2.6.2 相容类 69
习题2.6 70
2.7 偏序关系 70
2.7.1 偏序关系的定义 70
2.7.2 偏序集的哈斯图 72
2.7.3 偏序集中的特殊元素 73
习题2.7 75
本章小结 76
第3章 命题逻辑 79
3.1 命题的有关概念 79
习题3.1 81
3.2 逻辑联结词 81
3.2.1 否定联结词？p 82
3.2.2 合取联结词p∧q 82
3.2.3 析取联结词p∨q 82
3.2.4 异或联结词p？q 83
3.2.5 条件联结词p→q 83
3.2.6 双条件联结词p？q 84
3.2.7 与非联结词p↑q 84
3.2.8 或非联结词p↓q 85
3.2.9 条件否定联结词p？q 85
习题3.2 85
3.3 命题公式及其真值表 85
3.3.1 命题公式的定义 85
3.3.2 命题的符号化 86
3.3.3 命题公式的真值表 87
3.3.4 命题公式的类型 88
习题3.3 89
3.4 逻辑等值的命题公式 90
3.4.1 逻辑等值的定义 90
3.4.2 基本等值式 91
3.4.3 等值演算法 93
3.4.4 对偶原理 94
习题3.4 94
3.5 命题公式的范式 95
3.5.1 命题公式的析取范式及合取范式 96
3.5.2 命题公式的主析取范式及主合取范式 98
习题3.5 104
3.6 联结词集合的功能完备性 105
3.6.1 联结词的个数 105
3.6.2 功能完备联结词集 106
习题3.6 108
3.7 命题逻辑中的推理 108
3.7.1 推理形式有效性的定义 108
3.7.2 基本推理规则 110
3.7.3 命题逻辑的自然推理系统 111
习题3.7 114
本章小结 115
第4章 谓词逻辑 118
4.1 个体、谓词、量词和函词 118
4.1.1 个体 118
4.1.2 谓词 119
4.1.3 量词 119
4.1.4 函词 121
习题4.1 121
4.2 谓词公式及命题的符号化 122
4.2.1 谓词公式 122
4.2.2 命题的符号化 122
习题4.2 124
4.3 谓词公式的解释及类型 126
4.3.1 谓词公式的解释 126
4.3.2 谓词公式的类型 127
习题4.3 127
4.4 逻辑等值的谓词公式 129
4.4.1 谓词公式等值的定义 129
4.4.2 基本等值式 129
习题4.4 131
4.5 谓词公式的前束范式 131
4.5.1 谓词公式的前束范式的定义 131
4.5.2 谓词公式的前束范式的计算 132
习题4.5 132
4.6 谓词逻辑中的推理 133
4.6.1 逻辑蕴涵式 133
4.6.2 基本推理规则 133
4.6.3 谓词逻辑的自然推理系统 134
习题4.6 136
本章小结 137
第5章 代数结构 140
5.1 代数结构简介 140
5.1.1 代数结构的定义 140
5.1.2 两种最简单的代数结构：半群及独异点 141
5.1.3 子代数 142
5.1.4 代数结构的同态与同构 142
习题5.1 144
5.2 群的定义及性质 145
5.2.1 群的有关概念 146
5.2.2 子群 148
5.2.3 群的同态 148
习题5.2 149
5.3 环和域 150
5.3.1 环的定义 150
5.3.2 几种特殊的环 150
5.3.3 域的定义 152
5.3.4 有限域 152
习题5.3 153
5.4 格与布尔代数 154
5.4.1 格的定义和性质 155
5.4.2 分配格 158
5.4.3 有补格 158
5.4.4 布尔代数 160
习题5.4 162
本章小结 163
第6章 图论 165
6.1 图的基本概念 165
6.1.1 图的定义 165
6.1.2 邻接 167
6.1.3 关联 167
6.1.4 简单图 167
习题6.1 168
6.2 节点的度数 169
习题6.2 171
6.3 子图、图的运算和图同构 171
6.3.1 子图 171
6.3.2 图的运算 173
6.3.3 图同构 173
习题6.3 174
6.4 路与回路 175
6.4.1 路 175
6.4.2 回路 176
习题6.4 176
6.5 图的连通性 177
6.5.1 无向图的连通性 177
6.5.2 无向连通图的点连通度与边连通度 178
6.5.3 有向图的连通性 180
习题6.5 181
6.6 图的矩阵表示 182
6.6.1 图的邻接矩阵 182
6.6.2 图的可达矩阵 183
6.6.3 图的关联矩阵 184
习题6.6 185
6.7 赋权图及最短路径 186
6.7.1 赋权图 186
6.7.2 最短路径 186
习题6.7 188
本章小结 189
第7章 几类特殊的图 191
7.1 欧拉图 191
7.1.1 欧拉图的有关概念 191
7.1.2 欧拉定理 191
7.1.3 中国邮递员问题 192
习题7.1 193
7.2 哈密尔顿图 194
7.2.1 哈密尔顿图的有关概念 194
7.2.2 哈密尔顿图的必要条件 195
7.2.3 哈密尔顿图的充分条件 195
7.2.4 旅行商问题 197
习题7.2 197
7.3 无向树 198
7.3.1 无向树的定义 198
7.3.2 无向树的性质 199
7.3.3 生成树 200
7.3.4 最小生成树 201
习题7.3 202
7.4 有向树 202
7.4.1 有向树的定义 203
7.4.2 根树 203
7.4.3 m叉树 204
7.4.4 有序树 206
7.4.5 定位二叉树 207
习题7.4 209
7.5 平面图 210
7.5.1 平面图的有关概念 211
7.5.2 欧拉公式 212
7.5.3 库拉托夫斯基定理 212
7.5.4 平面图的对偶图 213
习题7.5 214
7.6 平面图的面着色 215
7.6.1 平面图的面着色定义 215
7.6.2 图的节点着色 216
7.6.3 任意图的边着色 217
习题7.6 218
7.7 二部图及其匹配 218
7.7.1 二部图 218
7.7.2 匹配 219
习题7.7 220
本章小结 221
第8章 组合计数 223
8.1 计数原理、排列组合与二项式定理 223
8.1.1 计数原理 223
8.1.2 排列 224
8.1.3 组合 225
8.1.4 二项式定理 226
习题8.1 226
8.2 生成函数 227
8.2.1 组合计数生成函数 227
8.2.2 排列计数生成函数 229
习题8.2 230
8.3 递归关系 231
8.3.1 递归关系的概念 231
8.3.2 常用的递归关系求解方法 232
习题8.3 237
本章小结 237
附录A 符号索引 239
附录B 中英文名词索引 242
附录C 习题答案及提示 247
参考文献 270