简单百科
离散数学

离散数学

离散数学（Discrete 数学）是数学中几个分支的总称，以离散空间的数学结构为研究对象。同时，它也是计算机科学中以系统结构和客体之间关系为研究对象的一门新兴学科。

离散数学的发展起步较晚，但与它有关的各个分支很早就已经诞生。数论是一个古老的数学分支，首创于古希腊时代，欧几里得（Euclid）在其著作《几何原本》中对数论进行了研究。数理逻辑虽起源于古代的斯多葛学派，但是到了近代才得到广泛的研究，1847年和1854年，英国数学家布尔（G.Boole）为了研究逻辑学、数理逻辑的思维规律，提出了布尔代数这一数学模型。20世纪60年代，离散数学一词正式出现。1975年，特伦布莱（Tremblay）等人出版《离散数学结构及其对于计算机科学的应用》一书，阐述了离散数学的基本理论，将它与计算机科学中的数据结构与算法紧密地联系在一起。离散数学的发展帮助解决了图论、组合数学的许多困难猜想。四色定理于1852年提出，一个多世纪之后，阿佩尔（Kenneth Appel）和哈肯（Wolfgang Haken）大量使用了计算机辅助才将其成功证明。后来，离散数学的成就逐渐被认可，1981年，数学计划学会和美国数学学会创立了富尔克森奖，旨在奖励离散数学领域内的杰出论文。

离散数学的基本内容包括数理逻辑、集合论、代数系统、组合分析、图论、数论、信息论、理论计算机科学、连续数学中的离散版本。离散数学的研究离不开各种各样的方法，如有限元法。此外，离散数学的理论与成果在现实世界中应用广泛，如工程学中，通过引入图论模型，把诊断知识中的循环依赖检测问题抽象为有向图中的环搜索问题，采用一些算法可以对航天器下行遥测参数的正确性进行诊断，保障飞行任务的正常开展。

学科简介

离散数学是一个现代数学分支，也是计算机科学中以系统结构和客体之间关系为研究对象的一门新兴学科。

离散数学是数学中几个分支的总称，其研究对象是基于离散空间的数学结构。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括整数集）的数学分支。与传统数学学科不同的是，离散数学根据计算机科学的特点主要研究离散对象，它以离散量的结构和相互关系以及计数构形等作为主要的研究目标。

历史

早期研究

离散数学的发展起步较晚，但与它有关的各个分支很早就已经诞生。早在公元前2200年，组合数学的萌芽便已经在神龟背上的3阶幻方的数字游戏中体现出来。数论也是一个古老的数学分支，首创于古希腊时代，数学家欧几里得（Euclid）在其著作《几何原本》的第8、9、10篇对数论进行了研究。古代中国的《孙子算经》中记载的“物不知其数”问题是最早出现求解同余式组的问题，解法中包含的定理被称为“中国剩余定理”。17世纪，法国数学家皮耶·德·费玛（fermat）对该学科做出了巨大的贡献。

图论是一个年轻的分支，1736年，数学家莱昂哈德·欧拉（Euler）解决了当时著名的难题——哥尼斯堡七桥问题，标志着图论的诞生。数理逻辑虽起源于古代的斯多葛学派，但是到了近代才得到承认和广泛的研究。1847年和1854年，英国数学家布尔（G.Boole）为了研究逻辑学、数理逻辑的思维规律，提出了布尔代数这一数学模型。19世纪末，德国数学家格奥尔格·康托尔（G.Cantor）提出了无限集的势、序型等概念，同时对任意元素的集合进行了系统研究，为集合论的发展奠定了基础，20世纪初，恩斯特·策梅洛（Zermelo）给出了第一个公理集合论系统，促进了学科的快速发展。

后续发展

到了20世纪，其他领域的复杂问题推动了离散数学的发展与研究。第二次世界大战期间，破解密码的需要带动了密码学和计算机科学的发展，英国的布莱切利园发明了第一部数字电子计算器——巨像计算机。20世纪中叶，电讯工业的出现亦促进了离散数学，特别是图论和信息论的发展。60年代，离散数学一词正式出现。1973年，斯通（Stone）、泼里帕拉特（Puliparat）等人分别发表了以离散数学命名的书籍——《离散数学结构及其应用》和《离散结构导论》。1975年，特伦布莱（Tremblay）等人出版《离散数学结构及其对于计算机科学的应用》一书，阐述了离散数学的基本理论，将它与计算机科学中的数据结构与算法紧密地联系在一起。

离散数学的发展帮助解决了图论、组合数学的许多困难猜想。图论中的四色定理于1852年提出，一个多世纪之后，阿佩尔（Kenneth Appel）和哈肯（Wolfgang Haken）大量使用了计算机辅助成功地将其证明。后来，离散数学的成就也逐渐被认可与肯定，1981年，数学计划学会和美国数学学会创立了富尔克森奖，旨在奖励离散数学领域内的杰出论文。1990年，中国中科院应用数学所研究员堵丁柱与美籍华人黄光明合作，证明了有关网络路线最短的一个猜想（Pollak-Gibert猜想），这项工作被列为1989-1990年度美国离散数学界与理论计算机科学界的两项重大成果之一。

基本内容

数理逻辑

数理逻辑又称符号逻辑、理论逻辑，是研究数学概念与推理、数学证明与计算的逻辑问题的一个数学分支。其由命题逻辑和谓词逻辑组成，其他主要分支有算法理论、逆归论、证明论、模型论和集合论等。数理逻辑以推理中前提和结论之间的形式关系为研究对象，可以利用特定符号，使复杂的逻辑关系用公式表示出来，在计算机科学与其他许多科学的研究中具有重要意义。

逻辑公式：逻辑公式是用逻辑变量和与、或、非三种基本运算符号连接起来的式子，在逻辑代数中，各种逻辑变量间的逻辑关系可以用逻辑公式表示。在二值逻辑中，逻辑变量的取值不是就是，用来表示两种状态。模糊逻辑的算法和运算性质与二值逻辑有很多相似之处，但模糊逻辑公式的真值，可以是区间中的任何值，它表示了这个模糊命题“真”的程度。

集合论

集合论是现代数学的基础。它作为数学语言的基础几乎涉及到一切数学分支，包括离散数学。集合论由德国数学家康托尔（Cantor）在1874年创立，他所做的工作被称为朴素集合论，但是其定义集合的方法上缺乏限制，会导致悖论。后来，经过许多数学家的努力，公理集合论在20世纪逐渐发展起来。该理论也是数理逻辑的分支之一。

集合：集合是不能用其他的概念加以精确定义的一个基本概念，一般来说，把一些明确的、各不相同的事物汇合成一个整体，这就是集合，如。集合可以分为可数集与不可数集，称与自然数集等势的集合为可数（列）无限集，有限集和无限集统称为可数集；反之，不是可数集的集合称为不可数集。

代数系统

代数系统是在集合上通过代数运算构造数学模型的方法，又因为它是一种抽象的方法，也称抽象代数。

定义：一个非空集合连同若干个定义在该集合上的运算所组成的系统就称为一个代数系统，记作。

举例：布尔代数具有如下两种定义：

（1）设是一偏序集，若的每一对元素均有上确界与下确界，则称为格，而具有与的有补分配格称为布尔代数。

（2）设为代数系统，和是二元运算，是一元运算，如果对于中的任何元素满足交换律、分配律、同一律和互补律，则该代数系统为布尔代数。

对布尔代数中的任何元素，有以下性质：

组合分析

组合分析又称组合学、组合数学或组合论，是研究按照若干给定的规则安排一些物件时有关问题的一门学科。该学科的研究对象为进行排列或组合的途径，包含组合设计、计数组合、计数、组合几何、组合拓扑等内容。研究的问题主要有：符合要求的安排是否存在，当存在时，其构造方法如何；符合要求的安排的个数怎样计算；当有比较优劣的标准时，与最优（或次优）的安排有关的一些问题。组合分析遵从三个基本原则，分别为：卡氐积的计数、乘法原理以及加法原理。

图论

图论是近代应用数学分支，它以图为对象，研究事物之间的联系。在图论中，图是指某类具体离散事物集合和该集合中的每对事物间以某种方式相联系的数学模型，用图表示事物间的联系时，用节点表示事物，边表示具体事物间的联系。图论是建立和处理离散数学模型的一个重要工具，因此它是离散数学的组成部分之一。

图：一个图是一个二元组，即，其中是一个非空集合，称中的元素为图的节点或顶点，称为的顶点集；中的元素为图的边或弧，称为的边集。称和为图的顶点数（阶）和边数。

若图的顶点数和边数都是有限集，则称为有限图；否则称为无限图。的图称为空图；有个顶点的图称为阶图；的图称为零图；仅有一个顶点的图称为平凡图，否则称为非平凡图。

数论

数论是研究整数性质的学科，最开始它研究整数，又叫整数论，后来进一步发展演变为数论。

整数：整数是数论的研究对象，它可以分为奇数和偶数两大类。对于整数可以施加加、减、乘、除四则运算。其中，任意两个或以上整数相加、相减、相乘时，它们的和、差、积仍然是一个整数。但是除法在整数范围内不能毫无阻碍地进行。在整数性质的研究中，人们发现，素数是整数的基本单位，而算术基本定理揭示了正整数与素数的重要联系。因此，素数的性质一直备受数论学者的关注。

信息论

信息论是关于信息的本质和传输规律的科学理论，是研究信息的度量、发送、传递、交换、接收和存储的一门科学。该学科分为狭义、广义两种：狭义信息论是应用数理统计方法来研究信息处理和信息传递的科学，它研究通讯和控制系统中信息传递的规律；广义信息论则是由狭义信息论发展而来的，它研究信息的产生、获取、交换、传输等问题。

信息：信息论的基本概念是信息，从不同的学科及不同的角度来说，信息有不同的定义，一般把信息归结为三大类：第一种是从日常生活的认识来看，信息被看做新闻、消息与知识；第二种是从哲学角度上讲，信息依附于物质和能量，是人类认识改造客观世界的更高层次；第三种是科学家的论述，把信息作为事物的联系变化与差异。

理论计算机科学

理论计算机科学是研究计算机基本理论的学科，基本内容包括自动机论、形式语言理论、程序理论、算法分析、计算复杂理论等。该学科包含离散数学计算的领域，并特别注重图论和数理逻辑。理论计算机科学包括对计算数学结果的算法研究。可算性理论研究哪些对象在原则上可被计算，和逻辑有密切联系。而复杂性则研究计算耗费的时间，自动机理论和形式语言理论与复杂性紧密联系。计算几何应用算法解决几何问题，而计算机图像分析则是应用算法在计算机中再现图像。

连续数学中的离散版本

数学中存在两条主线在平行发展，一条是离散变量的数学，另一条是连续变量的数学，有许多公式和定理也具有一一对应的关系。连续数学与离散数学相对，是研究连续变量的学科，它包括传统几何、微积分、大部分泛函分析、微分方程、拓扑学等内容。将离散数学与连续数学相结合，许多新的分支会出现，例如离散微积分、离散概率分布、离散傅里叶变换、离散几何、离散对数、离散微分几何、离散外微分、差分方程、离散动力系统等。

离散微积分

微积分以无限可微的函数为研究对象，而离散数学的研究对象是离散函数，离散函数的“和差分”，相当于可微函数的“微积分”，所以可以称“和差分”为“离散微积分”。

离散和性微积分：此类的导数记为：

而常用

其中是的最小度量单位且，或是某个特定的度量单位，。由它出发建立的基础理论即为离散和性微积分。

离散积性微积分：此类导数记为：

离散概率分布

有一类随机试验，它们中的每一个试验只有有限个或无限可数个试验结果，即每一个实验仅有有限个或无限可数个元素。在此情形下，称此类随机试验的试验结果是离散的。此类随机试验的每一可能的结果都具有发生的可能性，即为发生的概率。考虑到它们发生的概率，一般称随机试验的离散试验结果服从离散概率分布。

定义：如果一个概率分布是定义在有穷或可列无穷样本空间上的话，就称之为离散的概率分布。设为样本空间，则对任何事件，

这是因为基本事件（尤其是中的）是互斥的。如果是有穷的，且每个基本事件（有概率）

则得上的一致概率分布。这种情况下的试验常被称为“随机地选择中的元素”。

举例：假设抛一枚硬币正面朝上和反面朝上的概率都为，如果抛硬币次，则有在样本空间上的一致概率分布。中的每个基本事件可以用上的长度为的串来表示；其发生的概率为。事件是的子集，大小为，因为上共有个串恰含有个。这样，事件的概率为。

离散几何

离散几何主要研究维欧氏空间中的一些基本且直觉的问题，如Kepler猜想、艾萨克·牛顿Gregory问题、Borsuk猜想和Hadwiger猜想等。这一学科的经典部分是指20世纪初赫尔曼·闵可夫斯基（Minkowski）创立的数的几何。它不仅与许多其他数学分支，如数论、组合数学、图论、群论和优化理论等有着密切的联系，也在编码理论和晶体结构理论等实用学科中具有重要应用。

基本方法

离散数学方法：针对某一物质整体连续发展（运动）的过程，视为若干个离散的对象，分别对每一个离散对象进行研究，然后，再考虑每一离散对象在整体连续过程中互相联系的特征，从而准确地描述客观过程，揭示其规律。对于不同的过程、现象，离散论有不同的方法。

离散时间系统方法

离散时间系统方法可用于解决经济问题。经济系统状态空间的描述通常分为连续时间模型与离散时间模型两类。在连续时间模型中，系统的变量是随时间连续变化的，其数学模型是一阶微分方程（组）；而在离散时间模型中，系统的变量是随时间离散变化的，其数学模型是一阶差分方程（组）。由于经济系统中的变量通常都是按月、按季或按年统计的，因此，描述经济系统的数学模型常采用离散形式。关于离散线性时间系统的解法通常有三种：迭代法、特征值法和变换法。

有限元法

有限元法是一种根据变分原理进行求解的离散化数值分析方法。其应用已由弹性力学平面问题扩展到板壳问题、空间问题，由静力问题扩展到稳定性问题、动力问题和波动问题，分析的对象从弹性材料到塑性、黏弹性，黏塑性和复合材料等，从固体力学到流体力学、传热学、电磁学等领域。该方法的基本思想是：把物理结构分割成有限个区域，这些区域称为单元。每个单元中有有限个节点，单元间通过节点相连。有限元法把要分析的连续体假想地分割成有限个单元所组成的组合体，这一过程简称为离散化。

网络分析法

网络分析法简称ANP法，由匹兹堡大学的萨蒂（T.L.saaty）教授提出，是在层次分析法（AHP）基础上发展形成的一种适应非独立的递阶层次结构的决策方法。其应用于实际生活、生产和科学研究中很多与图论理论有关的问题中，受到越来越广泛的重视。例如，在组织生产中，为完成某项生产任务，各工序之间如何衔接才能使生产任务完成得既快又好；还有各种通信网络的合理架设、交通网络的合理分布等问题。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。该方法将系统内各元素的关系用类似网络结构表示，而不再是简单的递阶层次结构，网络层中的元素可能相互影响、相互支配，它可以更准确地描述客观事物之间的联系，是一种有效的决策方法。

应用

计算机科学

随着技术的发展，多媒体数据中视频动态图像与声音类型、数据量也越来越大，数论变换可以做为数据压缩短发的理论基础。并且通过分析可知，NTT作为一种数论变换技术仅仅应用位移操作便能够完成图像压缩，并且不需要存储过多的基本函数，在一定程度上提升了变换的速度。除数论以外，计算机科学的各个方面都需要组合数学来指导。如，组合数学可以衡量一个算法的概率，要估计此算法解答具有给定长的输入（问题）时有多少步（例如算术运算、二进制比较、程序调用等的次数），那么就要对算法所需的计算量或存储单元数进行估计，这是一个组合分析中的计数问题。

工程学

工程学中，为保障飞行任务的正常开展，地面飞控人员需要实时监测航天器下行的遥测参数，并对其正确性进行诊断。针对航天器下行数据故障诊断系统中循环依赖的诊断知识缺陷问题，通过引入图论模型，把诊断知识中的循环依赖检测问题抽象为有向图中的环搜索问题，并采用经典的拓扑排序算法、Tarjan算法等可以解决这一难题。此外，信息在传输过程中受到外界环境的影响较大，与信息论密切相关的纠错码理论得到迅速发展。纠错码的三个参数相互制约，固定其中两个参数，使另一个参数达到最优是理论的基本问题，对其进行优化产生的改进纠错码具有较高的编码效率，应用于通信工程等领域。

物理学

物理学中，在分析电网信息物理系统（GCPS）逻辑结构的基础上，可以采用一种基于集合论的交互建模方法：通过剖析电力信息能量流与信息流的耦合方式，GCPS定义为物理对象集合与信息对象集合之间的关系，将其分解为电源子系统和负荷子系统，从输入、输出和状态三方面描述其行为水平与状态结构水平，并建立子系统的网络结构图。在电网拓扑结构的约束下，采用“纵向金字塔汇集、横向逻辑互联”的组网规则，最终构建完整的GCPS架构。而在基础物理学中，数理逻辑起到一个基本的串联作用，力学的逻辑线路即为数理逻辑。例如，应用牛顿第二运动定律通过数学推演的方法，可以得出质心运动定理等规律。

参考资料

Discrete Mathematics.mathworld.wolfram.2024-06-08

Four-Color Theorem.mathworld.wolfram.2024-06-01