離散數(shù)學的概念

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

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

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

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