本书是“十二五”普通高等教育本科国家级规划教材。本书是编者根据多年讲授离散数学课程的教学实践，并参考国内外同类教材编写而成的。为适应计算机科学发展的需要，本书增加了新的内容，其目的在于通过讲授离散数学中的基本概念、基本定理和运算及其在计算机科学与技术学科中的应用，培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力。本书力求概念阐述严谨，证明推演详尽，较难理解的概念用实例说明。全书分四篇共24章，内容包括：集合论与数理逻辑、图论与组合数学、代数结构与初等数论、形式语言与自动机理论基础。本书有配套教材《离散数学题解与分析（第二版）》（刘任任主编，中国铁道出版社出版，2015年）。
本书适合作为高等院校计算机及相关专业的教材，也可供从事离散结构领域研究工作的人员参考。

离散数学是计算机科学与技术学科的基础，它以离散量为研究对象，充分描述了计算机科学与技术学科的离散性特点.
离散数学是随着计算机科学与技术学科的发展而逐步建立的，尽管它的主要内容在计算机出现之前就已散见于数学的各个分支中.它形成于20世纪70年代初，因此，国外也有人称之为“计算机数学”，近期也其称为“离散结构”.
离散数学包括的内容主要有集合论、图论、数理逻辑、代数结构，并且其内容一直随着计算机科学与技术学科的发展而不断地扩充和完善. 作为计算机专业的核心课程，它为后续课程提供了必要的数学基础. 这些后续课程主要有: 数据结构、编译原理、算法分析、计算机密码学、人工智能和可计算性理论等等.
本书是在作者多年讲授离散数学课程的基础上编写而成的，其目的在于通过讲授离散数学中的基本概念、基本定理和运算及其在计算机科学与技术学科中的应用，培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力. 因此，本书力求概念阐述严谨，证明推演详尽，较难理解的概念用实例说明.
本书（第二版）在结构和内容上对第一版进行了修改和补充，增加了形式语言与自动机理论基础部分。全书共分四篇: 第一篇是集合论与数理逻辑. 主要介绍集合、关系、映射以及可数集与不可数集、命题逻辑与一阶逻辑。集合论是全书的基础知识和基本工具，命题逻辑与一阶逻辑则是数理逻辑中与计算机科学与技术学科关系较密切的基本内容. 第二篇是图论与组合数学. 主要介绍图与子图、树、平面图、匹配、图的着色、有向图、网络最大流等内容. 由于图为任何一个包含二元关系的系统提供了一种离散数学模型，因此，应用图论来解决计算机科学与技术学科相关领域中的问题已显示出极大的优越性. 此外，图论对于锻炼学生的抽象思维能力，提高运用数学工具描述并解决实际问题的能力也大有益处. 本篇还介绍了组合数学中关于存在性、计数、构造、分类，以及最优化等基本知识，目的在于向读者介绍组合分析这一强有力的数学工具.第三篇是代数结构与初等数论。主要内容有群、环、域、格与布尔代数、初等数论中关于整数的一些基本知识，以及代数结构在密码学中的应用. 第四篇是形式语言与自动机理论基础，主要介绍计算模型基础理论中形式语言与自动机理论的一些基本知识.
本书主要用作计算机科学与技术的专业基础课教材，也可以作为计算机相关专业的基础知识教材.教师可以按授课对象的实际情况和专业教育的要求对本书的内容进行取舍，决定讲授内容.
本书的编写得到了教育部第一类特色建设专业（计算机科学与技术）项目、“十二五”普通高等教育国家级规划教材建设项目的资助. 同时，中国计算机学会计算机教育委员会副主任蒋宗礼教授对本书提出了很多宝贵的意见和建议，在此表示衷心的感谢.
本书的第一篇和第三篇由刘任任编写，第二篇由王婷编写，第四篇由周经野编写，全书由刘任任和王婷统稿. 张陵山、肖芬、曹春红、邹娟、谢慧萍等老师对教材的编写提出了许多宝贵的意见和建议，在此一并表示感谢。由于编者的水平有限，难免存在错误和疏漏之处，恳请读者批评指正.
最后，我们引用计算机科学巨匠、图灵奖获得者D.E.Kunth的一段话来说明数学，特别是离散数学在计算机科学中的重要地位.
“除了无穷维Hibert空间不可能用得上以外，其它数学理论都可能在计算机科学中得到应用.概括地说:在计算机科学的研究领域中，凡一问题要求形式化、精确化表示，最可能用到的数学理论是数理逻辑，某些部分可能用到代数，甚至拓扑学；凡一问题要求表示出算法执行过程中各部分的逻辑结构或关系，最可能用到的数学理论是图论和数理逻辑，某些分可能用到代数；凡一问题要求给出量的测定，最可能用到的数学理论是组合数学、数论和概率论等；凡一问题要求得出最优方案，最可能用到的数学理论是运筹学、数论，甚至将来有可能用到数学分析.”

第一篇集合论与数理逻辑
第1章集合3
§1.1集合的概念及其表示3
§1.2集合的基本运算5
§1.3笛卡儿积6习题7
第2章关系9
§2.1关系及其表示9
§2.2关系的运算10
§2.3等价关系13
§2.4序关系15习题17
第3章映射19
§3.1基本概念19
§3.2映射的运算20习题21
第4章可数集与不可数集22
§4.1等势22
§4.2集合的基数23
§4.3可数集与不可数集的概念24习题25
第5章命题逻辑27
§5.1命题与逻辑联结词27
§5.2命题公式与等值演算29
§5.3对偶与范式33
§5.4推理理论38
§5.5命题演算的公理系统42习题45
第6章一阶逻辑48
§6.1谓词与量词48
§6.2合式公式及解释51
§6.3等值式与范式53
§6.4一阶逻辑的推理理论56习题60
第二篇图论与组合数学
第7章图与子图65
§7.1图的概念65
§7.2图的同构67
§7.3顶点的度68
§7.4子图及图的运算69
§7.5通路与连通图70
§7.6图的矩阵表示72
§7.7应用(最短通路问题)73习题77
第8章树80
§8.1树的定义80
§8.2生成树82
§8.3应用 (最优树问题)84习题86
第9章图的连通性87
§9.1点连通度和边连通度87
§9.2块89
§9.3应用 (构造可靠的通信网络)91习题92
第10章E图与H图94
§10.1七桥问题与E图94
§10.2周游世界问题与H图95
§10.3应用 (旅行推销员问题)99习题100
第11章匹配与点独立集102
§11.1匹配102
§11.2独立集和覆盖106
§11.3Ramsey数108
§11.4应用 (人员分配问题)112习题113
第12章图的着色115
§12.1顶点着色115
§12.2边着色118
§12.3色多项式120
§12.4应用123习题124
第13章平面图125
§13.1平面图的概念125
§13.2欧拉公式127
§13.3可平面性判定129
§13.4平面图的面着色129
§13.5应用（印制电路板的设计）131习题131
第14章有向图133
§14.1有向图的概念133
§14.2有向通路与有向回路135
§14.3有向树137
§14.4应用139习题140
第15章网络最大流142
§15.1网络的流与割142
§15.2最大流最小割定理144
§15.3应用（中国邮递员问题）147习题147
第16章排列和组合的一般计数方法149
§16.1两个基本的计数法则149
§16.2基本排列组合的计数方法149
§16.3可重复排列组合的计数方法151习题153
第17章容斥原理154
§17.1容斥原理概述154
§17.2有禁止位的排列155习题158
第18章递推关系与生成函数159
§18.1递推关系及其解法159
§18.2生成函数161习题163
第三篇代数结构与初等数论
第19章整数167
§19.1整除性167
§19.2素因数分解171
§19.3同余173
§19.4孙子定理?Euler函数175
§19.5数论在计算机密码学中的应用179习题181
第20章群183
§20.1群的概念183
§20.2子群186
*§20.3置换群189
§20.4陪集与Lagrange定理194
§20.5同态与同构197
§20.6群在计算机科学与技术中的应用201习题203
第21章环与域206
§21.1环与子环206
§21.2环同态209
§21.3域的特征?质域212
*§21.4有限域214
§21.5有限域的结构218
§21.6纠错码222
§21.7多项式编码方法及其实现230习题233
第22章格与布尔代数235
§22.1格的定义235
§22.2格的性质237
§22.3几种特殊的格240
§22.4布尔代数243
§22.5有限布尔代数的结构249
§22.6格与布尔代数在计算机科学与技术中的应用253习题257
第四篇形式语言与自动机理论基础
第23章形式语言263
§23.1符号、符号串及其运算263
§23.2文法与语言的形式定义265
§23.3正规表达式272
§23.4正规文法与正规式276习题279
第24章有限自动机理论280
§24.1有限自动机的定义与构造280
§24.2确定的有限自动机（DFA）282
§24.3不确定的有限自动机（NFA）283
§24.4NFA的确定化285
§24.5DFA的最小化288
§24.6正规集与有限自动机的等价性290习题292
参考文献294

刘任任，男，汉族，中共党员，博士，教授，博士生导师。 现任湘潭大学信息工程学院院长、中国计算机学会理事、中国人民解放军总参谋部三部八局兼职研究员、中国计算机学会多值逻辑与模糊逻辑专业委员会委员、理论计算机科学专业委员会委员、教育部高等学校计算机科学与技术专业教学指导分委员会专家工作组成员，全国高等学校计算机教育研究会常务理事，湖南省高教学会计算机教育专业委员会副理事长, 湖南省软件行业协会常务理事、专家委员会成员，《计算技术与自动化》杂志编委。