离散数学(第2版) 大中专理科数理化

第2版前言

本书自2016年第1版出版以后，已经印刷了8次。在5年多的时间里，许多同行对本书的内容提出了许多中肯的建议，在此深表感谢。
近年来，人工智能、大数据、区块链等计算机技术飞速发展，掀起了IT行业和产业的又一次发展热潮。与此同时，*自2017年开始积极推进新工科建设，先后形成了“复旦共识”“天大行动”和“北京指南”，并发布了《关于开展新工科研究与实践的通知》《关于推进新工科研究与实践项目的通知》，全力探索形成领跑全球工程教育的中国模式、中国经验，助力高等教育强国建设。2018年11月，*高等教育司吴岩司长提出了高校的“金课”标准，即高阶性、创新性、挑战度。按照这个要求，离散数学的课程内容应有效融合学科前沿知识，在计算机类专业的课程体系中呈现基础性、核心性和前沿性的特点。学生通过课程的学习，应达到知识、能力、素质的全面提升，初步具备解决复杂问题的综合能力和高级思维。
2016年，编者开始接手所在学院的程序设计创新实验室，带领学生参加国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）和中国大学生程序设计竞赛（China Collegiate Programming Contest，CCPC），对离散数学有了全新的理解和认识。按照新工科的理念，离散数学的授课应该与学生程序设计能力、计算思维的培养进行有机地结合，让学生充分体会到离散数学在计算机学科的基础性作用。通过学习离散数学，真正使计算机类专业的学生做到学以致用，学有所长，为以后专业课程的学习奠定必要的计算思维、逻辑思维基础。
本次修订是在第1版的基础上，结合计算机学科的发展，融合程序设计竞赛的相关知识点，对第1版的相关内容进行了调整和增删。本次修订也得到了鲁东大学、中国石油大学（华东）、曲阜师范大学和山东工商学院相关领导和老师的大力帮助。本次修订工作由张小峰、张学辉、李阿丽、李涛和赵峰5位老师共同完成。具体分工如下：        第?1、2章由张学辉负责，第3、4章由李涛负责，第5、6、10章由李阿丽负责，第9、10章由赵峰负责，所有章节中的阅读材料、程序设计实例的设计由张学辉负责，其余章节内容和全书的统稿工作由张小峰负责。
鲁东大学邹海林教授、山东大学张彩明教授、西安电子科技大学李兴华教授在百忙中对全书的修订工作提出了许多宝贵建议，在此向他们表示感谢。
特别感谢清华大学出版社，感谢责任编辑和参与本书编辑的各位老师，他们为本书的顺利出版付出了辛勤的劳动。

编  者 2022年1月 第1版前言

离散数学是现代数学的一个重要分支，是计算机科学与技术的重要理论基础。1977年，离散数学被IEEE确定为计算机专业核心主干课程，2004年在计算机5个相关专业的培养计划中，离散数学是计算机工程（Computer Engineering，CE）、计算机科学（Computer Science，CS）和系统工程（System Engineering，SE）3个专业的重要核心课程。作为数据结构、编译原理、数据库原理、操作系统、人工智能等专业课程的前导课程，离散数学不仅需要提供必要的基础知识，更重要的是通过学习离散数学，培养学生的抽象思维能力和逻辑思维能力，进一步强化学生的程序设计能力。
对于学生而言，单纯的理论知识是枯燥的。因此，增加必要的工程应用，与后续的专业课程进行有效衔接，将提高学生的学习兴趣。在设计具体内容时，本教材借鉴了目前主流教材的特点，除必要的基础知识外，增加了相关知识点的工程应用，突出离散数学在程序设计、算法分析以及相关专业课程中的应用。
1. 特点
1）针对性强，适用范围广
本书针对单学期、短学时的离散数学或计算机数学课程而设计，除必要的基础知识外，增加了学习本课程所需要的矩阵基础知识、组合数学以及数论基础知识。本教材适合高等学校计算机类、数学类等专业的学生使用。
2）授之以渔，注重对解题方法和解题思路的培养
本书针对每个例题，在给出完整的解题过程之前，尽可能给出详细的分析过程和必要的证明思路。通过对例题的分析，注重对学生解题方法和解题思路的培养，达到“授之以渔”的目的。
3）注重数学的工程应用，培养学生的程序设计思维
本书在设计教学内容时，注重知识点在程序设计、算法分析以及后续专业课程中的应用，让学生了解知识点的应用价值。同时，选取了程序设计大赛中的典型赛题，基于相关的知识点对赛题进行分析，设计巧妙的程序。
2. 内容安排
第1章  矩阵知识初步。对本书中需要的矩阵知识进行简要地介绍，包括矩阵的基本概念、矩阵的运算以及布尔矩阵等。
第2章  组合数学与数论初步。对组合数学及数论的基本知识进行介绍，包括基本计数原则、排列组合、鸽笼原理、素数、公约数与小公倍数、数制等。
第3章  命题逻辑。对命题逻辑的相关知识进行介绍，包括命题及命题联结词、命题公式、命题公式的等值演算、命题联结词的完备集、命题公式的范式、命题逻辑的推理等。
第4章  谓词逻辑。对谓词逻辑的相关知识进行介绍，包括谓词逻辑的基本知识、谓词公式的等价及蕴涵、谓词逻辑的蕴涵推理等。
第5章  集合论基础。对集合论的基础知识进行介绍，包括集合的基本表示、集合的基本运算、容斥原理等。
第6章  关系。对关系的相关知识进行介绍，包括关系的定义与表示、关系的运算、关系的性质等。
第7章  特殊关系。介绍了3类特殊的关系：等价关系、偏序关系和函数。
第8章  图论基础。对图论的基础知识进行介绍，包括图论的基本概念、通路与回路、无向图和有向图的连通性等。
第9章  特殊图。介绍3种常用的图：欧拉图、哈密顿图和树。
第10章  代数系统。对代数系统的基本概念进行介绍，包括运算与代数系统的基本定义、运算的性质及特殊元素、代数系统的同态、子代数等。
第11章  群论。对半群、独异点、群的基本概念进行介绍，此外，对置换群、循环群、正规子群等也进行了介绍。
第12章  其他代数系统。介绍了环、域、格和布尔代数等其他代数系统。
本书具体编写分工如下：第1、7章由李秀芳编写，第8、9章由杨洪勇编写，第10、12章由赵永升编写，其余章节由张小峰编写，全书的策划和定稿工作由张小峰负责。
作为鲁东大学软件工程专业、计算机科学与技术专业应用型人才培养的系列教材之一，本书曾作为校内讲义在校内多次印刷，在软件工程、计算机科学与技术、网络工程、信息管理与信息系统等专业中使用。在清华大学出版社正式出版之际，在原讲义的基础上，结合多年的教学实践与改革，进行了较大修改，使其既能适合在校学生学习，又能适合其他读者阅读。
在本书的规划和写作过程中，山东大学张彩明教授、西安电子科技大学李兴华教授、鲁东大学邹海林教授等对书稿进行了审阅，提出许多建设性的建议，在此深表感谢。清华大学出版社的广大员工也为教材的出版付出了大量的心血，使本书得以及时出版，在此一并致以衷心地感谢。
在本书编写的过程中，编者参考了国内外诸多版本的《离散数学》《计算机数学基     础》等相关教材，同时参考了相关计算机程序设计大赛的相关资料，这里不再一一列举，在此一并感谢。
限于编者学识水平，教材在内容的取舍、教学体系的设计、知识点的构造、程序设计思想的培养等方面肯定存在不足之处，恳请专家、同行和读者批评指正。

编  者   
2015年9月于烟台

本书共分12章，内容包含矩阵知识初步、排列组合与数论初步、命题逻辑、谓词逻辑、集合论基础、关系、特殊关系、图论基础、特殊图、代数系统、群论和其他代数系统。本书以训练学生的思维能力为核心，以培养计算机类专业的应用型人才为目的，将计算机数学与算法设计进行有效结合，全面提高学生的程序设计能力和应用创新能力。通过对典型的例题进行分析，培养学生分析问题和解决问题的能力。同时，对一些内容进行延伸，将计算机数学基础与后续的专业知识进行完美结合。 本书可以作为数学类专业、计算机类专业的本科教材，也可以作为程序设计大赛培训的参考用书。

本书共分12章，内容包含矩阵知识初步、排列组合与数论初步、命题逻辑、谓词逻辑、集合论基础、关系、特殊关系、图论基础、特殊图、代数系统、群论和其他代数系统。本书以训练学生的思维能力为核心，以培养计算机类专业的应用型人才为目的，将计算机数学与算法设计进行有效结合，全面提高学生的程序设计能力和应用创新能力。通过对典型的例题进行分析，培养学生分析问题和解决问题的能力。同时，对一些内容进行延伸，将计算机数学基础与后续的专业知识进行完美结合。 本书可以作为数学类专业、计算机类专业的本科教材，也可以作为程序设计大赛培训的参考用书。

张小峰，鲁东大学信息与电气工程学院副教授，担任鲁东大学ACM教练，长期从事程序设计基础、离散数学、数据结构、算法分析与设计等课程的教学工作。

第1章  矩阵知识初步 1
1.1  矩阵的概念 1
1.2  矩阵的运算 3
1.3  布尔矩阵 5
阅读材料 6
习题1 11
第2章  排列组合与数论初步 12
2.1  基本计数原则 12
2.1.1  加法原则 12
2.1.2  乘法原则 13
2.2  排列 13
2.3  组合 15
2.4  鸽笼原理 18
2.5  素数 18
2.6  公约数与小公倍数 21
阅读材料 24
习题2 31
第3章  命题逻辑 33
3.1  命题与命题联结词 33
3.1.1  命题 33
3.1.2  命题联结词 34
3.2  命题公式 38
3.3  命题公式的等值演算 42
3.4  命题联结词的完备集 46
3.5  范式 48
3.5.1  析取范式和合取范式 48
3.5.2  主析取范式和主合取范式 49
3.5.3  范式的应用 53
3.6  命题逻辑的推理 57
3.6.1  推理的基本概念 57
3.6.2  推理的基本方法 58
习题3 65
第4章  谓词逻辑 68
4.1  谓词逻辑的基本概念 68
4.2  谓词公式 71
4.3  谓词公式的等价与蕴涵 74
4.4  范式 79
4.5  谓词逻辑的蕴涵推理 80
阅读材料 86
习题4 95
第5章  集合论基础 98
5.1  集合的概念与表示 98
5.2  集合之间的关系 100
5.3  集合的运算 102
5.4  序偶与笛卡儿积 106
5.5  容斥原理 107
阅读材料 111
习题5 114
第6章  关系 116
6.1  关系的定义 116
6.2  关系的表示 118
6.3  关系的运算 119
6.3.1  关系的集合运算 119
6.3.2  关系的复合运算 119
6.3.3  关系的幂运算 125
6.3.4  关系的逆运算 126
6.4  关系的性质 127
6.4.1  自反性与反自反性 128
6.4.2  对称性与反对称性 130
6.4.3  传递性 133
6.5  关系的闭包 135
阅读材料 138
习题6 141
第7章  特殊关系 143
7.1  等价关系 143
7.2  偏序关系 148
7.3  相容关系 152
7.4  函数 154
7.4.1  函数的定义 154
7.4.2  函数的性质 155
7.4.3  函数的运算 156
阅读材料 158
习题7 159
第8章  图论基础 162
8.1  图的基本概念 162
8.1.1  图 162
8.1.2  图的表示 165
8.1.3  图的同构 166
8.1.4  图的操作 167
8.2  通路与回路 170
8.3  图的连通性 174
8.3.1  无向图的连通性 174
8.3.2  有向图的连通性 178
习题8 184
第9章  特殊图 187
9.1  欧拉图 187
9.2  哈密顿图 191
9.3  二分图 194
9.3.1  二分图的概念与判定 194
9.3.2  完备匹配 197
9.4  平面图 203
9.4.1  平面图的概念与判定方法 203
9.4.2  平面图的对偶图 206
9.5  图的着色 207
9.5.1  结点着色 208
9.5.2  边着色 211
9.6  树 213
9.6.1  树的定义 213
9.6.2  生成树与小生成树 216
9.7  根树 220
9.7.1  有向树与根树 220
9.7.2  根树的遍历 222
9.7.3  哈夫曼树 225
习题9 228
第10章  代数系统 230
10.1  代数运算 230
10.2  运算的性质与特殊元素 231
10.2.1  运算的性质 231
10.2.2  特殊元素 234
10.3  代数系统的同态与同构 238
10.4  子代数 240
习题10 241
第11章  群论 242
11.1  半群 242
11.2  群 244
11.2.1  群的基本概念 245
11.2.2  阿贝尔群 247
11.2.3  群同态与群同构 247
11.3  元素的周期与循环群 248
11.3.1  元素的周期 249
11.3.2  循环群 249
11.4  子群 251
11.5  置换群与伯恩赛德定理 254
11.6  陪集与拉格朗日定理 259
11.7  正规子群与商群 261
阅读材料 265
习题11 269
第12章  其他代数系统 270
12.1  环 270
12.2  域 272
12.3  格 272
12.3.1  格的定义 273
12.3.2  格的另一种定义 274
12.3.3  分配格、有界格与布尔格 276
12.4  布尔代数 276
习题12 281
参考文献 282
　　
离散数学（第2版）
　　
     目录
　　
　　
　　
　　
　　
　　
　　

本书共分12章，内容包含矩阵知识初步、排列组合与数论初步、命题逻辑、谓词逻辑、集合论基础、关系、特殊关系、图论基础、特殊图、代数系统、群论和其他代数系统。本书以训练学生的思维能力为核心，以培养计算机类专业的应用型人才为目的，将计算机数学与算法设计进行有效结合，全面提高学生的程序设计能力和应用创新能力。通过对典型的例题进行分析，培养学生分析问题和解决问题的能力。同时，对一些内容进行延伸，将计算机数学基础与后续的专业知识进行完美结合。 本书可以作为数学类专业、计算机类专业的本科教材，也可以作为程序设计大赛培训的参考用书。

张小峰，鲁东大学信息与电气工程学院副教授，担任鲁东大学ACM教练，长期从事程序设计基础、离散数学、数据结构、算法分析与设计等课程的教学工作。