清华大学出版社

离散数学是现代数学的重要分支，是计算机专业和软件工程专业的基础主干课程，是进一步学习后续课程以及进行研究和开发的基础。本书根据作者多年教学经验编写而成，着重讲解离散数学的基本概念、基本方法及其应用，给出了大量的典型例题和习题以及若干综合专题及应用案例。全书共10章，内容包括朴素集合论、数论基础、计数基础、命题逻辑、谓词逻辑、二元关系、函数、偏序关系与格、代数结构、图论、树、形式语言、自动机与正则表达式。附录给出了离散数学综合性研讨专题。 本书结构紧凑，内容精练，体系严谨，语言流畅，讲解详细，可作为高等学校计算机和软件工程专业本科生和研究生的离散数学课程教材，也可供其他专业学生和科技人员阅读参考。

前言 离散数学是现代数学的一个重要分支，是计算机专业和软件工程专业的基础主干课程，主要包含集合论、数理逻辑、图论和代数结构4部分基本内容，研究离散对象的结构、规律及相互关系。它在数据结构、操作系统、软件工程、数据库原理、计算机网络、人工智能、编译原理、软件设计形式化、信息安全等领域都有广泛的应用，并且该课程对于培养、训练和提高学生的问题抽象能力、逻辑推理能力、利用离散数学模型分析和解决实际应用问题的能力都有非常重要的作用，可以为学生进一步学习后续课程以及进行或参与创新性的研究和开发工作打下坚实基础。 2006年3月，卡内基·梅隆大学计算机科学系主任周以真（Jeannette M. Wing）教授在Communications of the ACM杂志上发文提出了“计算思维（computational thinking）”。它指的是与形式化问题及其解决方案相关的思维过程，表示由人和机器共同解决问题。周教授还指出： “计算思维中最重要、最高级的思维过程就是抽象过程。”（The most important and highlevel thought process in computational thinking is the abstraction process.）。 英国唯物主义哲学家弗朗西斯·培根也说过： “数学是思维的体操。” 综合这两者，就可以称“离散数学是计算思维的体操”。 这是因为计算离不开数学，现实问题需要先转换成离散的存储和表示方法，才能让计算机“理解”和“接受”，进而才能得以处理。可以说，离散数学是联系此岸（现实世界）和彼岸（抽象的数学处理）的桥梁。 离散数学以研究离散量的结构和相互间的关系为主要目标，是一个内涵极其深刻、外延极其丰富且充满变化、发展和活力的研究领域，是信息科学与技术的数学基础和必不可少的工具，也是计算机科学、软件工程、计算机工程等领域的核心课程之一，得到了越来越多的关注。通过学习离散数学，学生不仅可以为其他课程做好必要的基础准备，还可以提高自己的数学涵养，锻炼自己的思维能力、分析能力、学习新知识和创造性地处理新问题的能力。 作者主持建设并讲授的离散数学课程被评为首批国家级（线上）一流本科课程（主要开课平台为“爱课程（中国大学MOOC）”），该课程的指定教材即是本书。自本书第1版和第2版出版以来，作者收到了众多师生的反馈。 本着与时俱进的精神，在保持第1版和第2版语言准确、逻辑严谨、示例丰富、实用性强等特色的基础上，作者对本书进行了修订，新版内容更加完整，作者力求使它不仅是一本教材，更是一本值得收藏的参考书。此外，作者还编写了配套用书《离散数学及应用学习指导与习题解析》。 离散数学及应用(第3版)前言3在对本书进行修订时，保持全书篇幅合理和增加新内容之间的平衡是非常困难的。本次修订的处理方式是将一些附录作为独立的在线PDF文档（读者可以在清华大学出版社网站下载），并精简各章的习题，只保留较为基础的习题，同时以在线文档的形式提供大量难度和灵活性都较高的补充习题。这些做法可以确保作者尽可能地扩充本书的内容而又不使篇幅过于增大。 除此之外，第3版较第2版主要有以下变化: ●每章的开头都增加了该章内容的微词云，每章的最后都增加了“扩展阅读”一节，供有兴趣的读者参考。书中标有“”号的节/小节更适合进阶读者;其他读者可以跳过这些内容,不会影响学习的连贯性。 ●将习题从每章的最后调整至每节之后，这样更具有针对性。 ●将原“4.7关系在计算机中的表示方法”改为在线附录，将原“6.3.4信息流的格模型”移入附录A。 ●增加了“6.2.3有限偏序集的高度与宽度”“8.9图的连通度”和“10.7图灵机”。 ●对“6.3.2特殊的格”“6.3.3布尔代数”“7.2.6循环群”“7.2.7变换群与置换群”“8.3哈密顿图”“8.4平面图”和“8.8.2网络流的应用”等节进行了增补或重写。 ●“附录A离散数学综合性研讨专题”增加了波利亚的果园、国际标准刊号、15谜题、博弈树与决策树、龙曲线、社会网络中的结构平衡、市场清仓与单品拍卖、密码算法简介等内容。 ●第2版的“附录B课程综合实验”移至《离散数学及应用学习指导与习题解析》中，并增加了4个实验。 ●重写了第2版的“附录EProlog语言与逻辑推理”（作为在线附录），使用SWI Prolog描述并增加了大量示例。 ●增加了“罗素悖论与公理化集合论简介”“自然数、整数与数学归纳法”“模糊集合与模糊关系简介”“排列与组合的生成算法”和“五色定理”5个附录，均作为在线附录。 此外，第3版对各章都进行了一些文字表述与内容的调整，在此不一一列举。 在本书的编写过程中，作者参考了国内外大量文献，在此向有关作者一并致谢。 感谢清华大学出版社各位编辑对本书的出版所做的细致工作。 作者在完成书稿过程中得到了家人和朋友的很多帮助和支持，在此深表感谢。 限于时间与水平，书中难免有不妥之处，恳请广大读者批评指正。 作者在“爱课程（中国大学MOOC）”平台上开设了与本书配套的课程，欢迎大家扫码加入，开启愉快的离散数学学习之旅。 作者2022年1月自本书第1版出版以来，作者收到了来自使用本书的师生的众多反馈，而作者在使用本书的过程中也发现了一些问题，特别是作者目前正在进行“离散数学”课程的MOOC建设及实施，这些因素都促使作者进行了第2版的编写工作。 第2版对各章都进行了一些文字与内容的调整，特别是在正文中讲授知识点时补充了一些简单的应用示例，并增补了一定数量的习题，部分较难的习题增加了必要的提示。 此外，较大的变化如下： ●第4章增加了“相容关系与集合的覆盖”一节。 ●第6章增加了“信息流的格模型”一节。 ●第8章增加了点支配、点独立、点覆盖、匹配、边覆盖、网络与流等内容。 ●增加了第10章“形式语言、自动机与正规表达式”。 ●增加了附录A“综合性研讨专题”，可供师生课后阅读和开展研讨使用。 ●附录B“课程综合实验”增加了三个实验。 ●增加了附录E“Prolog语言与逻辑推理”，介绍了逻辑编程语言Prolog的基本概念、基本语法以及简单示例。 感谢北京交通大学重点教学改革和建设项目“软件工程专业课程群基于MOOC的教学改革研究与实践”对本书出版的支持。感谢清华大学出版社各位编辑对本书的出版所做的细致工作。 在作者完成书稿的过程中，家人和朋友给予了很多帮助和大力支持，在此深表感谢。 由于水平所限，书中难免有不妥或错误之处，恳请广大读者批评指正。 作者2017年10月离散数学是现代数学的一个重要分支，是计算机专业和软件工程专业的基础主干课程，主要包含集合论、数理逻辑、图论和代数结构4部分基本内容，研究离散对象的结构、规律及相互关系。它在数据结构、操作系统、软件工程、数据库原理、计算机网络、人工智能、编译原理、软件设计形式化、信息安全等领域都有广泛的应用。并且该课程对于培养、训练和提高学生的问题抽象能力、逻辑推理能力、利用离散数学模型分析和解决实际应用问题的能力都有非常重要的作用，可以为学生进一步学习后续课程以及进行或参与创新性的研究和开发工作打下坚实基础。 本书的特点是着重讲解基本概念、基本方法及其应用，尽可能减少需要记忆的内容。除严谨系统的理论阐述和细致详尽的内容讲解外，本书给出了大量的典型例题、丰富的应用实例和难易程度不同的大量习题，而且还设计了几个综合的应用案例和实验项目，学生可以利用这些内容加深对基本内容的理解和掌握，更可以动手体会分析问题和解决问题的过程，提高学习的兴趣和效果。 本书的内容由浅入深，可读性强，部分内容比较抽象的章节在标题前加了号，教师可根据实际情况选择使用。 本书可供高等院校计算机或软件工程专业不同方向本科生一学期的离散数学课程教学使用，也可供其他专业学生和科技人员阅读参考。 在编写本书过程中，作者参考了许多已经出版的同类书籍，在此对这些作者表示由衷的感谢！同时特别感谢孙波同志通读全稿并给出很多很好的意见和建议。 本书的出版得到了北京交通大学教学改革项目“‘离散结构（双语）’课程研究性教学改革及课程资源建设”的支持。 清华大学出版社龙启铭、战晓雷两位编辑为本书的出版做出了大量辛苦而细致的工作，作者在此表示深深的谢意。 最后，虽然作者在结构和内容上斟酌再三，几易其稿，但由于水平所限，书中难免有不妥或错误之处，恳请广大读者批评指正。 作者2012年12月

版权图片链接