本书是北京高等教育精品教材。内容主要包括数理逻辑、集合论、图论、组合分析初步、代数结构及形式语言和自动机初步6方面的内容。书中概念论述清楚，内容丰富，通俗易懂，并且着重于概念的应用，而不着重于定理的证明。每章后均附有习题，建议学时为54～72。

本书可以作为计算机及信息管理等相关专业本科生的教材，也可以供从事计算机软件、硬件开发和应用的人员使用。另有配套教材《离散数学题解（第六版）》。

第六版

本次修订除了改正一些错误和修改一些文字外, 主要重新改写了第10章形式语言和自动机初步。删除了几个定理的证明, 简化了图灵机的内容, 这些内容对于使用本书的大多数读者不是很必要；增加了10.3节正则表达式, 正则表达式和正则文法、自动机是等价的, 是描述正则语言的常用工具；另外，还添加了10.1.4节和10.1.5节, 分别介绍正则文法和上下文无关文法的应用和语法分析树。希望这些简单的介绍能够帮助读者在后续课程中学习有关内容时在理论上更好地理解这些技术。

对配套出版的《离散数学题解(第六版)》(书号为9787302593201)也进行了相应的修订。

由于作者水平所限, 书中难免仍有不妥和错误, 恳请读者指正。

作者2021年8月第五版

本书自从2008年发行第四版以来，随着信息技术飞速发展和社会对高层次信息人才的迫切需求，根据教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范》和《高等学校计算机科学与技术专业核心课程教学实施方案》的建议，结合信息管理与信息系统专业的教学要求，本书第五版在保持原有写作风格的基础上，除了对文字做了进一步加工，纠正了某些疏漏以外，并对部分内容进行了调整，主要表现如下。

（1） 将代数结构部分的内容进行了整合，并调整到教材的最后。

（2） 图论部分(第5～7章)的叙述有较大的改动。

（3） 增添了一些内容，主要是与离散数学应用相关的内容，它们是组合电路(第1章),欧拉函数(第3章),着色问题(第5章),地图着色与四色定理、格雷码(第6章)等。

（4） 对部分习题做了补充和调整。

    在此次修订中，也对配套出版的《离散数学题解(第五版)》进行了同步更新和调整，PPT电子教案的修订版随后推出。各章修订都由原作者完成。

本书适合作为计算机应用和信息技术等相关专业的教学用书，教师可以根据不同教学要求进行适当调整，大约用54～72学时完成教学计划。此外，本书也可以作为从事信息系统开发的科技人员的参考书。

作者2013年2月第四版

 本书从1992年发行第一版，到2004年推出第三版并被评为北京高等教育精品教材以来，信息技术飞速发展，新成果层出不穷，一个崭新的信息时代正在到来。为了应对高层次信息人才需求的巨大挑战，近年来，教育部计算机科学与技术专业教学指导委员会组织有关专家对国内外计算机专业教育进行了深入调研，提出了《计算机科学与技术专业规范》(CCC2004—2005)。在这个规范中，计算机科学与技术专业被细化成计算机科学、计算机工程、软件工程、信息技术4个专业方向，并提出了相关专业方向的教学计划和课程设计。

    根据这个意见的指导思想，并结合信息管理与信息系统专业的教学要求，本书第四版在保持原有写作风格的基础上，除了对文字做了进一步加工，纠正了某些疏漏以外，并对部分内容进行了调整，主要表现如下。

（1） 在组合分析中补充了递推方程的求解及其在计算机递归算法分析中的应用。

    (2) 形式系统通常包含形式语言以及用形式语言表述的公理和推理规则。在形式系统中，符号串本身是没有语义的，只能通过解释赋予它们一定的语义，但在讨论系统的公理或推理规则时应该与语义无关。本书在以前几个版本关于一阶逻辑推理的叙述中没有采用公理化的方法。为了兼顾逻辑体系的严谨性及本书的定位与写作风格，决定删除这部分内容。

    (3) 面向计算机科学技术的新发展，补充了一些离散数学在相关领域的应用实例。

    在此次修订中，也对配套出版的《离散数学题解(第四版)》进行了相应的更新和调整，PPT电子教案的修订版随后推出。各章修订都由原作者完成。

本书适合作为计算机应用和信息技术等相关专业的教学用书，教师可以根据不同教学要求进行适当剪裁，用54～72学时完成教学计划。此外，本书也可以作为从事信息系统开发的科技人员的参考书。

作者2007年10月第三版

    本书已出版发行11个年头。当初是为了适应全国计算机软件专业技术资格和水平考试的需要而编写的。现在，全国计算机软件专业技术资格和水平考试的内容有了很大的变化，仅在系统分析员级中还有离散数学。但是，出乎我们意料的是，本书的发行量一直在逐年上升，被很多学校选作教材。为了更好地适应这种形势的需要，应清华大学出版社的要求，出版本书的第三版。

    第三版在内容上没有做大的改动。除订正第二版中的错误和修改了少量的表述外，主要是对每章的最后一节“题例分析”进行了修改和补充。原来“题例分析”中的例题全部是选择题(这是因为当初全国计算机软件专业技术资格和水平考试中的离散数学只有这种题型)，尽管每一题都加了“分析”，对相关知识和技巧做了尽可能全面的讲解，但由于这种题型的限制，还是很难充分发挥这一节的应有作用。第三版保留了部分选择题，根据内容的需要添加或改写了其他形式的例题，使得这一节更好地起到它应有的作用，即帮助读者理解和掌握本章的内容，强调学习中应注意的事项(如容易犯的错误)，进一步讲解做题的技巧等。

各部分的修改由原作者完成。

作者2003年9月第二版

计算机的出现和蓬勃发展彻底改变了人类的生活，它必将作为20世纪最灿烂辉煌的成就之一载入史册。从科学计算到大型的信息管理系统，从人工智能直至进入家庭，计算机已成为人们生活中密不可分的一个组成部分。当前，人类社会经过农业经济、工业经济，正在进入知识经济的时代。经济的增长将更多地依赖知识和信息的生产、扩散和应用，人类社会正在成为名副其实的信息化社会。这既为计算机科学技术的发展提供了前所未有的机遇和动力，也提出了更多的问题和更高的要求。解决这些问题的关键就是知识和技术的创新。因此，作为计算机科学技术的支撑学科之一的离散数学正变得日益重要。离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，通过离散数学的教学，不仅能为学生的专业课学习及将来从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养他们的抽象思维、严格的逻辑推理和创新能力。

    《离散数学》一书自从1992年2月由清华大学出版社作为“全国计算机软件专业技术资格和水平考试系列教材”出版以来，已历经7年。由于它取材适度、概念清楚、讲解翔实、通俗易读、既适合教学也便于自学的特点，也由于它“着重于基本概念的论述和应用，而不重于定理证明”的风格而受到读者的欢迎和好评。本书不仅被广大参加软件水平考试培训的人员使用，同时也被许多高校选作计算机或相关专业本科生的教材。

    作为第二版，本书保留了原书的体系、风格和6部分的基本内容，即①数理逻辑； ②集合论； ③代数结构； ④图论； ⑤组合分析初步； ⑥形式语言与自动机初步。同时,为了适应专科教育的要求，与第一版相比，除了对原书中的错误和疏漏之处进行订正以外，还在以下两方面进行了修订。

(1) 对原书的习题进行了调整和充实。个别章节更新了某些习题，而对大部分章节补充了难度适当、风格多样、覆盖面较广的习题。

    (2) 删除了原书中关于习题的提示或解答的内容。为了更好地帮助初学者，特别是自学者掌握离散数学的主要概念及解题方法与技巧，与本书配套出版了《离散数学题解》。在题解中按章给出内容提要、解题要求、习题和解答，并结合习题针对一些普遍性的分析方法、解题技巧、求解步骤和规范，以及应该避免的错误进行了详尽的论述。

    在以上的修订工作中，数理逻辑与图论(第1、2、7、8、9章)由耿素云完成；集合论、代数结构与组合分析初步(第3、4、5、6、10章)由屈婉玲完成；形式语言与自动机初步(第11章)由张立昂完成。

    本书既可以作为计算机及相关专业本科生的教材，也可以作为计算机软件专业技术资格和水平考试的参考教材，同时适合于从事计算机软硬件开发和应用的科学技术人员使用。根据多年的教学经验，作为本科生教材，本书可在120学时内讲授完毕。

最后，我们诚恳欢迎广大读者对本书批评和指正。

作者1999年2月离散数学(第六版)第二版第一版

    本书是根据“计算机专业技术资格和水平考试大纲”的要求编写的，是“全国计算机软件专业技术资格和水平考试系列教材”之一，它是高级程序员级和系统分析员级的离散数学教材。离散数学是现代数学的重要分支，是计算机科学理论的基础。本书共含6方面的内容： ①数理逻辑； ②集合论； ③代数结构； ④图论； ⑤组合分析初步； ⑥形式语言与自动机初步。

    数理逻辑与图论(第1、2、7、8、9章)由耿素云编写；集合论、代数结构、组合分析初步(第3、4、5、6、10章)由屈婉玲编写；形式语言与自动机初步(第11章)由张立昂编写。

根据全国计算机软件专业技术资格和水平考试的特点，本书着重于基本概念的论述和应用，而不着重于定理的证明。每章均给出了典型的题例分析，并配置了相当数量的习题，书后给出了大部分习题的提示或解答。本书不仅是函授的教材，便于考生复习与自学，而且也可供计算机软件人员学习与参考。

由于作者水平所限，书中难免有不妥或错误之处，恳请读者指正。

作者  1991年4月于北京大学

第1章命题逻辑1

1.1命题符号化及联结词1

1.2命题公式及分类5

1.3等值演算8

1.4范式12

1.5联结词全功能集17

1.6组合电路19

1.7推理理论21

1.8题例分析26

习题31

第2章一阶逻辑37

2.1一阶逻辑基本概念37

2.2一阶逻辑合式公式及解释42

2.3一阶逻辑等值式与前束范式46

2.4题例分析49

习题52

第3章集合的基本概念和运算56

3.1集合的基本概念56

3.2集合的基本运算58

3.3集合中元素的计数63

3.4题例分析67

习题71

第4章二元关系和函数77

4.1集合的笛卡儿积与二元关系77

4.2关系的运算81

4.3关系的性质86

4.4关系的闭包88

4.5等价关系和偏序关系90

4.6函数的定义和性质95

4.7函数的复合和反函数99

4.8题例分析107

习题113

第5章图的基本概念119

5.1无向图及有向图119

5.2通路、回路和图的连通性124

离散数学(第六版)5.3图的矩阵表示126

5.4最短路径、关键路径和着色129

5.5题例分析135

习题138

第6章特殊的图141

6.1二部图141

6.2欧拉图143

6.3哈密顿图145

6.4平面图147

6.5题例分析152

习题155

第7章树158

7.1无向树及生成树158

7.2根树及其应用162

7.3题例分析168

习题172

第8章组合分析初步175

8.1加法法则和乘法法则175

8.2基本排列组合的计数方法176

8.3递推方程的求解与应用182

8.4题例分析188

习题193

第9章代数系统简介197

9.1二元运算及其性质197

9.2代数系统203

9.3几个典型的代数系统207

9.4题例分析219

习题224

第10章形式语言和自动机初步231

10.1形式语言和形式文法231

10.1.1字符串和形式语言231

10.1.2形式文法232

10.1.3形式文法的分类235

10.1.4正则文法和上下文无关文法的应用236

10.1.5语法分析树238

10.2有穷自动机239

10.2.1基本概念240

10.2.2非确定型有穷自动机240

10.2.3带ε转移的非确定型有穷自动机243

10.3正则表达式246

10.4图灵机248

10.5题例分析252

习题254

取材适度、通俗易懂、概念清楚、讲解翔实，适合作为教材供学生使用。 着重讲解基本概念及其应用，而不在定理证明等方面花费过多的篇幅。 全书包括数理逻辑、集合论、图论、组合分析初步、代数结构、形式语言和自动机初步6部分，每部分基本上自成系统，可以根据需要取舍、组织教学。 每章最后一节是题例分析，帮助读者更好地理解和掌握本章的内容，了解学习中需注意的事项（如容易犯的错误），掌握做题的技巧。 习题丰富，难度适中，并且有配套的习题解答，见《离散数学题解（第六版）》，书号为9787302593201。

耿素云    北京大学信息科学学院教授 致力于离散数学教学20余年，出版教材和译著多部，其中包括多部国家级规划教材和北京高等教育精品教材。被评为北京市教书育人、服务育人先进工作者，北京市优秀教师，北京大学“我爱我师――最受学生爱戴的老师”；获北京市教育教学成果（高等教育）一等奖，北京大学教学成果一等奖等。 屈婉玲    北京大学信息科学学院教授，博士生导师 曾任中国人工智能学会离散数学专业委员会委员。 一直从事离散数学和算法的教学，主要研究方向是算法设计与分析。 出版教材和译著多部， 其中包括多部国家级规划教材和北京高等教育精品教材。 主持过多项国家级教材和课程建设项目，所讲授的离散数学课程被评为国家精品课程，两次被评为北京大学十佳教师。获北京市优秀教师称号，北京市教育教学成果（高等教育）一等奖，北京大学“我爱我师――最受学生爱戴的老师”称号和教学成果一等奖等。 张立昂    北京大学信息科学学院教授，博士生导师 一直从事数学和理论计算机科学的教学及研究工作，主要研究方向是计算复杂性理论和算法设计与分析，出版教材和译著多部，其中包括多部国家级规划教材和北京高等教育精品教材。获教育部科学技术进步二等奖，北京市教育教学成果（高等教育）一等奖，北京大学教学成果一等奖等。