离散数学及其应用

第2章　谓词逻辑29
2.1　谓词逻辑的基本概念29
2.1.1　个体词和谓词29
2.1.2　量词31
2.2　谓词合式公式34
2.3　谓词公式的解释和分类35
2.3.1　谓词公式的解释35
2.3.2　谓词公式的分类36
2.4　谓词演算的关系式37
2.5　前束范式40
2.6　谓词演算的推理41
2.6.1　推理理论41
2.6.2　推理问题的证明43
习题48
第二部分　集合、关系和函数
第3章　集合54
3.1　集合及其表示54
3.2　集合间的关系55
3.3　集合的运算57
3.4　自然数62
3.5　集合的特征函数63
习题64
第4章　关系和函数67
4.1　关系的概念67
4.1.1　有序对和有序n元组67
4.1.2　笛卡儿积67
4.1.3　关系的概念69
4.2　关系的表示法71
4.2.1　用集合表示关系71
4.2.2　用关系图表示关系72
4.2.3　用矩阵表示关系73
4.3　关系的运算73
4.3.1　关系的逆运算74
4.3.2　关系的复合运算75
4.4　关系的性质79
4.5　关系的闭包85
4.6　等价关系和等价类91
4.6.1　等价关系91
4.6.2　等价类92
4.7　偏序关系96
4.8　函数100
4.8.1　函数的定义100
4.8.2　特殊函数101
4.8.3　复合函数103
4.8.4　反函数105
4.8.5　集合的基数106
习题108
第三部分　组合数学
第5章　计数114
5.1　基本计数法则114
5.1.1　加法法则114
5.1.2　乘法法则115
5.2　排列与组合117
5.2.1　排列117
5.2.2　组合118
5.2.3　多重集的排列与组合119
5.2.4　二项式定理120
5.3　容斥原理121
5.4　鸽巢原理125
习题126
第6章　高级计数技术128
6.1　递推方程128
6.1.1　求解递推方程130
6.1.2　常系数线性齐次递推方程的求解130
6.1.3　常系数线性非齐次递推方程的求解133
6.2　生成函数136
6.2.1　牛顿二项式系数与牛顿二项式定理136
6.2.2　生成函数的定义及其性质138
6.2.3　生成函数的应用139
6.2.4　指数型生成函数142
习题144
第四部分　图　　论
第7章　图论148
7.1　图的基本概念148
7.1.1　无向图和有向图148
7.1.2　度的概念150
7.1.3　图的分类151
7.1.4　子图与补图155
7.1.5　图的同构157
7.2　通路与回路、连通的概念158
7.2.1　通路与回路158
7.2.2　连通的概念160
7.3　图的表示164
7.3.1　邻接表164
7.3.2　邻接矩阵165
7.3.3　可达矩阵169
7.3.4　关联矩阵169
7.4　图的运算172
习题172
第8章　特殊图176
8.1　欧拉图与哈密顿图176
8.1.1　欧拉图176
8.1.2　哈密顿图178
8.2　带权图182
8.2.1　旅行商问题182
8.2.2　最短路径问题182
8.2.3　中国邮路问题184
8.3　匹配和二分图185
8.3.1　匹配185
8.3.2　二分图186
8.4　平面图189
8.4.1　平面图的定义189
8.4.2　平面图的欧拉公式191
8.4.3　对偶图与着色194
习题197
第9章　树200
9.1　树的定义和特性200
9.2　生成树202
9.2.1　生成树的定义202
9.2.2　最小生成树及其应用203
9.3　根树205
9.3.1　有向根树和有序根树205
9.3.2　有序根树的遍历208
9.4　根树的应用209
9.4.1　前缀码209
9.4.2　最优二元树和赫夫曼编码211
9.4.3　决策树212
习题213
第五部分　代数结构
第10章　代数系统218
10.1　代数系统的概念和性质218
10.1.1　二元运算及其性质218
10.1.2　代数系统和子代数221
10.1.3　代数系统的性质222
10.1.4　代数系统的分类224
10.2　代数系统的同态和同构225
10.3　半群227
10.4　群229
10.4.1　群及其基本性质229
10.4.2　子群232
10.5　循环群和置换群233
10.5.1　循环群233
10.5.2　置换群235
10.6　环和域236
习题238
第11章　格与布尔代数240
11.1　格240
11.1.1　格的基本概念240
11.1.2　分配格243
11.1.3　有界格和有补格245
11.2　布尔代数246
11.2.1　布尔代数的基本概念246
11.2.2　布尔表达式与布尔函数248
11.2.3　布尔代数和数字电路249
习题251
参考文献254