離散數學南京大學信息管理學院楊建林什么叫離散數學？離散：分離，分散（空間）；與連續相對離散對象（量）：不連續的，可分離的，如自然數。不同于實數對象的集合，有限或可數離散數學是以離散(即非連續)對象的數量和空間關系為研究內容的若干個數學分支的總稱。包括數理邏輯、近世代數、古典概率、組合學、圖論、集合論、數論、自動機和形式語言、可計算性和可判定性、離散幾何、代數結構等。簡介

“離散”和“連續”之間的對立與統一是數學發展的重要動力之一.古代數學主要討論整數等離散與離散化了的數量關系，因而，那時數學被看成是研究上述數量關系的科學.但隨著數學理論的發展，處理離散數量關系的數學工具在刻畫和處理某類事務方面顯得無能為力，因此出現了處理連續數量關系的數學工具：微積分.簡介4離散數學的由來與發展離散數學是隨著計算機科學與技術的產生發展和應用領域的不斷發展而逐步形成和發展起來的一門新興學科，作為一門課程開設于上世紀70年代初。數論舉例：費馬大定理勾股定理：特例32+42=52簡介簡介圖論舉例：歐拉的七橋問題18世紀著名古典數學問題之一東普魯士的哥尼斯堡城，普雷格爾河流經此鎮，奈發夫島位于河中，共有7座橋橫跨河上，把全鎮連接起來

戰爭期間，破壞這七座橋。設想用一輛裝載炸藥的車，每過一橋便炸毀該橋，車無法從原橋駛回設計一種行駛路線的方案，要將七座橋都這樣炸毀，不許遺漏一座橋把這個問題轉化為數學問題：把東、南、北及島四區看成四個點，連接它們的七座橋看成七條通路，如東區與北區由橋3相連，則它們之間有一條通路，南區與北區沒有橋直接相連，則它們之間就沒有直接的通路。以A代表島區，B，C，D分別代表北、東、南三區，把這四個點和連接它們的代表七座橋的通路在圖上畫出來，就得到圖(2)．問題可以敘述為：以A，B，C，D這四點中的任一點為起點，能否不重復地用一筆便將上面的圖形畫出來一個圖形要能一筆畫完成必須符合兩個條件，即圖形是封閉聯通的和圖形中的奇點（與奇數條邊相連的點）個數為0或2。離散數學與計算機科學的關系離散數學是計算機科學的理論基礎計算機的理論模型是離散的圖靈機本質上計算機只處理離散對象，但可通過近似和模擬等手段處理連續對象（如求極值問題）現代計算機越來越多地用于處理離散對象離散數學在計算機科學中直接有用，是計算機科學的工具離散數學與計算機科學的關系離散數學是后繼課程的基礎離散數學是實際應用的基礎工具計算機科學和離散數學處理問題的方法、思維方式有相似之處離散數學可提供所需的思維訓練，培養所需的分析問題和解決問題的能力離散數學是學習數據結構與算法、數據庫、編譯原理、算法設計與分析、計算機網絡等課程的主要基礎，對開發大型軟件、研究信息安全和密碼學、開展計算機理論研究以及開發新型計算機都提供了不可缺少的基礎知識簡介離散數學一命題邏輯二謂詞邏輯三集合論四圖論教材：耿素云，屈婉玲，離散數學，高教出版社，2004

數理邏輯邏輯一詞源于希臘文，意思指：詞、思想、理性、規律等。邏輯學研究的是：判別一個推理過程是否正確的標準。數理邏輯也叫符號邏輯，即用人工符號來書寫邏輯法則，它是一門涉及數學、邏輯學、哲學等學科的橫向交叉學科。數理邏輯現代數理邏輯可分為命題邏輯演算謂詞邏輯演算證明論模型論遞歸函數論公理化集合論等數理邏輯命題邏輯和一階謂詞邏輯是數理邏輯中最成熟的部分，在計算機科學中應用最為廣泛命題邏輯是數理邏輯的最基礎部分謂詞邏輯在命題邏輯的基礎上發展起來數理邏輯在數理邏輯的歷史上，哥德爾的工作起著承前啟后的作用他的不完全性定理，把人們引向一種完全不同的境界

第一不完全性定理：一個包括初等數論的形式系統，如果是協調的，那就是不完全的。數理邏輯集合論的產生是近代數學發展的重大事件集合論本來是論證很嚴格的一個分支，被公認為是數學的基礎在集合論的研究過程中，出現了一次稱作數學史上的第三次大危機。這次危機是由于發現了集合論的悖論引起。（悖論就是邏輯矛盾）羅素悖論的提出幾乎動搖了整個數學基礎。數理邏輯羅素悖論中有許多例子，其中一個很通俗也很有名的例子就是“理發師悖論”：某鄉村有一位理發師，有一天他宣布：只給不自己理發的人理發。那么就產生了一個問題：理發師究竟給不給自己理發？如果他給自己理發，他就是自己理發的人，按照他的原則，他又不該給自己理發；如果他不給自己理發，那么他就是不自己理發的人，按照他的原則，他又應該給自己理發。這就產生了矛盾。數理邏輯悖論的提出，促使許多數學家去研究集合論的無矛盾性問題，從而產生了數理邏輯的一個重要分支—公理集合論數理邏輯無理數的發現---第一次數學危機畢達哥拉斯學派證明了勾股定理，由此發現一些直角三角形的斜邊不能表示成整數或整數之比（不可通約）無窮小是零嗎？---第二次數學危機龜兔賽跑，“兔子永遠追不上烏龜”數理邏輯非歐幾何的產生和集合論的悖論的發現，說明數學本身還存在許多問題，為了研究數學系統的無矛盾性問題，產生了證明論數理邏輯證明論（prooftheory）證明論是數學家D.希爾伯特于20世紀初期建立的，目的是要證明公理系統的無矛盾性1931年，K.哥德爾證明：一個包含公理化的算術的系統中不能證明它自身的無矛盾性。這就是著名的哥德爾不完備性定理1936年，G.根岑證明了算術公理系統的無矛盾性20世紀60年代以后，證明論不再局限于無矛盾性的證明歐氏幾何歐氏幾何的五條公理是：1、任意兩個點可以通過一條直線連接。2、任意線段能無限延伸成一條直線。3、給定任意線段，可以以其一個端點作為圓心，該線段作為半徑作一個圓。4、所有直角都全等。5、若兩條直線都與第三條直線相交，并且在同一邊的內角之和小于兩個直角，則這兩條直線在這一邊必定相交。過直線外一點有且只有一條直線與已知直線平行第五條公理稱為平行公理羅巴切夫斯基幾何

簡稱羅氏幾何羅氏幾何的五條公理是：

1、任意兩個點可以通過一條直線連接。2、任意線段能無限延伸成一條直線。3、給定任意線段，可以以其一個端點作為圓心，該線段作為半徑作一個圓。4、所有直角都全等。5、一個和歐式平行公理相矛盾的命題。過直線外一點至少存在兩條直線和已知直線平行黎曼幾何黎曼幾何的五條公理是：1、任意兩個點可以通過一條直線連接。2、任意線段能無限延伸成一條直線。3、給定任意線段，可以以其一個端點作為圓心，該線段作為半徑作一個圓。4、所有直角都全等。5、在同一平面內任何兩條直線都有公共點(交點)。過直線外一點，不能做直線和已知直線平行三種幾何的關系歐氏幾何、羅氏幾何、黎曼幾何是三種各有區別的幾何。這三中幾何各自所有的命題都構成了一個嚴密的公理體系，各公理之間滿足和諧性、完備性和獨立性。因此這三種幾何都是正確的。(相容性問題，解決的工具是證明論與模型論）在我們這個不大不小、不遠不近的空間里，也就是在我們的日常生活中，歐式幾何是適用的；在宇宙空間中或原子核世界，羅氏幾何更符合客觀實際；在地球表面研究航海、航空等實際問題中，黎曼幾何更準確一些。愛因斯坦花了四年的時間，認真地學習黎曼幾何，后來用黎曼幾何的語言創立和表述了廣義相對論。離散數學與信息管理專業關系離散數學在信息管理與信息系統專業中的應用或分散或隱藏，無處不在作為基礎課程的離散數學的教學在內容與形式上缺乏對本專業的直接針對性將離散數學知識轉為具體應用有時依賴于知識掌握人的悟性離散數學與信息管理專業關系離散數學的原理滲透于信息管理與信息系統專業的一些相關課程之中。如《數據結構》中的“樹”的結構與遍歷；《數據庫原理》中