1、離散數(shù)學(xué)的概念離散數(shù)學(xué)(Discrete mathematics)是數(shù)學(xué)的幾個分支的總稱，以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對象一般地是有限個或可數(shù)無窮個元素；是我們計算機學(xué)科的基礎(chǔ)。 序言由于數(shù)字電子計算機是一個離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系， 因此，無論計算機科學(xué)本身，還是與計算機科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計算機加以處理。 離散數(shù)學(xué)課程主要介紹離散數(shù)學(xué)的各個分支的基本概念、基本理論和基本方法。這些概念、理論以及方法大量地應(yīng)用在數(shù)字電路、編譯原理、

2、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、算法的分析與設(shè)計、人工智能、計算機網(wǎng)絡(luò)等專業(yè)課程中；同時，該課程所提供的訓(xùn)練十分有益于學(xué)生概括抽象能力、邏輯思維能力、歸納構(gòu)造能力的提高，十分有益于學(xué)生嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度的培養(yǎng)。 簡而論之，一般認(rèn)為，離散數(shù)學(xué)包括了以下幾個子學(xué)科：數(shù)理邏輯、集合論、關(guān)系論、函數(shù)論、代數(shù)系統(tǒng)與圖論。集合論的學(xué)科起源與發(fā)展第一次數(shù)學(xué)危機的經(jīng)過：公元前一世紀(jì)，古希臘數(shù)學(xué)走到了世界的前列，起很多研究成果甚至領(lǐng)先世界近千年，其中最有代表意義的莫過于“畢達(dá)哥拉斯”學(xué)派。該學(xué)派是一個很專制很嚴(yán)密的組織，它要求成員嚴(yán)守紀(jì)律，對宗師畢達(dá)哥拉斯絕對服從，不允許有任何人跟任何組織冒犯學(xué)派在數(shù)學(xué)

3、上的權(quán)威。畢達(dá)哥拉斯在數(shù)論上曾有過“萬物皆數(shù)”，且“數(shù)”只能是整數(shù)跟分?jǐn)?shù)。但是，畢達(dá)哥拉斯的學(xué)生希帕蘇斯發(fā)現(xiàn)了以下命題:“邊長為1的正方形對角線長度應(yīng)該是多少？”，當(dāng)時勾股定理已經(jīng)得到嚴(yán)格證明，命題于是演變成“什么數(shù)的平方是2？”顯然按照畢達(dá)哥拉斯的理論，這個數(shù)是找不到的，但邊長為1的正方形又確實存在！畢達(dá)哥拉斯感到了恐懼，為了防止泄密，他讓人將希帕蘇斯投入了愛琴海。亞里士多德后來證明了這個正方形的長度并非有理數(shù)，畢達(dá)哥拉斯的絕對權(quán)威受到了嚴(yán)重的挑戰(zhàn)。一方面已經(jīng)證明單位正方形對角線的長不是整數(shù)與分?jǐn)?shù)，按畢達(dá)哥拉斯學(xué)派的觀點，這并不是一個“數(shù)”，這令人難以接受；另一方面，當(dāng)時占統(tǒng)治地位的畢達(dá)哥拉

4、斯學(xué)派對數(shù)的根深蒂固的人數(shù)又使他們不肯承認(rèn)并打壓這種“怪異的數(shù)字”的存在，一時間數(shù)學(xué)界陷入極大的矛盾之中，這就是第一次數(shù)學(xué)危機的由來。十八世紀(jì)，才華橫溢的牛頓跟萊布尼茨幾乎同時發(fā)現(xiàn)了微積分方法，這對于數(shù)學(xué)界來說，有著劃時代的意義。但由于牛萊二人對于微積分這種方法內(nèi)含的原理本身不是很清楚，他們對“流數(shù)”（即我們現(xiàn)在的增量）的表述十分含糊，整個推導(dǎo)過程并不清晰，于是被英國哲學(xué)家，神職人員伯克萊抓到了空子，提出了著名的伯克萊悖論：“因為如果讓增量變?yōu)榱悖蛘哒f沒有任何增量，那么原來關(guān)于增量存在的假設(shè)也就不能成立，而由這一假設(shè)引出的結(jié)果，即借助于增量而得到的表達(dá)式卻必須保留。”按照邏輯上講，伯克萊的悖

5、論是有道理的，牛萊二人的對于微積分方法的推導(dǎo)過程確實存在著邏輯上的致命漏洞！但是對于微積分的實際應(yīng)用卻是擺在那里的，它的實用性不言自明。這樣，伯克萊的批評與諷刺指出了當(dāng)時微積分在理論上的漏洞跟推導(dǎo)過程中的粗糙，一時間，牛萊二人的“微積學(xué)說”跟伯克萊等人的“反微積學(xué)說”爭持激烈，這就是第二次數(shù)學(xué)危機的由來。要說清楚這個問題，我覺得很有必要先跟大家說清楚一個大家都已經(jīng)聞名遐邇但又可能知之不詳?shù)囊粋€相當(dāng)著名的概念數(shù)學(xué)發(fā)展史上出現(xiàn)的三次危機第三次數(shù)學(xué)危機先介紹康托爾（Cantor）這個偉大的數(shù)學(xué)家，集合論的創(chuàng)始人，離散數(shù)學(xué)的奠基者。康托爾1845年岀生于俄國圣彼得堡，后隨父移居法蘭克福，先后在格丁根大

6、學(xué)和法蘭克福大學(xué)里是從外爾斯特拉斯、庫默爾和克羅內(nèi)克，后任哈類大學(xué)教授，或西爾威斯特獎?wù)拢瑢９ゼ兇鈹?shù)學(xué)康托爾是數(shù)學(xué)史上第一個給出集合定義，且引入點集的極限點、閉集、開集、交集、并集等概念的人1874年，康托爾證明了代數(shù)數(shù)集與有理數(shù)集的可數(shù)性和實數(shù)集的不可數(shù)性，同年構(gòu)造了“Cantor”塵集1878年他又引入集合“勢”的概念，且證明了Cantor塵集與實數(shù)集等勢而不可數(shù)，但其測度為零1883年，康托爾證明了著名的“Cantor定理”：一個集合與它的冪集間不可能建立一一對應(yīng)，冪集的勢大于原集合的勢。（冪集的概念是我們的課堂內(nèi)容）1877年，康托爾證明了一條直線上的點與平面上的點（乃至n維空間上的點

7、）一一對應(yīng)1878年，康托爾提出了連續(xù)統(tǒng)假設(shè)（代號CH，continuum hypothesis）：在自然數(shù)的勢與實數(shù)集的 勢之間不存在其他的勢。這個假設(shè)是否成立，至今無人證真或證偽！1883年，康托爾提出良序集和序數(shù)的概念：一個集合，他的元素按確定的順序排列，存在該集合的第一個元素，而且對于每個元素，都存在一個確定的后繼，這樣的集合稱為良序集。舉個例子：自然數(shù)集合1，2n，n+1就是一個良序集，1為第一個元素，n+1是n的后繼。康托爾用w表示自然數(shù)這個良序集的自然順序，而把w寫在緊跟自然數(shù)序列之后，且稱w也是一個“數(shù)”，或稱w為第一個“超窮序數(shù)”，它比所有自然數(shù)都大，是自然數(shù)序列永遠(yuǎn)達(dá)不到的

8、極限康托爾以他那大膽而又浪漫的構(gòu)想，巧奪天工的證明技巧，對數(shù)學(xué)那份執(zhí)著的敏感和新奇的思路，成為了后世數(shù)學(xué)家學(xué)習(xí)跟敬仰的模范，但是在他所處的那個時代，他是一個徹頭徹尾的爭議人物在當(dāng)時，他的理論，尤其是上面說到的“實無窮理論”，更是成為了當(dāng)時主流數(shù)學(xué)界的靶子，為此，他跟他的業(yè)師克羅內(nèi)克翻了臉，用康托爾自身的話說：我已經(jīng)意識到，我必須要跟我的前輩們徹底決裂！事實上，他自己也困于自己的推理世界中不能自拔，當(dāng)他在1877年推出“一一對應(yīng)”理論時，他曾郁悶地向好友戴德金表示：“我看到了這個事實，但連我自己都不敢相信它。”當(dāng)然，他還是相信自己嚴(yán)格證明出的東西是真的，這種自信與質(zhì)疑，纏繞了這個天才的一生。康托

9、爾（Cantor）康托爾的樸素集合論：把一定的并且彼此可以明確識別的事物這種事物，可以是直觀的對象，也可以是思維的對象放在一起，稱為一個集合，這些事物的每一個稱為該集合的每一個元素。其實，作為第三次數(shù)學(xué)危機的主角之一，康托爾已經(jīng)很敏感地認(rèn)識到這種樸素的集合論在邏輯上可能要出事，他向戴德金說過要“禁談一切集合組成的集合”十分可惜的是，這位天才沒有來得及建立一套公理系統(tǒng)給出的集合論以及明確無暇的概念與理論便與世長辭了。果然出事了1902年，羅素提出了著名的“理發(fā)師悖論”：一位鄉(xiāng)村理發(fā)師，宣稱他不給村子里任何自己刮臉的人刮臉，但給所有不自己刮臉的人刮臉。人們問：“那您自己給不給自己刮臉？”理發(fā)師無言

10、以對。的確如果理發(fā)師自己刮臉，那么違背了他自己原則的前半部分，但如果他不自己刮臉，那么按照原則的后一部分，他又必須給自己刮臉，理發(fā)師則陷入深深地矛盾中不能自圓其說。事實上，“理發(fā)師悖論”只是“羅素悖論”的通俗版本，下面我們看一下羅素制造的“仿理發(fā)師悖論”：事實上，有的集合，比如26個字母的集合： = a,b,c,x,y,z 顯然有 不屬于中的元素但有的集合，比如“集合是以10個以上元素的集合為元素組成的集合”。則1，2，3，10，11，1，2，3，10，11，12，1，2，3，10，,n，n+1這些集合皆有10個以上的元素，而的元素個數(shù)也超過10個，故而 。則可見，若根據(jù)康托爾的“樸素集合論”

11、，則會發(fā)生集合不是自己的元素，又會發(fā)生集合是自己元素的現(xiàn)象。那么，羅素構(gòu)造了以下集合：B=A|A不屬于A羅素問：“BB嗎？”我們驚奇地發(fā)現(xiàn)，我們居然無法回答這個問題！若BB，按照B的定義，則B不屬于B，矛盾；若B不屬于B，按照B的定義，則BB，又矛盾！羅素認(rèn)為解決理發(fā)師悖論的根本辦法是宣布世界上根本不存在這種理發(fā)師，或者把理發(fā)師排除在“他給刮臉跟他不給刮臉的人群”之外，也就是說，排除羅素悖論的根本途徑是不承認(rèn)B=A|A不屬于A是一個集合，禁談一個集合是自己本身的元素，即不可以討論BB。 就是這樣，第三次數(shù)學(xué)危機爆發(fā)了，突破口是天才數(shù)學(xué)家康托爾的樸素集合論。自此之后，一大群數(shù)學(xué)精英為了推進(jìn)數(shù)論的

12、發(fā)展，先后為剔除“羅素悖論”前赴后繼.其中，以法國數(shù)學(xué)家策墨羅提出的方案最為徹底，他跟弗倫克爾合作提出一套ZF公理，策墨羅是這樣評價這個方案的：從現(xiàn)有的集合論成果出發(fā)，建立這一數(shù)學(xué)分支的原則，這些原則必須足夠狹窄，以保證排除一切矛盾；另一方面，又必須充分廣闊，使得康托爾集合論中一切有價值的東西得以保留。在ZF公理出現(xiàn)以前，人們可以自由地構(gòu)造集合x|(x)，其中(x)是對該集合中的元素性質(zhì)的一種描述，正是這樣的限制不夠嚴(yán)格地隨意制集合才導(dǎo)致了羅素悖論。對此，ZF公理的辦法是：必須先有一個集合A，在A中選擇滿足性質(zhì)(x)的元素來構(gòu)造另一個集合（A的子集），包含一切集的集合不存在。這也叫公理集合論ZF公理較好的 解決了第三次數(shù)學(xué)危機，到目前為止，還沒有人發(fā)現(xiàn)任何悖論或者矛盾。在這個歷史背景下去評論它，無疑是成功的。在一大群數(shù)學(xué)家的不懈努力下，消除悖論的努力成為了集合論發(fā)展的巨大推動力，比如說外延公理、空集公理、分離公理、冪集公理、并集公理、選擇公理和無窮公理共七個公理的集合論體系，這個就是策墨羅所提出的ZF系統(tǒng)的理論基礎(chǔ)。但是我們也應(yīng)該清楚，其實嚴(yán)格來講，羅素悖論不是被剔除了，只不過是被避開了。雖然集合論公理化運動是假定了數(shù)學(xué)運用的邏輯本身不成問題，但數(shù)學(xué)家們對于這一前提陸續(xù)提出了不同的觀點，并形成了關(guān)于數(shù)