前言


离散数学(discrete mathematics)又称离散结构(discrete structure)，是以离散变量特征的对象为主要目标，研究其模型、性质及操作的一个数学分支。从人类社会历史的发展过程来看，18世纪以前的数学主要讨论整数、整数的比(有理数)，甚至把几何图形也看作由很多孤立的“原子”组成的。因而，那时的数学被看作研究离散的或离散化的数量关系的科学，基本上属于离散数学的范畴。此后，随着数学理论的不断发展(不可通约线段的发现，对无限概念的深入探讨)，加之天文学、物理学中遇到的物体运动等相关问题的需求推动，出现了连续数量的实数概念以及处理连续数量关系的微积分学。20世纪80年代后，随着计算机日益渗透到现代社会的各个方面，工业革命时代以微积分为代表的连续数学占主流地位的情况逐渐发生了变化，离散数学又重新受到高度的重视。
离散数学与计算机科学两者之间有着相辅相成的关系。一方面，离散数学是计算机科学与技术的理论基础，为计算机及其应用的诞生和发展提供了必要的理论支撑。例如，图灵(Alan Mathison Turing，1912—1954)针对可计算所建立的图灵机是计算机的理论模型，这个理念推动了计算机的诞生； 布尔(George Boole，1800—1864)的逻辑代数是计算机硬件分析与设计的基础； 谓词逻辑演算为人工智能学科提供了一种重要的知识表示和推理方法； 代数系统的域为信息安全提供了一种重要的椭圆曲线密码体制，代数系统的格是计算机硬件和软件模型检验验证的理论基础。另一方面，数字电子计算机是一个离散结构，它只能处理离散的或离散化的数量关系。随着计算机科学的迅猛发展，在计算技术、计算机软硬件和计算机应用等各个领域提出了许多以离散变量为特征的理论问题，迫切需要适当的数学工具来描述和深化，从而使人们重新认识到离散变量对象的研究意义，重新重视讨论离散数量关系的数学分支，并取得新的发展。离散数学也因此作为一门学科应运而生，并成为现代数学的一个重要组成部分。
离散数学在计算机科学与技术及相关领域有着广泛的应用。它是计算机科学与技术及相关专业的一门核心基础课程，是许多其他后续课程，如数字电路、程序设计语言、数据结构、操作系统、编译原理、软件工程、人工智能、数据库系统、算法设计与分析、计算机网络、密码学、运筹学等必不可少的先修课程。通过离散数学的学习，学生不但可以掌握处理离散结构的描述工具和研究方法，为后续课程的学习创造条件，而且可以提高抽象思维、逻辑推理和归纳构造能力，为将来参与创新性的研究和开发工作打下坚实的基础。
离散数学是数理逻辑、集合论、关系论、函数论、组合学、数论、代数结构、图论等汇集而成的一门综合课程。它跨越了数学的诸多分支，并与整个计算机学科紧密联系，所涉及的概念和方法，以及采用的符号和工具都远远超出其他任何一门课程，所以不少读者会对这门课程或多或少产生畏惧、厌倦情绪。鉴于上述情况，我们根据多年来对离散数学的研究与教学实践的经验总结，从学生的学习情况及相关专业人员的自学特点出发编写了本书。在编写过程中，我们以“够用”为主，重点突出，并配合了丰富的例题讲解，以达到内容翔实而结构清晰、语言严谨而通俗易懂。同时，在课程的内容和知识体系的设计上，依据ACM和IEEECS发布的CC2020教程，以及教育部高等学校计算机科学与技术教学指导委员会制定的计算机科学与技术专业规范，着力达到理论与实际结合、抽象与直观统一、局部与整体协调。全书共分4篇，第1篇为集合论，包括集合、关系、函数； 第2篇为数理逻辑，包括命题逻辑、谓词逻辑； 第3篇为抽象代数，包括代数系统的基本概念与性质、半群和群、环和域、格和布尔代数； 第4篇为图论基础，包括图的基本概念、赋权图、欧拉图、哈密顿图、二部图、平面图、树等。
本书在撰写过程中参阅了国内外大量的离散数学书籍和相关文献资料，从中汲取了许多先进的思想，摘取了大量有用的素材，在此向相关作者表示感谢。孟瑜、周小川、林煜明等参与了书稿的讨论及部分书稿的文字整理，在此一并表示感谢。
限于作者水平，书中不妥和疏漏之处在所难免，恳请广大读者批评指正。
作者
2022年11月