前言（第二版）

FOREWORD

离散数学是计算机科学与技术学科的基础，它以离散量为研究对象，充分描述了计算机科学与技术学科的离散性特点。

离散数学是随着计算机科学与技术学科的发展而逐步建立的，尽管它的主要内容在计算机出现之前就已散见于数学的各个分支中。它形成于20世纪70年代初，因此，国外也有人称之为“计算机数学”，或称其为“离散结构”。

离散数学包括的内容主要有集合论、图论、数理逻辑、代数结构，并且其内容一直随着计算机科学与技术学科的发展而不断地扩充和完善。作为计算机专业的核心课程，它为后续课程提供了必要的数学基础。这些后续课程主要有：数据结构、编译原理、算法分析、计算机密码学、人工智能和可计算性理论等。

本书是在编者多年讲授离散数学课程的基础上编写而成的，其目的在于通过讲授离散数学中的基本概念、基本定理和运算及其在计算机科学与技术学科中的应用，培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力。因此，本书力求概念阐述严谨，证明推演详尽，较难理解的概念用实例说明。

本书是“十二五”普通高等教育本科国家级规划教材。本书第二版在内容和结构上对第一版进行了修改和补充，增加了形式语言与自动机理论部分。全书共分四篇：第一篇是集合论与数理逻辑。主要介绍集合、关系、映射、可数集与不可数集、命题逻辑与一阶逻辑。集合论是全书的基础知识和基本工具，命题逻辑与一阶逻辑则是数理逻辑中与计算机科学与技术学科关系较密切的基本内容。第二篇是图论与组合数学。主要介绍图与子图、树、图的连通性、E图与H图、匹配与点独立集、图的着色、平面图、有向图、网络最大流、排列和组合的一般计数方法、容斥原理、递推关系与生成函数。由于图为任何一个包含二元关系的系统提供了一种离散数学模型，因此，应用图论来解决计算机科学与技术学科相关领域中的问题已显示出极大的优越性。此外，图论对于锻炼学生的抽象思维能力，提高运用数学工具描述并解决实际问题的能力也大有益处。本篇还介绍了组合数学中关于存在性、计数、构造、分类，以及最优化等基本知识，目的在于向读者介绍组合分析这一强有力的数学工具。第三篇是代数结构与初等数论。主要内容有整数、群、环与域、格与布尔代数。第四篇是形式语言与自动机理论基础，主要介绍计算模型基础理论中形式语言与有限自动机理论的一些基本知识。

本书有配套教材《离散数学题解与分析（第二版）》（刘任任主编，中国铁道出版社出版，2015年），对书中习题进行了较详细的分析与解答，以帮助读者加深对基本概念、基本定理以及运算规律的理解。

本书适合作为高等院校计算机及相关专业的教材，书中加*的部分为选学内容，教师可以按授课对象的实际情况和专业教育的要求进行取舍，决定讲授内容。本书也可供从事离散结构领域研究工作的人员参考。

本书的编写得到了教育部第一类特色建设专业（计算机科学与技术）项目、“十二五”普通高等教育国家级规划教材建设项目的资助。同时，中国计算机学会计算机教育委员会副主任蒋宗礼教授对本书提出了很多宝贵的意见和建议，在此表示衷心的感谢。

本书由刘任任、王婷、周经野担任主编。其中，本书的第一篇和第三篇由刘任任编写，第二篇由王婷编写，第四篇由周经野编写，全书由刘任任和王婷统稿。张陵山、肖芬、曹春红、邹娟、谢慧萍等对教材的编写提出了许多宝贵的意见和建议，在此表示感谢。由于编者的水平有限，书中难免存在疏漏和不足之处，恳请读者批评指正。

最后，我们引用计算机科学巨匠、图灵奖获得者D.E.Kunth的一段话来说明数学，特别是离散数学在计算机科学中的重要地位：

“除了无穷维Hibert空间不可能用得上以外，其他数学理论都可能在计算机科学中得到应用。概括地说：在计算机科学的研究领域中，凡一问题要求形式化、精确化表示，最可能用到的数学理论是数理逻辑，某些部分可能用到代数，甚至拓扑学；凡一问题要求表示出算法执行过程中各部分的逻辑结构或关系，最可能用到的数学理论是图论和数理逻辑，某些部分可能用到代数；凡一问题要求给出量的测定，最可能用到的数学理论是组合数学、数论和概率论等；凡一问题要求得出最优方案，最可能用到的数学理论是运筹学、数论，甚至将来有可能用到数学分析。”

编者

2015年7月