离散数学

**篇数 理 逻 辑
第1章命题逻辑/31.1命题及其表示3
1.1.1命题3
1.1.2命题的表示4
1.2联结词4
1.2.1否定5
1.2.2合取5
1.2.3析取6
1.2.4条件6
1.2.5双条件7
1.3命题公式与翻译8
1.3.1命题公式8
1.3.2翻译9
1.4真值表与等价式10
1.4.1真值表10
1.4.2等价式12
1.5重言式、蕴含式与对偶式14
1.5.1重言式14
1.5.2蕴含式15
1.5.3对偶式17
1.6联结词的完备集18
1.6.1不可兼析取18
1.6.2条件的否定19
1.6.3与非19
1.6.4或非19
1.6.5联结词的完备集20
1.7命题公式的范式21
1.7.1合取范式与析取范式211.7.2主析取范式23
1.7.3主合取范式26
1.7.4主析取范式与主合取范式之间的联系28
1.8推理理论29
1.8.1有效结论与推理规则29
1.8.2判断有效结论的常用方法31
1.9命题逻辑的应用35
1.10本章总结37
1.11本章习题38
〖1〗离散数学目录〖3〗〖3〗第2章谓词逻辑/44
2.1谓词的概念与表示44
2.1.1谓词的定义44
2.1.2n元谓词45
2.2命题函数与量词46
2.2.1命题函数46
2.2.2量词47
2.3谓词公式与翻译48
2.3.1谓词公式48
2.3.2谓词公式的翻译49
2.4变元的约束50
2.4.1约束变元与自由变元50
2.4.2约束变元的换名与自由变元的代入51
2.4.3有限论域客体变元的枚举52
2.5谓词演算的等价式与蕴含式52
2.5.1谓词公式的赋值及分类52
2.5.2谓词演算的等价式53
2.5.3谓词演算的蕴含式55
2.5.4多个量词之间的等价关系与蕴含关系56
2.6前束范式57
2.7谓词演算的推理理论58
2.8本章总结61
2.9本章习题63第二篇集合论
第3章集合/713.1集合的概念和表示法71
3.1.1集合的概念71
3.1.2集合的表示72
3.1.3特殊集合74
3.1.4集合之间的关系74
3.2集合的运算76
3.3序偶与笛卡儿积82
3.3.1序偶82
3.3.2笛卡儿积83
3.4包含排斥原理85
3.5集合的划分与覆盖87
3.6集合的应用89
3.7本章总结92
3.8本章习题95
第4章关系/100
4.1关系的概念与表示100
4.1.1关系的概念100
4.1.2关系的表示102
4.2关系的性质105
4.2.1关系的几种性质105
4.2.2性质的判别109
4.3复合关系和逆关系111
4.3.1复合关系111
4.3.2逆关系115
4.4关系的闭包运算117
4.4.1关系的闭包定义118
4.4.2关系闭包运算的相关定理118
4.5等价关系与等价类123
4.5.1等价关系124
4.5.2等价类125
4.5.3商集126
4.6相容关系128
4.6.1相容关系及其表示128
4.6.2相容类129
4.6.3*大相容类130
4.6.4完全覆盖131
4.7序关系132
4.7.1偏序关系及其表示132
4.7.2盖住关系132
4.7.3全序关系134
4.7.4特殊元素135
4.7.5良序集合137
4.8关系的应用138
4.9本章总结142
4.10本章习题143
第5章函数/151
5.1函数的概念151
5.2几种特殊的函数152
5.3函数的运算（复合、逆函数）154
5.3.1复合函数154
5.3.2逆函数155
5.4函数的应用157
5.5本章总结161
5.6本章习题162
第三篇代 数 系 统
第6章代数结构/1676.1代数系统引论167
6.2基本运算及其性质168
6.3半群与独异点174
6.4群与子群176
6.5阿贝尔群与循环群180
6.5.1阿贝尔群（交换群）180
6.5.2循环群180
6.6置换群183
6.7陪集与拉格朗日定理184
6.7.1陪集184
6.7.2拉格朗日定理186
6.8同构与同态188
6.8.1同构188
6.8.2同态190
6.9环与域193
6.9.1环193
6.9.2域196
6.10代数结构的应用198
6.10.1计数问题198
6.10.2群码与纠错码201
6.11本章总结215
6.12本章习题217
第7章格与布尔代数/221
7.1格的定义221
7.2分配格226
7.3有补格228
7.4布尔代数230
7.4.1布尔代数的一般概念230
7.4.2子代数231
7.4.3布尔同态与布尔同构232
7.5布尔代数表达式235
7.6格与布尔代数的应用242
7.6.1布尔函数的表示法243
7.6.2逻辑电路设计方法246
7.6.3时序逻辑电路的设计250
7.7本章总结254
7.8本章习题256
第四篇图论
第8章图/2618.1图的基本概念261
8.2路、回路与连通性267
8.2.1路与回路267
8.2.2无向图的连通性268
8.2.3有向图的连通性271
8.3图的矩阵表示273
8.3.1邻接矩阵273
8.3.2可达矩阵276
8.3.3关联矩阵277
8.4图的应用279
8.4.1无向图的应用279
8.4.2有向图的应用280
8.4.3混合图的应用280
8.4.4一些特殊简单图及其应用280
8.5本章总结282
8.6本章习题284
第9章特殊图/287
9.1欧拉图287
9.2哈密尔顿图292
9.3平面图296
9.4对偶图299
9.5树与根树302
9.5.1树的概念302
9.5.2生成树304
9.5.3根树305
9.6树与根树的应用307
9.6.1*小生成树307
9.6.2*优树308
9.7本章总结309
9.8本章习题312
参考文献/315