《离散数学（第3版）》本教材是参照ACM和IEEE最新推出的Computing Curricula，根据教育部高等学校计算机科学与技术教学指导委员会最新编制的“高等学校计算机科学与技术专业规范”中制定的关于离散数学的知识结构和体系撰写的。

内容简介

全书共14章，内容包含证明技巧、数理逻辑、集合与关系、函数、组合计数、图和树、初等数论、离散概率、代数系统等。本书体系严谨，文字精练，内容翔实，例题丰富，注重与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，适合教学。另外，本书有配套的习题解答与学习指导等教学辅导用书，以及用于课堂教学的PPT演示文稿和在线数字资源等，以满足教学需要. 本书适合作为高等学校计算机及相关专业本科生“离散数学”课程的教材，也可以作为对离散数学感兴趣的人员的入门参考书.

图书目录

第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目录[][][]离散数学（第3版）[]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

参考资料