离散数学
离散数学（英语：Discrete mathematics）是数学的几个分支的总称，研究基于离散空间而不是连续的数学结构。与连续变化的实数不同，离散数学的研究对象——例如整数、图和数学逻辑中的命题[1]——不是连续变化的，而是拥有不等、分立的值。[2]因此离散数学不包含微积分和分析等“连续数学”的内容。
离散对象经常可以用整数来枚举。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括实数集）的数学分支。[3]但是，“离散数学”不存在准确且普遍认可的定义。[4]实际上，离散数学经常被定义为不包含连续变化量及相关概念的数学，甚少被定义为包含什么内容的数学。
离散数学中的对象集合可以是有限或者是无限的。有限数学一词通常指代离散数学处理有限集合的那些部分，特别是在与商业相关的领域。
随着电脑科学的飞速发展，离散数学的重要性则日益彰显。它为许多资讯学课程提供了数学基础，包括数据结构、算法、数据库理论、形式语言与操作系统等。如果没有离散数学的相关数学基础，学生在学习上述课程中，便会遇到较多的困难。此外，离散数学也包含了解决运筹学、化学、工程学、生物学等众多领域的数学背景。由于运算对象是离散的，所以电脑科学的数学基础基本上也是离散的。我们可以说电脑科学的数学语言就是离散数学。人们会使用离散数学里面的槪念和表示方法，来研究和描述电脑科学下所有分支的对象和问题，如电脑运算、编程语言、密码学、自动定理证明和软件开发等。相反地，电脑的应用使离散数学的概念得以应用于日常生活当中（如运筹学）。
虽然离散数学的主要研究对象是离散对象，但是连续数学的分析方法往往也可以采用。数论就是离散和连续数学的交叉学科。同样的，有限拓扑（对有限拓扑空间的研究）从字面上可看作离散化和拓扑的交集。
历史
[编辑]
历史上，离散数学涉及了各个领域的一系列挑战性问题。在图论中，许多的研究动机是来自于尝试证明四色定理。这些研究虽然从1852年开始，但是直至1976年四色定理才得到证明，是由肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）借由大量电脑辅助而完成的。[5]
在逻辑领域，大卫·希尔伯特（David Hilbert）于1900年提出的公开问题清单的第二个问题是要证明算术的公理是一致的。1931年，库尔特·哥德尔的第二不完备定理证明这是不可能的——至少算术本身不可能。大卫·希尔伯特的第十个问题是要确定某一整系数多项式丢番图方程是否有一个整数解。1970年，尤里·马季亚谢维奇证明这不可能做到。
第二次世界大战时盟军有破解纳粹德军密码的需要，带动了密码学和理论电脑科学的发展。英国的布莱切利园因而发明出第一部数码电脑——巨像电脑。与此同时，军事上的需求亦带动了运筹学的发展。直至冷战时期，密码学的地位依然重要，其后的几十年间更发展出如公开密钥加密等根本性的长进。随着1950年代关键路径方法的创立，运筹学则于商业和项目管理上愈趋重要。电讯工业的出现亦助长了离散数学，特别是图论和信息论上的发展。数理逻辑上叙述的形式验证至今已经成为安全关键系统的软件开发中必不可少的一环，自动定理证明的技术也因此而提高。
当今，理论电脑科学中最著名的开放问题之一是P/NP问题，P/NP问题中包含了复杂度类P与NP的关系。克雷数学研究所为此及其他6个千禧年大奖难题的第一个正确证明各悬赏100万美元。[6]
主题
[编辑]
离散数学包含几个不同的主题，列举如下：
数理逻辑
[编辑]逻辑是对有效推理和推理原则，及其连续性、合理性和完整性的研究。举一个简单的例子：在大多数逻辑系统中，皮尔士定律（((P→Q)→P)→P）是正确的，而且可以简易地利用真值表得到证明。数学证明在数理逻辑中十分重要，而且在自动定理证明和软件开发（如形式验证）有广泛应用。
集合论
[编辑]集合论是研究集合的数学分支。集合是指一定对象的总和，例如：{蓝色，白色，红色}是一个有限集合；所有素数组成一个无限集合。 偏序关系和拥有其他关系特征的集合在多个数学领域都有应用。
信息论
[编辑]
信息论涉及信息量化。与此密切相关的编码理论则用来设计高效可靠的数据传输和数据储存方法。
数论
[编辑]数论关注普通数字，特别是整数的特性。数论在密码学和密码分析中有应用，特别是关于素数和素性测试方面。在解析数论中，也使用连续数学的理论。
组合数学
[编辑]
组合数学研究对象进行排列或组合的途径，包含组合设计（Combinatorial design）、计数组合（enumerative combinatorics）、计数、组合几何（combinatorial geometry）、组合拓扑（Combinatorial topology）等主题。图论是组合数学的重要部分，有很多实际应用。
在组合分析（analytic combinatorics）和代数图论（algebraic graph theory）中也使用连续数学的理论，而且代数图论还与群论有着紧密联络。
图论
[编辑]图论是研究图和网络的数学分支，常被认为包含于组合数学中，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题，在数学和科学的所有领域都有广泛的应用。例如：有名的七桥问题。[7]
抽象代数
[编辑]代数结构既可以是离散的，也可以是连续的。离散代数包括逻辑门和编程中使用的逻辑代数、数据库中使用的关系代数、代数编码理论中重要的离散有限群、环和域、形式语言理论中的离散半群和幺半群。
理论电脑科学
[编辑]
离散数学充分描述了电脑科学离散性的特点。
理论电脑科学（Theoretical computer science）包含离散数学计算的领域，并特别注重图论和数理逻辑。理论电脑科学包括对计算数学结果的算法研究。可算性理论研究那些对象在原则上可被计算，和逻辑有密切联络。而复杂性则研究计算耗费的时间，自动机理论和形式语言理论与复杂性紧密联络。计算几何应用算法解决几何问题，而电脑图像分析则是应用算法在电脑中再现图像。
拓扑学
[编辑]虽然拓扑学是形式化和一般化物体“连续形变”的直觉概念的研究领域，其也包含很多离散主题，如拓扑变换时常取离散值，组合拓扑、拓扑图论、拓扑组合、计算拓扑、离散空间、有限拓扑空间等领域。
运筹学
[编辑]
运筹学的研究为解决一些商业上和其他范筹上实质的问题提供方法。这些问题包括如何分配资源以使利润增至最高和如何为企划调度使风险减至最低等。运筹学的研究方向包括线性规划、最优化、等候理论、调度理论、网络理论，和一些正在增加的其他方面。运筹学的内容也会涉及一些连续主题，如连续时间马尔可夫过程、连续时间鞅、过程优化以及连续混合控制理论。
博弈论、决策论、效用理论、社会选择理论
[编辑]| 合作 | 背叛 | |
| 合作 | -1, -1 | -10, 0 |
| 背叛 | 0, -10 | -5, -5 |
| 囚徒困境的支付矩阵 | ||
博弈论用于处理的问题比较复杂，通常这些选择成功与否取决于其他人的选择，因此如何作最好出一个最好的选择比较复杂。连续对策甚至也是存在的，如微分博弈。博弈论的主题包括拍卖理论和公平分配博弈。
决策论是有关判定特定决策的价值、不确定性、合理性以及最终能够确定的最优决策的理论。
效用理论的研究内容是由各种商品和服务评估相对经济满足程度，或是评估各种商品和服务的希求程度。
社会选择理论是关于投票的理论。更近似于谜题的有关投票的问题是抽签问题（Bertrand's ballot theorem）。
离散化
[编辑]离散化关注将连续模型或等式转化为离散形式的过程，通常是基于简化计算的目的。数值分析是离散化一个重要实例。
连续数学的离散近似
[编辑]
很多的连续数学概念都有离散数学的版本，例如:
在应用数学中，离散模型是连续模型的离散近似。在离散模型中，离散方程由数据确定。使用递推关系是这种建模方式的一般方法。
离散和连续混合数学
[编辑]时标微积分是差分方程理论与微分方程理论的统一，应用在需要建立离散和连续同步数据模型的领域。
参考文献
[编辑]- ^ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
- ^ Weisstein, Eric W. (编). Discrete mathematics. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
- ^ Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
- ^ Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
- ^ 5.0 5.1 Wilson, Robin, Four Colors Suffice, London: Penguin Books, 2002, ISBN 0-691-11533-8
- ^ 千禧年大奖难题. 2000-05-24 [2008-01-12]. （原始内容存档于2008-01-08）.
- ^ Graphs on Surfaces （页面存档备份，存于互联网档案馆）, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001
延伸阅读
[编辑]
- Norman L. Biggs, Discrete Mathematics 2nd ed. Oxford University Press. ISBN 978-0-19-850717-8. Companion Web site: includes questions together with solutions.
- Ronald Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics
- Richard Johnsonbaugh, Discrete Mathematics 6th ed. Macmillan. ISBN 978-0-13-045803-2. Companion Web site: [1] （页面存档备份，存于互联网档案馆）
- Reinhard Klette and Azriel Rosenfeld. Digital Geometry. Morgan Kaufmann. 2004 [2020-05-25]. ISBN 1-55860-861-3. （原始内容存档于2021-02-10）. Also on (digital) topology, graph theory, combinatorics, axiomatic systems.
- Donald E. Knuth, The Art of Computer Programming
- Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics CRC Press. ISBN 978-0-8493-0149-0.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill. ISBN 978-0-07-288008-3. Companion Web site: http://highered.mcgraw-hill.com/sites/0072880082/information_center_view0/ （页面存档备份，存于互联网档案馆）
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 5th ed. Addison Wesley. ISBN 978-0-201-72634-3
- C.L. Liu, Elements of Discrete Math
- Neville Dean, Essence of Discrete Mathematics Prentice Hall. ISBN 978-0-13-345943-2. Not as in depth as above texts, but a gentle intro.
- Mathematics Archives, Discrete Mathematics links to syllabi, tutorials, programs, etc. http://archives.math.utk.edu/topics/discreteMath.html （页面存档备份，存于互联网档案馆）
- Jiří Matoušek & Jaroslav Nešetřil, Invitation to Discrete Mathematics, OUP.
外部链接
[编辑]- （中文）数学领域：离散数学 (Episte Math) （页面存档备份，存于互联网档案馆）
