1、南京大學(xué)信息管理學(xué)院楊建林l什么叫離散數(shù)學(xué)？什么叫離散數(shù)學(xué)？離散：分離，分散（空間）；與連續(xù)相對(duì)離散：分離，分散（空間）；與連續(xù)相對(duì)離散對(duì)象（量）：不連續(xù)的，可分離的，如自然數(shù)。不同于離散對(duì)象（量）：不連續(xù)的，可分離的，如自然數(shù)。不同于實(shí)數(shù)對(duì)象的集合，有限或可數(shù)實(shí)數(shù)對(duì)象的集合，有限或可數(shù)離散數(shù)學(xué)是以離散離散數(shù)學(xué)是以離散( (即即非連續(xù)非連續(xù)) )對(duì)象的對(duì)象的數(shù)量和空間關(guān)系數(shù)量和空間關(guān)系為研究為研究內(nèi)容的若干個(gè)數(shù)學(xué)分支的總稱。內(nèi)容的若干個(gè)數(shù)學(xué)分支的總稱。包括包括數(shù)理邏輯數(shù)理邏輯、近世代數(shù)、古典概率、近世代數(shù)、古典概率、組合學(xué)組合學(xué)、圖論、集合圖論、集合論論、數(shù)論、自動(dòng)機(jī)和形式語言、數(shù)論、自動(dòng)機(jī)和

2、形式語言、可計(jì)算性和可判定性可計(jì)算性和可判定性、離散、離散幾何、代數(shù)結(jié)構(gòu)等。幾何、代數(shù)結(jié)構(gòu)等。l “離散離散”和和“連續(xù)連續(xù)”之間的對(duì)立與統(tǒng)一是數(shù)學(xué)發(fā)展的之間的對(duì)立與統(tǒng)一是數(shù)學(xué)發(fā)展的重要?jiǎng)恿χ恢匾獎(jiǎng)恿χ?l古代數(shù)學(xué)主要討論整數(shù)等離散與離散化了的數(shù)量關(guān)系，古代數(shù)學(xué)主要討論整數(shù)等離散與離散化了的數(shù)量關(guān)系，因而，那時(shí)數(shù)學(xué)被看成是研究上述數(shù)量關(guān)系的科學(xué)因而，那時(shí)數(shù)學(xué)被看成是研究上述數(shù)量關(guān)系的科學(xué).l但隨著數(shù)學(xué)理論的發(fā)展，處理離散數(shù)量關(guān)系的數(shù)學(xué)工但隨著數(shù)學(xué)理論的發(fā)展，處理離散數(shù)量關(guān)系的數(shù)學(xué)工具在刻畫和處理某類事務(wù)方面顯得無能為力，因此出具在刻畫和處理某類事務(wù)方面顯得無能為力，因此出現(xiàn)了處理連續(xù)數(shù)量關(guān)

3、系的數(shù)學(xué)工具：微積分現(xiàn)了處理連續(xù)數(shù)量關(guān)系的數(shù)學(xué)工具：微積分.4l離散數(shù)學(xué)是隨著計(jì)算機(jī)科學(xué)與技術(shù)的產(chǎn)生發(fā)展和應(yīng)用領(lǐng)域的不斷發(fā)展而逐步形成和發(fā)展起來的一門新興學(xué)科，作為一門課程開設(shè)于上世紀(jì)70年代初。l數(shù)論舉例：費(fèi)馬大定理數(shù)論舉例：費(fèi)馬大定理l勾股定理：特例勾股定理：特例3 32 2+4+42 2=5=52 2)3(nzyxnnnl圖論舉例：圖論舉例：l歐拉的七橋問題歐拉的七橋問題18世紀(jì)著名古典數(shù)學(xué)問題之一世紀(jì)著名古典數(shù)學(xué)問題之一東普魯士的哥尼斯堡城，東普魯士的哥尼斯堡城，普雷格爾河流經(jīng)此鎮(zhèn)，奈發(fā)夫島位普雷格爾河流經(jīng)此鎮(zhèn)，奈發(fā)夫島位于河中，共有于河中，共有7座橋橫跨河上，把全鎮(zhèn)連接起來座橋橫跨河

4、上，把全鎮(zhèn)連接起來 戰(zhàn)爭期間，破壞這七座橋。設(shè)想用一輛裝載炸藥的車，每過戰(zhàn)爭期間，破壞這七座橋。設(shè)想用一輛裝載炸藥的車，每過一橋便炸毀該橋，車無法從原橋駛回一橋便炸毀該橋，車無法從原橋駛回設(shè)計(jì)一種行駛路線的方案，要將七座橋都這樣炸毀，不許遺設(shè)計(jì)一種行駛路線的方案，要將七座橋都這樣炸毀，不許遺漏一座橋漏一座橋l把這個(gè)問題轉(zhuǎn)化為數(shù)學(xué)問題：把東、南、北及島四區(qū)看成四個(gè)點(diǎn)，連接它們的七把這個(gè)問題轉(zhuǎn)化為數(shù)學(xué)問題：把東、南、北及島四區(qū)看成四個(gè)點(diǎn)，連接它們的七座橋看成七條通路，如東區(qū)與北區(qū)由橋座橋看成七條通路，如東區(qū)與北區(qū)由橋3 3相連，則它們之間有一條通路，南區(qū)與相連，則它們之間有一條通路，南區(qū)與北區(qū)沒有

5、橋直接相連，則它們之間就沒有直接的通路。北區(qū)沒有橋直接相連，則它們之間就沒有直接的通路。l以以A A代表島區(qū)，代表島區(qū)，B B，C C，D D分別代表北、東、南三區(qū)，把這四個(gè)點(diǎn)和連接它們的代表分別代表北、東、南三區(qū)，把這四個(gè)點(diǎn)和連接它們的代表七座橋的通路在圖上畫出來，就得到圖七座橋的通路在圖上畫出來，就得到圖(2)(2)l問題可以敘述為：以問題可以敘述為：以A A，B B，C C，D D這四點(diǎn)中的任一點(diǎn)為起點(diǎn)，能否不重復(fù)地用一筆這四點(diǎn)中的任一點(diǎn)為起點(diǎn)，能否不重復(fù)地用一筆便將上面的圖形畫出來便將上面的圖形畫出來l一個(gè)圖形要能一筆畫完成必須符合兩個(gè)條件，即圖形是封閉聯(lián)通的和圖形中的奇一個(gè)圖形要能一

6、筆畫完成必須符合兩個(gè)條件，即圖形是封閉聯(lián)通的和圖形中的奇點(diǎn)（與奇數(shù)條邊相連的點(diǎn)）個(gè)數(shù)為點(diǎn)（與奇數(shù)條邊相連的點(diǎn)）個(gè)數(shù)為0或或2。l離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)l計(jì)算機(jī)的理論模型是離散的圖靈機(jī)計(jì)算機(jī)的理論模型是離散的圖靈機(jī)l本質(zhì)上計(jì)算機(jī)只處理離散對(duì)象，但可通過近似和模擬本質(zhì)上計(jì)算機(jī)只處理離散對(duì)象，但可通過近似和模擬等手段處理連續(xù)對(duì)象（如求極值問題）等手段處理連續(xù)對(duì)象（如求極值問題）l現(xiàn)代計(jì)算機(jī)越來越多地用于處理離散對(duì)象現(xiàn)代計(jì)算機(jī)越來越多地用于處理離散對(duì)象l離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中直接有用，是計(jì)算機(jī)科學(xué)的離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中直接有用，是計(jì)算機(jī)科學(xué)的工具工具l離散數(shù)學(xué)是

7、后繼課程的基礎(chǔ)離散數(shù)學(xué)是后繼課程的基礎(chǔ)l離散數(shù)學(xué)是實(shí)際應(yīng)用的基礎(chǔ)工具離散數(shù)學(xué)是實(shí)際應(yīng)用的基礎(chǔ)工具l計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)處理問題的方法、思維計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)處理問題的方法、思維方式有相似之處方式有相似之處l離散數(shù)學(xué)可提供所需的思維訓(xùn)練，培養(yǎng)所需的離散數(shù)學(xué)可提供所需的思維訓(xùn)練，培養(yǎng)所需的分析問題和解決問題的能力分析問題和解決問題的能力l離散數(shù)學(xué)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、離散數(shù)學(xué)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、數(shù)據(jù)庫數(shù)據(jù)庫、編編譯原理譯原理、算法設(shè)計(jì)與分析、算法設(shè)計(jì)與分析、計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)等課程等課程的主要基礎(chǔ)，對(duì)的主要基礎(chǔ)，對(duì)開發(fā)大型軟件開發(fā)大型軟件、研究信息安全研究信息安全和密碼學(xué)和密碼學(xué)、開展計(jì)算機(jī)

8、理論研究以及開發(fā)新型、開展計(jì)算機(jī)理論研究以及開發(fā)新型計(jì)算機(jī)都提供了不可缺少的基礎(chǔ)知識(shí)計(jì)算機(jī)都提供了不可缺少的基礎(chǔ)知識(shí)l一一 命題邏輯命題邏輯l二二 謂詞邏輯謂詞邏輯l三三 集合論集合論l四四 圖論圖論l教材：耿素云，屈婉玲，離散數(shù)學(xué)，高教出版社，教材：耿素云，屈婉玲，離散數(shù)學(xué)，高教出版社，2004 l邏輯一詞源于希臘文，意思指：詞、思想、理邏輯一詞源于希臘文，意思指：詞、思想、理性、規(guī)律等。性、規(guī)律等。l邏輯學(xué)研究的是：判別一個(gè)推理過程是否正確邏輯學(xué)研究的是：判別一個(gè)推理過程是否正確的標(biāo)準(zhǔn)。的標(biāo)準(zhǔn)。l數(shù)理邏輯也叫符號(hào)邏輯，即用人工符號(hào)來書寫數(shù)理邏輯也叫符號(hào)邏輯，即用人工符號(hào)來書寫邏輯法則，它是

9、一門涉及數(shù)學(xué)、邏輯學(xué)、邏輯法則，它是一門涉及數(shù)學(xué)、邏輯學(xué)、哲學(xué)哲學(xué)等學(xué)科的橫向交叉學(xué)科。等學(xué)科的橫向交叉學(xué)科。l現(xiàn)代數(shù)理邏輯可分為現(xiàn)代數(shù)理邏輯可分為命題邏輯演算命題邏輯演算謂詞邏輯演算謂詞邏輯演算證明論證明論模型論模型論遞歸函數(shù)論遞歸函數(shù)論公理化集合論等公理化集合論等l命題邏輯和一階謂詞邏輯是數(shù)理邏輯中命題邏輯和一階謂詞邏輯是數(shù)理邏輯中最成熟的部分，在計(jì)算機(jī)科學(xué)中應(yīng)用最最成熟的部分，在計(jì)算機(jī)科學(xué)中應(yīng)用最為廣泛為廣泛命題邏輯是數(shù)理邏輯的最基礎(chǔ)部分命題邏輯是數(shù)理邏輯的最基礎(chǔ)部分謂詞邏輯在命題邏輯的基礎(chǔ)上發(fā)展起來謂詞邏輯在命題邏輯的基礎(chǔ)上發(fā)展起來l在數(shù)理邏輯的歷史上，哥德爾的工作起著承前在數(shù)理邏輯的

10、歷史上，哥德爾的工作起著承前啟后的作用啟后的作用l他的不完全性定理，把人們引向一種完全不同他的不完全性定理，把人們引向一種完全不同的境界的境界 l第一不完全性定理：一個(gè)包括初等數(shù)論的形式第一不完全性定理：一個(gè)包括初等數(shù)論的形式系統(tǒng)，如果是協(xié)調(diào)的，那就是不完全的。系統(tǒng)，如果是協(xié)調(diào)的，那就是不完全的。l集合論的產(chǎn)生是近代數(shù)學(xué)發(fā)展的重大事件集合論的產(chǎn)生是近代數(shù)學(xué)發(fā)展的重大事件集合論本來是論證很嚴(yán)格的一個(gè)分支，被公認(rèn)為是集合論本來是論證很嚴(yán)格的一個(gè)分支，被公認(rèn)為是數(shù)學(xué)的基礎(chǔ)數(shù)學(xué)的基礎(chǔ)在集合論的研究過程中，出現(xiàn)了一次稱作數(shù)學(xué)史上在集合論的研究過程中，出現(xiàn)了一次稱作數(shù)學(xué)史上的第三次大危機(jī)。這次危機(jī)是由于發(fā)

11、現(xiàn)了集合論的的第三次大危機(jī)。這次危機(jī)是由于發(fā)現(xiàn)了集合論的悖論引起。（悖論就是邏輯矛盾）悖論引起。（悖論就是邏輯矛盾） 羅素悖論的提出幾乎動(dòng)搖了整個(gè)數(shù)學(xué)基礎(chǔ)。羅素悖論的提出幾乎動(dòng)搖了整個(gè)數(shù)學(xué)基礎(chǔ)。l羅素悖論中有許多例子，其中一個(gè)很通俗也很羅素悖論中有許多例子，其中一個(gè)很通俗也很有名的例子就是有名的例子就是“理發(fā)師悖論理發(fā)師悖論”：某鄉(xiāng)村有一位理發(fā)師，有一天他宣布：只給不自己某鄉(xiāng)村有一位理發(fā)師，有一天他宣布：只給不自己理發(fā)的人理發(fā)。那么就產(chǎn)生了一個(gè)問題：理發(fā)師究理發(fā)的人理發(fā)。那么就產(chǎn)生了一個(gè)問題：理發(fā)師究竟給不給自己理發(fā)？如果他給自己理發(fā)，他就是自竟給不給自己理發(fā)？如果他給自己理發(fā)，他就是自己理發(fā)

12、的人，按照他的原則，他又不該給自己理發(fā)；己理發(fā)的人，按照他的原則，他又不該給自己理發(fā)；如果他不給自己理發(fā)，那么他就是不自己理發(fā)的人，如果他不給自己理發(fā)，那么他就是不自己理發(fā)的人，按照他的原則，他又應(yīng)該給自己理發(fā)。這就產(chǎn)生了按照他的原則，他又應(yīng)該給自己理發(fā)。這就產(chǎn)生了矛盾。矛盾。l悖論的提出，促使許多數(shù)學(xué)家去研究集悖論的提出，促使許多數(shù)學(xué)家去研究集合論的無矛盾性問題，從而產(chǎn)生了數(shù)理合論的無矛盾性問題，從而產(chǎn)生了數(shù)理邏輯的一個(gè)重要分支邏輯的一個(gè)重要分支公理集合論公理集合論l無理數(shù)的發(fā)現(xiàn)無理數(shù)的發(fā)現(xiàn)-第一次數(shù)學(xué)危機(jī)第一次數(shù)學(xué)危機(jī)畢達(dá)哥拉斯學(xué)派證明了勾股定理，由此發(fā)現(xiàn)畢達(dá)哥拉斯學(xué)派證明了勾股定理，由此

13、發(fā)現(xiàn)一些直角三角形的斜邊不能表示成整數(shù)或整一些直角三角形的斜邊不能表示成整數(shù)或整數(shù)之比（不可通約）數(shù)之比（不可通約）l無窮小是零嗎？無窮小是零嗎？-第二次數(shù)學(xué)危機(jī)第二次數(shù)學(xué)危機(jī)龜兔賽跑，龜兔賽跑，“兔子永遠(yuǎn)追不上烏龜兔子永遠(yuǎn)追不上烏龜”l非歐幾何的產(chǎn)生和集合論的悖論的發(fā)現(xiàn)，非歐幾何的產(chǎn)生和集合論的悖論的發(fā)現(xiàn)，說明數(shù)學(xué)本身還存在許多問題，為了研說明數(shù)學(xué)本身還存在許多問題，為了研究數(shù)學(xué)系統(tǒng)的無矛盾性問題，產(chǎn)生了證究數(shù)學(xué)系統(tǒng)的無矛盾性問題，產(chǎn)生了證明論明論l證明論（證明論（proof theory）證明論是數(shù)學(xué)家證明論是數(shù)學(xué)家D.希爾伯特于希爾伯特于20世紀(jì)初期建立的，目的是要世紀(jì)初期建立的，目的是

14、要證明公理系統(tǒng)的無矛盾性證明公理系統(tǒng)的無矛盾性1931年，年，K.哥德爾證明：一個(gè)包含公理化的算術(shù)的系統(tǒng)中不哥德爾證明：一個(gè)包含公理化的算術(shù)的系統(tǒng)中不能證明它自身的無矛盾性。這就是著名的哥德爾不完備性定能證明它自身的無矛盾性。這就是著名的哥德爾不完備性定理理1936年，年，G.根岑證明了算術(shù)公理系統(tǒng)的無矛盾性根岑證明了算術(shù)公理系統(tǒng)的無矛盾性20世紀(jì)世紀(jì)60年代以后，證明論不再局限于無矛盾性的證明年代以后，證明論不再局限于無矛盾性的證明l歐氏幾何的五條公理是：歐氏幾何的五條公理是：1、任意兩個(gè)點(diǎn)可以通過一條直線連接。、任意兩個(gè)點(diǎn)可以通過一條直線連接。 2、任意線段能無限延伸成一條直線。、任意線段

15、能無限延伸成一條直線。 3、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作一個(gè)圓。一個(gè)圓。 4、所有直角都全等。、所有直角都全等。 5、若兩條直線都與第三條直線相交，并且在同一邊的內(nèi)角之和小于、若兩條直線都與第三條直線相交，并且在同一邊的內(nèi)角之和小于兩個(gè)直角，則這兩條直線在這一邊必定相交。兩個(gè)直角，則這兩條直線在這一邊必定相交。l過直線外一點(diǎn)有且只有一條直線與已知直線平行過直線外一點(diǎn)有且只有一條直線與已知直線平行 l第五條公理稱為平行公理第五條公理稱為平行公理 羅氏幾何的五條公理是：羅氏幾何的五條公理是：1、任意兩個(gè)點(diǎn)可以通過

16、一條直線連接。、任意兩個(gè)點(diǎn)可以通過一條直線連接。 2、任意線段能無限延伸成一條直線。、任意線段能無限延伸成一條直線。 3、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作一個(gè)圓。一個(gè)圓。 4、所有直角都全等。、所有直角都全等。 5、一個(gè)和歐式平行公理相矛盾的命題、一個(gè)和歐式平行公理相矛盾的命題 。 l過直線外一點(diǎn)至少存在兩條直線和已知直線平行過直線外一點(diǎn)至少存在兩條直線和已知直線平行 l黎曼幾何的五條公理是：黎曼幾何的五條公理是：1、任意兩個(gè)點(diǎn)可以通過一條直線連接。、任意兩個(gè)點(diǎn)可以通過一條直線連接。 2、任意線段能無限延伸成一條

17、直線。、任意線段能無限延伸成一條直線。 3、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作、給定任意線段，可以以其一個(gè)端點(diǎn)作為圓心，該線段作為半徑作一個(gè)圓。一個(gè)圓。 4、所有直角都全等。、所有直角都全等。 5、在同一平面內(nèi)任何兩條直線都有公共點(diǎn)、在同一平面內(nèi)任何兩條直線都有公共點(diǎn)(交點(diǎn)交點(diǎn))。 l過直線外一點(diǎn)，不能做直線和已知直線平行過直線外一點(diǎn)，不能做直線和已知直線平行l(wèi)歐氏幾何、羅氏幾何、黎曼幾何是三種各有區(qū)別的幾何。這三中歐氏幾何、羅氏幾何、黎曼幾何是三種各有區(qū)別的幾何。這三中幾何各自所有的命題都構(gòu)成了一個(gè)嚴(yán)密的公理體系，各公理之間幾何各自所有的命題都構(gòu)成了一個(gè)嚴(yán)密的公理體系，

18、各公理之間滿足和諧性、完備性和獨(dú)立性。因此這三種幾何都是正確的。滿足和諧性、完備性和獨(dú)立性。因此這三種幾何都是正確的。(相相容性問題，解決的工具是證明論與模型論）容性問題，解決的工具是證明論與模型論）l在我們這個(gè)不大不小、不遠(yuǎn)不近的空間里，也就是在我們的日常在我們這個(gè)不大不小、不遠(yuǎn)不近的空間里，也就是在我們的日常生活中，歐式幾何是適用的；在宇宙空間中或原子核世界，羅氏生活中，歐式幾何是適用的；在宇宙空間中或原子核世界，羅氏幾何更符合客觀實(shí)際；在地球表面研究航海、航空等實(shí)際問題中，幾何更符合客觀實(shí)際；在地球表面研究航海、航空等實(shí)際問題中，黎曼幾何更準(zhǔn)確一些。黎曼幾何更準(zhǔn)確一些。l愛因斯坦花了四年的時(shí)間，認(rèn)真地學(xué)習(xí)黎曼幾何，后來用黎曼幾愛因斯坦花了四年的時(shí)間，認(rèn)真地學(xué)習(xí)黎曼幾何，后來用黎曼幾何的語言創(chuàng)立和表述了廣義相對(duì)論。何的語言創(chuàng)立和表述了廣義相對(duì)論。 l離散數(shù)學(xué)在信息管理與信息系統(tǒng)專業(yè)中離散數(shù)學(xué)在信息管理與信息系統(tǒng)專業(yè)中的應(yīng)用或分散或隱藏，無處不在的應(yīng)用或分散或隱藏，無處不在l作為基礎(chǔ)課程的離散數(shù)學(xué)的教學(xué)在內(nèi)容作為基