离散数学

.2.1.2命题公式及其分类42
2.2命题逻辑等值演算48
2.2.1等值式与等值演算48
2.2.2联结词完备集53
2.3范式55
2.3.1析取范式与合取范式55
2.3.2主析取范式与主合取范式58
2.4命题逻辑推理理论66
2.4.1推理的形式结构66
2.4.2自然推理系统p69
2.4.3归结证明法75
习题78
第3章一阶逻辑84
3.1一阶逻辑基本概念84
3.1.1命题逻辑的局限性84
3.1.2个体词、谓词与量词84
3.1.3一阶逻辑命题符号化86
3.1.4一阶逻辑公式与分类90
3.2一阶逻辑等值演算95
3.2.1一阶逻辑等值式与置换规则95
3.2.2一阶逻辑前束范式99
3.3一阶逻辑推理理论102
3.3.1一阶逻辑中推理的形式结构102
3.3.2量词消去与引入规则102
3.3.3自然推理系统f104
习题107
第4章关系113
4.1关系的定义及其表示113
4.1.1有序对与笛卡儿积113
4.1.2二元关系的定义114
4.1.3二元关系的表示116
4.2关系的运算117
4.2.1关系的基本运算117
4.2.2关系的幂运算121
4.3关系的性质124
4.3.1关系性质的定义和判别124
4.3.2关系的闭包128
4.4等价关系与偏序关系133
4.4.1等价关系133
4.4.2等价类和商集134
4.4.3集合的划分135
4.4.4偏序关系137
4.4.5偏序集与哈斯图138
习题143
第5章函数148
5.1函数的定义及其性质148
5.1.1函数的定义148
5.1.2函数的像与完全原像151
5.1.3函数的性质151
5.2函数的复合与反函数155
5.2.1函数的复合155
5.2.2反函数157
习题158
第6章图162
6.1图的基本概念162
6.1.1无向图与有向图162
6.1.2顶点的度数与握手定理164
6.1.3简单图、完全图、正则图、圈图、轮图、方体图167
6.1.4子图、补图169
6.1.5图的同构170
6.2图的连通性172
6.2.1通路与回路172
6.2.2无向图的连通性与连通度173
6.2.3有向图的连通性及其分类176
6.3图的矩阵表示176
6.3.1无向图的关联矩阵177
6.3.2有向无环图的关联矩阵177
6.3.3有向图的邻接矩阵178
6.3.4有向图的可达矩阵180
6.4几种特殊的图181
6.4.1二部图181
6.4.2欧拉图184
6.4.3哈密顿图186
6.4.4平面图191
习题200
第7章树及其应用205
7.1无向树205
7.1.1无向树的定义及其性质205
7.1.2生成树与基本回路和基本割集208
7.1.3最小生成树211
7.2根树及其应用212
7.2.1根树及其分类212
7.2.2最优树与哈夫曼算法213
7.2.3最佳前缀码214
7.2.4根树的周游及其应用216
习题218
第8章组合计数基础222
8.1基本计数规则223
8.1.1加法法则223
8.1.2乘法法则224
8.1.3分类处理与分步处理224
8.2排列与组合225
8.2.1集合的排列与组合225
8.2.2多重集的排列与组合229
8.3二项式定理与组合恒等式232
8.3.1二项式定理232
8.3.2组合恒等式233
8.3.3非降路径问题237
8.4多项式定理与多项式系数240
8.4.1多项式定理240
8.4.2多项式系数241
习题242
第9章容斥原理245
9.1容斥原理及其应用245
9.1.1容斥原理的基本形式245
9.1.2容斥原理的应用246
9.2对称筛公式及其应用250
9.2.1对称筛公式250
9.2.2棋盘多项式与有限制条件的排列252
习题256
第10章递推方程与生成函数257
10.1递推方程及其应用257
10.1.1递推方程的定义及实例257
10.1.2常系数线性齐次递推方程的求解260
10.1.3常系数线性非齐次递推方程的求解263
10.1.4递推方程的其他解法265
10.1.5递推方程与递归算法270
10.2生成函数及其应用272
10.2.1牛顿二项式定理与牛顿二项式系数272
10.2.2生成函数的定义及其性质273
10.2.3生成函数的应用276
10.3指数生成函数及其应用281
10.4catalan数与stirling数284
习题289
第11章初等数论292
11.1素数292
11.2最大公约数与最小公倍数296
11.3同余298
11.4一次同余方程与中国剩余定理301
11.4.1一次同余方程301
11.4.2中国剩余定理303
11.4.3大整数算术运算304
11.5欧拉定理和费马小定理306
习题307
第12章离散概率312
12.1随机事件与概率、事件的运算312
12.1.1随机事件与概率312
12.1.2事件的运算314
12.2条件概率与独立性315
12.2.1条件概率315
12.2.2独立性317
12.2.3伯努利概型与二项概率公式318
12.3离散型随机变量319
12.3.1离散型随机变量及其分布律319
12.3.2常用分布321
12.3.3数学期望322
12.3.4方差324
12.4概率母函数326
习题329
第13章初等数论和离散概率的应用333
13.1密码学333
13.1.1恺撒密码333
13.1.2rsa公钥密码334
13.2产生伪随机数的方法337
13.2.1产生均匀伪随机数的方法337
13.2.2产生离散型伪随机数的方法338
13.3算法的平均复杂度分析340
13.3.1排序算法340
13.3.2散列表的检索和插入344
13.4随机算法348
13.4.1随机快速排序算法348
13.4.2多项式恒零测试349
13.4.3素数测试351
13.4.4蒙特卡罗法和拉斯维加斯法352
习题353
第14章代数系统356
14.1二元运算及其性质356
14.1.1二元运算与一元运算的定义356
14.1.2二元运算的性质358
14.2代数系统362
14.2.1代数系统的定义与实例362
14.2.2代数系统的分类363
14.2.3子代数系统与积代数系统364
14.2.4代数系统的同态与同构365
14.3几个典型的代数系统367
14.3.1半群与独异点367
14.3.2群368
14.3.3环与域376
14.3.4格与布尔代数379
习题385