本书分为四部分，共9章。第一部分为数理逻辑，主要包括命题逻辑、一阶逻辑及数理逻辑中的推理证明等内容。第二部分为集合论，主要包括集合、矩阵、关系和函数等内容。第三部分为图论，主要包括图的基本概念和矩阵表示、特殊的图和树等内容。第四部分为代数系统，主要包括代数系统基础、格与布尔代数等内容。
本书内容丰富，层次分明，重点突出，并注重离散数学的实用性，可以为计算机专业学生提供重要的数学基础。本书可作为计算机专业本科生、大专生等的理论教学教材。
为配合教学，本书配有电子课件、教学大纲、习题答案等教学资源，有需要的教师可登录机械工业出版社教育服务网（www.cmpedu.com）免费注册,审核通过后下载，或联系编辑索取（微信：18515977506，电话：010-88379739）。本书还配有教学视频，读者可在正文中扫描二维码观看。

适读人群 ：计算机专业本、专科生

本书是一本通俗易懂的离散数学课程教材。由浅入深地介绍了数理逻辑、集合论、图论和代数系统四个部分，每一部分均配有大量难易程度不同的例题，且重、难点知识点均配有视频讲解。

本书内容翔实，深入浅出，是一本适宜学生预习和复习，且可读性强的教材。

本书注重先进性和实用性，同时概念清楚，系统性强，力求保持离散数学知识的完整性，有利于不同层次的读者从不同起点逐步理解和掌握离散数学知识。

课时安排：本书数理逻辑部分适宜12～16个课时，集合论部分适宜16～22个课时，图论部分适宜10～12个课时，代数系统部分适宜6～8个课时。

前　言

离散数学是计算机科学的基础核心学科,也是计算机专业的核心基础课程，主要研究离散结构和相互关系。离散数学是数据结构、编译原理、数据库原理、计算机组成原理和计算机操作系统等计算机专业课程的数学基础。基础研究是科学之本和创新之源。党的二十大报告中指出：“加强基础学科、新兴学科、交叉学科建设，加快建设中国特色、世界一流的大学和优势学科。”可见，基础研究是国家核心竞争力的重要组成部分，是提升原始创新能力的根本途径。学习离散数学不仅能帮助学生学会应用数学知识，更重要的是可以提高学生的数学逻辑思维能力，为将来参与创新性的研究和开发工作打下坚实的基础。

编写本书的宗旨是在帮助学生全面掌握离散数学理论知识的基础上，注重理论和实践的结合，培养学生运用基础知识分析和解决问题的能力。编者经过对目前主流离散数学教材的分析研究并结合计算机专业的后续学习需求，由浅入深地介绍了数理逻辑、集合论、图论和代数系统四个部分，每一部分均配有大量难易程度不同的例题，且重、难点知识点均配有视频讲解。本书内容翔实，深入浅出，是一本适宜学生预习和复习，且可读性强的教材。

本书注重先进性和实用性，同时概念清楚，系统性强，力求保持离散数学知识的完整性，有利于不同层次的读者从不同起点逐步理解和掌握离散数学知识。本书数理逻辑部分适宜12～16个课时，集合论部分适宜16～22个课时，图论部分适宜10～12个课时，代数系统部分适宜6～8个课时。

本书第1、2、3、4章由田秋红执笔，第5、6、7章由王成群执笔，第8、9章由梁道雷执笔，田秋红负责确定全书的组织架构，金耀负责全书的统稿。本书的出版得到了“十四五”省级教改项目“研究导向的‘计算机科学的教学基础’课程改革研究”（11120032412306）、“浙江理工大学521人才项目”、“浙江理工大学博士科研启动项目（11122932611817）”
和校级教改项目“基于实践课程的学生创新能力培养方法研究（xxjg202103）”的经费资助。

本书的编写和出版得到了机械工业出版社的大力支持，以及许多教师及业界同人的帮助，他们为本书的顺利出版提供了良好的条件，编者表示衷心感谢。

由于时间和编者水平有限，错漏之处在所难免，欢迎广大读者批评指正。



编　者

田秋红，女，博士，浙江理工大学计算机科学与技术学院（人工智能学院）教授，硕士生导师，计算机科学与技术系副主任，计算机系党支部书记，曾获计算机科学与技术学院与信息学院第一届“我心目中的好老师”称号。主持或参与国家自然科学基金和浙江省自然科学基金项目10余项；主持横向与参与课题10余项；授权国家发明专利20余项，其中国家发明专利转化5项、先后发表论文30余篇，其中SCI、EI收录10余篇、编写教材2部。指导的本科生以第一作者发表论文6篇，其中SCI文章一篇。指导本科生参加大学生挑战杯与互联网+竞赛，并于2021年获互联网+竞赛浙江省铜奖，大学生挑战杯浙江省三等奖，2022年获大学生挑战杯浙江省金奖。指导本科生立项国家级大学生创新创业项目3项、浙江省新苗项目10项；指导本科生授权国家发明专利2项、受理国家发明专利10余项、授权软件著作权20余项、实用新型专利1项。

第一部分　数理逻辑
第1章　命题逻辑2
　1.1　命题及符号化2
　　1.1.1　命题2
　　1.1.2　联结词3
　　1.1.3　真值表5
　　1.1.4　复合命题符号化6
　　1.1.5　命题公式分类7
　1.2　命题等值演算9
　　1.2.1　等值式9
　　1.2.2　等值演算9
　1.3　范式12
　　1.3.1　析取范式和合取范式12
　　1.3.2　主析取范式和主合取范式14
　1.4　逻辑电路20
　1.5　习题22
第2章　一阶逻辑26
　2.1　一阶逻辑基本概念26
　　2.1.1　个体词、谓词26
　　2.1.2　量词27
　　2.1.3　嵌套量词29
　2.2　一阶逻辑公式分类及解释30
　　2.2.1　谓词公式解释30
　　2.2.2　谓词公式分类32
　2.3　一阶逻辑等值式和前束范式33
　　2.3.1　一阶逻辑等值式33
　　2.3.2　前束范式35
　2.4　逻辑推理36
　　2.4.1　命题逻辑推理37
　　2.4.2　一阶逻辑推理41
　2.5　习题44
第二部分　集合论
第3章　集合和矩阵50
　3.1　集合50
　　3.1.1　集合概念50
　　3.1.2　集合间关系51
　　3.1.3　集合运算53
　　3.1.4　集合证明55
　　3.1.5　集合的计算机表示方法58
　3.2　矩阵59
　　3.2.1　矩阵概念59
　　3.2.2　矩阵基本运算60
　　3.2.3　布尔矩阵运算62
　3.3　习题63
第4章　关系和函数66
　4.1　关系66
　　4.1.1　关系概念66
　　4.1.2　关系表示方法70
　　4.1.3　关系运算72
　　4.1.4　关系性质77
　　4.1.5　关系闭包82
　　4.1.6　等价关系84
　　4.1.7　偏序关系88
　4.2　函数92
　　4.2.1　函数定义92
　　4.2.2　函数性质94
　　4.2.3　函数运算95
　4.3　习题97
第三部分　图论
第5章　图的基本概念和矩阵表示102
　5.1　图的基本概念102
　5.2　顶点的度数与度序列104
　5.3　握手定理105
　5.4　完全图106
　5.5　图的同构与子图107
　5.6　图的操作109
　5.7　通路回路111
　5.8　连通性112
　　5.8.1　无向图的连通性112
　　5.8.2　有向图的连通性114
　5.9　矩阵表示115
　　5.9.1　邻接矩阵115
　　5.9.2　可达矩阵118
　　5.9.3　关联矩阵119
　　5.9.4　连通性与矩阵关系120
　5.10　路径120
　　5.10.1　最短路径120
　　5.10.2　Dijkstra算法121
　　5.10.3　Bellman-Ford算法123
　　5.10.4　SPFA算法125
　　5.10.5　Floyd算法127
　　5.10.6　拓扑排序和关键路径130
　5.11　习题134
第6章　特殊的图136
　6.1　欧拉图136
　　6.1.1　基本概念136
　　6.1.2　判定137
　6.2　哈密顿图138
　6.3　二部图142
　6.4　平面图146
　　6.4.1　基本概念146
　　6.4.2　欧拉公式147
　　6.4.3　平面图判定148
　6.5　图的着色问题151
　　6.5.1　对偶图151
　　6.5.2　地图着色与四色猜想152
　　6.5.3　平面图着色与五色定理153
　　6.5.4　平面图点着色154
　6.6　习题156
第7章　树159
　7.1　概念介绍159
　7.2　生成树与最小生成树160
　　7.2.1　Kruskal算法162
　　7.2.2　管梅谷算法163
　　7.2.3　逐步短接法164
　7.3　根树165
　　7.3.1　根树概念165
　　7.3.2　二叉树遍历167
　　7.3.3　最优二叉树和哈夫曼编码169
　　7.3.4　一般树遍历170
　7.4　习题172
第四部分　代数系统
第8章　代数系统基础174
　8.1　代数系统概念174
　8.2　半群与独异点182
　8.3　群的基本定义与性质184
　8.4　子群与陪集189
　8.5　循环群和置换群195
　8.6　环和域200
　8.7　习题203
第9章　格与布尔代数206
　9.1　格206
　9.2　布尔代数213
　9.3　习题215
参考文献217