离散数学(微课版)

第1章命题演算基础1
1.1命题和联结词1
1.1.1命题1
1.1.2联结词2
1.1.3合式公式5
1.1.4命题逻辑的应用6
1.2真假性9
1.2.1解释9
1.2.2等价公式10
1.2.3联结词的完备集11
1.2.4对偶式和内否式12
1.3范式及其应用14
1.3.1范式14
1.3.2主范式16
1.3.3范式的应用19
1.4典型例题20
习题21
第2章命题演算的推理理论25
2.1命题演算的公理系统25
2.1.1公理系统的组成部分26
2.1.2公理系统的推理过程27
2.2若干重要的导出规则29
2.2.1分离规则的讨论29
2.2.2公理和定理的导出规则29
2.3命题演算的假设推理系统31
2.3.1假设推理系统的组成31
2.3.2假设推理系统的推理过程32
2.3.3额外假设推理法34
2.4命题演算的归结推理法36
2.4.1归结证明过程36
2.4.2归结证明示例37
2.5典型例题38
习题41
〖3〗离散数学（微课版）目录〖3〗第3章谓词演算基础43
3.1个体和谓词43
3.1.1个体43
3.1.2谓词43
3.2函数项和量词46
3.2.1函数项46
3.2.2量词46
3.3自由变元和约束变元48
3.3.1自由出现和约束出现48
3.3.2改名和代入49
3.4永真性和可满足性50
3.4.1真假性50
3.4.2同真假性、永真性和可满足性52
3.4.3范式55
3.5唯一性量词和摹状词56
3.5.1唯一性量词56
3.5.2摹状词57
3.6典型例题58
习题59
第4章谓词演算的推理理论62
4.1谓词演算的永真推理系统62
4.1.1公理系统的组成部分62
4.1.2公理系统的推理过程64
4.2谓词演算的假设推理系统65
4.2.1假设推理系统的组成及证明方法65
4.2.2定理的假设推导过程66
4.3谓词演算的归结推理系统67
4.3.1置换68
4.3.2归结反演系统69
4.4霍恩子句逻辑程序72
4.5Prolog简介74
4.6典型例题76
习题78
第5章递归函数论81
5.1数论函数和数论谓词81
5.1.1数论函数81
5.1.2数论谓词和特征函数82
5.2函数的构造84
5.2.1迭置法84
5.2.2算子法85
5.2.3原始递归函数86
5.3典型例题87
习题88
第6章集合89
6.1集合的基本概念89
6.1.1集合的定义89
6.1.2集合的表示90
6.1.3集合的包含关系91
6.1.4集合的特点91
6.1.5多重集92
6.2集合的基本运算92
6.2.1集合的并、交、差92
6.2.2集合的对称差94
6.2.3文氏图94
6.2.4集合的幂集合95
6.2.5多个集合的并与交96
6.3全集和补集97
6.3.1全集和补集的定义97
6.3.2基本运算定理97
6.3.3集合的计算机表示98
6.4自然数与自然数集99
6.4.1后继99
6.4.2自然数和自然数集的定义99
6.4.3皮亚诺公理假设100
6.4.4自然数集的性质101
6.4.5集合的递归定义与递归子程序102
6.5包含与排斥原理104
6.6典型例题106
习题107
第7章关系111
7.1集合的笛卡儿积集111
7.1.1有序二元组111
7.1.2笛卡儿积集111
7.1.3有序n元组、n个集合的笛卡儿积集112
7.2二元关系的基本概念113
7.2.1二元关系113
7.2.2二元关系的表示113
7.2.3二元关系与数据结构114
7.2.4二元关系的运算115
7.3n元关系及其运算117
7.3.1n元关系117
7.3.2n元关系的运算118
7.4二元关系的性质120
7.4.1自反性、反自反性、对称性、反对称性、传递性和反传递性120
7.4.2二元关系性质的判定定理122
7.5二元关系的闭包运算124
7.5.1自反闭包、对称闭包和传递闭包124
7.5.2闭包的判定定理124
7.6等价关系和集合的划分128
7.6.1等价关系和等价类128
7.6.2商集合129
7.6.3集合的划分130
7.7偏序关系和格132
7.7.1偏序关系和偏序集132
7.7.2哈斯图133
7.7.3链、反链、全序集133
7.7.4极大元、极小元、*大元和*小元134
7.7.5上界、下界、*小上界和*大下界135
7.7.6格135
7.7.7拓扑排序136
7.8粗糙集概论138
7.8.1知识与知识分类138
7.8.2集合近似与粗糙集概念140
7.9典型例题141
习题142
第8章函数与集合的势148
8.1函数的基本概念148
8.1.1函数(映射)的定义148
8.1.2函数的性质150
8.2函数的复合和逆函数151
8.2.1函数的复合151
8.2.2左可逆函数、右可逆函数和逆函数152
8.3无限集155
8.3.1势155
8.3.2有限集和无限集156
8.3.3可数无限集和不可数无限集157
8.4集合势大小的比较159
8.4.1集合势的大小159
8.4.2伯恩斯坦定理159
8.5鸽巢原理160
8.6典型例题161
习题162
第9章图论165
9.1图的基本概念165
9.1.1有向图和无向图166
9.1.2图的同构、子图和补图167
9.1.3顶点的度168
9.2图中的通路、图的连通性和图的矩阵表示169
9.2.1通路、回路和连通性169
9.2.2图的矩阵表示171
9.3带权图与带权图中的*短通路174
9.4欧拉图176
9.5哈密顿图180
9.6二部图183
9.7平面图与平面图的着色186
9.7.1平面图186
9.7.2平面图的着色189
9.8典型例题191
习题192
第10章树和有序树197
10.1树的基本概念197
10.2连通图的生成树和带权连通图的*小生成树199
10.3有序树202
10.3.1根树202
10.3.2根树的应用203
10.4前缀码和*优2分树206
10.4.1前缀码206
10.4.2*优2分树207
10.4.3赫夫曼编码210
10.5典型例题211
习题213
第11章群和环216
11.1代数运算的基本概念216
11.1.1代数运算216
11.1.2交换律、结合律217
11.1.3n元运算218
11.2代数系统和半群219
11.2.1代数系统219
11.2.2同态映射和同构映射219
11.2.3半群与含幺半群221
11.3群的基本概念223
11.3.1逆元223
11.3.2群的定义223
11.3.3群的同态、同构226
11.3.4无限群、有限群、交换群和元的阶228
11.4群的几个等价定义230
11.5变换群和置换群231
11.5.1变换群231
11.5.2置换群232
11.6循环群235
11.7子群237
11.7.1子群的定义237
11.7.2子群的判定定理237
11.8子群的陪集239
11.8.1按子群划分的剩余类239
11.8.2右陪集239
11.8.3左陪集241
11.8.4拉格朗日定理242
11.9正规子群和商群244
11.9.1正规子群244
11.9.2商群245
11.10环和域247
11.10.1环、子环与理想248
11.10.2交换环和整环248
11.10.3除环和域249
11.11典型例题249
习题253
第12章格与布尔代数256
12.1格定义的代数系统256
12.2格258
12.2.1格的代数定义258
12.2.2子格260
12.2.3格的同态和同构260
12.3一些特殊的格261
12.3.1分配格261
12.3.2布尔格和布尔代数263
12.4有限布尔代数的唯一性263
12.4.1原子263
12.4.2有限布尔代数非零元素的表达264
12.4.3布尔代数的同构265
12.5布尔表达式和布尔函数266
12.5.1布尔表达式266
12.5.2布尔函数267
12.6典型例题269
习题270
参考文献272