《离散数学（第3版）》是由屈婉玲、耿素云、张立昂编著，2014年清华大学出版社出版的普通高等教育“十一五”国家级规划教材、普通高等教育精品教材、21世纪大学本科计算机专业系列教材。该教材适合作为高等学校计算机及相关专业本科生“离散数学”课程的教材，也可以作为对离散数学感兴趣的人员的入门参考书。
全书共14章，内容包含证明技巧、数理逻辑、集合与关系、函数、组合计数、图和树、初等数论等。
目录
- 第1章数学语言与证明方法1
- 1.1常用的数学符号1
- 1.1.1集合符号1
- 1.1.2运算符号2
- 1.1.3逻辑符号2
- 1.2集合及其运算3
- 1.2.1集合及其表示法3
- 1.2.2集合之间的包含与相等4
- 1.2.3集合的幂集5
- 1.2.4集合的运算6
- 1.2.5基本集合恒等式及其应用8
- 1.3证明方法概述11
- 1.3.1直接证明法和归谬法12
- 1.3.2分情况证明法和构造性证明法12
- 1.3.3数学归纳法14
- 1.4递归定义16
- 习题17
- 第2章命题逻辑22
- 2.1命题逻辑基本概念22
- 2.1.1命题与联结词22
- 2.1.2命题公式及其分类28
- 2.2命题逻辑等值演算33
- 2.2.1等值式与等值演算33
- 2.2.2联结词完备集37
- 2.3范式39
- 2.3.1析取范式与合取范式39
- 2.3.2主析取范式与主合取范式42
- 2.4推理49
- 2.4.1推理的形式结构49
- 2.4.2推理的证明51
- 2.4.3归结证明法57
- 2.4.4对证明方法的补充说明60
- 习题60
- 第3章一阶逻辑66
- 3.1一阶逻辑基本概念66
- 3.1.1命题逻辑的局限性66
- 3.1.2个体词、谓词与量词66
- 3.1.3一阶逻辑命题符号化68
- 3.1.4一阶逻辑公式与分类71
- 3.2一阶逻辑等值演算75
- 3.2.1一阶逻辑等值式与置换规则75
- 3.2.2一阶逻辑前束范式79
- 习题81
- 第4章关系86
- 4.1关系的定义及其表示86
- 4.1.1有序对与笛卡儿积86
- 4.1.2二元关系的定义87
- 4.1.3二元关系的表示89
- 4.2关系的运算90
- 4.2.1关系的基本运算90
- 4.2.2关系的幂运算93
- 4.3关系的性质96
- 4.3.1关系性质的定义和判别96
- 4.3.2关系的闭包100
- 4.4等价关系与偏序关系104
- 4.4.1等价关系104
- 4.4.2等价类和商集104
- 4.4.3集合的划分105
- 4.4.4偏序关系107
- 4.4.5偏序集与哈斯图108
- 习题112
- 第5章函数116
- 5.1函数的定义及其性质116
- 5.1.1函数的定义116
- 5.1.2函数的像与完全原像118
- 5.1.3函数的性质119
- 5.2函数的复合与反函数122
- 5.2.1函数的复合122
- 5.2.2反函数124
- 习题128
- 第6章图132
- 6.1图的基本概念132
- 6.1.1无向图与有向图132
- 6.1.2顶点的度数与握手定理134
- 6.1.3简单图、完全图、正则图、圈图、轮图、方体图136
- 6.1.4子图、补图138
- 6.1.5图的同构139
- 6.2图的连通性141
- 6.2.1通路与回路141
- 6.2.2无向图的连通性与连通度141
- 6.2.3有向图的连通性及其分类144
- 6.3图的矩阵表示144
- 6.3.1无向图的关联矩阵144
- 6.3.2有向无环图的关联矩阵145
- 6.3.3有向图的邻接矩阵146
- 6.3.4有向图的可达矩阵147
- 6.4几种特殊的图149
- 6.4.1二部图149
- 6.4.2欧拉图152
- 6.4.3哈密顿图154
- 6.4.4平面图157
- 习题166
- 第7章树及其应用173
- 7.1无向树173
- 7.1.1无向树的定义及其性质173
- 7.1.2生成树176
- 7.2根树及其应用177
- 7.2.1根树及其分类177
- 7.2.2最优树与哈夫曼算法178
- 7.2.3最佳前缀码179
- 7.2.4根树的周游及其应用181
- 习题182
- 第8章组合计数基础185
- 8.1基本计数规则186
- 8.1.1加法法则186
- 8.1.2乘法法则186
- 8.1.3分类处理与分步处理187
- 8.2排列与组合187
- 8.2.1集合的排列与组合188
- 8.2.2多重集的排列与组合191
- 8.3二项式定理与组合恒等式193
- 8.3.1二项式定理193
- 8.3.2组合恒等式194
- 8.3.3非降路径问题198
- 8.4多项式定理与多项式系数201
- 8.4.1多项式定理201
- 8.4.2多项式系数202
- 习题203
- 第9章容斥原理206
- 9.1容斥原理及其应用206
- 9.1.1容斥原理的基本形式206
- 9.1.2容斥原理的应用207
- 9.2对称筛公式及其应用210
- 9.2.1对称筛公式210
- 9.2.2棋盘多项式与有限制条件的排列212
- 习题215
- 第10章递推方程与生成函数217
- 10.1递推方程及其应用217
- 10.1.1递推方程的定义及实例217
- 10.1.2常系数线性齐次递推方程的求解219
- 10.1.3常系数线性非齐次递推方程的求解222
- 10.1.4递推方程的其他解法224
- 10.1.5递推方程与递归算法228
- 10.2生成函数及其应用233
- 10.2.1牛顿二项式定理与牛顿二项式系数233
- 10.2.2生成函数的定义及其性质234
- 10.2.3生成函数的应用236
- 10.3指数生成函数及其应用241
- 10.4Catalan数与Stirling数243
- 习题248
- 第11章初等数论251
- 11.1素数251
- 11.2最大公约数与最小公倍数254
- 11.3同余257
- 11.4一次同余方程与中国剩余定理259
- 11.4.1一次同余方程259
- 11.4.2中国剩余定理260
- 11.4.3大整数算术运算262
- 11.5欧拉定理和费马小定理263
- 习题264
- 第12章离散概率268
- 12.1随机事件与概率、事件的运算268
- 12.1.1随机事件与概率268
- 12.1.2事件的运算270
- 12.2条件概率与独立性271
- 12.2.1条件概率271
- 12.2.2独立性273
- 12.2.3伯努利概型与二项概率公式273
- 12.3离散型随机变量274
- 12.3.1离散型随机变量及其分布律274
- 12.3.2常用分布275
- 12.3.3数学期望276
- 12.3.4方差278
- 12.4概率母函数280
- 习题282
- 第13章初等数论和离散概率的应用286
- 13.1密码学286
- 13.1.1恺撒密码286
- 13.1.2RSA公钥密码287
- 13.2产生伪随机数的方法289
- 13.2.1产生均匀伪随机数的方法289
- 13.2.2产生离散型伪随机数的方法290
- 13.3算法的平均复杂度分析292
- 13.3.1排序算法292
- 13.3.2散列表的检索和插入295
- 13.4随机算法298
- 13.4.1随机快速排序算法298
- 13.4.2多项式恒零测试299
- 13.4.3素数测试301
- 13.4.4蒙特卡罗法和拉斯维加斯法302
- 习题303
- 第14章代数系统306
- 14.1二元运算及其性质306
- 14.1.1二元运算与一元运算的定义306
- 14.1.2二元运算的性质308
- 14.2代数系统311
- 14.2.1代数系统的定义与实例311
- 14.2.2代数系统的分类312
- 14.2.3子代数系统与积代数系统313
- 14.2.4代数系统的同态与同构314
- 14.3几个典型的代数系统315
- 14.3.1半群与独异点315
- 14.3.2群317
- 14.3.3环与域323
- 14.3.4格与布尔代数325
- 习题330
- 参考文献335
