第一篇 集合论 3
第1章 集合 3
1.1集合的基本概念 3
1.2集合的运算 5
1.3包含排斥原理 9
第2章 二元关系 12
2.1关系 12
2.2关系矩阵和关系图 16
2.3关系的运算 20
2.4闭包运算 23
2.5等价关系和相容关系 28
2.6偏序关系 33
第3章 函数和运算 37
3.1函数 37
3.2运算 42
第4章 无限集合 45
4.1基数 45
4.2可列集 47
4.3不可列集 50
4.4基数的比较 52
第5章 形式语言 57
5.1文法和语言 57
5.2文法的类型 62
第二篇 代数结构 69
第1章 代数系统 69
1.1代数系统的实例和一般性质 69
1.2同态和同构 73
1.3商代数与积代数 80
第2章 半群和群 84
2.1半群和有幺半群 84
2.2群和循环群 88
2.3二面体群、置换群 92
2.4子群、群的同态 98
2.5陪集、正规子群、商群 101
第3章 格和布尔代数 106
3.1格 106
3.2布尔代数 114
3.3其他代数系统 121
第4章 群码 125
4.1通信模型和错误校正的基本概念 125
4.2二进制编码 128
4.3解码和错误校正 136
第三篇 数理逻辑 147
第1章 命题演算 147
1.1命题和逻辑连接词 147
1.2合式公式 150
1.3真值表、永真式 153
1.4命题演算中的等价关系 157
1.5逻辑连接词的可省略性 161
1.6范式 165
1.7推理和证明方法 172
第2章 谓词演算 179
2.1谓词 179
2.2量词 182
2.3合式公式 185
2.4合式公式的有效性 192
2.5谓词演算的等价公式 195
2.6谓词公式的范式 201
第3章 推理系统 206
3.1自然推理系统 206
3.2量词规则 212
3.3导出规则和运算符规则 216
3.4其他的命题逻辑系统 220
3.5永真式系统 224
第4章 消解法 230
4.1句形 230
4.2 Herbrand过程 234
4.3一致化算法 240
4.4消解规则 244
第5章 递归函数 248
5.1数论递归函数 248
5.2非数值递归函数 253
5.3部分递归函数和递归集合 259
第四篇 图论 267
第1章 图的定义和实例 267
1.1图的基本概念 267
1.2子图 273
1.3图的运算 276
1.4图的同构 280
第2章 路与回路 283
2.1路径与回路 283
2.2欧拉路径与欧拉回路 289
2.3M图 294
2.4哈米尔顿路径与回路 297
第3章 通路与最短通路 302
3.1通路的集合 302
3.2最短路径 307
3.3多端点的最短路径 313
3.4中国邮递员问题 317
第4章 树 320
4.1树 320
4.2生成树 321
4.3最优树 324
4.4基本回路与环路空间 327
第5章 关联集和割集 332
5.1关联集和割集 332
5.2完全图的割集 335
5.3关联集生成割集 339
5.4生成树生成割集 345
第6章 图的连通度 349
6.1连通度 349
6.2不可分离图 353
第7章 图的矩阵表示 357
7.1关联矩阵 357
7.2回路矩阵 363
7.3割集矩阵 372
第8章 平面图和对偶 379
8.1平面图 379
8.2平面图的欧拉公式 383
8.3对偶图 386
8.4图的厚度 393
第9章 图的着色 397
9.1顶点着色 397
9.2地图的着色 400
9.3边着色 403
9.4色多项式 405
第10章 有向图 410
10.1有向图 410
10.2连通有向图 413
10.3有向树和有序树 418
第11章 有向图的矩阵表示 421
11.1有向图的关联矩阵和回路矩阵 421
11.2有向图的割集矩阵 429
11.3电网络方程 435
11.4支路电压电流关系 444
第12章 生成树的产生 452
12.1生成树的基本变换 452
12.2生成树的生成 455
12.3生成树的计数 464
参考文献 467