目录
第1章集合、映射与运算1
1.1集合的有关概念1
1.1.1集合1
1.1.2子集3
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
本章小结33第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关系的复合运算43
2.2.4关系的其他运算46
习题2.246
2.3关系的性质47
2.3.1自反性47
2.3.2反自反性48
2.3.3对称性49
2.3.4反对称性49
2.3.5传递性51
习题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
本章小结72第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条件否定联结词 79
习题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推理形式有效性的定义105
3.7.3命题逻辑的自然推理系统105
习题3.7109
本章小结110第4章谓词逻辑112
4.1个体、谓词、量词和函词112
4.1.1个体112
4.1.2谓词113
4.1.3量词113
4.1.4函词115
习题4.1115
4.2谓词公式及命题的符号化116
4.2.1谓词公式116
4.2.2命题的符号化117
习题4.2118
4.3谓词公式的解释及类型120
4.3.1谓词公式的解释120
4.3.2谓词公式的类型121
习题4.3122
4.4逻辑等值的谓词公式123
4.4.1谓词公式等值的定义123
4.4.2基本等值式123
习题4.4125
4.5谓词公式的前束范式126
4.5.1谓词公式的前束范式的定义126
4.5.2谓词公式的前束范式的计算126
习题4.5127
4.6谓词逻辑中的推理127
4.6.1逻辑蕴涵式127
4.6.2基本推理规则128
4.6.3谓词逻辑的自然推理系统128
习题4.6130
4.7常用证明方法131
4.7.1与证明有关的概念131
4.7.2几种常用的证明方法132
习题4.7134
本章小结134第5章初等数论137
5.1整除关系与素数137
5.1.1整除关系与带余除法137
5.1.2素数与素因数分解138
5.1.3最大公因数140
5.1.4最小公倍数143
习题5.1143
5.2模同余关系144
5.2.1模同余关系144
5.2.2模同余方程(组)148
习题5.2149
5.3RSA密码算法150
5.3.1加密与解密过程150
5.3.2RSA密码算法150
习题5.3152
本章小结152第6章图论基础154
6.1图的基本概念154
6.1.1图的定义154
6.1.2邻接156
6.1.3关联156
6.1.4简单图及补图156
习题6.1157
6.2节点的度数158
习题6.2160
6.3子图、图的运算和图同构160
6.3.1子图160
6.3.2图的运算161
6.3.3图同构162
习题6.3163
6.4路与回路164
6.4.1路164
6.4.2回路164
习题6.4165
6.5图的连通性166
6.5.1无向图的连通性166
6.5.2连通无向图的点连通度与边连通度167
6.5.3有向图的连通性168
习题6.5170
6.6图的矩阵表示171
6.6.1图的邻接矩阵171
6.6.2图的可达矩阵172
6.6.3图的关联矩阵173
习题6.6174
6.7赋权图及最短路径175
6.7.1赋权图175
6.7.2最短路径176
习题6.7177
本章小结178第7章几类特殊的图180
7.1欧拉图180
7.1.1欧拉图的有关概念180
7.1.2欧拉定理180
7.1.3中国邮递员问题181
习题7.1182
7.2哈密顿图183
7.2.1哈密顿图的有关概念183
7.2.2哈密顿图的必要条件184
7.2.3哈密顿图的充分条件184
7.2.4旅行商问题186
习题7.2186
7.3无向树187
7.3.1无向树的定义187
7.3.2无向树的性质188
7.3.3生成树189
7.3.4最小生成树190
习题7.3191
7.4有向树191
7.4.1有向树的定义192
7.4.2有根树192
7.4.3m叉树193
7.4.4有序树195
7.4.5定位二叉树196
习题7.4198
7.5平面图200
7.5.1平面图的有关概念200
7.5.2欧拉公式201
7.5.3库拉托夫斯基定理202
7.5.4平面图的对偶图202
习题7.5203
7.6平面图的面着色204
7.6.1平面图的面着色定义205
7.6.2图的节点着色205
7.6.3任意图的边着色206
习题7.6207
7.7二部图及匹配208
7.7.1二部图208
7.7.2匹配209
习题7.7210
本章小结210第8章组合计数213
8.1计数原理、排列组合与二项式定理213
8.1.1计数原理213
8.1.2排列214
8.1.3组合215
8.1.4二项式定理216
习题8.1216
8.2生成函数216
8.2.1组合计数生成函数217
8.2.2排列计数生成函数219
习题8.2220
8.3递归关系221
8.3.1递归关系的概念221
8.3.2常用的递归关系求解方法222
习题8.3227
本章小结228第9章代数结构230
9.1代数结构简介230
9.1.1代数结构的定义230
9.1.2两种最简单的代数结构: 半群及独异点231
9.1.3子代数232
9.1.4代数结构的同态与同构232
习题9.1234
9.2群235
9.2.1群的有关概念235
9.2.2子群238
9.2.3群的同态238
习题9.2239
9.3环和域240
9.3.1环的定义240
9.3.2几种特殊的环241
9.3.3域的定义242
9.3.4有限域243
习题9.3243
9.4格与布尔代数244
9.4.1格的定义和性质245
9.4.2分配格248
9.4.3有补格249
9.4.4布尔代数250
习题9.4252
本章小结253附录A离散数学常用符号256附录B中英文名词对照表261附录C部分习题答案及提示266参考文献291
