目录 1
前言 1
第1章 预备知识 1
1.1 集合论的初步知识 1
1.1.1 集合的基本概念 1
1.1.2 集合的表示 2
习题1.1 3
1.2 集合的关系与运算 3
1.2.1 集合间的基本关系 3
1.2.2 幂集 5
1.2.3 集合的基本运算 5
1.2.4 文氏图 6
1.2.5 主要的运算律 6
1.2.6 集合运算成员表 8
习题1.2 9
1.3 有限集合中元素的计数 10
1.3.1 文氏图法计数 10
1.3.2 容斥原理 10
习题1.3 12
1.4 整数的基本性质 12
1.4.1 带余除法与整除 12
1.4.2 最大公因数和最小公倍数 14
1.4.3 同余 17
习题1.4 17
1.5 例题解析 17
复习题1 19
第2章 命题逻辑 21
2.1 命题与命题联结词 21
2.1.1 命题 21
2.1.2 命题联结词 22
习题2.1 26
2.2 命题公式及其分类 27
2.2.1 命题公式 27
2.2.2 公式的赋值及分类 28
习题2.2 30
2.3 等价演算 30
2.3.1 基本等价式 30
2.3.2 等价演算 32
习题2.3 34
＊2.4 其他常用联结词及功能完备集 35
2.4.1 其他常用联结词介绍 35
2.4.2 联结词的功能完备集 36
习题2.4 37
2.5.1 对偶 38
2.5 对偶与范式 38
2.5.2 范式 39
2.5.3 主范式 40
习题2.5 44
2.6 推理理论 45
2.6.1 重言蕴含式 45
2.6.2 形式证明 46
习题2.6 49
＊2.7 命题逻辑在门电路中的应用介绍 50
习题2.7 51
2.8 例题解析 51
复习题2 54
第3章 谓词逻辑 57
3.1 谓词逻辑的基本概念 57
3.1.1 个体与谓词 57
3.1.2 量词 58
习题3.1 61
3.2 谓词合式公式及解释 61
3.2.1 谓词公式 62
3.2.2 谓词公式的解释 63
3.2.3 谓词公式的类型 64
习题3.2 65
3.3 谓词逻辑等值式 66
习题3.3 69
3.4 谓词逻辑推理理论 69
习题3.4 73
3.5 例题解析 74
复习题3 78
4.1.1 有序对 80
4.1 有序对与笛卡尔积 80
第4章 关系 80
4.1.2 笛卡尔积 81
习题4.1 82
4.2 关系及其表示 83
4.2.1 关系的基本概念 83
4.2.2 关系矩阵和关系图 84
习题4.2 85
4.3 复合关系与逆关系 86
4.3.1 复合关系 86
4.3.2 复合关系的性质 87
4.3.3 关系的幂和逆关系 88
习题4.3 89
4.4 关系的性质 90
4.5 关系的闭包 94
4.5.1 关系闭包的概念 94
习题4.4 94
4.5.2 关系闭包的求法 95
习题4.5 100
4.6 等价关系 100
4.6.1 集合的划分 100
4.6.2 等价关系 102
4.6.3 等价类 102
习题4.6 105
＊4.7 相容关系 105
4.7.1 相容关系 105
4.7.2 相容类 106
习题4.7 107
4.8 偏序关系 107
4.8.1 偏序关系和拟序关系 107
4.8.2 哈斯图 109
4.8.3 全序关系和良序关系 112
习题4.8 113
4.9 例题解析 113
复习题4 120
第5章 函数 121
5.1 函数的基本概念 121
习题5.1 123
5.2 特殊函数及特征函数 124
5.2.1 特殊函数 124
5.2.2 特征函数 125
习题5.2 127
5.3 逆函数与复合函数 127
5.3.1 逆函数 127
5.3.2 复合函数 128
5.4.1 集合的势 131
5.4 集合的势与无限集合 131
习题5.3 131
5.4.2 可数集 132
习题5.4 134
5.5 例题解析 134
复习题5 136
第6章 图论基础 138
6.1 图的基本概念 138
6.1.1 图的定义及相关概念 139
6.1.2 结点的度 140
6.1.3 完全图和补图 142
6.1.4 子图与图的同构 143
习题6.1 145
6.2 图的连通性 146
6.2.1 通路 146
6.2.2 无向图和有向图的连通性 148
6.2.3 割边和割点 149
习题6.2 149
6.3 图的矩阵表示 150
6.3.1 无向图的关联矩阵 150
6.3.2 无环有向图的关联矩阵 151
6.3.3 有向图的邻接矩阵 151
6.3.4 无向简单图的邻接矩阵 153
6.3.5 有向图的可达矩阵 153
习题6.3 153
6.4 欧拉图与哈密尔顿图 154
6.4.1 欧拉图 154
6.4.2 哈密尔顿图 158
习题6.4 160
6.5.1 最短路问题 161
6.5 图论的应用 161
6.5.2 中国邮递员问题 163
6.5.3 旅行售货员问题 166
习题6.5 168
6.6 例题解析 168
复习题6 171
第7章 特殊图类 174
7.1 树 174
7.1.1 树的定义及性质 174
7.1.2 生成树 176
7.1.3 最小生成树 178
习题7.1 179
7.2 根树 180
7.2.1 根树及相关概念 180
7.2.2 二元树 181
7.2.3 二元树的一个应用——前缀码 183
习题7.2 186
7.3 二部图与匹配 186
7.3.1 二部图的概念及性质 186
7.3.2 二部图的匹配 187
习题7.3 188
7.4 平面图 189
7.4.1 平面图的定义 189
7.4.2 欧拉公式 190
7.4.3 库拉图斯基定理 192
习题7.4 193
7.5 例题解析 194
复习题7 196
8.1 二元运算及其性质 198
8.1.1 运算 198
第8章 代数系统 198
8.1.2 二元运算的性质 199
8.1.3 代数系统的特殊元素 201
习题8.1 203
8.2 代数系统 子代数 积代数 204
8.2.1 代数系统 204
8.2.2 子代数 205
8.2.3 积代数 205
习题8.2 206
8.3 同态与同构 206
8.3.1 同态与同构的概念 206
8.3.2 满同态的性质 207
8.4 例题解析 209
习题8.3 209
复习题8 211
第9章 特殊的代数系统 212
9.1 半群与独异点 212
9.1.1 半群 212
9.1.2 独异点 213
习题9.1 214
9.2 群的定义与性质 215
9.2.1 群的定义 215
9.2.2 群的性质 216
9.2.3 群的同态 217
习题9.2 218
9.3 循环群与置换群 218
9.3.1 循环群 218
9.3.2 置换群 220
9.4 子群及其特征 223
习题9.3 223
习题9.4 224
＊9.5 陪集 正规子群和商群 225
9.5.1 子群的陪集 225
9.5.2 正规子群 227
9.5.3 商群 228
习题9.5 229
＊9.6 环和域 229
9.6.1 环的定义及其性质 229
9.6.2 子环 231
9.6.3 整环和域 232
习题9.6 234
9.7 例题解析 234
复习题9 235
10.1.1 格的定义 237
10.1 格 237
第10章 格和布尔代数 237
10.1.2 格的对偶原理和性质 239
习题10.1 241
10.2 格的代数定义 241
习题10.2 243
10.3 特殊的格 243
10.3.1 分配格 243
10.3.2 有界格和有补格 244
10.3.3 有补分配格 246
习题10.3 246
10.4 布尔代数 247
习题10.4 249
10.5 例题解析 249
复习题10 251
参考文献 252