离散数学（第3版）

第1章命题逻辑1
1.1现代逻辑学的基本研究
方法1
1.2命题及其表示法3
1.2.1命题的概念3
1.2.2联结词4
1.3命题公式与语句形式化8
1.3.1命题公式的定义8
1.3.2公式的层次8
1.3.3语句形式化9
1.3.4复合命题真假值9
1.3.5真值表11
1.4重言式12
1.4.1重言式概述12
1.4.2逻辑等价式13
1.4.3等值演算16
1.5对偶与范式16
1.5.1对偶16
1.5.2简单合取式和简单
析取式17
1.5.3范式18
1.5.4范式的*性——
主范式20
1.6其他联结词24
1.6.1n元真值函数24
1.6.2真值函数与命题
公式的关系25
1.6.3联结词完备集25
1.6.4单元素联结词构成
的联结词完备集26
1.7命题演算的推理理论27
1.7.1有效推理27
1.7.2有效推理的等价
定理29
1.7.3重言蕴涵式30
1.7.4形式推理系统31
1.7.5自然推理系统P234
1.8命题演算中的归结推理38
1.8.1归结推理规则38
1.8.2归结反演40
1.8.3命题逻辑归结反演的
合理性和完备性41
1.9应用案例41
1.9.1克雷格探长案卷录41
1.9.2忘却林中的艾丽丝
（狮子与独角兽）43
习题44
计算机编程题52
第2章谓词逻辑53
2.1谓词逻辑的基本概念53
2.1.1个体词54
2.1.2谓词54
2.1.3量词55
2.2谓词逻辑公式与翻译56
2.2.1一阶语言56
2.2.2自由与约束57
2.2.3闭公式58
2.2.4谓词逻辑公式的
解释59
2.2.5谓词逻辑命题符
号化60
2.2.6一阶公式的分类63
2.3谓词逻辑等值演算64
2.3.1基本等价式与置换
规则64
2.3.2谓词逻辑前束
范式67
2.4谓词演算的推理理论68
2.4.1推理定律69
2.4.2量词消去与引入
规则69
2.4.3一阶谓词演算公理
系统F170
2.4.4自然推理系统F271
2.5谓词演算中的归结推理73
2.5.1子句型73
2.5.2置换和合一75
2.5.3合一算法77
2.5.4归结式77
2.5.5归结反演及其完
备性78
2.6应用案例79
2.6.1电路领域的知识
工程79
2.6.2基于逻辑的财务
顾问80
2.7逻辑在计算机科学中的
作用80
2.7.1逻辑与计算80
2.7.2逻辑与计算机的
起源81
2.7.3逻辑与程序设计81
习题81
计算机编程题86
离散数学（第3版）目录第3章集合与关系88
3.1集合的概念和表示法88
3.1.1集合的表示88
3.1.2基本概念89
3.2集合的运算91
3.2.1集合的基本运算91
3.2.2有穷计数集92
3.2.3包含排斥原理93
3.2.4广义交和广义并94
3.3有序对与笛卡儿积96
3.4关系及其表示98
3.4.1基本概念98
3.4.2关系表示法99
3.5关系的运算101
3.5.1基本概念101
3.5.2复合关系102
3.5.3逆关系103
3.5.4关系幂105
3.5.5幂运算的性质106
3.6关系的性质108
3.6.1关系的5种基本
性质108
3.6.2关系性质的等价
描述109
3.7关系的闭包112
3.7.1基本概念112
3.7.2闭包的性质116
3.8集合的划分与覆盖118
3.9等价关系和等价类119
3.9.1等价关系119
3.9.2等价类的性质120
3.9.3商集与划分121
3.10相容关系和相容类122
3.11偏序关系124
3.12偏序集与哈斯图125
3.13应用案例128
3.13.1同余关系在出版
业中的应用128
3.13.2拓扑排序在建筑
工序中的应用128
3.13.3等价关系在软件
测试等价类划分
中的应用129
习题129
计算机编程题135
第4章函数136
4.1函数的定义136
4.1.1函数和像136
4.1.2函数的性质138
4.1.3常用函数139
4.2复合函数和反函数140
4.2.1复合函数140
4.2.2反函数142
4.3特征函数与模糊子集144
4.4基数的概念146
4.4.1后继与归纳集146
4.4.2自然数，有穷集，
无穷集147
4.4.3基数152
4.5可数集与不可数集153
4.6数学归纳法154
4.7应用案例157
4.7.1逢黑必反魔术157
4.7.2生成函数在解决汉诺塔
问题中的应用158
习题158
计算机编程题162
第5章组合计数163
5.1基本原理163
5.1.1加法原理163
5.1.2乘法原理164
5.2排列与组合165
5.2.1排列165
5.2.2组合165
5.3排列组合生成算法166
5.3.1排列生成算法166
5.3.2组合生成算法168
5.4广义的排列和组合170
5.5二项式系数和组合恒
等式171
5.5.1二项式定理171
5.5.2组合恒等式173
5.6鸽笼原理174
5.6.1鸽笼原理的简单
形式174
5.6.2鸽笼原理的一般
形式174
5.7递推关系及应用176
5.7.1递推定义函数176
5.7.2递推定义集合177
5.7.3递推关系模型178
5.7.4求解递推关系180
5.7.5递推在算法分析中的
应用181
5.7.6生成函数183
5.8应用案例186
5.8.1大使馆通信的码
字数186
5.8.2条条道路通罗马186
习题187
计算机编程题188
第6章图论189
6.1图的基本概念189
6.1.1图的定义和表示189
6.1.2图的同构194
6.1.3完全图与正则图195
6.1.4子图与补图195
6.1.5通路与回路198
6.2图的连通性199
6.2.1无向图的连通性199
6.2.2有向图的连通性201
6.3图的矩阵表示202
6.3.1关联矩阵202
6.3.2有向图的邻接
矩阵203
6.3.3有向图的可达
矩阵204
6.4欧拉图204
6.5哈密顿图207
6.6二部图210
6.6.1二部图及判别
定理210
6.6.2完备匹配211
6.7平面图213
6.7.1平面图及其判定
定理213
6.7.2平面图的对偶图219
6.8带权图220
6.9应用案例221
6.9.1网络爬虫221
6.9.2读心术魔术222
6.9.3高度互联世界的
行为原理222
习题222
计算机编程题229
第7章树及其应用230
7.1概述230
7.1.1树的定义及相关
术语230
7.1.2树的性质232
7.2生成树233
7.3*小生成树237
7.4树的遍历239
7.5二叉树241
7.5.1二叉树的性质241
7.5.2二叉搜索树242
7.5.3哈夫曼树242
7.6决策树244
7.6.1决策树的定义245
7.6.2*短时间排序246
7.7树的同构247
7.8博弈树251
7.8.1博弈树的概念251
7.8.2极大极小分析法252
7.9应用案例254
7.9.1哈夫曼压缩算法的
基本原理254
7.9.2决策树在风险决策
中的应用254
7.9.3一字棋博弈的极大
极小过程255
习题255
计算机编程题257
第8章代数系统259
8.1二元运算及其性质259
8.1.1定义和表示259
8.1.2二元运算的性质261
8.2代数系统263
8.2.1定义和实例263
8.2.2子代数系统265
8.2.3代数系统的同态
与同构266
8.3半群与独异点266
8.3.1定义与性质266
8.3.2子系统与直积268
8.4群269
8.4.1群的定义269
8.4.2群的性质271
8.4.3子群的定义273
8.4.4特殊的群274
8.4.5陪集与拉格朗日
定理277
8.4.6正规子群与商群278
8.4.7群的同态与同构
实例280
8.5环与域282
8.5.1环282
8.5.2域284
8.6格与布尔代数284
8.6.1格284
8.6.2布尔代数288
8.7应用案例291
8.7.1组合电路291
8.7.2物理世界中群的
应用292
8.7.3群码及纠错能力292
习题292
计算机编程题299
第9章自动机、文法和语言300
9.1串和语言300
9.2形式文法301
9.3有限状态机304
9.4有限状态自动机306
9.5不确定有限状态自动机310
9.6语言和自动机之间的
关系313
9.7应用案例314
9.7.1奇偶校验机314
9.7.2识别地址的有限
状态机314
9.7.3语音识别315
习题315
计算机编程题318
第10章数论与密码学319
10.1素数319
10.2*公约数与*小公
倍数320
10.3同余323
10.4一次同余方程和中国
剩余定理325
10.4.1一次同余方程325
10.4.2中国剩余定理326
10.5欧拉定理和费马小
定理327
10.6数论在密码学中的
应用328
10.6.1公钥密码学328
10.6.2RSA密码328
10.7应用案例330
10.7.1密码系统与公开
密钥330
10.7.2单向陷门函数在
公开密钥密码系
统中的应用330
习题331
计算机编程题331
附录历史注记332
参考文献334