本书是编者根据多年讲授“离散数学”课程的教学实践,为适应计算机科学与技术发展的需要,并参考国内外同类教材而编写,目的在于通过讲授离散数学中的基本概念、基本定理和运算及其在计算机科学与技术学科中的应用,培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力。 本书力求概念阐述严谨,证明推演详尽,较难理解的概念用实例说明。 全书分四篇共 24 章,主要包括集合论与数理逻辑、图论与组合数学、代数结构与初等数论、线性规划与博弈论等内容。
本书适合作为普通高等院校计算机类专业的教材,也可供从事离散结构领域研究工作的人员参考。


？

教材是学校教育教学中落实立德树人根本任务的关键要素和重要载体,它直接关系到党的教育方针的落实和教育目标的实现。 教材编写工作是高等教育体系的战略性、基础性工作,高质量的教育教学离不开高质量的教材建设。 党的二十大对新时代教材编写工作提出了新的要求。
本书涉及的离散数学是计算机科学与技术学科的基础,它以离散量为研究对象,充分描述了计算机科学与技术学科的离散性特点。
离散数学是随着计算机科学与技术学科的发展而逐步建立的,尽管它的主要内容在计算机出现之前就已散见于数学的各个分支中。 它形成于 20 世纪 70 年代初,因此,也有人称之为“计算机数学”,近期也称其为“离散结构”。
离散数学包括的内容主要有集合论、图论、数理逻辑、代数结构,并且其内容一直随着计算机科学与技术学科的发展而不断扩充和完善。 作为计算机专业的核心课程,它为后续课程提供了必要的数学基础。 这些后续课程主要有数据结构、编译原理、算法分析、计算机密码学、人工智能和可计算性理论,等等。
本书是在编者多年讲授离散数学课程的基础上编写而成的,其目的在于通过讲授离散数学中的基本概念、基本定理和运算及其在计算机科学与技术学科中的应用,培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力。 因此,本书力求概念阐释严谨,证明推演详尽,较难理解的概念用实例说明。
在本书第一、二版使用过程中,读者提出了许多宝贵的意见和建议,在此表示感谢。
为迎接新一轮人工智能浪潮和人工智能大模型普及和应用,本书第三版在结构和内容上对第二版进行了修改和补充,如增加了线性规划与博弈论部分。 全书共分四篇 24 章。
第 1 篇是集合论与数理逻辑,包含第 1 ~ 6 章,主要论述集合、关系、映射、可数集与不可数集、命题逻辑与一阶逻辑。 集合论是全书的基础知识和基本工具,命题逻辑与一阶逻辑则是数理逻辑中与计算机科学与技术学科关系较密切的基本内容。
第 2 篇是图论与组合数学,包含第 7 ~ 18 章,主要论述图与子图、树、图的连通性、E图与 H 图、匹配与点独立集、图的着色、平面图、有向图、网络最大流、排列和组合的一般计数方法、容斥原理、递推关系与生成函数等内容。 由于图为任何一个包含二元关系的系统提供了一种离散数学模型,因此,应用图论来解决计算机科学与技术学科相关领域中的问题具有极大的优越性。 此外,图论对于锻炼学生的抽象思维能力及提高运用数学工具描述并解决实际问题的能力也大有益处。 本篇论述了组合数学中关于存在性、计数、构造、分类及最优化等基本知识,目的在于论述组合分析这一强有力的数学工具。
第 3 篇是代数结构与初等数论,包含第 19 ~ 22 章,主要论述整数、群、环与域、格与布尔代数。
第 4 篇是线性规划与博弈论,它们是运筹学的重要分支,包含第 23、24 章。 前者主要论述在生产实践和日常生活中如何合理地利用有限的人力、物力、财力等资源得到最优的经济效益等一类规划问题的数学建模及常见的求解方法。 在人们的社会和经济生活中,博弈无处不在,职场中有博弈,商场上有博弈,人际交往中也有博弈。 博弈就是一种有策略、有规则的对抗游戏。 本篇所论述的博弈论知识,对读者会有较大的帮助,可以让读者的工作、生活更加有效率,从而更好地实现自己的目标。
本书适合作为普通高等院校计算机类专业的教材,书中加？的部分为选学内容,教师可以按授课对象的实际情况和专业教育的要求对本书内容进行取舍,决定讲授内容。
本书的编写得到了 2009 年度教育部、财政部“高等学校特色专业建设点”项目“计算机科学与技术”专业(项目编号:TS11622)、2019 年度“国家级一流本科专业建设点”项目“计算机科学与技术”专业、“十二五”普通高等教育国家级规划教材建设项目的资助,在此表示衷心的感谢。
本书由刘任任、王婷、曹春红主编,其中第1 篇和第3 篇由刘任任编写,第2 篇由王婷编写,第 4 篇由曹春红编写,全书由刘任任和王婷统稿。 由于编者的水平有限,难免存在错误和疏漏之处,恳请读者批评指正。
最后,我们引用计算机科学巨匠、图灵奖获得者 D. E. Kunth 的一段话来说明数学,特别是离散数学在计算机科学与技术中的重要地位:“除了无穷维 Hibert 空间不可能用得上以外,其他数学理论都可能在计算机科学与技术中得到应用。 概括地说,在计算机科学与技术的研究领域中,凡一问题要求形式化、精确化表示,最可能用到的数学理论是数理逻辑,某些部分可能用到代数,甚至拓扑学;凡一问题要求表示出算法执行过程中各部分的逻辑结构或关系,最可能用到的数学理论是图论和数理逻辑,某些部分可能用到代数;凡一问题要求给出量的测定,最可能用到的数学理论是组合数学、数论和概率论等;凡一问题要求得出最优方案,最可能用到的数学理论是运筹学、数论,甚至将来有可能用到数学分析。”
编 者
2023 年 11 月
？

第 1 篇 集合论与数理逻辑
第 1 章 集合  2
§ 1. 1 集合的概念及其表示  2
§ 1. 2 集合的基本运算  4
§ 1. 3 笛卡尔积  5
习 题  6
第 2 章 关系  8
§ 2. 1 关系及其表示  8
§ 2. 2 关系的运算  9
§ 2. 3 等价关系  12
§ 2. 4 序关系  14
习 题  16
第 3 章 映射  19
§ 3. 1 基本概念  19
§ 3. 2 映射的运算  20
习 题  21
第 4 章 可数集与不可数集  22
§ 4. 1 等势  22
§ 4. 2 集合的基数  23
§ 4. 3 可数集与不可数集简介  24
习 题  26
第 5 章 命题逻辑  27
§ 5. 1 命题与逻辑联结词  27
§ 5. 2 命题公式与等值演算  30
§ 5. 3 对偶与范式  33
§ 5. 4 推理理论  38
§ 5. 5 命题演算的公理系统  43
习 题  46
第 6 章 一阶逻辑  49Ⅰ
§ 6. 1 谓词与量词  49
§ 6. 2 合式公式及解释  52
§ 6. 3 等值式与范式  54
§ 6. 4 一阶逻辑的推理理论  58
习 题  62
第 2 篇 图论与组合数学
第 7 章 图与子图  66
§ 7. 1 图的概念  66
§ 7. 2 图的同构  68
§ 7. 3 顶点的度  69
§ 7. 4 子图及图的运算  69
§ 7. 5 通路与连通图  71
§ 7. 6 图的矩阵表示  73
§ 7. 7 应用(最短通路问题)  74
习 题  77
第 8 章 树  80
§ 8. 1 树的定义  80
§ 8. 2 生成树  82
§ 8. 3 应用(最优树问题)  84
习 题  85
第 9 章 图的连通性 86
§ 9. 1 点连通度和边连通度  88
？§ 9. 2 块 88
§ 9. 3 应用(构造可靠的通信网络)  90
习 题  91
第 10 章 E 图与 H 图  93
§ 10. 1 七桥问题与 E 图  93
§ 10. 2 周游世界问题与 H 图  94
§ 10. 3 应用(旅行推销员问题)  98
习 题  99
第 11 章 匹配与点独立集  101
§ 11. 1 匹配  101
§ 11. 2 独立集和覆盖  105
§ 11. 3 Ramsey 数  107
§ 11. 4 应用(人员分配问题)  110
习 题  111
第 12 章 图的着色  113
§ 12. 1 顶点着色  113
§ 12. 2 边着色  115
§ 12. 3 色多项式  118
§ 12. 4 应用  121
习 题  122
第 13 章 平面图  123
§ 13. 1 平面图的概念  123
§ 13. 2 欧拉公式  125
§ 13. 3 可平面性判定  127
§ 13. 4 平面图的面着色  128
§ 13. 5 应用(印制电路板的设计)  130
习 题  130
第 14 章 有向图  132
§ 14. 1 有向图的概念  132
§ 14. 2 有向通路与有向回路  134
§ 14. 3 有向树简介  136
§ 14. 4 应用  137
习 题  139
第 15 章 网络最大流 140
§ 15. 1 网络的流与割  140
§ 15. 2 最大流最小割定理  142
§ 15. 3 应用(中国邮递员问题)  146
习 题  146
第 16 章 排列和组合的一般计数方法  148
§ 16. 1 两个基本的计数法则  148
§ 16. 2 基本排列组合的计数方法  149
§ 16. 3 可重复排列组合的计数方法  150
习 题  152
第 17 章 容斥原理  154
§ 17. 1 容斥原理概述  154
§ 17. 2 有禁止位的排列  156
习 题  158
第 18 章 递推关系与生成函数  159
§ 18. 1 递推关系及其解法  159
§ 18. 2 生成函数  161
习 题  163
第 3 篇 代数结构与初等数论
第 19 章 整数  166
§ 19. 1 整除性  166
§ 19. 2 素因数分解  170
§ 19. 3 同余  172
§ 19. 4 孙子定理与 Euler 函数  174
§ 19. 5 数论在计算机密码学中的应用  178
习 题  180
第 20 章 群  182
§ 20. 1 群的概念  182
§ 20. 2 子群  185
？§ 20. 3 置换群  189
§ 20. 4 陪集与 Lagrange 定理  194
§ 20. 5 同态与同构  196
§ 20. 6 群在计算机科学与技术中的应用  200
习 题  203
第 21 章 环与域  205
§ 21. 1 环与子环  205
§ 21. 2 环同态  208
§ 21. 3 域的特征和素域  212
？§ 21. 4 有限域  214
§ 21. 5 有限域的结构  218
§ 21. 6 纠错码  223
§ 21. 7 多项式编码方法及其实现  231
习 题  234
第 22 章 格与布尔代数  237
§ 22. 1 格的定义  237
§ 22. 2 格的性质  239
§ 22. 3 几种特殊的格  242
§ 22. 4 布尔代数  246
§ 22. 5 有限布尔代数的结构  252
§ 22. 6 格与布尔代数在计算机科学与技术中的应用  256
习 题  260
第 4 篇 线性规划与博弈论
第 23 章 线性规划  264
§ 23. 1 线性规划问题及其数学模型  264
§ 23. 2 图解法  267
§ 23. 3 单纯形法原理  269
§ 23. 4 单纯形法计算步骤  274
§ 23. 5 线性规划的对偶问题  278
习 题  279
第 24 章 博弈论  281
§ 24. 1 博弈问题  281
§ 24. 2 矩阵博弈的基本理论  283
§ 24. 3 矩阵博弈的解法  289
§ 24. 4 矩阵博弈均衡  293
习 题  296
参考文献 297

刘任任，博士，教授，任职于湘潭大学计算机学院，专业方向为多值逻辑理论、计算机算法，主讲课程有离散数学、编译原理、数据结构、计算机算法设计与分析、计算机科学中的逻辑学、可计算性理论。IEEE计算机学会多值逻辑技术委员会委员，公开出版学术专著1部，发表学术论文90余篇，湖南省优秀教学成果二等奖1项、三等奖2项，出版教材4本，其中所主编的《离散数学》被选为国家级“十二五”规划教材。

王婷，硕士，副教授，任职于湘潭大学计算机学院，专业方向为计算机算法，主讲课程有离散数学、集合论与数理逻辑、图论与组合数学等，主持湖南省教育厅科技项目1项，参与国家自然科学基金项目1项，发表学术论文10多篇，教改论文5篇，获湖南省优秀教学成果奖一等奖1项（排名第3）。

曹春红，博士，副教授，曾赴美国乔治亚大学从事访问研究，任职于湘潭大学计算机学院，专业方向为智能计算，主讲课程有离散数学、数据结构 、运筹学、集合论与数理逻辑、代数结构与初等数论等，在中国科学等国内外重要期刊和学术会议上发表论文20多篇，主持完成国家自然科学基金1项，参与2项。

？

①被评为“十二五”普通高等教育本科国家级规划教材。
②内容难易适中、层次分明，融知识传授和能力培养为一体，且案例题型多样，配有丰富的教学资源。
③对培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力有帮助。
④有助于提高学生解决复杂工程问题的数学建模能力和计算思维能力。
？