离散数学及其应用

离散数学是研究离散结构数学模型的数学分支的统称，是计算机类专业的必修课程，也是计算机科学与技术、软件工程等专业的核心基础课程。
“离散”和“连续”之间是对立与统一的关系。在数学发展史的初期阶段，因为人们对数的认识局限于整数，所以研究的问题主要是离散问题。由于描述离散数据的模型在处理某些事物时的局限性，再加上后来数域扩展到了实数，从而近代数学主要研究连续数量关系及其模型，并取得了极其辉煌的成果，如微积分等，乃至现在这一情况仍然在继续着。
然而，自从1946年数字电子计算机诞生以来，情况就逐步发生了变化。因为计算机的快速发展和普遍应用，出现了大量的离散结构问题，亟须给出它们的模型，描述清楚它们的关系。出现这种情况的原因在于，现代的数字电子计算机不识别连续量，只识别0、1代码，用计算机处理问题时，终都要翻译成这样的符号。这里涉及两个问题，一个是这些连续的量如何离散化，并且离散化的量还能反映原来事物的特性。另一个是如何为离散量建立模型，方便使用计算机处理，以及这些离散量之间的关系如何描述。这些问题大大促进了离散数学理论的发展，人们由此重新开始重视离散数学理论，也重新认识离散数量关系的研究意义，重新重视讨论离散数量关系的数学分支，并取得新的进展。
一方面，人们借助早期的一些离散数学的理论和方法来描述计算机系统中的一些问题，常用的理论包括集合理论、图论、数理逻辑、代数系统、递归理论和组合理论等。例如，人们利用布尔代数理论研究开关电路，建立了一套完整的数理逻辑理论，对计算机逻辑设计起了很大作用。另一方面，人们也借助其他学科的一些研究成果来解决计算机系统中遇到的问题。例如，计算机的编译系统，它的理论基础就来源于心理学领域中用形式化方法研究语言学的成果，这一成果由乔姆斯基给出。
对于连续量的离散化，为显著的成果就是图像数字化、语音数字化等，正是对模拟量的离散化才使得图像和语音的数字化成为可能，并取得了很大发展，得到了广泛应用。
全书共分为8章，第1章是绪论，总体上介绍了离散数学在信息技术，特别是计算技术中的作用，以及连续量的离散化方法。第2章介绍了集合理论及其应用。主要介绍了集合和关系的表示方法，以及它们的交、并、补、差等运算；还介绍了等价关系和序关系，以及由等价关系导出的等价类和集合的划分问题；作为应用，讲述了关系模型在数据库中的应用，也就是关系数据库理论中的关系代数，以及等价关系和等价类在机器学习中的应用，也就是粗糙集理论；作为实践内容，要求实现集合的交、并、差运算。第3章介绍了数理逻辑的基本知识及其应用。包含命题逻辑和谓词逻辑；作为应用，讨论了数理逻辑在人工智能自动推理和程序设计中的应用；作为实践内容，要求编程实现SAT的算法。第4章介绍了图的基本知识及其应用。包含图的定义、表示方法，以及一些特殊的图，如欧拉图、哈密顿图、树和可平面化图等；还包含图论在计算机科学中的应用，有印刷电路板的平面化问题、前缀代码问题和文件压缩问题；作为实践的内容，要求编程实现文件压缩。第5章讲述了代数系统的知识及其应用。包含群、环、域、格、布尔代数；还讲述了代数系统成果的应用，包括代数语义，以及多项式环在密码学中的应用。第6章介绍了形式语言及其应用。包括形式文法与自动机理论，以及它们在编译系统中的应用。作为实践的内容，要求实现一个词法分析器。第7章是递归理论及其应用。内容包括递归关系和递归理论，以及递归式的求解方法、把递归转化为迭代的方法；作为实践的内容，要求实现递归算法到迭代算法的转化。第8章是组合理论初步。内容包括排列组合、鸽巢原理、二项式系数、排列组合生成算法和组合设计。本书第1章、第5章、第6章和第7章由栾尚敏撰写；第2章由谭立云撰写；第3章、第4章和第8章由文小艳撰写。全书由栾尚敏统稿处理，并进行了修正和校对。
本书具有如下特点：
(1)注重了基础性。本书详细介绍了每个主题涉及的基础理论知识，为进一步地应用打好基础。
(2)注重了理论和实践的结合。对每个主题，既注重了理论知识的介绍，也讲述了其应用案例。让读者既能学习到理论知识，也能了解其应用场景，还能掌握编程实现的技巧。
(3)注重了时效性。本书介绍的一些应用案例都是比较新的研究成果，有的是近些年才兴起的研究领域，如多项式环在密码学中的应用等。
本书可作为信息领域相关专业本科生的教材，特别是计算机类相关专业“离散数学”“离散结构及应用”等课程的教材，也可作为想了解离散数学理论、应用情况的人员的参考书。
本书受到国家重点研发计划(批准号：2018YFC0808306)、青海省重点实验室重点研发项目(批准号：2017-ZJ-Y21和2017-ZJ-752)、河北省物联网监控中心和河北省重点项目 (批准号：3142016020和19270318D)、河北省重点研发计划项目(批准号：18210339)、河北省高等学校科学技术项目(批准号：Z2019044)和中央高校基本业务费(批准号：HKJYZD201808、HKJYZD201526和HKJYGH201817)的资助。作者对以上项目的支持深表感谢。还要感谢编辑谭文芳老师，她不仅在格式、文字和图表符号方面给予了很多指导，还在书稿内容方面提出了很好的建议，也正是她的努力才使本书得以顺利出版。
限于作者水平，书中难免会有一些错误和不足，希望读者指正，联系方式623320726@qqcom。

离散数学在信息技术领域有着广泛的应用，是计算机类相关专业的基础知识，也是计算机类及其他信息类相关专业的一门重要基础课程。离散数学研究的对象是离散数量关系和离散结构的数学模型，包含集合理论、数理逻辑、图论、代数系统和计算理论。这些概念、理论以及方法广泛地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络、密码学等专业课程中。该课程所提供的训练有助于提高学生概括抽象能力、逻辑思维能力、归纳构造能力，有益于学生严谨、完整、规范的科学态度的培养，实践环节的内容对提高学生的编程技能也有很大帮助。
本书可作为信息技术领域相关专业本科生“离散数学”及相关课程的教材，也可作为想了解离散数学及其应用人员的参考书。

栾尚敏，男，1968年出生，教授，博士毕业于北京航空航天大学，博士后出站于中国科学院软件研究所，曾经在山东大学、北京理工大学、中国科学院软件研究所工作，目前就职于华北科技学院。主要从事计算机软件与理论、人工智能的研究工作，发表论文50余篇，这些论文发表在《Logic Journal of IGPL》《Science in China:Series F》《Journal of Computer Science and Technology》《中国科学：信息科学》《中国科学：技术科学》《计算机学报》《软件学报》《计算机研究与发展》等刊物，SCI收入12篇，EI收入9篇。

第1章绪论
1.1离散数学的研究对象
1.2连续量的数字化
1.2.1图像的数字化
1.2.2语音的数字化
1.3离散数学在信息技术中的应用
1.3.1离散数学与关系数据库
1.3.2形式语言与编译系统
1.3.3数理逻辑与程序设计语言
1.3.4代数系统与密码学
1.3.5代数系统与程序语义
1.3.6印刷电路板布线问题
1.4本课程的特点和学习方法
1.5本章小结
1.6习题
第2章集合理论
2.1集合理论的发展历史
2.2集合的定义和运算
2.2.1集合的基本概念
2.2.2集合上的基本运算
2.3关系及其性质
2.3.1序对和笛卡儿积
2.3.2二元关系
2.3.3关系的运算
2.3.4关系的性质
2.3.5关系的闭包运算
2.4等价关系与集合的划分
2.4.1等价关系与等价类
2.4.2集合的划分
2.5序关系
2.5.1偏序关系的定义
2.5.2偏序集的哈斯图
2.6函数
2.6.1函数的定义
2.6.2逆函数与复合函数
2.7集合理论在计算机科学中的应用
2.7.1集合理论在关系数据库理论中的应用：关系代数
2.7.2集合理论在机器学习中的应用：粗糙集理论
2.8实践内容：集合上的运算
2.8.1编程实现集合的交、并和差运算
2.8.2二元关系性质的验证
2.9本章小结
2.10习题
第3章数理逻辑
3.1数理逻辑的发展历史
3.2命题逻辑
3.2.1命题演算的基本概念
3.2.2命题逻辑的合式公式及范式
3.2.3命题逻辑的推理理论
3.3谓词逻辑
3.3.1谓词逻辑的基本概念
3.3.2谓词逻辑的合式公式
3.3.3谓词形式系统的语义
3.3.4谓词演算的等值式
3.3.5前束范式
3.4数理逻辑在人工智能中的应用
3.4.1定理自动证明
3.4.2逻辑式程序设计语言Prolog运行机理
3.5实践内容：命题公式可满足性验证
3.5.1SAT基础知识
3.5.2SAT的求解算法
3.5.3变量和子句的存储方法
3.6本章小结
3.7习题
第4章图论及其应用
4.1图论的发展历史
4.2图的基本概念
4.2.1无向图及有向图
4.2.2相邻和度
4.2.3子图
4.2.4通路与连通性
4.3图的矩阵表示
4.3.1关联矩阵
4.3.2邻接矩阵
4.3.3可达矩阵
4.4欧拉图与哈密顿图
4.4.1欧拉图
4.4.2哈密顿图
4.5平面图与平面化算法
4.5.1平面图
4.5.2平面化算法
4.6带权图与生成树
4.6.1带权图
4.6.2树与生成树
4.7根树及二叉树
4.7.1根树
4.7.2二叉树
4.7.3前缀编码
4.8实践内容：用前缀编码压缩文件
4.9本章小结
4.10习题
第5章代数系统
5.1代数学的发展历史
5.2代数系统的基本概念、运算与性质
5.2.1二元运算
5.2.2代数系统的基本概念及性质
5.3半群、群与子群
5.3.1半群与含幺半群
5.3.2群与子群
5.3.3阿贝尔群
5.3.4循环群
5.3.5置换群
5.4同态、同构
5.4.1同态与同构的概念及性质
5.4.2同余
5.5环、域、格和布尔代数
5.5.1环
5.5.2域
5.5.3格
5.5.4布尔代数
5.5.5一元多项式环
5.6数据类型的代数规格说明
5.6.1代数系统的规格说明
5.6.2数据类型的代数规格说明
5.6.3SPEC-代数
5.7代数系统与密码学
5.7.1AES方法的总体结构
5.7.2数学基础
5.7.3AES的基本变换
5.7.4圈密钥生成
5.7.5AES的加密算法
5.7.6AES的基本逆变换
5.8实践内容：代数系统的实现
5.8.1面向对象的程序设计与代数系统
5.8.2代数系统的面向对象实现
5.9本章小结
5.10习题
第6章形式语言与自动机理论
6.1形式语言发展的历史
6.2形式语言理论
6.2.1语言的表示
6.2.2文法：语言的有限描述
6.2.3文法的乔姆斯基体系
6.2.4正规表达式
6.3自动机理论
6.3.1有限自动机
6.3.2下推自动机
6.3.3图灵机
6.3.4通用图灵机
6.4实践内容：词法分析器的设计
6.4.1目标语言的定义
6.4.2程序实现
6.5本章小结
6.6习题
第7章递归理论及其应用
7.1递归与计算
7.1.1递归、归纳和迭代
7.1.2可计算的含义
7.1.3递归理论的发展历史
7.2递归函数理论
7.2.1构造函数的方法
7.2.2递归函数
7.3递归与程序设计
7.4递归式求解
7.4.1递归关系的建立
7.4.2常系数齐次线性递归方程
7.4.3常系数非齐次线性递归方程
7.4.4迭代法
7.4.5归纳法
7.4.6母函数法
7.5实践内容：用堆栈模拟递归
7.5.1斐波那契数列问题的递归和迭代的比较
7.5.2用堆栈模拟递归
7.6本章小结
7.7习题
第8章组合理论初步
8.1组合理论简介
8.2排列、组合与二项式定理
8.2.1基本计数原理
8.2.2排列与组合
8.2.3多重集的排列组合
8.2.4二项式定理
8.3排列组合生成算法
8.3.1生成排列
8.3.2生成组合
8.4鸽巢原理
8.4.1抽屉原理
8.4.2鸽巢原理的加强形式
8.4.3Ramsey数及其在信息技术中的应用
8.5组合设计
8.5.1区组设计
8.5.2拉丁方设计
8.6本章小结
8.7习题
参考文献

离散数学在信息技术领域有着广泛的应用，是计算机类相关专业的基础知识，也是计算机类及其他信息类相关专业的一门重要基础课程。离散数学研究的对象是离散数量关系和离散结构的数学模型，包含集合理论、数理逻辑、图论、代数系统和计算理论。这些概念、理论以及方法广泛地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络、密码学等专业课程中。该课程所提供的训练有助于提高学生概括抽象能力、逻辑思维能力、归纳构造能力，有益于学生严谨、完整、规范的科学态度的培养，实践环节的内容对提高学生的编程技能也有很大帮助。
本书可作为信息技术领域相关专业本科生“离散数学”及相关课程的教材，也可作为想了解离散数学及其应用人员的参考书。