离散数学（第4版）

清华大学出版社“21世纪大学本科计算机专业系列教材”《离散数学（第3版）》已经出版8年了. 在这8年里，计算机科学技术又有了长足的发展，新的技术不断涌现，从人机对弈，到人脸识别和自动驾驶，新技术的应用场景不断扩大. 对计算机专业的需求也不断扩大，在全球范围内，学习计算机专业的学生人数不断增加. 因此，为高等学校计算机专业的师生提供好的教材，就成了很有意义的工作. 
作为计算机专业的基础课之一，离散数学的内容相对稳定，传统上主要包括数理逻辑、集合论、图论、组合数学、代数结构等. 本书在这些内容之外，还覆盖了初等数论和离散概率、算法的平均情况复杂度分析、随机算法等内容. 书中还举例说明了离散数学中的各种概念和结论在关系数据库、工作流模型、密码学、算法分析等领域的应用. 本书有大量难度适当的习题，并有配套的习题解答和电子教案，既方便师生的课堂教学，也方便对离散数学感兴趣的读者自学. 
从本书初版到现在已经有十几个年头了，经过之前的两次修订改版和多年的实际使用，内容已经相当成熟. 这次修订在内容上没有做大的改动，除了更正一些错误，以及对文字做了进一步的精细加工外，主要是在第14章代数系统的内容里增加了后一节，介绍了皮亚诺系统，补充了相应的习题. 皮亚诺系统给出了自然数集的严格定义，在此基础上，可以定义自然数的各种运算并证明这些运算的性质. 在这个过程里，要综合运用本课程前面学过的集合、函数、递归定义、归纳证明、代数系统的同构等概念和技巧. 
作者衷心感谢广大读者和清华大学出版社的支持和鼓励. 此次修订主要由刘田完成. 不当之处，欢迎广大读者批评指正.作者
2022年3月于北京大学第3版前言FOREWORD作为清华大学出版社和中国计算机学会共同规划的“21世纪大学本科计算机专业系列教材”之一，《离散数学(第2版)》已经出版5年了. 在这5年里，一些新的教育理念、教学模式不断提出并加以实践，其中重要的是“计算思维（computational thinking）”和“大规模开放式在线课程(massive open online course,MOOC)”. 计算思维是数学思维与工程思维的互补与融合，不但是从事计算机科学技术工作的人所需要的专业素质，也对其他学科的发展产生了深远的影响，计算思维的培养已经成为大学计算机专业的重要目标之一. MOOC教学模式近年来在国外迅速增长，已经产生了巨大的影响；国内也把优质教学资源共享列入国家计划并给予了大力支持.  这些新的教育理念和教学模式对教材的修订有着重要的影响.  
离散数学是研究离散结构及其性质的学科，大量用于计算机系统及其应用领域的建模及分析.  离散数学对培养计算思维起着重要的作用，不但被列入计算机专业的核心课程，而且近年来电子工程、经济学等专业领域也开始在教学中加入一些离散数学的内容.  如何在离散系统建模中体现计算思维是本教材修订的指导思想.  本着对读者负责的精神，我们在这次修订工作中认真地审阅了原书，对其中的部分内容做了调整，更正了某些错误和疏漏之处，并对文字做了进一步的精细加工. 
本版在内容上主要做了如下改动：   对第1章“数学语言与证明方法”做了部分重写，对重要的数学证明方法进行了分类和较详细的阐述，补充了有关递归定义的内容.  第5章补充了关系与函数在数据库及软件工程建模中的应用实例.  第6章增加了二部图的匹配、着色和四色定理.  第7章删除了基本回路与基本割集系统.  第10章对递推方程在算法设计与分析中的应用加以补充.   
与本教材同步更新的有配套的教学辅导用书《离散数学习题解答与学习指导（第3版）》和用于课堂上教学的PPT演示文稿.  更多的后续教学资源正在开发，并将上传到清华大学出版社的在线数字资源平台上，为使用本书的读者提供更大的支持.  
对广大读者所提出的建议和意见，我们表示衷心的感谢！作者
2013年8月于北京大学第2版前言FOREWORD作为清华大学出版社和中国计算机学会共同规划的“21世纪大学本科计算机专业系列教材”之一，《离散数学》已经出版两年多了. 在这两年多的时间里，教育bu高等学校计算机科学与技术教学指导委员会编制了“高等学校计算机科学与技术专业规范”，教育bu更推出了一系列为提高本科生教育质量的重要举措，特别是2007年1月和2月分别发布的《教育bu、财政部关于实施高等学校本科教学质量与教学改革工程的意见》（教高\[2007\]1号）和《教育bu关于进一步深化本科教学改革，全面提高教学质量的若干意见》（教高\[2007\]2号），对专业设置、教学模式、课程建设、师资队伍等各个方面不但提出了更高的建设目标，也为保证这一工程的顺利执行提供了有力的保证. 
好的教师和好的教材是保证教学质量的前提条件. 本着对读者负责的精神，我们在这次修订工作中认真地审阅了原书，根据教学要求对其中的部分内容做了调整，更正了错误和疏漏之处，并对文字做了进一步的精细加工. 
本版在内容上主要做了如下改动： 去掉了数理逻辑中有关“一阶逻辑推理理论”的内容. 主要原因是这部分内容涉及形式系统. 形式系统在系统定义和推理中应该采用完全形式化的方法，通常包含形式语言以及用形式语言表述的公理和推理规则. 在形式系统中，符号串本身是没有语义的，只能通过解释赋予它们一定的语义，但在讨论系统的公理或推理规则时应该与语义无关. 本书在第1版的叙述中没有完全采用这种形式化的方法. 如果从知识体系的严谨性出发，应该采用这种完全形式化的表述方法. 但是，这不但与本书的整体写作风格不够协调，而且内容也偏深，超出本教材的要求，因此本次修订决定删掉这部分内容. 
为了进一步提高本书的质量，我们恳切地欢迎读者继续提出建议和意见. 作者
2007年11月于北京大学第1版前言FOREWORD科学技术的发展离不开基础研究和创新. 19世纪至20世纪是人类科学技术飞速发展的时代，其中作为数学基础的微积分为促进物理学和其他工程学科的发展起到至关重要的作用. 21世纪是信息时代，作为信息科学和计算机科学的数学基础，离散数学受到越来越多的关注. 在美国ACM和IEEE推出的Computing Curricula 2005课程体系和我国教育bu高等教育司组织评审通过的《中国计算机科学与技术学科教程 2002》（CCC2002）中,离散数学都被列入核心课程. 
离散数学研究各种离散形式的对象，研究它们的结构及其关系，在数据结构、算法设计与分析、操作系统、编译系统、人工智能、软件工程、网络与分布式计算、计算机图形学、人机交互、数据库以及计算机体系结构等领域都得到了广泛的应用. 除了计算机科学以外，在自动化、化学工程、生物学、经济学等各个学科领域中，都广泛使用数学建模，而离散数学是数学建模的重要工具之一. 离散数学已经成为计算机科学技术和相关专业的必修课程. 
除了作为多门课程必需的数学基础之外，离散数学中所体现的现代数学思想对于加强学生的素质教育，培养学生的抽象思维和逻辑表达能力，提高发现问题、分析问题、解决问题的能力也有着不可替代的作用. 
国内外现已出版了各种版本的《离散数学》教材，取材差异很大，深浅不一，风格各异. 本教材是以《中国计算机科学与技术学科教程2002》中制定的关于离散数学的知识结构和体系为依据撰写的，主要内容包含证明技巧、数理逻辑、集合与关系、函数、图和树、组合计数、初等数论、离散概率和代数系统等. 在教材编写过程中，作者力求体系严谨、选材适当、适于教学，同时在素材组织上更加注重在计算机科学技术中的应用. 
全书共14章. 第1章介绍全书使用的数学语言（主要是命题逻辑符号和集合运算）与证明方法. 第2章和第3章分别介绍命题逻辑和一阶逻辑的基本概念、等值演算和推理理论. 第4章和第5章介绍离散结构的集合表示——关系和函数，讨论关系和函数的各种运算、性质、表示方法以及应用. 第6章和第7章介绍离散结构的图形表示——图和树，包括图的基本概念、图的矩阵表示、特殊图、无向树和有向树及其应用. 第8章到第10章介绍组合计数技术及其在计算机科学技术中的应用. 第11章到第13章介绍初等数论和离散概率及其在密码学和算法分析中的应用. 第14章简要介绍离散系统的代数模型. 每章除了阐述相关的概念和定理之外，还配有典型的例题，并且选用或编写了数十道难度适当的习题供课后练习使用. 
为了更好地为使用本教材的读者服务，作者还撰写和开发了与本教材配套的教学辅助用书和电子教案. 离散数学（第4版）本书的第1章至第3章和第6章、第7章由耿素云编写，第4章、第5章、第8章至第10章和第14章由屈婉玲编写，第11章至第13章由张立昂编写.
在编写过程中，作者参考了国内外多种版本的《离散数学》教材和相关的文献资料，从中吸取了许多好的思想，摘取了不少有用的素材，在此一并向有关作者致谢. 感谢“21世纪大学本科计算机专业系列教材”编委会和清华大学出版社对本书出版的大力支持，特别要感谢李晓明教授，他在百忙之中认真地审阅了全稿，并提出了宝贵的修改意见，使作者受益匪浅. 我们更期待着广大读者，特别是使用本书作为教材的老师和学生对本书的批评、指正、建议和评论.

作者
2005年2月于北京大学

《离散数学（第4版）》参照美国ACM和IEEE CS推出的Computing Curricula，根据教育bu高等学校计算机科学与技术教学指导委员会编制的“高等学校计算机科学与技术专业规范”中关于离散数学的知识结构和体系撰写. 全书共14章，内容包含证明技巧、数理逻辑、集合与关系、函数、组合计数、图和树、初等数论、离散概率、代数系统等.  体系严谨，文字精练，内容翔实，例题丰富，注重与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，适合教学. 另外，本书有配套的习题解答与学习指导等教学辅导用书，以及用于课堂教学的PPT演示文稿和在线数字资源等，以满足教学需要.
本书适合作为高等学校计算机及相关专业本科生“离散数学”课程的教材，也可以作为对离散数学感兴趣的人员的入门参考书.

《离散数学（第4版）》参照美国ACM和IEEE CS最新推出的Computing Curricula，根据教育bu高等学校计算机科学与技术教学指导委员会最新编制的“高等学校计算机科学与技术专业规范”中关于离散数学的知识结构和体系撰写. 全书共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分情况证明法和构造性证明法13
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
目录离散数学（第4版）第3章 一阶逻辑66
3.1一阶逻辑基本概念66
3.1.1命题逻辑的局限性66
3.1.2个体词、谓词与量词66
3.1.3一阶逻辑命题符号化68
3.1.4一阶逻辑公式与分类71
3.2一阶逻辑等值演算76
3.2.1一阶逻辑等值式与置换规则76
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集合的划分106
4.4.4偏序关系107
4.4.5偏序集与哈斯图 108
习题112
第5章 函数117
5.1函数的定义及其性质117
5.1.1函数的定义117
5.1.2函数的像与完全原像  119
5.1.3函数的性质   120
5.2函数的复合与反函数123
5.2.1函数的复合123
5.2.2反函数125
习题129
第6章 图133
6.1图的基本概念133
6.1.1无向图与有向图133
6.1.2顶点的度数与握手定理135
6.1.3简单图、完全图、正则图、圈图、轮图、方体图137
6.1.4子图、补图139
6.1.5图的同构140
6.2图的连通性142
6.2.1通路与回路142
6.2.2无向图的连通性与连通度142
6.2.3有向图的连通性及其分类145
6.3图的矩阵表示145
6.3.1无向图的关联矩阵145
6.3.2有向无环图的关联矩阵146
6.3.3有向图的邻接矩阵147
6.3.4有向图的可达矩阵148
6.4几种特殊的图150
6.4.1二部图150
6.4.2欧拉图153
6.4.3哈密顿图154
6.4.4平面图158
习题167
第7章 树及其应用174
7.1无向树174
7.1.1无向树的定义及其性质174
7.1.2生成树177
7.2根树及其应用178
7.2.1根树及其分类178
7.2.2树与哈夫曼算法179
7.2.3前缀码180
7.2.4根树的周游及其应用182
习题183
第8章 组合计数基础186
8.1基本计数规则187
8.1.1加法法则187
8.1.2乘法法则187
8.1.3分类处理与分步处理188
8.2排列与组合188
8.2.1集合的排列与组合189
8.2.2多重集的排列与组合192
8.3二项式定理与组合恒等式194
8.3.1二项式定理194
8.3.2组合恒等式195
8.3.3非降路径问题200
8.4多项式定理与多项式系数202
8.4.1多项式定理202
8.4.2多项式系数203
习题204
第9章 容斥原理207
9.1容斥原理及其应用207
9.1.1容斥原理的基本形式207
9.1.2容斥原理的应用208
9.2对称筛公式及其应用211
9.2.1对称筛公式211
9.2.2棋盘多项式与有限制条件的排列213
习题216
第10章 递推方程与生成函数218
10.1递推方程及其应用218
10.1.1递推方程的定义及实例218
10.1.2常系数线性齐次递推方程的求解220
10.1.3常系数线性非齐次递推方程的求解223
10.1.4递推方程的其他解法225
10.1.5递推方程与递归算法229
10.2生成函数及其应用234
10.2.1牛顿二项式定理与牛顿二项式系数234
10.2.2生成函数的定义及其性质235
10.2.3生成函数的应用237
10.3指数生成函数及其应用242
10.4Catalan数与Stirling数244
习题249
第11章 初等数论252
11.1素数252
11.2公约数与小公倍数255
11.3同余258
11.4一次同余方程与中国剩余定理260
11.4.1一次同余方程260
11.4.2中国剩余定理262
11.4.3大整数算术运算263
11.5欧拉定理和费马小定理264
习题265
第12章 离散概率269
12.1随机事件与概率、事件的运算269
12.1.1随机事件与概率269
12.1.2事件的运算271
12.2条件概率与独立性272
12.2.1条件概率272
12.2.2独立性274
12.2.3伯努利概型与二项概率公式274
12.3离散型随机变量275
12.3.1离散型随机变量及其分布律275
12.3.2常用分布276
12.3.3数学期望278
12.3.4方差279
12.4概率母函数281
习题283
第13章 初等数论和离散概率的应用287
13.1密码学287
13.1.1凯撒密码287
13.1.2RSA公钥密码288
13.2产生伪随机数的方法290
13.2.1产生均匀伪随机数的方法290
13.2.2产生离散型伪随机数的方法291
13.3算法的平均复杂度分析293
13.3.1排序算法293
13.3.2散列表的检索和插入296
13.4随机算法299
13.4.1随机快速排序算法299
13.4.2多项式恒零测试300
13.4.3素数测试302
13.4.4蒙特卡罗法和拉斯维加斯法303
习题304
第14章 代数系统307
14.1二元运算及其性质307
14.1.1二元运算与一元运算的定义307
14.1.2二元运算的性质309
14.2代数系统312
14.2.1代数系统的定义与实例312
14.2.2代数系统的分类313
14.2.3子代数系统与积代数系统314
14.2.4代数系统的同态与同构315
14.3几个典型的代数系统316
14.3.1半群与独异点316
14.3.2群318
14.3.3环与域324
14.3.4格与布尔代数327
14.4皮亚诺系统332
习题334
参考文献338

《离散数学（第4版）》参照美国ACM和IEEE CS推出的Computing Curricula，根据教育bu高等学校计算机科学与技术教学指导委员会编制的“高等学校计算机科学与技术专业规范”中关于离散数学的知识结构和体系撰写. 全书共14章，内容包含证明技巧、数理逻辑、集合与关系、函数、组合计数、图和树、初等数论、离散概率、代数系统等.  体系严谨，文字精练，内容翔实，例题丰富，注重与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，适合教学. 另外，本书有配套的习题解答与学习指导等教学辅导用书，以及用于课堂教学的PPT演示文稿和在线数字资源等，以满足教学需要.
本书适合作为高等学校计算机及相关专业本科生“离散数学”课程的教材，也可以作为对离散数学感兴趣的人员的入门参考书.

本书是北京大学教学团队编写的“离散数学”经典畅销教材，国家精品课课程配套教材，普通高等教育精品教材。参照ACM和IEEE推出的Computing Curricula，符合教育bu高等学校计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术专业规范”，围绕核心知识点精心选材，教学目标定位清晰。引入了较多的来自科研和工程实践的典型实例，注重把离散数学严谨的知识体系与计算机科学技术的发展相结合。凝练了北京大学教学团队多年的课程建设成果，内容覆盖合理，习题选配恰当，语言通俗易懂，教学资源丰富。