離散數(shù)學(xué)的概念第1頁，課件共12頁，創(chuàng)作于2023年2月由于數(shù)字電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系，因此，無論計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對(duì)離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計(jì)算機(jī)加以處理。

離散數(shù)學(xué)課程主要介紹離散數(shù)學(xué)的各個(gè)分支的基本概念、基本理論和基本方法。這些概念、理論以及方法大量地應(yīng)用在數(shù)字電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、算法的分析與設(shè)計(jì)、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)等專業(yè)課程中；同時(shí)，該課程所提供的訓(xùn)練十分有益于學(xué)生概括抽象能力、邏輯思維能力、歸納構(gòu)造能力的提高，十分有益于學(xué)生嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度的培養(yǎng)。

第2頁，課件共12頁，創(chuàng)作于2023年2月簡而論之，一般認(rèn)為，離散數(shù)學(xué)包括了以下幾個(gè)子學(xué)科：數(shù)理邏輯、集合論、關(guān)系論、函數(shù)論、代數(shù)系統(tǒng)與圖論。第3頁，課件共12頁，創(chuàng)作于2023年2月集合論的學(xué)科起源與發(fā)展第4頁，課件共12頁，創(chuàng)作于2023年2月第一次數(shù)學(xué)危機(jī)的經(jīng)過：公元前一世紀(jì)，，古希臘數(shù)學(xué)走到了世界的前列，起很多研究成果甚至領(lǐng)先世界近千年，其中最有代表意義的莫過于“畢達(dá)哥拉斯”學(xué)派。該學(xué)派是一個(gè)很專制很嚴(yán)密的組織，它要求成員嚴(yán)守紀(jì)律，對(duì)宗師畢達(dá)哥拉斯絕對(duì)服從，不允許有任何人跟任何組織冒犯學(xué)派在數(shù)學(xué)上的權(quán)威。畢達(dá)哥拉斯在數(shù)論上曾有過“萬物皆數(shù)”，且“數(shù)”只能是整數(shù)跟分?jǐn)?shù)。但是，畢達(dá)哥拉斯的學(xué)生希帕蘇斯發(fā)現(xiàn)了以下命題:“邊長為1的正方形對(duì)角線長度應(yīng)該是多少？”，當(dāng)時(shí)勾股定理已經(jīng)得到嚴(yán)格證明，命題于是演變成“什么數(shù)的平方是2？”顯然按照畢達(dá)哥拉斯的理論，這個(gè)數(shù)是找不到的，但邊長為1的正方形又確實(shí)存在！畢達(dá)哥拉斯感到了恐懼，為了防止泄密，他讓人將希帕蘇斯投入了愛琴海。亞里士多德后來證明了這個(gè)正方形的長度并非有理數(shù)，畢達(dá)哥拉斯的絕對(duì)權(quán)威受到了嚴(yán)重的挑戰(zhàn)。一方面已經(jīng)證明單位正方形對(duì)角線的長不是整數(shù)與分?jǐn)?shù)，按畢達(dá)哥拉斯學(xué)派的觀點(diǎn)，這并不是一個(gè)“數(shù)”，這令人難以接受；另一方面，當(dāng)時(shí)占統(tǒng)治地位的畢達(dá)哥拉斯學(xué)派對(duì)數(shù)的根深蒂固的人數(shù)又使他們不肯承認(rèn)并打壓這種“怪異的數(shù)字”的存在，一時(shí)間數(shù)學(xué)界陷入極大的矛盾之中，這就是第一次數(shù)學(xué)危機(jī)的由來。十八世紀(jì)，才華橫溢的牛頓跟萊布尼茨幾乎同時(shí)發(fā)現(xiàn)了微積分方法，這對(duì)于數(shù)學(xué)界來說，有著劃時(shí)代的意義。但由于牛萊二人對(duì)于微積分這種方法內(nèi)含的原理本身不是很清楚，他們對(duì)“流數(shù)”（即我們現(xiàn)在的增量）的表述十分含糊，整個(gè)推導(dǎo)過程并不清晰，于是被英國哲學(xué)家，神職人員伯克萊抓到了空子，提出了著名的伯克萊悖論：“因?yàn)槿绻屧隽孔優(yōu)榱?，或者說沒有任何增量，那么原來關(guān)于增量存在的假設(shè)也就不能成立，而由這一假設(shè)引出的結(jié)果，即借助于增量而得到的表達(dá)式卻必須保留?！卑凑者壿嬌现v，伯克萊的悖論是有道理的，牛萊二人的對(duì)于微積分方法的推導(dǎo)過程確實(shí)存在著邏輯上的致命漏洞！但是對(duì)于微積分的實(shí)際應(yīng)用卻是擺在那里的，它的實(shí)用性不言自明。這樣，伯克萊的批評(píng)與諷刺指出了當(dāng)時(shí)微積分在理論上的漏洞跟推導(dǎo)過程中的粗糙，一時(shí)間，牛萊二人的“微積學(xué)說”跟伯克萊等人的“反微積學(xué)說”爭持激烈，這就是第二次數(shù)學(xué)危機(jī)的由來。要說清楚這個(gè)問題，我覺得很有必要先跟大家說清楚一個(gè)大家都已經(jīng)聞名遐邇但又可能知之不詳?shù)囊粋€(gè)相當(dāng)著名的概念——數(shù)學(xué)發(fā)展史上出現(xiàn)的三次危機(jī)第5頁，課件共12頁，創(chuàng)作于2023年2月第三次數(shù)學(xué)危機(jī)先介紹康托爾（Cantor）這個(gè)偉大的數(shù)學(xué)家，集合論的創(chuàng)始人，離散數(shù)學(xué)的奠基者?？低袪?845年岀生于俄國圣彼得堡，后隨父移居法蘭克福，先后在格丁根大學(xué)和法蘭克福大學(xué)里是從外爾斯特拉斯、庫默爾和克羅內(nèi)克，后任哈類大學(xué)教授，或西爾威斯特獎(jiǎng)?wù)拢瑢９ゼ兇鈹?shù)學(xué)康托爾是數(shù)學(xué)史上第一個(gè)給出集合定義，且引入點(diǎn)集的極限點(diǎn)、閉集、開集、交集、并集等概念的人1874年，康托爾證明了代數(shù)數(shù)集與有理數(shù)集的可數(shù)性和實(shí)數(shù)集的不可數(shù)性，同年構(gòu)造了“Cantor”塵集1878年他又引入集合“勢”的概念，且證明了Cantor塵集與實(shí)數(shù)集等勢而不可數(shù)，但其測度為零1883年，康托爾證明了著名的“Cantor定理”：一個(gè)集合與它的冪集間不可能建立一一對(duì)應(yīng)，冪集的勢大于原集合的勢。（冪集的概念是我們的課堂內(nèi)容）1877年，康托爾證明了一條直線上的點(diǎn)與平面上的點(diǎn)（乃至n維空間上的點(diǎn)）一一對(duì)應(yīng)1878年，康托爾提出了連續(xù)統(tǒng)假設(shè)（代號(hào)CH，continuumhypothesis）：在自然數(shù)的勢與實(shí)數(shù)集的勢之間不存在其他的勢。這個(gè)假設(shè)是否成立，至今無人證真或證偽！1883年，康托爾提出良序集和序數(shù)的概念：一個(gè)集合，他的元素按確定的順序排列，存在該集合的第一個(gè)元素，而且對(duì)于每個(gè)元素，都存在一個(gè)確定的后繼，這樣的集合稱為良序集。舉個(gè)例子：自然數(shù)集合1，2…n，n+1就是一個(gè)良序集，1為第一個(gè)元素，n+1是n的后繼。第6頁，課件共12頁，創(chuàng)作于2023年2月康托爾用w表示自然數(shù)這個(gè)良序集的自然順序，而把w寫在緊跟自然數(shù)序列之后，且稱w也是一個(gè)“數(shù)”，或稱w為第一個(gè)“超窮序數(shù)”，它比所有自然數(shù)都大，是自然數(shù)序列永遠(yuǎn)達(dá)不到的極限康托爾以他那大膽而又浪漫的構(gòu)想，巧奪天工的證明技巧，對(duì)數(shù)學(xué)那份執(zhí)著的敏感和新奇的思路，成為了后世數(shù)學(xué)家學(xué)習(xí)跟敬仰的模范，但是在他所處的那個(gè)時(shí)代，他是一個(gè)徹頭徹尾的爭議人物在當(dāng)時(shí)，他的理論，尤其是上面說到的“實(shí)無窮理論”，更是成為了當(dāng)時(shí)主流數(shù)學(xué)界的靶子，為此，他跟他的業(yè)師克羅內(nèi)克翻了臉，用康托爾自身的話說：我已經(jīng)意識(shí)到，我必須要跟我的前輩們徹底決裂！事實(shí)上，他自己也困于自己的推理世界中不能自拔，當(dāng)他在1877年推出“一一對(duì)應(yīng)”理論時(shí)，他曾郁悶地向好友戴德金表示：“我看到了這個(gè)事實(shí)，但連我自己都不敢相信它?！碑?dāng)然，他還是相信自己嚴(yán)格證明出的東西是真的，這種自信與質(zhì)疑，纏繞了這個(gè)天才的一生?？低袪枺–antor）第7頁，課件共12頁，創(chuàng)作于2023年2月康托爾的樸素集合論：把一定的并且彼此可以明確識(shí)別的事物——這種事物，可以是直觀的對(duì)象，也可以是思維的對(duì)象——放在一起，稱為一個(gè)集合，這些事物的每一個(gè)稱為該集合的每一個(gè)元素。其實(shí)，作為第三次數(shù)學(xué)危機(jī)的主角之一，康托爾已經(jīng)很敏感地認(rèn)識(shí)到這種樸素的集合論在邏輯上可能要出事，他向戴德金說過要“禁談一切集合組成的集合”十分可惜的是，這位天才沒有來得及建立一套公理系統(tǒng)給出的集合論以及明確無暇的概念與理論便與世長辭了。第8頁，課件共12頁，創(chuàng)作于2023年2月果然出事了1902年，羅素提出了著名的“理發(fā)師悖論”：一位鄉(xiāng)村理發(fā)師，宣稱他不給村子里任何自己刮臉的人刮臉，但給所有不自己刮臉的人刮臉。人們問：“那您自己給不給自己刮臉？”理發(fā)師無言以對(duì)。的確如果理發(fā)師自己刮臉，那么違背了他自己原則的前半部分，但如果他不自己刮臉，那么按照原則的后一部分，他又必須給自己刮臉，理發(fā)師則陷入深深地矛盾中不能自圓其說。第9頁，課件共12頁，創(chuàng)作于2023年2月事實(shí)上，“理發(fā)師悖論”只是“羅素悖論”的通俗版本，下面我們看一下羅素制造的“仿理發(fā)師悖論”：事實(shí)上，有的集合，比如26個(gè)字母的集合：?={a,b,c,…,x,y,z}

顯然有?不屬于?中的元素但有的集合，比如“集合β是以10個(gè)以上元素的集合為元素組成的集合”。則{1，2，3…，10，11}，{1，2，3…，10，11，12}，…{1，2，3…，10，…,n，n+1}這些集合皆有10個(gè)以上的元素，而β的元素個(gè)數(shù)也超過10個(gè)，故而β∈β。則可見，若根據(jù)康托爾的“樸素集合論”，則會(huì)發(fā)生集合不是自己的元素，又會(huì)發(fā)生集合是自己元素的現(xiàn)象。那么，羅素構(gòu)造了以下集合：B={A|A不屬于A}羅素問：“B∈B嗎？”我們驚奇地發(fā)現(xiàn)，我們居然無法回答這個(gè)問題！若B∈B，按照B的定義，則B不屬于B，矛盾；若B不屬于B，按照B的定義，則B∈B，又矛盾！羅素認(rèn)為解決理發(fā)師悖論的根本辦法是宣布世界上根本不存在這種理發(fā)師，或者把理發(fā)師排除在“他給刮臉跟他不給刮臉的人群”之外，也就是說，排除羅素悖論的根本途徑是不承認(rèn)B={A|A不屬于A}是一個(gè)集合，禁談一個(gè)集合是自己本身的元素，即不可以討論B∈B。

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