第1篇 集合论 3
第1章 集合 3
1.1集合的概念及表示 3
1.1.1基本概念 3
1.1.2集合的表示 4
1.2特殊集合 6
1.2.1子集合 6
1.2.2幂集合 7
1.2.3补集合 7
1.3集合的运算 8
1.3.1基本运算 8
1.3.2运算的性质 9
1.4计数问题 11
1.4.1基本计数原理 11
1.4.2排列与组合 12
1.4.3容斥原理 13
1.5集合的应用 17
习题 20
第2章 关系 24
2.1关系的概念及表示 24
2.1.1序偶与笛卡儿积 24
2.1.2关系的定义 26
2.1.3关系的表示 28
2.2关系的性质 30
2.2.1性质的定义 30
2.2.2性质的判别 33
2.3关系的运算 35
2.3.1基本运算 35
2.3.2复合运算 36
2.3.3逆运算 39
2.3.4幂运算 41
2.3.5闭包运算 44
2.3.6关系性质的运算封闭性 49
2.4特殊关系 51
2.4.1等价关系 51
2.4.2相容关系 56
2.4.3偏序关系 58
2.5关系的应用 65
习题 68
第3章 函数 75
3.1函数的概念 75
3.1.1函数的定义 75
3.1.2特殊函数 78
3.2函数的运算 80
3.2.1复合运算 80
3.2.2逆运算 82
3.3函数的应用 83
习题 86
第2篇 数理逻辑 91
第4章 命题逻辑 91
4.1命题逻辑的基本概念 91
4.1.1命题 91
4.1.2联结词 93
4.2命题逻辑公式 98
4.2.1命题公式及其解释 98
4.2.2命题公式的分类 104
4.2.3命题公式的等值式 107
4.2.4命题公式的范式 111
4.3命题逻辑推理 122
4.3.1推理的基本概念 122
4.3.2简单证明推理 125
4.3.3构造证明推理 129
4.4命题逻辑的应用 135
习题 140
第5章 谓词逻辑 145
5.1谓词逻辑的基本概念 145
5.1.1个体词 145
5.1.2谓词 146
5.1.3函词 147
5.1.4量词 148
5.2谓词逻辑公式 149
5.2.1谓词公式及其解释 149
5.2.2谓词公式的分类 156
5.2.3谓词公式的等值式 158
5.2.4谓词公式的范式 164
5.3谓词逻辑推理 168
5.4谓词逻辑的应用 176
习题 179
第3篇 抽象代数 189
第6章 代数系统 189
6.1代数系统的基本概念 189
6.1.1代数运算 189
6.1.2代数系统 191
6.2代数运算的性质 192
6.2.1基本性质 192
6.2.2特殊元素 198
6.3相互联系的代数系统 202
6.3.1同构代数系统 202
6.3.2同态代数系统 206
6.3.3商代数系统 210
6.4代数系统的应用 215
习题 217
第7章 典型代数系统 221
7.1半群和群 221
7.1.1半群 221
7.1.2群 227
7.1.3特殊群 244
7.1.4群的应用 250
7.2环和域 254
7.2.1环 254
7.2.2域 259
7.2.3域的应用 261
7.3格和布尔代数 265
7.3.1格 265
7.3.2特殊格 271
7.3.3布尔代数 274
7.3.4格的应用 280
习题 284
第4篇 图论基础 291
第8章图 291
8.1图的概念与表示 291
8.1.1基本概念 291
8.1.2图的连通性 298
8.1.3图的操作 302
8.1.4图的表示 303
8.2赋权图 307
8.2.1赋权图的定义 307
8.2.2最短通路问题 308
8.3欧拉图 309
8.3.1欧拉图的定义 309
8.3.2欧拉图的判定 311
8.3.3中国邮路问题 313
8.4哈密顿图 315
8.4.1哈密顿图的定义 315
8.4.2哈密顿图的判定 316
8.4.3货郎担问题 319
8.5二部图 321
8.5.1二部图的定义 321
8.5.2二部图的判定 322
8.5.3匹配问题 322
8.6平面图 326
8.6.1平面图的定义 326
8.6.2平面图的判定 328
8.6.3图的着色问题 330
习题 334
第9章树 340
9.1无向树 340
9.1.1基本概念 340
9.1.2生成树 343
9.1.3最小生成树问题 345
9.2有向树 348
9.2.1基本概念 348
9.2.2根树 349
9.2.3二叉树 353
9.2.4最优树问题 354
习题 360
参考文献 362