离散数学

目录 第1章命题演算基础1
1.1命题和联结词1
1.1.1命题1
1.1.2联结词2
1.1.3合式公式6
1.1.4命题逻辑的应用6
1.2真假性9
1.2.1解释9
1.2.2等价公式10
1.2.3联结词的完备集12
1.2.4对偶式和内否式13
1.3范式及其应用15
1.3.1范式15
1.3.2主范式17
1.3.3范式的应用20
1.4典型例题21
习题23
第2章命题演算的推理理论26
2.1命题演算的公理系统26
2.1.1公理系统的组成部分27
2.1.2公理系统的推理过程28
2.2若干重要的导出规则30
2.2.1分离规则的讨论30
2.2.2公理和定理的导出规则30
2.3命题演算的假设推理系统32
2.3.1假设推理系统的组成32
2.3.2假设推理系统的推理过程33〖1〗离 散 数 学 〖1〗目录 2.3.3额外假设推理法35
2.4命题演算的归结推理法37
2.4.1归结证明过程38
2.4.2归结证明示例39
2.5典型例题40
习题43
第3章谓词演算基础45
3.1谓词和个体45
3.1.1个体45
3.1.2谓词45
3.2函数项和量词48
3.2.1函数项48
3.2.2量词49
3.3自由变元和约束变元51
3.3.1自由出现和约束出现51
3.3.2改名和代入51
3.4永真性和可满足性53
3.4.1真假性53
3.4.2同真假性、永真性和可满足性55
3.4.3范式58
3.5唯一性量词和摹状词59
3.5.1唯一性量词59
3.5.2摹状词60
3.6典型例题61
习题62
第4章谓词演算的推理理论65
4.1谓词演算的永真推理系统65
4.1.1公理系统的组成部分65
4.1.2公理系统的推理过程67
4.2谓词演算的假设推理系统68
4.2.1假设推理系统的组成及证明方法68
4.2.2定理的假设推导过程69
4.3谓词演算的归结推理系统71
4.3.1置换72
4.3.2归结反演系统72
4.3.3霍恩子句逻辑程序75
4.4Prolog简介78
4.5典型例题80
习题82
第5章递归函数论85
5.1数论函数和数论谓词85
5.1.1数论函数85
5.1.2数论谓词和特征函数86
5.2函数的构造88
5.2.1迭置法88
5.2.2算子法90
5.2.3原始递归函数91
5.3典型例题92
习题92
第6章集合94
6.1集合的基本概念94
6.1.1集合的定义94
6.1.2集合的表示95
6.1.3集合的包含关系96
6.1.4集合的特点97
6.1.5多重集97
6.2集合的基本运算98
6.2.1集合的并、交、差98
6.2.2集合的对称差99
6.2.3文氏图100
6.2.4集合的幂集合101
6.2.5多个集合的并与交101
6.3全集和补集102
6.3.1全集和补集的定义102
6.3.2基本运算定理103
6.3.3集合的计算机表示104
6.4自然数与自然数集105
6.4.1后继105
6.4.2自然数和自然数集105
6.4.3皮亚诺公理假设106
6.4.4自然数集的性质107
6.4.5集合的递归定义与递归子程序108
6.5包含与排斥原理110
6.6典型例题112
习题113
第7章关系118
7.1集合的笛卡儿积集118
7.1.1有序二元组118
7.1.2笛卡儿积集118
7.1.3有序n元组、n个集合的笛卡儿积集119
7.2二元关系的基本概念120
7.2.1二元关系120
7.2.2二元关系的表示120
7.2.3二元关系与数据结构122
7.2.4二元关系的运算122
7.3n元关系及其运算125
7.3.1n元关系125
7.3.2n元关系的运算125
7.4二元关系的性质128
7.4.1自反性、反自反性、对称性、反对称性、传递性和反传递性128
7.4.2二元关系性质的判定定理130
7.5二元关系的闭包运算132
7.5.1自反闭包、对称闭包和传递闭包132
7.5.2闭包的判定定理132
7.6等价关系和集合的划分137
7.6.1等价关系和等价类137
7.6.2商集合138
7.6.3集合的划分138
7.7偏序关系和格141
7.7.1偏序关系和偏序集141
7.7.2哈斯图142
7.7.3链、反链、全序集142
7.7.4极大元、极小元、最大元和最小元143
7.7.5上界、下界、最小上界和最大下界143
7.7.6格144
7.7.7拓扑排序145
7.8粗糙集概论147
7.8.1知识与知识分类147
7.8.2集合近似与粗糙集概念150
7.9典型例题151
习题152
第8章函数与集合的势157
8.1函数的基本概念157
8.1.1函数(映射)的定义157
8.1.2函数的性质159
8.2函数的复合和逆函数160
8.2.1函数的复合160
8.2.2左可逆函数、右可逆函数和逆函数162
8.3无限集164
8.3.1势164
8.3.2有限集和无限集166
8.3.3可数无限集和不可数无限集166
8.4集合势大小的比较168
8.4.1集合势的大小168
8.4.2伯恩斯坦定理169
8.5鸽巢原理169
8.6典型例题171
习题172
第9章图论175
9.1图的基本概念175
9.1.1有向图和无向图176
9.1.2图的同构、子图和补图177
9.1.3顶点的度178
9.2图中的通路、图的连通性和图的矩阵表示179
9.2.1通路、回路和连通性179
9.2.2图的矩阵表示181
9.3带权图与带权图中的最短通路184
9.4欧拉图187
9.5哈密顿图190
9.6二部图194
9.7平面图与平面图的着色197
9.7.1平面图197
9.7.2平面图的着色200
9.8典型例题203
习题204
第10章树和有序树209
10.1树的基本概念209
10.2连通图的生成树和带权连通图的最小生成树211
10.3有序树214
10.3.1根树214
10.3.2根树的应用216
10.4前缀码和最优2分树218
10.4.1前缀码218
10.4.2最优2分树220
10.4.3赫夫曼编码222
10.5典型例题224
习题226
第11章群和环229
11.1代数运算的基本概念229
11.1.1代数运算229
11.1.2交换律、结合律230
11.1.3n元运算231
11.2代数系统和半群232
11.2.1代数系统232
11.2.2同态映射和同构映射233
11.2.3半群与含幺半群235
11.3群的基本概念236
11.3.1逆元236
11.3.2群的定义237
11.3.3群的同态、同构240
11.3.4无限群、有限群、交换群和元的阶242
11.4群的几个等价定义244
11.5变换群和置换群245
11.5.1变换群246
11.5.2置换群247
11.6循环群250
11.7子群252
11.7.1子群的定义252
11.7.2子群的判定定理252
11.8子群的陪集254
11.8.1按子群划分的剩余类254
11.8.2右陪集254
11.8.3左陪集256
11.8.4拉格朗日定理257
11.9正规子群和商群259
11.9.1正规子群259
11.9.2商群260
11.10环和域262
11.10.1环、子环与理想263
11.10.2交换环和整环264
11.10.3除环和域264
11.11典型例题265
习题268
第12章格与布尔代数271
12.1格定义的代数系统271
12.2格的代数定义273
12.2.1格的代数定义273
12.2.2子格275
12.2.3格的同态和同构275
12.3一些特殊的格276
12.3.1分配格276
12.3.2布尔格和布尔代数278
12.4有限布尔代数的唯一性279
12.4.1原子279
12.4.2有限布尔代数非零元素的表达279
12.4.3布尔代数的同构280
12.5布尔表达式和布尔函数282
12.5.1布尔表达式282
12.5.2布尔函数283
12.6典型例题285
习题286
参考文献288