离散数学/第2版

《离散数学(第2版)》借鉴国内外计算机科学与技术学科和计算机基础课程体系的研究成果，努力反映计算机科学技术的最新成果和发展趋势。
强调理论与实践紧密结合，注重能力和综合素质的培养，通过实例讲解原理和方法，引导学生掌握理论方法的实际运用。
主教材配有电予课件，习题解答，实验指导等丰富的教学资源，方便师生的教与学。
离散数学是计算机科学与技术专业的一门重要基础课。《离散数学(第2版)》主要包含数理逻辑、集合与关系、函数，组合计数，图和树，代数系统，自动机和初等数论等内容。附录“历史注记”给出了各章内容的发源和历史轨迹。《离散数学(第2版)》结合作者多年的教学经验，总结了学习离散数学的方法。
《离散数学(第2版)》体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，且给出奇数题的答案，适合教学。《离散数学(第2版)》适合作为计算机和相关专业本科生“离散数学”课程的教学用书，也可作为对离散数学感兴趣的人员的参考书。

《离散数学(第2版)》体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，书中选配了大量难度适当的习题，并给出奇数题的答案，适合教学。《离散数学(第2版)》适合作为计算机和相关专业本科生“离散数学”的教学用书，亦可作为对离散数学感兴趣的人员的参考书。
离散数学是数学中专门用来研究离散对象及其关系的一个分支，是计算机科学与技术专业的一门重要基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。全书共10章，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。《离散数学(第2版)》中的“历史注记”可以帮助读者理解数学，洞察内在本质。

第1章命题逻辑1
1.1现代逻辑学的基本研究方法1
1.2命题及其表示法3
1.2.1命题的概念3
1.2.2联结词4
1.3命题公式与语句形式化7
1.3.1命题公式的定义7
1.3.2公式的层次8
1.3.3语句形式化8
1.3.4复合命题真假值9
1.3.5真值表10
1.4重言式11
1.4.1重言式概述11
1.4.2逻辑等价式13
1.4.3等值演算15
1.5对偶与范式16
1.5.1对偶16
1.5.2简单合取式和简单析取式16
1.5.3范式17
1.5.4范式的唯一性——主范式19
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离散数学（第2版）
1.7.3重言蕴涵式31
1.7.4形式推理系统32
1.7.5自然推理系统p235
1.8命题演算中的归结推理42
1.8.1归结推理规则42
1.8.2归结反演43
1.8.3命题逻辑归结反演的合理性和完备性44
习题44

第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谓词逻辑前束范式68
2.4谓词演算的推理理论69
2.4.1推理定律69
2.4.2量词消去与引入规则70
2.4.3一阶谓词演算公理系统f171
2.4.4自然推理系统f272
2.5谓词演算中的归结推理74
2.5.1子句型74
2.5.2置换和合一76
2.5.3合一算法78
2.5.4归结式79
2.5.5归结反演及其完备性80
2.6逻辑在计算机科学中的作用81
2.6.1逻辑与计算81
2.6.2逻辑与计算机的起源82
2.6.3逻辑与程序设计83
习题84

第3章集合与关系90
3.1集合的概念和表示法90
3.1.1集合的表示90
3.1.2基本概念92
3.2集合的运算93
3.2.1集合的基本运算93
3.2.2有穷计数集93
3.2.3广义交和广义并95
3.3有序对与笛卡儿积97
3.4关系及其表示99
3.4.1基本概念99
3.4.2关系表示法100
3.5关系的运算102
3.5.1基本概念102
3.5.2复合关系103
3.5.3逆关系104
3.5.4关系幂106
3.5.5幂运算的性质107
3.6关系的性质109
3.6.1关系的5种基本性质109
3.6.2关系性质的等价描述110
3.7关系的闭包113
3.7.1基本概念114
3.7.2闭包的性质118
3.8集合的划分与覆盖119
3.9等价关系和等价类120
3.9.1等价关系120
3.9.2等价类的性质122
3.9.3商集与划分123
3.10相容关系和相容类124
3.11偏序关系125
3.12偏序集与哈斯图126
3.13包含排斥原理129
习题130

第4章函数137
4.1函数的定义137
4.1.1函数和像137
4.1.2函数的性质139
4.1.3常用函数140
4.2复合函数和反函数141
4.2.1复合函数141
4.2.2反函数143
4.3特征函数与模糊子集145
4.4基数的概念147
4.4.1后继与归纳集147
4.4.2自然数，有穷集，无穷集148
4.4.3基数152
4.5可数集与不可数集153
4.6数学归纳法155
习题158

第5章组合计数与离散概率162
5.1基本原理162
5.1.1加法原理162
5.1.2乘法原理163
5.2排列与组合164
5.2.1排列164
5.2.2组合164
5.3排列组合生成算法165
5.3.1排列生成算法165
5.3.2组合生成算法166
5.4广义的排列和组合169
5.5二项式系数和组合恒等式171
5.5.1二项式定理171
5.5.2组合恒等式172
5.6鸽笼原理174
5.6.1鸽笼原理的简单形式174
5.6.2鸽笼原理的一般形式174
5.7递推关系及应用176
5.7.1递推定义函数176
5.7.2递推定义集合178
5.7.3递推关系模型179
5.7.4求解递推关系181
5.7.5递推在算法分析中的应用183
5.7.6生成函数187
5.8离散概率190
5.8.1随机事件与概率190
5.8.2有限概率191
5.8.3条件概率与独立性193
5.8.4Bayes定理194
习题195

第6章图论198
6.1图的基本概念198
6.1.1图的定义和表示198
6.1.2图的同构202
6.1.3完全图与正则图204
6.1.4子图与补图204
6.1.5通路与回路206
6.2图的连通性208
6.2.1无向图的连通性208
6.2.2有向图的连通性209
6.3图的矩阵表示210
6.3.1关联矩阵210
6.3.2有向图的邻接矩阵211
6.3.3有向图的可达矩阵212
6.4欧拉图213
6.5哈密顿图215
6.6二部图218
6.6.1二部图及判别定理218
6.6.2完备匹配219
6.7平面图221
6.7.1平面图及其判定定理221
6.7.2平面图的对偶图226
6.8带权图228
习题229

第7章树及其应用237
7.1概述237
7.1.1树的定义及相关术语237
7.1.2树的性质239
7.2生成树240
7.3最小生成树243
7.4树的遍历246
7.5二叉树248
7.5.1二叉树的性质248
7.5.2二叉搜索树249
7.5.3哈夫曼树250
7.6决策树252
7.6.1决策树的定义252
7.6.2最短时间排序253
7.7树的同构254
7.8博弈树258
7.8.1博弈树的概念258
7.8.2极大极小分析法258
习题260

第8章代数系统264
8.1二元运算及其性质264
8.1.1定义和表示264
8.1.2二元运算的性质266
8.2代数系统268
8.2.1定义和实例268
8.2.2子代数系统270
8.2.3代数系统的同态与同构270
8.3半群与独异点271
8.3.1定义与性质271
8.3.2子系统与直积273
8.4群273
8.4.1群的定义273
8.4.2群的性质275
8.4.3子群的定义278
8.4.4特殊的群279
8.4.5陪集与拉格朗日定理282
8.4.6正规子群与商群283
8.4.7群的同态与同构实例286
8.5环与域288
8.5.1环288
8.5.2域289
8.6格与布尔代数290
8.6.1格290
8.6.2布尔代数295
8.7组合电路297
习题299

第9章自动机、文法和语言306
9.1串和语言306
9.2形式文法307
9.3有限状态机310
9.4有限状态自动机312
9.5不确定有限状态自动机315
9.6语言和自动机之间的关系318
习题319

第10章初等数论322
10.1素数322
10.2最大公约数与最小公倍数323
10.3同余326
10.4一次同余方程和中国剩余定理328
10.4.1一次同余方程328
10.4.2中国剩余定理329
10.5欧拉定理和费马小定理330
10.6数论在密码学中的应用331
10.6.1公钥密码学331
10.6.2RSA密码332
习题333
附录历史注记335
习题答案348
参考文献370