第3版前言FOREWORD作为清华大学出版社的21世纪大学本科计算机专业系列教材之一，《离散数学》(第2版)已经出版5年了.在这5年里，一些新的教育理念、教学模式不断提出并加以实践，其中最重要的是“计算思维（computational thinking）”和“大规模开放式在线课程(massive open online course,MOOC)”.计算思维是数学思维与工程思维的互补与融合，不但是从事计算机科学技术工作的人所需要的专业素质，也对其他学科的发展产生了深远的影响，计算思维的培养已经成为大学计算机专业的重要目标之一.MOOC教学模式近年来在国外迅速增长，已经产生了巨大的影响；国内也把优质教学资源共享列入国家计划并给予了大力支持. 这些新的教育理念和教学模式对教材的修订有着重要的影响. 

离散数学是研究离散结构及其性质的学科，大量用于计算机系统及其应用领域的建模及分析. 离散数学对培养计算思维起着重要的作用，不但被列入计算机专业的核心课程，而且近年来电子工程、经济学等专业领域也开始在教学中加入一些离散数学的内容. 如何在离散系统建模中体现计算思维是本教材修订的指导思想. 本着对读者负责的精神，我们在这次修订工作中认真地审阅了原书，对其中的部分内容做了调整，更正了某些错误和疏漏之处，并对文字做了进一步的精细加工. 内容上主要做了如下改动：   

对第1章“数学语言与证明方法”做了部分重写，对重要的数学证明方法进行了分类和较详细的阐述，补充了有关递归定义的内容. 第5章补充了关系与函数在数据库及软件工程建模中的应用实例. 第6章增加了二部图的匹配、着色和四色定理. 第7章删除了基本回路与基本割集系统. 第10章对递推方程在算法设计与分析中的应用加以补充.  

与本教材同步更新的有配套的教学辅导用书《离散数学习题解答与学习指导》（第3版）和用于课堂上教学的PPT演示文稿. 更多的后续教学资源正在开发，并将上传到清华大学出版社的在线数字资源平台上，为使用本书的读者提供更大的支持. 

对广大读者所提出的建议和意见，我们表示衷心的感谢！作者

2013年8月于北京大学第2版前言FOREWORD作为清华大学出版社和中国计算机学会共同规划的“21世纪大学本科计算机专业系列教材”之一，这本《离散数学》已经出版两年多了.在这两年多的时间里，教育部高等学校计算机科学与技术教学指导委员会编制了“高等学校计算机科学与技术专业规范”，教育部更推出了一系列为提高本科生教育质量的重要举措，特别是2007年1月和2月分别发布的《教育部、财政部关于实施高等学校本科教学质量与教学改革工程的意见》（教高\[2007\]1号）和《教育部关于进一步深化本科教学改革.全面提高教学质量的若干意见》（教高\[2007\]2号），对专业设置、教学模式、课程建设、师资队伍等各个方面不但提出了更高的建设目标，也为保证这一工程的顺利执行提供了有力的保证.

好的教师和好的教材是保证教学质量的前提条件.本着对读者负责的精神，我们在这次修订工作中认真地审阅了原书，根据教学要求对其中的部分内容做了调整，更正了某些错误和疏漏之处，并对文字做了进一步的精细加工.

本版在内容上主要做了如下改动： 去掉了数理逻辑中有关“一阶逻辑推理理论”的内容.主要原因是这部分内容涉及形式系统.形式系统在系统定义和推理中应该采用完全形式化的方法，通常包含形式语言以及用形式语言表述的公理和推理规则.在形式系统中，符号串本身是没有语义的，只能通过解释赋予它们一定的语义，但在讨论系统的公理或推理规则时应该与语义无关.本书在第1版的叙述中没有完全采用这种形式化的方法.如果从知识体系的严谨性出发，应该采用这种完全形式化的表述方法.但是，这不但与本书的整体写作风格不够协调，而且内容也偏深，超出本教材的要求，因此本次修订决定删掉这部分内容.

为了进一步提高本书的质量，我们恳切地欢迎读者继续提出建议和意见.作者

2007年11月于北京大学第1版前言FOREWORD科学技术的发展离不开基础研究和创新.19世纪至20世纪是人类科学技术飞速发展的时代，其中作为数学基础的微积分为促进物理学和其他工程学科的发展起到至关重要的作用.21世纪是信息时代，作为信息科学和计算机科学的数学基础，离散数学受到越来越多的关注.在美国ACM和IEEE最新推出的Computing Curricula 2005课程体系和我国教育部高等教育司组织评审通过的《中国计算机科学与技术学科教程 2002》（CCC2002）中,离散数学都被列入核心课程.

离散数学研究各种离散形式的对象，研究它们的结构及其关系，在数据结构、算法设计与分析、操作系统、编译系统、人工智能、软件工程、网络与分布式计算、计算机图形学、人机交互、数据库以及计算机体系结构等领域都得到了广泛的应用.除了计算机科学以外，在自动化、化学工程、生物学、经济学等各个学科领域中，都广泛使用数学建模，而离散数学是数学建模的重要工具之一.离散数学已经成为计算机科学技术和相关专业的必修课程.

除了作为多门课程必需的数学基础之外，离散数学中所体现的现代数学思想对于加强学生的素质教育，培养学生的抽象思维和逻辑表达能力，提高发现问题、分析问题、解决问题的能力也有着不可替代的作用.

国内外现已出版了各种版本的《离散数学》教材，取材差异很大，深浅不一，风格各异.本教材是以《中国计算机科学与技术学科教程2002》中制定的关于离散数学的知识结构和体系为依据撰写的，主要内容包含证明技巧、数理逻辑、集合与关系、函数、图和树、组合计数、初等数论、离散概率和代数系统等.在教材编写过程中，作者力求体系严谨、选材适当、适于教学，同时在素材组织上更加注重在计算机科学技术中的应用.

全书共分14章.第1章介绍全书使用的数学语言（主要是命题逻辑符号和集合运算）与证明方法.第2章和第3章分别介绍命题逻辑和一阶逻辑的基本概念、等值演算和推理理论.第4章和第5章介绍离散结构的集合表示——关系和函数，讨论关系和函数的各种运算、性质、表示方法以及应用.第6章和第7章介绍离散结构的图形表示——图和树，包括图的基本概念、图的矩阵表示、特殊图、无向树和有向树及其应用.第8章到第10章介绍组合计数技术及其在计算机科学技术中的应用.第11章到第13章介绍初等数论和离散概率及其在密码学和算法分析中的应用.第14章简要介绍离散系统的代数模型.每章除了阐述相关的概念和定理之外，还配有典型的例题，并且选用或编写了数十道难度适当的习题供课后练习使用.

为了更好地为使用本教材的读者服务，作者还撰写和开发了与本教材配套的教学辅助用书和电子教案.[]离散数学（第3版）[]本书的第1章至第3章和第6章、第7章由耿素云编写；第4章、第5章、第8章至第10章和第14章由屈婉玲编写；第11章至第13章由张立昂编写.

在编写过程中，作者参考了国内外多种版本的《离散数学》教材和相关的文献资料，从中吸取了许多好的思想，摘取了不少有用的素材，在此一并向有关作者致谢.感谢“21世纪大学本科计算机专业系列教材”编委会和清华大学出版社对本书出版的大力支持，特别要感谢李晓明教授，他在百忙之中认真地审阅了全稿，并提出了宝贵的修改意见，使作者受益匪浅.我们更期待着广大读者，特别是用本书作教材的老师和学生，对本书的批评、指正、建议和评论.作者

2005年2月于北京大学