離散數學（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）設為代數系統，和是二元運算，是一元運算，如果對于中的任何元素滿足交換律、分配律、同一律和互補律，則該代數系統為布爾代數。
對布爾代數中的任何元素，有以下性質：
組合分析
組合分析又稱組合學、組合數學或組合論，是研究按照若干給定的規則安排一些物件時有關問題的一門學科。該學科的研究對象為進行排列或組合的途徑，包含組合設計、計數組合、計數、組合幾何、組合拓撲等內容。研究的問題主要有：符合要求的安排是否存在，當存在時，其構造方法如何；符合要求的安排的個數怎樣計算；當有比較優劣的標準時，與最優（或次優）的安排有關的一些問題。組合分析遵從三個基本原則，分別為：卡氐積的計數、乘法原理以及加法原理。
圖論
圖論是近代應用數學分支，它以圖為對象，研究事物之間的聯系。在圖論中，圖是指某類具體離散事物集合和該集合中的每對事物間以某種方式相聯系的數學模型，用圖表示事物間的聯系時，用節點表示事物，邊表示具體事物間的聯系。圖論是建立和處理離散數學模型的一個重要工具，因此它是離散數學的組成部分之一。
圖：一個圖是一個二元組，即，其中是一個非空集合，稱中的元素為圖的節點或頂點，稱為的頂點集；中的元素為圖的邊或弧，稱為的邊集。稱和為圖的頂點數（階）和邊數。
若圖的頂點數和邊數都是有限集，則稱為有限圖；否則稱為無限圖。的圖稱為空圖；有個頂點的圖稱為階圖；的圖稱為零圖；僅有一個頂點的圖稱為平凡圖，否則稱為非平凡圖。
數論
數論是研究整數性質的學科，最開始它研究整數，又叫整數論，后來進一步發展演變為數論。
整數：整數是數論的研究對象，它可以分為奇數和偶數兩大類。對于整數可以施加加、減、乘、除四則運算。其中，任意兩個或以上整數相加、相減、相乘時，它們的和、差、積仍然是一個整數。但是除法在整數范圍內不能毫無阻礙地進行。在整數性質的研究中，人們發現，素數是整數的基本單位，而算術基本定理揭示了正整數與素數的重要聯系。因此，素數的性質一直備受數論學者的關注。
信息論
信息論是關于信息的本質和傳輸規律的科學理論，是研究信息的度量、發送、傳遞、交換、接收和存儲的一門科學。該學科分為狹義、廣義兩種：狹義信息論是應用數理統計方法來研究信息處理和信息傳遞的科學，它研究通訊和控制系統中信息傳遞的規律；廣義信息論則是由狹義信息論發展而來的，它研究信息的產生、獲取、交換、傳輸等問題。
信息：信息論的基本概念是信息，從不同的學科及不同的角度來說，信息有不同的定義，一般把信息歸結為三大類：第一種是從日常生活的認識來看，信息被看做新聞、消息與知識；第二種是從哲學角度上講，信息依附于物質和能量，是人類認識改造客觀世界的更高層次；第三種是科學家的論述，把信息作為事物的聯系變化與差異。
理論計算機科學
理論計算機科學是研究計算機基本理論的學科，基本內容包括自動機論、形式語言理論、程序理論、算法分析、計算復雜理論等。該學科包含離散數學計算的領域，并特別注重圖論和數理邏輯。理論計算機科學包括對計算數學結果的算法研究?？伤阈岳碚撗芯磕男ο笤谠瓌t上可被計算，和邏輯有密切聯系。而復雜性則研究計算耗費的時間，自動機理論和形式語言理論與復雜性緊密聯系。計算幾何應用算法解決幾何問題，而計算機圖像分析則是應用算法在計算機中再現圖像。
連續數學中的離散版本
數學中存在兩條主線在平行發展，一條是離散變量的數學，另一條是連續變量的數學，有許多公式和定理也具有一一對應的關系。連續數學與離散數學相對，是研究連續變量的學科，它包括傳統幾何、微積分、大部分泛函分析、微分方程、拓撲學等內容。將離散數學與連續數學相結合，許多新的分支會出現，例如離散微積分、離散概率分布、離散傅里葉變換、離散幾何、離散對數、離散微分幾何、離散外微分、差分方程、離散動力系統等。
離散微積分
微積分以無限可微的函數為研究對象，而離散數學的研究對象是離散函數，離散函數的“和差分”，相當于可微函數的“微積分”，所以可以稱“和差分”為“離散微積分”。
離散和性微積分：此類的導數記為：
而常用
其中是的最小度量單位且，或是某個特定的度量單位，。由它出發建立的基礎理論即為離散和性微積分。
離散積性微積分：此類導數記為：
離散概率分布
有一類隨機試驗，它們中的每一個試驗只有有限個或無限可數個試驗結果，即每一個實驗僅有有限個或無限可數個元素。在此情形下，稱此類隨機試驗的試驗結果是離散的。此類隨機試驗的每一可能的結果都具有發生的可能性，即為發生的概率?？紤]到它們發生的概率，一般稱隨機試驗的離散試驗結果服從離散概率分布。
定義：如果一個概率分布是定義在有窮或可列無窮樣本空間上的話，就稱之為離散的概率分布。設為樣本空間，則對任何事件，
這是因為基本事件（尤其是中的）是互斥的。如果是有窮的，且每個基本事件（有概率）
則得上的一致概率分布。這種情況下的試驗常被稱為“隨機地選擇中的元素”。
舉例：假設拋一枚硬幣正面朝上和反面朝上的概率都為，如果拋硬幣次，則有在樣本空間上的一致概率分布。中的每個基本事件可以用上的長度為的串來表示；其發生的概率為。事件是的子集，大小為，因為上共有 個串恰含有個。這樣，事件的概率為 。
離散幾何
離散幾何主要研究維歐氏空間中的一些基本且直覺的問題，如Kepler猜想、艾薩克·牛頓Gregory問題、Borsuk猜想和Hadwiger猜想等。這一學科的經典部分是指20世紀初赫爾曼·閔可夫斯基（Minkowski）創立的數的幾何。它不僅與許多其他數學分支，如數論、組合數學、圖論、 群論和優化理論等有著密切的聯系，也在編碼理論和晶體結構理論等實用學科中具有重要應用。
基本方法
離散數學方法：針對某一物質整體連續發展（運動）的過程，視為若干個離散的對象，分別對每一個離散對象進行研究，然后，再考慮每一離散對象在整體連續過程中互相聯系的特征，從而準確地描述客觀過程，揭示其規律。對于不同的過程、現象，離散論有不同的方法。
離散時間系統方法
離散時間系統方法可用于解決經濟問題。經濟系統狀態空間的描述通常分為連續時間模型與離散時間模型兩類。在連續時間模型中，系統的變量是隨時間連續變化的，其數學模型是一階微分方程（組）；而在離散時間模型中，系統的變量是隨時間離散變化的，其數學模型是一階差分方程（組）。由于經濟系統中的變量通常都是按月、按季或按年統計的，因此，描述經濟系統的數學模型常采用離散形式。關于離散線性時間系統的解法通常有三種：迭代法、特征值法和變換法。
有限元法
有限元法是一種根據變分原理進行求解的離散化數值分析方法。其應用已由彈性力學平面問題擴展到板殼問題、空間問題，由靜力問題擴展到穩定性問題、動力問題和波動問題，分析的對象從彈性材料到塑性、黏彈性，黏塑性和復合材料等，從固體力學到流體力學、傳熱學、電磁學等領域。該方法的基本思想是：把物理結構分割成有限個區域，這些區域稱為單元。每個單元中有有限個節點，單元間通過節點相連。有限元法把要分析的連續體假想地分割成有限個單元所組成的組合體，這一過程簡稱為離散化。
網絡分析法
網絡分析法簡稱ANP法，由匹茲堡大學的薩蒂（T.L.saaty）教授提出，是在層次分析法（AHP）基礎上發展形成的一種適應非獨立的遞階層次結構的決策方法。其應用于實際生活、生產和科學研究中很多與圖論理論有關的問題中，受到越來越廣泛的重視。例如，在組織生產中，為完成某項生產任務，各工序之間如何銜接才能使生產任務完成得既快又好；還有各種通信網絡的合理架設、交通網絡的合理分布等問題。將龐大復雜的工程系統和管理問題用圖描述，可以解決很多工程設計和管理決策的最優化問題。該方法將系統內各元素的關系用類似網絡結構表示，而不再是簡單的遞階層次結構，網絡層中的元素可能相互影響、相互支配，它可以更準確地描述客觀事物之間的聯系，是一種有效的決策方法。
相關猜想
四色猜想
內容：平面上的任何一個地圖都能至多用四種顏色給各個國家染色，使得任何兩個有公共邊界的相鄰國家有不同的顏色。
解決：19世紀中葉，該猜想自提出以來，吸引到大批學者的廣泛關注。其中，肯普（Kempe）和泰勒（Tait）分別獨立地給出過錯誤的證明，肯普的證明在一段時間內被人們接受，但被希伍德（Heawood）用18個面的地圖指出了錯誤。直到1976年，美國伊利諾伊州大學的阿佩爾（Appel）、哈肯（Haken）借助于電子計算機給出了證明。電子計算機在解決這一問題中所發揮的重大應用，告訴人們機器可以完成人的智力難以完成的工作，大大推動了機器證明、人工智慧及計算機科學的發展。
NP猜想
內容：人們發現，所有的完全非確定性多項式問題（NP）都可以轉換為一類叫作滿足性問題的邏輯運算。既然這類問題的所有可能答案都可以在多項式時間內計算出來，那么，人們就猜想，這類問題是否存在一個確定性算法，可以在多項式時間內直接算出或是搜尋出正確的答案。
解決：該問題的解決包含兩種思路，一種可能是找到一個算法，將問題轉化為同一問題；另一種就是找不到這種算法，就要證明它為什么不存在。該問題的解決較為困難，不過有許多著名的組合數學問題被證明是NP難題，但是沒有一個確定性的算法，因此求解近似算法或許是一條必由之路。
希爾伯特問題
算術的無矛盾性問題：歐氏幾何的無矛盾性可歸納為算術公理的無矛盾性，該問題是希爾伯特第二問題。
解決：邏輯學家庫爾特·卡塞雷斯（Kurt G?del）提出了不完備性定理，指出對于任何一個公理系統，必定存在一個用形式語言表述的語句無法用形式語言的推理來證實或證偽，即這個語句是不確定的，因而只能靠增加一個新的公理來解決。該定理從相反的方向解決了該問題。1936年，根茨（Genaen）用超限歸納法證明了算術公理的無矛盾性。
丟番圖方程可解性的判別問題：求出一個整系數方程的整數根，稱為丟番圖方程可解。問：是否能用有限步構成的一般算法判斷一個丟番圖方程的可解性。
解決：1970年，蘇聯數學家馬蒂塞維奇（Mattisevich）在美國數學家戴維斯（Davis）、希拉里·普特南（Putmam）、羅賓遜（Robinson）工作的基礎上證明了戴維·希爾伯特所期望的一般算法不能實現。
應用
計算機科學
隨著技術的發展，多媒體數據中視頻動態圖像與聲音類型、數據量也越來越大，數論變換可以做為數據壓縮短發的理論基礎。并且通過分析可知，NTT作為一種數論變換技術僅僅應用位移操作便能夠完成圖像壓縮，并且不需要存儲過多的基本函數，在一定程度上提升了變換的速度。除數論以外，計算機科學的各個方面都需要組合數學來指導。如，組合數學可以衡量一個算法的概率，要估計此算法解答具有給定長的輸入（問題）時有多少步（例如算術運算、二進制比較、程序調用等的次數），那么就要對算法所需的計算量或存儲單元數進行估計，這是一個組合分析中的計數問題。
工程學
工程學中，為保障飛行任務的正常開展，地面飛控人員需要實時監測航天器下行的遙測參數，并對其正確性進行診斷。針對航天器下行數據故障診斷系統中循環依賴的診斷知識缺陷問題，通過引入圖論模型，把診斷知識中的循環依賴檢測問題抽象為有向圖中的環搜索問題，并采用經典的拓撲排序算法、Tarjan算法等可以解決這一難題。此外，信息在傳輸過程中受到外界環境的影響較大，與信息論密切相關的糾錯碼理論得到迅速發展。糾錯碼的三個參數相互制約，固定其中兩個參數，使另一個參數達到最優是理論的基本問題，對其進行優化產生的改進糾錯碼具有較高的編碼效率，應用于通信工程等領域。
物理學
物理學中，在分析電網信息物理系統（GCPS）邏輯結構的基礎上，可以采用一種基于集合論的交互建模方法：通過剖析電力信息能量流與信息流的耦合方式，GCPS定義為物理對象集合與信息對象集合之間的關系，將其分解為電源子系統和負荷子系統，從輸入、輸出和狀態三方面描述其行為水平與狀態結構水平，并建立子系統的網絡結構圖。在電網拓撲結構的約束下，采用“縱向金字塔匯集、橫向邏輯互聯”的組網規則，最終構建完整的GCPS架構。而在基礎物理學中，數理邏輯起到一個基本的串聯作用，力學的邏輯線路即為數理邏輯。例如，應用牛頓第二運動定律通過數學推演的方法，可以得出質心運動定理等規律。
參考資料 >
Discrete Mathematics.mathworld.wolfram.2024-06-08
Four-Color Theorem.mathworld.wolfram.2024-06-01