离散数学

第1章命题逻辑1
1.1现代逻辑学的基本研究方法1
1.1.1思维： 感知的概念化和理性化1
1.1.2现代逻辑学求助数学——符号化2
1.1.3现代逻辑学追随数学——公理化2
1.1.4现代逻辑学改造数学——形式化3
1.2命题及其表示法4
1.2.1命题的概念4
1.2.2复合命题4
1.2.3联结词5
1.2.4复合命题真假值7
1.3命题公式与翻译9
1.3.1命题公式的定义9
1.3.2公式的层次10
1.3.3翻译10
1.4真值表与等价公式11
1.4.1真值表11
1.4.2等价公式12
1.5重言式与等值演算12
1.5.1重言式12
1.5.2等值演算14
1.6对偶与范式16
1.6.1对偶16
1.6.2简单合取式和简单析取式17
1.6.3范式18
1.6.4范式的唯一性——主范式20
1.7其他联结词25
1.7.1n元真值函数26
1.7.2真值函数与命题公式的关系26
1.7.3联结词完备集27
1.7.4单元素联结词构成的联结词完备集28
1.8推理理论29
1.8.1有效推理29
1.8.2有效推理的等价定理30
1.8.3重言蕴涵式32
1.8.4形式推理系统P134
1.8.5自然推理系统P235
习题41
第2章谓词逻辑51
2.1谓词逻辑的基本概念51
2.1.1个体词52
2.1.2谓词52
2.1.3量词53
2.2谓词逻辑公式与翻译54
2.2.1一阶语言54
2.2.2自由与约束55
2.2.3闭公式56
2.2.4谓词逻辑公式的解释57
2.2.5谓词逻辑命题符号化58
2.2.6谓词逻辑公式的分类61
2.3谓词逻辑等值演算62
2.3.1基本等价式与置换规则62
2.3.2谓词逻辑前束范式66
2.4谓词演算的推理理论68
2.4.1推理定律68
2.4.2量词消去与引入规则69
2.4.3一阶谓词演算公理系统F169
2.4.4自然推理系统F271
2.5逻辑在计算机科学中的作用73
2.5.1逻辑与计算73
2.5.2逻辑与计算机的起源74
2.5.3逻辑与程序设计75
习题76离散数学目录
第3章集合与关系82
3.1集合的概念和表示法82
3.1.1集合的表示82
3.1.2集合的基本概念84
3.2集合的运算85
3.2.1集合的基本运算85
3.2.2有穷计数集86
3.2.3广义交和广义并87
3.3有序对与笛卡儿积89
3.4关系及其表示91
3.4.1关系的基本概念91
3.4.2关系表示法92
3.5关系的运算94
3.5.1基本概念94
3.5.2复合关系95
3.5.3逆关系96
3.5.4关系幂98
3.5.5幂运算的性质99
3.6关系的性质101
3.6.1关系的五种基本性质101
3.6.2关系性质的等价描述102
3.7关系的闭包106
3.7.1闭包的基本概念106
3.7.2闭包的性质110
3.8集合的划分与覆盖111
3.9等价关系和等价类112
3.9.1等价关系112
3.9.2等价类的性质114
3.9.3商集与划分115
3.10偏序关系116
3.11偏序集与哈斯图117
3.12包含排斥原理120
习题121
第4章函数128
4.1函数的定义128
4.1.1函数和像128
4.1.2函数的性质130
4.1.3常用函数131
4.2复合函数和反函数132
4.2.1复合函数132
4.2.2反函数134
4.3特征函数与模糊子集136
4.3.1特征函数136
4.3.2模糊集合137
4.4基数的概念138
4.4.1后继与归纳集138
4.4.2自然数，有穷集，无穷集139
4.4.3基数144
4.5可数集与不可数集144
4.6数学归纳法146
4.6.1归纳法证明146
4.6.2数学归纳法第一原理146
4.6.3数学归纳法第二原理147
习题149
第5章图论153
5.1图的基本概念153
5.1.1图的定义和表示153
5.1.2图的同构157
5.1.3完全图与正则图159
5.1.4子图与补图159
5.1.5通路与回路161
5.2图的连通性163
5.2.1无向图的连通性163
5.2.2有向图的连通性165
5.3图的矩阵表示165
5.3.1关联矩阵165
5.3.2有向图的邻接矩阵166
5.3.3有向图的可达矩阵168
5.4二部图168
5.4.1二部图及判别定理168
5.4.2完备匹配169
5.5欧拉图171
5.6哈密顿图174
5.7平面图177
5.7.1平面图及其判定定理177
5.7.2平面图的对偶图183
5.8带权图184
习题185
第6章树及其应用193
6.1树的术语和性质193
6.1.1树的定义及相关术语193
6.1.2树的性质195
6.2生成树196
6.3最小生成树199
6.4树的遍历202
6.5二叉树204
6.5.1二叉树的性质204
6.5.2二叉搜索树205
6.5.3赫夫曼树206
6.6决策树207
6.6.1决策树的定义207
6.6.2最短时间排序209
6.7树的同构209
6.8博弈树213
6.8.1博弈树的概念213
6.8.2极大极小分析法213
6.8.3αβ剪枝技术216
习题218
第7章计数方法与鸽巢原理222
7.1基本原理222
7.1.1加法原理222
7.1.2乘法原理223
7.2排列与组合224
7.2.1排列224
7.2.2组合224
7.3排列组合生成算法225
7.3.1排列生成算法225
7.3.2组合生成算法226
7.4离散概率论229
7.4.1离散概率简介229
7.4.2有限概率230
7.4.3条件概率与独立性232
7.4.4Bayes定理233
7.5广义的排列和组合234
7.6二项式系数和组合恒等式236
7.6.1二项式定理236
7.6.2组合恒等式238
7.7鸽巢原理239
7.7.1鸽巢原理的简单形式239
7.7.2鸽巢原理的一般形式240
习题241
第8章数论与递归关系243
8.1素数243
8.2最大公约数与最小公倍数244
8.3同余247
8.4一次同余方程和中国剩余定理249
8.4.1一次同余方程249
8.4.2中国剩余定理250
8.5数论在密码学中的应用251
8.5.1公钥密码学251
8.5.2RSA密码252
8.6递归关系简介252
8.6.1递归定义函数252
8.6.2递归定义集合254
8.6.3递推关系模型255
8.7求解递归关系257
8.8递归在算法分析中的应用259
习题262
第9章代数系统264
9.1二元运算及其性质264
9.1.1定义和表示264
9.1.2二元运算的性质266
9.2代数系统268
9.2.1定义和实例268
9.2.2子代数系统270
9.2.3代数系统的同态与同构270
9.3半群与独异点271
9.3.1定义与性质271
9.3.2子系统与直积272
9.4群273
9.4.1群的定义273
9.4.2群的性质275
9.4.3子群的定义277
9.4.4正规子群与商群278
9.4.5群的同态与同构实例281
9.4.6循环群与置换群284
9.5环与域286
9.5.1环286
9.5.2域287
9.6格与布尔代数288
9.6.1格288
9.6.2布尔代数292
9.7组合电路295
习题297
第10章自动机、文法和语言305
10.1串和语言305
10.2形式文法306
10.3有限状态机309
10.4有限状态自动机311
10.5不确定有限状态自动机314
10.6语言和自动机之间的关系317
习题318
附录A历史注记322
参考文献332