目录
第1章集合、映射与运算1
1.1集合的有关概念1
1.1.1集合1
1.1.2子集2
1.1.3幂集3
1.1.4n元组4
1.1.5笛卡儿积4
习题1.15
1.2映射的有关概念5
1.2.1映射的定义5
1.2.2映射的性质7
1.2.3逆映射9
1.2.4复合映射10
习题1.211
1.3运算的定义及性质12
1.3.1运算的定义13
1.3.2运算的性质14
习题1.318
1.4集合的运算19
1.4.1并运算19
1.4.2交运算20
1.4.3补运算21
1.4.4差运算23
1.4.5对称差运算24
习题1.425
1.5集合的划分与覆盖26
1.5.1集合的划分26
1.5.2集合的覆盖28
习题1.529
1.6集合对等29
1.6.1集合对等的定义29
1.6.2无限集合30
1.6.3集合的基数30
1.6.4可数集合31
1.6.5不可数集合31
1.6.6基数的比较32
习题1.632
本章小结32第2章关系35
2.1关系的概念35
2.1.1n元关系的定义35
2.1.2二元关系36
2.1.3关系的定义域和值域37
2.1.4关系的表示38
2.1.5函数的关系定义39
习题2.140
2.2关系的运算41
2.2.1关系的集合运算41
2.2.2关系的逆运算42
2.2.3关系的复合运算42
2.2.4关系的其他运算45
习题2.246
2.3关系的性质47
2.3.1自反性47
2.3.2反自反性48
2.3.3对称性49
2.3.4反对称性49
2.3.5传递性50
习题2.353
2.4关系的闭包54
2.4.1自反闭包54
2.4.2对称闭包55
2.4.3传递闭包55
习题2.459
2.5等价关系60
2.5.1等价关系的定义60
2.5.2等价类61
习题2.562
2.6相容关系63
2.6.1相容关系的定义64
2.6.2相容类65
习题2.665
2.7偏序关系66
2.7.1偏序关系的定义66
2.7.2偏序集的哈斯图67
2.7.3偏序集中的特殊元素68
习题2.770
本章小结71第3章命题逻辑74
3.1命题的有关概念74
习题3.176
3.2逻辑联结词76
3.2.1否定联结词?瘙綈76
3.2.2合取联结词∧77
3.2.3析取联结词∨77
3.2.4异或联结词77
3.2.5条件联结词→78
3.2.6双条件联结词79
3.2.7与非联结词↑79
3.2.8或非联结词↓79
3.2.9条件否定联结词→n79
习题3.280
3.3命题公式及其真值表80
3.3.1命题公式的定义80
3.3.2命题的符号化81
3.3.3命题公式的真值表82
3.3.4命题公式的类型82
习题3.384
3.4逻辑等值的命题公式85
3.4.1逻辑等值的定义85
3.4.2基本等值式86
3.4.3等值演算法87
3.4.4对偶原理88
习题3.489
3.5命题公式的范式90
3.5.1命题公式的析取范式及合取范式90
3.5.2命题公式的主析取范式及主合取范式93
习题3.598
3.6联结词集合的功能完备性100
3.6.1联结词的个数100
3.6.2功能完备联结词集100
习题3.6102
3.7命题逻辑中的推理103
3.7.1推理形式有效性的定义103
3.7.2基本推理规则104
3.7.3命题逻辑的自然推理系统105
习题3.7109
本章小结110第4章谓词逻辑113
4.1个体、谓词、量词和函词113
4.1.1个体113
4.1.2谓词114
4.1.3量词114
4.1.4函词116
习题4.1116
4.2谓词公式及命题的符号化117
4.2.1谓词公式117
4.2.2命题的符号化118
习题4.2119
4.3谓词公式的解释及类型121
4.3.1谓词公式的解释121
4.3.2谓词公式的类型122
习题4.3123
4.4逻辑等值的谓词公式124
4.4.1谓词公式等值的定义124
4.4.2基本等值式124
习题4.4126
4.5谓词公式的前束范式126
4.5.1谓词公式的前束范式的定义127
4.5.2谓词公式的前束范式的计算127
习题4.5127
4.6谓词逻辑中的推理128
4.6.1逻辑蕴涵式128
4.6.2基本推理规则128
4.6.3谓词逻辑的自然推理系统129
习题4.6131
本章小结132第5章初等数论135
5.1整除关系与素数135
5.1.1整除关系与带余除法135
5.1.2素数与素因数分解136
5.1.3最大公因数138
5.1.4最小公倍数141
习题5.1141
5.2模同余关系142
5.2.1模同余关系142
5.2.2模同余方程(组)145
习题5.2147
5.3RSA密码算法148
5.3.1加密与解密过程148
5.3.2RSA密码算法148
习题5.3149
本章小结150第6章图论152
6.1图的基本概念152
6.1.1图的定义152
6.1.2邻接154
6.1.3关联154
6.1.4简单图154
习题6.1155
6.2节点的度数156
习题6.2158
6.3子图、图的运算和图同构158
6.3.1子图158
6.3.2图的运算159
6.3.3图同构160
习题6.3161
6.4路与回路162
6.4.1路162
6.4.2回路162
习题6.4163
6.5图的连通性164
6.5.1无向图的连通性164
6.5.2连通无向图的点连通度与边连通度165
6.5.3有向图的连通性166
习题6.5168
6.6图的矩阵表示169
6.6.1图的邻接矩阵169
6.6.2图的可达矩阵170
6.6.3图的关联矩阵171
习题6.6172
6.7赋权图及最短路径173
6.7.1赋权图173
6.7.2最短路径174
习题6.7175
本章小结176第7章几类特殊的图178
7.1欧拉图178
7.1.1欧拉图的有关概念178
7.1.2欧拉定理178
7.1.3中国邮递员问题179
习题7.1180
7.2哈密顿图181
7.2.1哈密顿图的有关概念181
7.2.2哈密顿图的必要条件182
7.2.3哈密顿图的充分条件182
7.2.4旅行商问题184
习题7.2184
7.3无向树185
7.3.1无向树的定义185
7.3.2无向树的性质186
7.3.3生成树187
7.3.4最小生成树188
习题7.3189
7.4有向树189
7.4.1有向树的定义190
7.4.2根树190
7.4.3m叉树191
7.4.4有序树194
7.4.5定位二叉树194
习题7.4196
7.5平面图198
7.5.1平面图的有关概念198
7.5.2欧拉公式199
7.5.3库拉托夫斯基定理200
7.5.4平面图的对偶图200
习题7.5201
7.6平面图的面着色202
7.6.1平面图的面着色定义203
7.6.2图的节点着色203
7.6.3任意图的边着色204
习题7.6205
7.7二部图及匹配206
7.7.1二部图206
7.7.2匹配207
习题7.7208
本章小结208第8章组合计数211
8.1计数原理、排列组合与二项式定理211
8.1.1计数原理211
8.1.2排列212
8.1.3组合213
8.1.4二项式定理214
习题8.1214
8.2生成函数214
8.2.1组合计数生成函数215
8.2.2排列计数生成函数217
习题8.2218
8.3递归关系218
8.3.1递归关系的概念219
8.3.2常用的递归关系求解方法220
习题8.3225
本章小结225第9章代数结构227
9.1代数结构简介227
9.1.1代数结构的定义227
9.1.2两种最简单的代数结构: 半群及独异点228
9.1.3子代数229
9.1.4代数结构的同态与同构229
习题9.1231
9.2群232
9.2.1群的有关概念232
9.2.2子群235
9.2.3群的同态235
习题9.2236
9.3环和域237
9.3.1环的定义237
9.3.2几种特殊的环238
9.3.3域的定义239
9.3.4有限域240
习题9.3240
9.4格与布尔代数241
9.4.1格的定义和性质242
9.4.2分配格245
9.4.3有补格246
9.4.4布尔代数247
习题9.4249
本章小结250附录A离散数学常用符号253附录B中英文名词对照表258附录C部分习题答案及提示263参考文献288
