第一章 集合论 1
1.1集合的概念和术语 1
1.1.1集合的基本概念和表示 1
1.1.2集合之间的关系 3
1.1.3集合簇 4
1.2集合的运算 5
1.2.1集合的基本运算 5
1.2.2幂集 6
1.2.3 n元组和笛卡儿乘积 7
*1.2.4广义并和广义交 7
1.3集合运算的性质 8
1.3.1集合恒等式 8
1.3.2集合演算 10
1.3.3对偶原理 11
1.4有限集合的计数 12
*1.5罗素悖论 13
1.6小结 14
1.7习题 14
第二章 数论基础 18
2.1最大公因数和最小公倍数 18
2.1.1整除、同余、最大公因数和最小公倍数 18
2.1.2欧几里得算法 20
2.1.3最大公因数和最小公倍数的性质 21
2.2素数 23
2.2.1整数的素分解 23
2.2.2素性探测 24
2.3一次同余方程 26
2.3.1一次同余方程 26
2.3.2一次同余方程组 27
*2.3.3大整数的剩余表示法 30
*2.4 RSA公钥密码体制 30
2.5小结 32
2.6习题 32
第三章 命题逻辑 34
3.1命题和命题公式 34
3.1.1命题与逻辑联结词 34
3.1.2命题公式 37
3.2等值演算 39
3.2.1等值的概念 39
3.2.2等值演算 40
3.2.3对偶原理 41
3.3范式 41
3.3.1主析取范式 42
3.3.2主合取范式 43
3.3.3联结词的功能完备集 44
3.4命题逻辑的推理理论 45
3.5小结 48
3.6习题 49
第四章 一阶逻辑 51
4.1谓词 51
4.1.1谓词和量词 51
4.1.2谓词公式 53
4.2等值演算和前束范式 55
4.3.阶逻辑的推理理论 57
4.4小结 59
4.5习题 59
第五章 关系 62
5.1关系的概念 62
5.1.1二元关系 62
5.1.2二元关系的表示 64
*5.1.3n元关系 65
5.2关系运算 66
5.2.1关系的基本运算 66
5.2.2关系运算的性质 68
5.3关系的特殊性质及其闭包 70
5.3.1关系的特殊性质 70
5.3.2关系的闭包 71
5.4等价关系和划分 73
5.4.1等价关系和等价类 73
5.4.2划分和等价关系 75
5.5偏序关系 76
5.5.1偏序关系和偏序集 77
5.5.2哈斯图 78
5.5.3偏序集的性质 78
*5.5.4拓扑序列 79
*5.5.5格 80
5.6小结 81
5.7习题 81
第六章 函数和集合的基数 86
6.1函数的概念和性质 86
6.1.1函数的基本概念 86
6.1.2函数的复合和逆 88
6.2集合的基数 91
6.2.1集合的等势 91
6.2.2可数集 92
6.2.3无限集和集合的基数 94
*6.3不可解问题 96
6.3.1不可解问题的存在性 96
6.3.2停机问题 97
6.4小结 98
6.5习题 99
第七章 图论基础 101
7.1图及其表示 101
7.1.1图的概念 101
7.1.2图的矩阵表示 103
7.1.3几种特殊的图 105
7.1.4子图和图运算 108
7.2握手定理 109
7.3图的连通性 110
7.3.1通路和回路 110
7.3.2图的连通性 111
7.3.3矩阵运算和连通性 113
*7.4最短通路和Dijkstra算法 114
7.4.1广度优先搜索算法 115
7.4.2带权图和Dijkstra算法 116
7.5顶点着色 117
7.6图同构 121
7.7小结 122
7.8习题 123
第八章 具有特殊性质的图 126
8.1欧拉图 126
8.1.1欧拉图的概念 126
8.1.2无向欧拉图的性质 127
8.1.3有向欧拉图的性质 128
8.2哈密顿图 129
8.2.1哈密顿图的概念 129
8.2.2无向哈密顿图的性质 130
*8.2.3格雷码 131
*8.2.4竞赛图 132
8.3平面图 133
8.3.1平面图的概念 133
8.3.2平面图的性质 135
8.4无向树 137
8.4无向树的概念 137
8.4.2无向树的基本性质 137
*8.4.3求最小生成树的Kruskal算法 141
8.5有向树 142
8.5.1有向树和根树及其简单性质 142
*8.5.2求最优树的Huffman算法 145
8.6小结 146
8.7习题 147
第九章 基本计数方法 150
9.1鸽笼原理 150
9.2加法原理与乘法原理 151
9.3排列与组合 152
9.3.1排列 152
9.3.2组合 153
9.4二项式系数 154
9.5可重复的排列和组合 155
9.5.1可重复的排列 155
9.5.2可重复的组合 156
9.6容斥原理 157
9.7生成排列和组合 159
9.7.1生成排列 159
9.7.2生成组合 160
9.8小结 160
9.9习题 160
第十章 递推关系和生成函数 163
10.1递推关系 163
10.2常系数线性递推关系 165
10.2.1求解常系数线性齐次递推关系 166
*10.2.2求解常系数线性非齐次递推关系 169
10.3生成函数 171
10.3.1幂级数型生成函数 171
*10.3.2指数型生成函数 173
10.4生成函数应用举例 175
10.5小结 178
10.6习题 179
第十一章 代数结构基础 181
11.1代数系统 181
11.2二元运算的性质 182
11.3半群和独异点 183
11.4同态和同构 184
11.5小结 186
11.6习题 186
第十二章 群 188
12.1群 188
12.2子群 189
12.2.1子群 190
12.2.2元素的阶 191
12.3循环群和群的直积 191
12.3.1循环群 191
*12.3.2群的直积 192
12.4陪集和正规子群 193
*12.5群同态 194
12.6变换群和置换群 195
*12.7群码 198
12.7.1纠错码的基本概念 198
12.7.2线性码的生成矩阵与校验矩阵 199
12.7.3群码 202
12.8小结 205
12.9习题 205
第十三章 环和域 209
13.1环 209
13.1.1环的定义 209
13.1.2特殊元素和性质 210
13.1.3环的分类 210
13.2子环、理想和商环 212
13.2.1子环和理想 212
13.2.2商环 212
*13.3环同态 213
13.4一元多项式环与多项式编码 214
13.4.1域上的一元多项式 215
*13.4.2一元多项式环的主理想 218
*13.4.3多项式编码 219
*13.5域 221
*13.5.1域的基本概念和简单性质 221
*13.5.2有限域 222
*13.5.3扩域的性质和几何作图问题 223
13.6小结 225
13.7习题 225
第十四章 格和布尔代数 228
14.1格 228
14.1.1偏序格 228
14.1.2代数格 231
14.2有界格、有补格和分配格 232
14.3布尔代数 234
14.3.1布尔格和布尔代数 234
14.3.2有限布尔代数 235
14.3.3对偶原理 235
14.4小结 235
14.5习题 236
参考文献 238