前   言



离散数学一直被IEEE & ACM认定为计算机专业核心课程, 也是我国计算机科学与技术专业的核心基础课程。本教材以教育部高等学校计算机类专业教学指导委员会最新编制的《高等学校计算机科学与技术专业规范》和《高等学校计算机科学与技术专业核心课程教学实施方案》为指导，对教学内容进行定位和设计，并针对应用型本科院校和工程类本科院校计算机科学与技术及相关专业的本科生进行选材，结合计算机科学和现代数学发展的新成果，以及编写组多年离散数学课程教学及精品课程建设的经验，吸取教学团队及师生们对该课程的建议编写而成。
离散数学的研究对象是各种离散量的结构及其性质和相互间的关系，并且一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学包含的主要内容有集合论、数理逻辑、图论、代数系统，并且其内容一直随着计算机科学与技术的发展在不断扩充和完善。作为计算机相关专业的核心课程，它为后续的数据结构、操作系统、数据库技术、编译理论、算法分析、可计算性与计算复杂性理论、机器定理证明、逻辑程序、计算机网络、容错诊断、人工智能等专业课程提供必要的数学基础。
五邑大学计算机科学与技术、软件工程、网络工程、信息安全、通信工程（计算机通信网络）、数学与应用数学、信息与计算科学、大数据科学与技术八个专业的培养计划中都将离散数学设置为核心基础课程，但学时不断调整或压缩，从最初的72学时，到64学时或48学时。本书在借鉴各种离散数学教材的基础上，结合作者多年的教学实践，没有将离散数学内容按照模块分割，而是突出知识的内在联系，循序渐进。内容以“工科学生易懂及够用”为原则，由浅入深，逻辑严谨，结构清晰。既强化基本概念的描述，又重视阐述证明方法及各部分知识在计算机科学与技术相关领域的应用实例。本书共分9章，依次为集合基础、命题逻辑、谓词逻辑、关系、函数、图论基础、特殊图、代数系统基础、几个典型的代数系统。各章之间的逻辑和内在联系体现如下图：

本书清晰地介绍了离散数学中的概念，并向读者展示其相关性和实用性。主要特点是：
（1）本书将最基本、最重要的内容选入，并努力做到简明扼要、深入浅出，既保持各章体系的独立性，又展现出它们的密切联系。如集合部分增加了多重集合及计数内容，为所有章节的基础；关系和函数部分应用了数理逻辑的内容等。
（2）通过大量的实例从不同的角度对一些抽象的概念进行诠释，使其易于被学生接受和理解。将同类且对比鲜明的概念或结论集中阐述，并通过典型的实例进行对比说明，使学生深刻理解它们的区别与联系。
（3）每章内容的最后一节介绍离散数学相关理论在日常生活、计算机科学及信息科学中的一些典型应用，以增加知识的趣味性，激发学生学习的积极性。
本书在内容的组织上，精心安排各部分内容的先后顺序，使结构更合理、内容更充实、语言更通俗易懂。注重展现离散数学在计算机科学及信息科学中的应用，以增强学生使用离散数学知识分析问题和解决问题的能力。通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后处理离散信息以及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。
本书的框架结构、样式及符号由吴明芬老师统一设计，李继容老师撰写第1章、第4章和第5章，邢润丹老师撰写第2章和第3章，朱铁丹老师撰写第6章和第7章，吴明芬老师撰写第8章、第9章，第1章、第6章和第7章的习题由奚悦老师完成，编写组老师之间相互补充修正，最后由吴明芬老师对全书进行了统稿，对每章内容及应用进行补充、修正及完善，确保全书内容、前后逻辑、符号等正确和一致。研究生杨光、刘超和高连飞帮助处理书稿的排版、图片处理、部分习题答案及录入，数理逻辑部分借鉴了张先勇老师以前撰写的内容，在此深表谢意。
我们在编写本书的过程中参阅了许多国内外离散数学教材及专著，在此对这些著作的作者表示感谢。在本书的编写过程中，得到了清华大学出版社领导和编辑的大力支持，在此表示深深的谢意。
由于我们的水平和经验有限，书中不妥之处在所难免，恳请读者批评指正。           
　　                                                     
                                                          编  者      
 　                                                2020年10月于五邑大学
                       

??

??

??

离散数学及其应用

  

  


集合基础