第一部分 集合论 3
第1章 集合及其运算 3
1.1集合的概念 3
1.2集合之间的关系 5
1.3集合的运算 7
1.4笛卡儿积 13
1.5有穷集合的基数 15
第2章 映射 19
2.1映射的基本概念 19
2.2抽屉原理 23
2.3映射的合成和逆 24
2.4置换 27
2.5二元运算和n元运算 29
第3章 关系 31
3.1关系的概念 31
3.2关系矩阵和关系图 33
3.3关系的性质 35
3.4复合关系和逆关系 38
3.5关系的闭包 41
3.6等价关系与集合的划分 43
3.7偏序关系 46
第4章 无穷集合及其基数 49
4.1可数集 49
4.2连续统集 52
4.3基数及其比较 54
4.4康托—伯恩斯坦定理 56
第二部分 图论 61
第5章 图的基本概念 61
5.1图的基本定义 61
5.2路、圈与连通图 65
5.3补图与偶图 67
5.4欧拉图和哈密顿图 69
5.5图的矩阵表示 73
5.6带权图与最短路问题 75
第6章树 78
6.1树及其性质 78
6.2生成树 80
6.3割点和桥 82
6.4顶点连通度和边连通度 84
第7章 平面图与图的着色 86
7.1平面图及其欧拉公式 86
7.2库拉托夫斯基定理 88
7.3图的着色 90
第8章 有向图 94
8.1有向图的概念 94
8.2有向路与有向圈 96
8.3有向树与有序树 100
8.4判定树与比赛图 103
第三部分 近世代数 107
第9章群 107
9.1二元代数运算 107
9.2半群和么半群 109
9.3群的定义和性质 112
9.4子群 115
9.5变换群和循环群 117
9.6陪集和拉格朗日定理 119
9.7同态与同构 121
第10章 环与域 126
10.1环与域的定义及性质 126
10.2同态和理想 130
10.3环的同态基本定理 133
第11章 格与布尔代数 135
11.1格的定义及简单性质 135
11.2特殊的格 139
11.3布尔代数的定义及简单性质 140
11.4布尔表达式与布尔函数 144
第四部分 数理逻辑 151
第12章 命题逻辑 151
12.1命题及联结词 151
12.2命题公式与恒等式 154
12.3重言式与蕴含式 160
12.4其他联结词 164
12.5范式 166
12.6命题逻辑的推理理论 169
第13章 谓词逻辑 173
13.1谓词与量词 173
13.2谓词公式与变元的约束 176
13.3谓词演算的恒等式与蕴含式 178
13.4前束范式 180
13.5谓词逻辑的推理理论 182
参考文献 184