集合論即其與計算機(jī)相關(guān)的問題

1、百度文庫集合論1、集合論的歷史。/集合論是一門研究數(shù)學(xué)基礎(chǔ)的學(xué)科。 集合論是現(xiàn)代數(shù)學(xué)的基礎(chǔ)，是數(shù)學(xué)不可 或缺的基本描述工具?？梢赃@樣講，現(xiàn)代數(shù)學(xué)與離散數(shù)學(xué)的“大廈”是建立在集 合論的基礎(chǔ)之上的。21世紀(jì)數(shù)學(xué)中最為深刻的活動，就是關(guān)于數(shù)學(xué)基礎(chǔ)的探討。 這不僅涉及到數(shù)學(xué)的本性，也涉及到演繹數(shù)學(xué)的正確性。數(shù)學(xué)中若干悖論的發(fā)現(xiàn)， 引發(fā)了數(shù)學(xué)史上的第三次危機(jī)，而這種悖論在集合論中尤為突出。/ 集合論是德國著名數(shù)學(xué)家康托爾于19世紀(jì)末創(chuàng)立的。十七世紀(jì)數(shù)學(xué)中出現(xiàn)了一門新的分支： 微積分。在之后的一二百年中這一嶄 新學(xué)科獲得了飛速發(fā)展并結(jié)出了豐碩成果。其推進(jìn)速度之快使人來不及檢查和鞏 固它的理論基礎(chǔ)。十九世紀(jì)

2、初，許多迫切問題得到解決后，出現(xiàn)了一場重建數(shù)學(xué)二 基礎(chǔ)的運(yùn)動。正是在這場運(yùn)動中，康托爾開始探討了前人從未碰過的實數(shù)點集， 這是集合論研究的開端。1874年，德國數(shù)學(xué)家康托爾在著名的克雷爾數(shù)學(xué)雜 志上發(fā)表了關(guān)于無窮集合論的第一章革命性文章。從1874年到1884年，康托爾的一系列關(guān)于集合的文章，奠定了集合論的基礎(chǔ)。他對集合所下的定義是：把 若干確定的、有區(qū)別的(不論是具體的或抽象的)事物合并起來，看作一個整體， 其中各事物稱為該集合的元素。沒想到集合論一誕生就遭到了許多數(shù)學(xué)家的激烈反對，當(dāng)時的權(quán)威數(shù)學(xué)家克羅內(nèi)克(Kronecker)非常敵視康托爾的集合論思想，時間達(dá)整整十年之久，法國 數(shù)學(xué)大家龐

3、加萊(Poincare)則預(yù)測后一代人將把集合論當(dāng)作一種疾病。在猛烈的 攻擊下與過度的用腦思考中，康托爾本人一度成為這一激烈論爭的犧牲品，他得了精神分裂癥，幾次陷于精神崩潰。然而烏云遮不住太陽，經(jīng)歷二十余年后，集合論最終獲得了世界公認(rèn)。到二 十世紀(jì)初集合論已得到數(shù)學(xué)家們的贊同。數(shù)學(xué)家們樂觀地認(rèn)為從算術(shù)公理系統(tǒng)出 發(fā)，只要借助集合論的概念，便可以建造起整個數(shù)學(xué)的大廈。在1900年第二次國際數(shù)學(xué)大會上，著名數(shù)學(xué)家龐加萊就曾興高采烈地宣布“數(shù)學(xué)已被算術(shù)化 了。我們可以說，現(xiàn)在數(shù)學(xué)已經(jīng)達(dá)到了絕對的嚴(yán)格?！比欢@種自得的情緒并沒 能持續(xù)多久。英國哲學(xué)家羅素(Russell)就很懷疑數(shù)學(xué)的這種嚴(yán)密性，他經(jīng)

4、過三百度文庫年的苦思冥想，于1902年找到了一個能證明自己觀點的簡單明確的 “羅素悖論”。 不久，集合論是有漏洞的消息迅速就傳遍了數(shù)學(xué)界。羅素構(gòu)造了一個所有不屬于自身（即不包含自身作為元素）的集合R?，F(xiàn)在問R是否屬于R?如果R屬于R,則R滿足R的定義，因此R不應(yīng)屬于自身，即 R不屬于R另一方面/如果R不屬于R,則R不滿足R的定義，因此R應(yīng)屬于 自身，即R屬于R這樣，不論何種情況都存在著矛盾（為了使羅素悖論更加通 俗易懂，羅素本人在1919年將其改寫為“理發(fā)師悖論”）。這一僅涉及集合與屬 于兩個最基本概念的悖論如此簡單明了以致根本留不下為集合論漏洞辯解的余 地。號稱“天衣無縫”、“絕對嚴(yán)密”的數(shù)

5、學(xué)陷入了自相矛盾之中。從此整個數(shù)學(xué) 的基礎(chǔ)被動搖了，由此引發(fā)了數(shù)學(xué)史上的第三次數(shù)學(xué)危機(jī)。危機(jī)產(chǎn)生后，眾多數(shù)學(xué)家投入到解決危機(jī)的工作中去。1908年，德國數(shù)學(xué)家策梅羅提出公理化集合論，試圖把集合論公理化的方法來消除悖論。 他認(rèn)為悖 論的出現(xiàn)是由于康托爾沒有把集合的概念加以限制，康托爾對集合的定義是含混的.策梅羅希望簡潔的公理能使集合的定義及其具有的性II更為顯然。策梅羅的公理化集合論后來演變成ZF或ZFS公理系統(tǒng)。從此原本直觀的集合概念被建立 在嚴(yán)格的公理基礎(chǔ)之上，從而避免了悖論的出現(xiàn)。這就是集合論發(fā)展的第二個階 段：公理化集合論。與此相對應(yīng)，在 1908年以前由康托爾創(chuàng)立的集合論被稱為 樸素集

6、合論。公理化集合論是對樸素集合論的嚴(yán)格處理。 它保留了樸素集合論的 有價值的成果并消除了其可能存在的悖論，因而較圓滿地解決了第三次數(shù)學(xué)危 機(jī)。公理化集合論的建立，標(biāo)志著著名數(shù)學(xué)家希耳伯特所表述的一種激情的勝利， 他大聲疾呼：沒有人能把我們從康托爾為我們創(chuàng)造的樂園中趕出去。2、集合論在計算科學(xué)中的應(yīng)用。/起初，集合論主要是對分析數(shù)學(xué)中的“數(shù)集”或幾何學(xué)中的“點集”進(jìn)行研 究。但是隨著科學(xué)的發(fā)展, 集合論的概念已經(jīng)深入到現(xiàn)代各個方面，成為表達(dá)各 種嚴(yán)謹(jǐn)科學(xué)概念必不可少的數(shù)學(xué)語言。隨著計算機(jī)時代的到來，集合的元素已由傳統(tǒng)的“數(shù)集”和“點集”拓展成 包含文字、符號、圖形、圖表和聲音等多媒體信息，構(gòu)成了

7、各種數(shù)據(jù)類型的集合。 集合不僅可以用來表示數(shù)及其運(yùn)算， 更可以用來表示和處理非數(shù)值信息。 數(shù)據(jù)的百度文庫增加、刪除、修改、排序以及數(shù)據(jù)間關(guān)系的描述等這些很難用傳統(tǒng)的數(shù)值計算操 作，可以很方便地用集合運(yùn)算來處理。從而集合論在編譯原理、開關(guān)理論、信息 檢索、形式語言、數(shù)據(jù)庫和知識庫、 CAD CAM CAI及AI等各個領(lǐng)域得到了廣 泛的應(yīng)用，而且還得到了發(fā)展，如扎德 （Zadeh）的模糊集理論和保拉克（Pawlak） 的粗糙集理論等等。集合論的方法已經(jīng)成為計算科學(xué)工作者不可缺少的數(shù)學(xué)基礎(chǔ) 知識。3、公理化方法及其作用。、/ 在計算科學(xué)的發(fā)展中，公理化方法曾在一些分支學(xué)科的發(fā)展中得到廣泛應(yīng)用 并產(chǎn)生

8、重要的影響。例如，在形式語義學(xué)和程序理論的研究中， 公理語義學(xué)一直 占有重要的地位。一些軟件開發(fā)工具也是用到了這種思想。那么什么是公理化方法呢？所謂公理化方法， 就是從盡可能少的無需定義的 原始概念（基本概念）和盡可能少的一組不加證明的原始命題（基本公理、公設(shè)） 出發(fā)，應(yīng)用嚴(yán)格的邏輯推理規(guī)則，用演繹推理來對一門學(xué)科進(jìn)行研究的方法。公理系統(tǒng)有一定的要求：無矛盾性、完備性和獨立性。顯然，在構(gòu)建一門完 整的科學(xué)理論體系時，所建立的公理系統(tǒng)必須無矛盾性，即在該系統(tǒng)中不能推出 自相矛盾的結(jié)論。另外，完備性要求所建立的公理系統(tǒng)應(yīng)盡可能多地推出這門科 學(xué)中已經(jīng)客觀存在的結(jié)論，最好是能推出全部的結(jié)論（但哥德爾

9、（Godel）業(yè)已證明完備的公理系統(tǒng)是不存在的）。獨立性要求基本公理不多不少，任何一條公理 都不能從其他公理中推出來。對一門科學(xué)公理化的目的是在于把該門學(xué)科表述為一個演繹系統(tǒng)，并通過對基本概念的選取、公理的設(shè)計，以及嚴(yán)格的演繹推理過程的研究， 揭示這門學(xué)科 深刻的內(nèi)在規(guī)律,*確保這門學(xué)科的表述更加嚴(yán)謹(jǐn)、 準(zhǔn)確。公理化方法主要有如下 的作用：（1）分析和總結(jié)學(xué)科知識的作用；（2）把學(xué)科的基礎(chǔ)搞清楚的作用，從 而有助于在學(xué)科的深層次比較和統(tǒng)一不同的子學(xué)科，啟發(fā)、促進(jìn)和推動新理論的創(chuàng)立；（3）在科學(xué)方法論上有示范作用，它對各門學(xué)科新建立具有很好的借鑒作用。百度文庫4、關(guān)系在關(guān)系數(shù)據(jù)庫中的應(yīng)用。數(shù)據(jù)庫

10、是計算機(jī)管理數(shù)據(jù)的一種機(jī)構(gòu)叭它由兩部分組成：一部分是存儲數(shù)據(jù) 的存儲空間，另一部分是管理數(shù)據(jù)的一組程序即數(shù)據(jù)庫管理系統(tǒng)，簡稱 DBMS 用戶通過DBMSI供的語言對數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行處理：數(shù)據(jù)的檢索、數(shù)據(jù)的插 入、數(shù)據(jù)的修改和數(shù)據(jù)的刪除。用戶使用數(shù)據(jù)庫中數(shù)據(jù)的速度取決于數(shù)據(jù)存儲的方式數(shù)據(jù)庫目前有三種上 結(jié)構(gòu)模型：層次模型、網(wǎng)絡(luò)模型和關(guān)系模型。關(guān)系模型是基于關(guān)系理論的模型， 而采用關(guān)系模型作為結(jié)構(gòu)模型的數(shù)據(jù)庫就叫關(guān)系數(shù)據(jù)庫。/ 在關(guān)系數(shù)據(jù)庫中，數(shù)據(jù)庫就是一個n元關(guān)系，在計算機(jī)中存放在一個二維數(shù) 組中。一個二維數(shù)組可以有 m行和n歹I，其中每一行的分量組成一個n元組，它 是一條記錄，代表一個完整的

11、數(shù)據(jù)，它的分量稱為記錄的域。對應(yīng)的實體可以有 m條記錄（m個數(shù)據(jù)）。用戶使用關(guān)系數(shù)據(jù)庫就是對一些二維數(shù)組進(jìn)行檢索、插入、修改和刪除等操作。為此DBM泌須向用戶提供使用數(shù)據(jù)庫的語言，即數(shù)據(jù)子語言。這種語言目 前是以關(guān)系代數(shù)或謂詞邏輯等方法表示的，即它是以關(guān)系代數(shù)或謂詞邏輯為其數(shù) 學(xué)基礎(chǔ)。由于引入了數(shù)學(xué)方法，使得關(guān)系數(shù)據(jù)庫具有比其他幾種數(shù)據(jù)庫更優(yōu)越， 從而關(guān)系數(shù)據(jù)庫這幾年得到了迅猛的發(fā)展，日前已代替其他類型的數(shù)據(jù)庫。當(dāng)今 流行的各種大型網(wǎng)絡(luò)數(shù)據(jù)庫如 Oracle、Foxpro、Sybase等都是關(guān)系型數(shù)據(jù)庫。 它已經(jīng)成為數(shù)據(jù)庫中最有實用價值和理論價值的數(shù)據(jù)庫。5、關(guān)系在計算科學(xué)中的應(yīng)用。關(guān)系這一概

12、念對計算科學(xué)的理論和應(yīng)用是非常重要的。像鏈表、樹等復(fù)合的 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)都是由元素之間的關(guān)系來聯(lián)系的。另外由于關(guān)系是數(shù)學(xué)模型的一部分，故它常常在數(shù)據(jù)結(jié)構(gòu)內(nèi)隱含地體現(xiàn)出來。數(shù)值應(yīng)用、信息檢索、網(wǎng)絡(luò)問 題等也是關(guān)系的應(yīng)用領(lǐng)域叭 在這些領(lǐng)域中關(guān)系作為問題描述的一部分出現(xiàn)，因而為了解決問題，關(guān)系的運(yùn)算和處理是重要的。關(guān)系在包括程序結(jié)構(gòu)和算法分析的 計算理論方面也有重要的作用，如主程序和子程序的調(diào)用關(guān)系、高級語言編程中 經(jīng)常用到的函數(shù)（對應(yīng)關(guān)系）、程序的輸入與輸出關(guān)系、計算機(jī)語言中的字符關(guān) 系、OO啕程中的類繼承關(guān)系等等。百度文庫6、劃分（等價關(guān)系）在信息檢索中的應(yīng)用。在日常生活中或在科學(xué)研究中，我們

13、常常需要對一些事物按照某種方式進(jìn)行 分類。如將全中國人分成兩類：男公民和女公民、將所有參賽的運(yùn)動員分成不同 的重量級別進(jìn)行舉重比賽；將所有的整數(shù)按模10同余關(guān)系分成10類：如果兩個 整數(shù)的差是10的倍數(shù)，則這兩個整數(shù)屬于同一個類。抽象地講，就是需要對某 個集合中的元素按照某種方式進(jìn)行分類（集合的劃分）。集合的劃分與等價關(guān)系 密切相關(guān)。/ 而對信息和數(shù)據(jù)進(jìn)行分類正是計算機(jī)的重要處理之一。分類的目的在于研究每一類中對象的共性。在信息檢索系統(tǒng)中，根據(jù)一個主碼進(jìn)行檢索，可把全體信息分成兩個劃分塊 （劃分）。不同的主碼對應(yīng)的分類是不同的。指定一個主碼，在對應(yīng)的劃分的每 個劃分塊里按指定第二個主碼進(jìn)行分類

14、，則可以得到全體信息的新的更細(xì)的劃分 （有4個劃分塊），這相當(dāng)于在檢索中在兩個主碼之間使用了邏輯聯(lián)結(jié)詞 AND 得到的4個劃分塊中的每個塊類分別是兩個主碼對應(yīng)的劃分中劃分塊的交。若在兩個主碼之間使用了邏輯聯(lián)結(jié)詞 OR則得到的4個類中的每個類分別是兩個主 碼對應(yīng)的劃分中劃分塊的并（這4個類不是兩兩不相交的，故不構(gòu)成全體信息的 一個劃分）。7、序關(guān)系在計算科學(xué)中的應(yīng)用。集合元素間的序關(guān)系與元素間的等價關(guān)系一樣也是一種重要的關(guān)系。根據(jù)等 價關(guān)系可以將集合中的元素進(jìn)行劃分，而根據(jù)序關(guān)系則可以將集合中的元素進(jìn)行排序。只有有了一定的序關(guān)系，才能對數(shù)據(jù)庫中的“信息”與“數(shù)據(jù)”進(jìn)行存 儲、加工和傳輸。序關(guān)系對

15、于情報檢索、數(shù)據(jù)處理、信息傳輸、程序運(yùn)行等都是 極為重要的。如計算機(jī)程序執(zhí)行時往往是“串行”的，這就涉及到了序關(guān)系（程 序執(zhí)行的先后問題；即使是“并行”處理，也不可避免地存在瞬間的先后問題。 另外面向?qū)ο缶幊讨械念惱^承關(guān)系、結(jié)構(gòu)化程序設(shè)計中的函數(shù)或子程序調(diào)用關(guān)系 都是序關(guān)系的應(yīng)用實例。百度文庫8、集合論中的悖論。所謂悖論就是邏輯矛盾：如果假定語句所指為真，那么會推出語句所指為假； 反之，如果假定語句所指為假，又會推出語句所指為真。真是說它對也不是，不 對也不是，讓人左右為難。古今中外有不少著名的悖論，它們震撼了邏輯和數(shù)學(xué) 的基礎(chǔ)，激發(fā)了人們求知和精密的思考，吸引了古往今來許多思想家和愛好者的

16、注意力。解決悖論難題需要創(chuàng)造性的思考，因此悖論的解決往往可以給人帶來全 新的觀念，從而悖論的出現(xiàn)和解決往往成為數(shù)學(xué)發(fā)展的一種內(nèi)在動力。1) /理發(fā)師悖論：在薩維爾村，理發(fā)師掛出一塊招牌：“我只給村里所有那 些不給自己理發(fā)的人理發(fā)?！庇腥藛査骸澳憬o不給自己理發(fā)？”理發(fā)師頓時無 言以對。因為這是一個矛盾推理：如果理發(fā)師不給自己理發(fā)，他就屬于招牌上的那一 類人。有言在先，他應(yīng)該給自己理發(fā)。反之，如果這個理發(fā)師給他自己理發(fā)，根 據(jù)招牌所言，他只給村中不給自己理發(fā)的人理發(fā)，他不能給自己理發(fā)。因此，無論這個理發(fā)師怎么回答，都不能排除內(nèi)在的矛盾。這個悖論是羅素 給出的對一九。二年提出來的集合論悖論-“羅素

17、悖論”所作的一個通俗的、有 故事情節(jié)的表述。2)由“自指”引發(fā)的悖論：有人說“我在說慌”。如果他在說謊，那么“我 在說謊”就是一個謊，因此他說的是實話；但是如果這是實話，他又在說謊。矛 盾不可避免。它的一個翻版是：“這句話是錯的”。這類悖論的一個標(biāo)準(zhǔn)形式是：如果事件A發(fā)生，則推導(dǎo)出非A ,非A發(fā)生則 推導(dǎo)出A,這是一個自相矛盾的無限邏輯循環(huán)。3)集合論悖論一“羅素悖論”：“R是所有不包含自身的集合的集合?！?這 是羅素(B. Russell)由于懷疑數(shù)學(xué)基礎(chǔ)的嚴(yán)密性，于 1902年找到的悖論。用集 合的描述性定義方式可定義為 R=S|S S。于是就產(chǎn)生了這樣的邏輯矛盾：若 R 包含R本身，則根

18、據(jù)R的定義，R R,即R不屬于Ro若R不包含R本身，即R R, 則根據(jù)R的定義，R R,即R包含Ro4)書目悖論：一個圖書館編纂了一本書名詞典，它列出這個圖書館里所有 不列出自己書名的書。那么它列不列出自己的書名？這個悖論與理發(fā)師悖論基本一致。百度文庫5）最大集合論悖論：存在一個最大的集合，它是包含一切集合的集合。若 設(shè)這個最大的集合是A,現(xiàn)在問：A是否包含它自己？如果 A包含它自己，那么 A就是A所包含的元素，于是A就不是最大的集合，與定義矛盾；而如果 A不包 含A,那么A就不是包含一切集合的集合，也與定義矛盾。無論 A是否是最大的 集合都會推出矛盾，這就是最大集合悖論。這也和“羅素悖論”類

19、似。9、悖論對數(shù)學(xué)發(fā)展的積極作用。/ 悖論并非一無是處。雖然他們的出現(xiàn)會直接導(dǎo)致“數(shù)學(xué)危機(jī)”的產(chǎn)生，但是 悖論的出現(xiàn)逼迫數(shù)學(xué)家投入最大的熱情去解決它們。而在解決悖論的過程中，數(shù)學(xué)本身也得到了發(fā)展。第二次數(shù)學(xué)危機(jī)導(dǎo)源于微積分工具的使用。 微積分這一銳利無比的數(shù)學(xué)工具、 問世。許許多多疑難問題運(yùn)用這一工具后變得易如翻掌，從而顯示出了它的非凡 威力。但是不管是牛頓、還是萊布尼茲所創(chuàng)立的微積分理論都是不嚴(yán)格的。兩人的理論都建立在無窮小分析之上，但他們對作為基本概念的無窮小量的理解與運(yùn) 用卻是混亂的。因而，微積分一誕生就遭到了一些人的反對與攻擊。其中攻擊最猛烈的是英國大主教貝克萊。貝克萊對牛頓的理論進(jìn)行

20、了攻擊。 他提出的問題在數(shù)學(xué)史上稱為“貝克萊悖 論”?；\統(tǒng)地說，貝克萊悖論可以表述為“無窮小量究竟是否為0”的問題。就無窮小量在當(dāng)時的實際應(yīng)用而言， 它必須既是0,又不是00但從形式邏輯而言， 這無疑是一個矛盾。另外古希臘的大詭辯家芝諾（Zeno）的幾個悖論阿基里斯悖論、二分法悖論（運(yùn)動不存在）、“飛矢不動”悖論也反映出了有限與無限、無 窮小與零、零與非零的邏輯矛盾。這些悖論在當(dāng)時的數(shù)學(xué)界引起了一定的混亂， 導(dǎo)致了第二次數(shù)學(xué)危機(jī)的產(chǎn)生。為解決這一悖論，無數(shù)人投入了大量的勞動。法國數(shù)學(xué)家柯西首先給出了極 限的定義；”若代表某變量的一串?dāng)?shù)值無限地趨向于某一數(shù)值時，其差可任意小，則該固定值稱為這一用

21、數(shù)值的極限”?？挛髦?，魏爾斯特拉斯、戴德金、康托 爾各自經(jīng)過自己獨立深入的研究， 都將分析基礎(chǔ)歸結(jié)為實數(shù)理論，各自建立了自 己完整的實數(shù)體系。由此，沿柯西開辟的道路建立起來的嚴(yán)謹(jǐn)?shù)臉O限理論與實數(shù)百度文庫理論，完成了分析學(xué)的邏輯奠基工作。數(shù)學(xué)分析的無矛盾性問題歸納為實數(shù)論的 無矛盾性，從而使微積分學(xué)這座人類數(shù)學(xué)史上空前雄偉的大廈建在了牢固可靠的 基礎(chǔ)之上。重建微積分學(xué)基礎(chǔ)，這項重要而困難的工作就這樣經(jīng)過許多杰出學(xué)者 的努力而勝利完成了。微積分學(xué)堅實牢固基礎(chǔ)的建立，結(jié)束了數(shù)學(xué)中暫時的混亂 局面，同時也宣布了第二次數(shù)學(xué)危機(jī)的徹底解決。同樣，以“羅素悖論”為代表的一系列悖論的出現(xiàn)導(dǎo)致了第三次數(shù)學(xué)危機(jī)

22、。為了消除悖論，數(shù)學(xué)家紛紛提出自己的解決方案。1908年，策梅羅提出第一個公理化集合論體系，后來經(jīng)其他數(shù)學(xué)家改進(jìn)，稱為 ZF系統(tǒng)。這一公理化集 / 合系統(tǒng)很大程度上彌補(bǔ)了康托爾樸素集合論的缺陷。除ZF系統(tǒng)外，集合論的公理系統(tǒng)還有多種，如諾伊曼等人提出的NBG8統(tǒng)等。公理化集合系統(tǒng)的建立，成 功排除了集合論中出現(xiàn)的悖論，從而比較圓滿地解決了第三次數(shù)學(xué)危機(jī)。同時， 羅素悖論對數(shù)學(xué)而言有著更為深刻的影響。 它使得數(shù)學(xué)基礎(chǔ)問題第一次以最迫切、 的需要的姿態(tài)擺到數(shù)學(xué)家面前，導(dǎo)致了數(shù)學(xué)家對數(shù)學(xué)基礎(chǔ)的研究。而這方面的進(jìn) 一步發(fā)展又極其深刻地影響了整個數(shù)學(xué)。 如圍繞著數(shù)學(xué)基礎(chǔ)之爭，形成了現(xiàn)代數(shù) 學(xué)史上著名的三

23、大數(shù)學(xué)流派：邏輯主義學(xué)派、形式主義學(xué)派和直覺主義學(xué)派， 而 各派的工作又都促進(jìn)了數(shù)學(xué)的大發(fā)展。 數(shù)理邏輯也取得了大發(fā)展，證明論、模型 論、遞歸論、多值邏輯、非標(biāo)準(zhǔn)邏輯等相繼問世。第一次數(shù)學(xué)危機(jī)促成了公理幾何與邏輯的誕生； 第二次數(shù)學(xué)危機(jī)促成了分析 基礎(chǔ)理論的完善與集合論的創(chuàng)立；第三次數(shù)學(xué)危機(jī)促成了數(shù)理邏輯的發(fā)展與一批 現(xiàn)代數(shù)學(xué)的產(chǎn)生。數(shù)學(xué)由此獲得了蓬勃發(fā)展，這或許就是數(shù)學(xué)悖論重要意義之所 在吧。10、聰明的囚徒。古希臘有個國王，處死囚徒總是用兩種方式：砍頭或絞刑。他自恃聰明地 做出了這樣一種規(guī)定，讓囚徒自己選擇死的方式：囚徒可以說一句話，并且這 句話是馬上可以驗證其真假的。如果囚徒說的是真話，

24、那么處以絞刑；如果囚 徒說的是假話，那么處以砍頭。許多囚徒或者是因為說了假話而被砍頭或者因 為說了真話而被處以絞刑。有一位極具聰明的囚徒，當(dāng)輪到他來選擇處死方法時，他說出了一句巧妙百度文庫的話，結(jié)果使這個國王不管按照哪種方法處死他，都違背自己的決定，最后只 得將他放了。試問：這囚徒說的是句什么話？答：在日常語言中，凡是可以決定真假的陳述句叫做命題。 但是有一類陳述句卻 就無法判定其真假。這就是所謂的悖論：一個語句 Q,如果從Q為真，可以推出 Q為假；而從Q為假，可以推出Q為真。聰明的囚徒所說的話，就應(yīng)該是這樣的悖論，使得國王無論怎么處置他都會 帶來矛盾。這句話就是“國王決定砍我的頭”。 如果國

25、王決定砍他的頭，則他說的是真/ 話，因此按國王規(guī)定的處死方法（講真話應(yīng)處以絞刑），他應(yīng)該受絞刑。這樣就 造成了國王的規(guī)定同國王決定的處死方法相矛盾。同樣如果國王決定讓受絞刑， 則他說的是假話，因此按國王規(guī)定的處死方法（講假話應(yīng)砍頭），他應(yīng)該砍頭。這樣也造成了國王的規(guī)定同國王決定的處死方法相矛盾。無論如何，國王都將處于進(jìn)退維谷的處境，因此只好免這個囚徒一死，將他放掉。代數(shù)結(jié)構(gòu)1、為什么要研究代數(shù)系統(tǒng)？答：代數(shù)是專門研究離散對象的數(shù)學(xué)， 是對符號的操作。它是現(xiàn)代數(shù)學(xué)的三大支 柱之一（另兩個為分析與幾何）。代數(shù)從19世紀(jì)以來有驚人的發(fā)展，帶動了整個 數(shù)學(xué)的現(xiàn)代化。隨著信息時代的到來，計算機(jī)、信息都是

26、數(shù)字（離散化）的，甚 至電視機(jī).攝像機(jī)、照相機(jī)都在數(shù)字化。知識經(jīng)濟(jì)有人也稱為數(shù)字經(jīng)濟(jì)。這一切 的背后的科學(xué)基礎(chǔ)，就是數(shù)學(xué)，尤其是專門研究離散對象的代數(shù)。代數(shù)發(fā)端于“用 符號代替數(shù)”，后來發(fā)展到以符號代替各種事物。在一個非空集合上，確定了某些運(yùn)算以及這些運(yùn)算滿足的規(guī)律， 于是該非空 集合中的元素就說是有了一種代數(shù)結(jié)構(gòu)。 現(xiàn)實世界中可以有許多具體的不相同的 代數(shù)系統(tǒng)。但事實上，不同的代數(shù)系統(tǒng)可以有一些共同的性質(zhì)。正因為此，我們 要研究抽象的代數(shù)系統(tǒng)，并假設(shè)它具有某一類具體代數(shù)系統(tǒng)共同擁有的性質(zhì)。任百度文庫何在這個抽象系統(tǒng)中成立的結(jié)論，均可適用于那一類代數(shù)系統(tǒng)中的任何一個。2、代數(shù)的歷史。/代數(shù)學(xué)歷

27、史悠久。代數(shù)的發(fā)展可分成兩個階段。19世紀(jì)之前的代數(shù)稱為古典代數(shù)，19世紀(jì)至今的代數(shù)稱為近世代數(shù)(抽象代數(shù))工。遠(yuǎn)在古希臘時期，人們就知道可以用符號代表所解問題中的未知數(shù)，并且這些符號可以像數(shù)一樣進(jìn)行運(yùn)算，直到獲得問題的解。古典代數(shù)的基本研究對象是 方程,它是以討論方程的解法為中心。 在古典代數(shù)中，每一個符號代表的總是一 個數(shù)，但這個數(shù)可以是整數(shù)也可以是實數(shù)。 古典代數(shù)的主要目標(biāo)是用代數(shù)運(yùn)算解 一元多次方程。它成功地解決了一元二次、一元三次和一元四次方程的求解問題。19世紀(jì)初，人們逐漸認(rèn)識到，符號不僅可以代表數(shù)，而且可以代表任何事 物。在這種思想認(rèn)識的支配下，人們開始將任意集合上所進(jìn)行的代數(shù)運(yùn)

28、算作為研 究的對象，從而出現(xiàn)了近世代數(shù)體系和方法。19世紀(jì)30年代，在尋找一元五次方程根式求解方法的過程中，年青的法國 數(shù)學(xué)家伽羅瓦(E. Galois)首次得出了群的概念一用置換群的方法徹底證明了高 于四次的代數(shù)方程的根式不可解性。起初他的奇思妙想和巧妙方法雖然并不被當(dāng) 時人接受和理解，卻發(fā)展出了一門新的學(xué)科-抽象代數(shù)學(xué)。抽象代數(shù)學(xué)的研究對象是抽象的，它不是以某一具體事物為研究對象， 而是 以一大類具有共同性質(zhì)的事物為研究對象。因此其研究成果適用于這一類事物中 的每一個，從而收到事半功倍之效。抽象代數(shù)學(xué)的主要內(nèi)容是研究各種各樣的代數(shù)系統(tǒng)。它把一些形式上很不相 同的代數(shù)系統(tǒng)，用統(tǒng)一的方法描述、

29、研究和推理，從而得到反映出它們共性的一 些本質(zhì)的結(jié)論，然后再把這些結(jié)論應(yīng)用到具體的代數(shù)系統(tǒng)中。從而抽象產(chǎn)生了廣 泛的應(yīng)用。3、抽象代數(shù)學(xué)在計算機(jī)中的應(yīng)用。100多年來，隨著科學(xué)的發(fā)展，抽象代數(shù)越來越顯示出它在數(shù)學(xué)的各個分支、 物理學(xué)、化學(xué)、力學(xué)、生物學(xué)等科學(xué)領(lǐng)域的重要作用。抽象代數(shù)的概念和方法也 是研究計算科學(xué)的重要數(shù)學(xué)工具。有經(jīng)驗和成熟的計算科學(xué)家都知道，除了數(shù)理10百度文庫邏輯外，對計算科學(xué)最有用的數(shù)學(xué)分支學(xué)就是代數(shù)，特別是抽象代數(shù)。抽象代數(shù)是關(guān)于運(yùn)算的學(xué)問，是關(guān)于計算規(guī)則的學(xué)問。在許多實際問題的研究中都離不開數(shù)學(xué)模型，而構(gòu)造數(shù)學(xué)模型就要用到某種 數(shù)學(xué)結(jié)構(gòu)，而抽象代數(shù)研究的中心問題就是一種

30、很重要的數(shù)學(xué)結(jié)構(gòu)-代數(shù)系統(tǒng)：半群、群、格與布爾代數(shù)等等。計算科學(xué)的研究也離不開抽象代數(shù)的應(yīng)用：半群 理論在自動機(jī)理論和形式語言中發(fā)揮了重要作用；有限域理論是編碼理論的數(shù)學(xué)基礎(chǔ)，在通訊中起過重要的作用；至于格和布爾代數(shù)則更不用說了， 是電子線路 設(shè)計、電子計算機(jī)硬件設(shè)計和通訊系統(tǒng)設(shè)計的重要工具。另外描述機(jī)器可計算的 函數(shù)、研究算術(shù)計算的復(fù)雜性、刻畫抽象數(shù)據(jù)結(jié)構(gòu)、描述作為程序設(shè)計基礎(chǔ)的形 式語義學(xué)，都需要抽象代數(shù)知識。4、布爾代數(shù)在邏輯線路中的應(yīng)用。19世紀(jì)50年代，只受過初級數(shù)學(xué)教育、自學(xué)成才的英國人喬治.布爾(George Boole)先后發(fā)表了邏輯之?dāng)?shù)學(xué)分析 (The Mathematica

31、l Analysis of Logic) 和思維規(guī)律(The Laws of Thought)這兩部杰作。他創(chuàng)造出了一套符號系統(tǒng)， 利用符號來表示邏輯中的各種概念。 并且建立了一系列的運(yùn)算法則，利用代數(shù)方 法研究邏輯問題，初步奠定了數(shù)理邏輯的基礎(chǔ)。布爾代數(shù)從此問世，數(shù)學(xué)史上樹 起了一座新的里程碑。布爾將邏輯推理過程簡化成極為容易和簡單的一種代數(shù)運(yùn)算。他規(guī)定在布爾代數(shù)中：.所有可能出現(xiàn)的數(shù)只有0和1兩個；.基本運(yùn)算只有“與”、“或”、“非”三種；/在布爾代數(shù)中用等式表示命題，把推理過程看作等式的變換。這種變換只依賴于 基本運(yùn)算的性質(zhì)。在其誕生100多年后才發(fā)現(xiàn)其應(yīng)用和價值。/雖然在布爾代數(shù)剛剛問

32、世的時間里并沒有受到人們應(yīng)有的重視，但布爾仍然堅信自己的研究會對后世有相當(dāng)大的幫助。隨著布爾的去世，人們對布爾代數(shù)的 了解也越來越少，直到20世紀(jì)初羅素在自己的數(shù)學(xué)原理中重新提到了布爾 代數(shù)的名稱才引起了世人足夠的關(guān)注。但是，此時距布爾去世早已相隔多年。11百度文庫對計算科學(xué)而言，布爾代數(shù)的重要性是不言而喻的。布爾代數(shù)也確實是在其 誕生100多年后才在計算機(jī)的發(fā)展中找到了它的用武之地，它為電子數(shù)字計算機(jī) 開關(guān)電路設(shè)計提供了最重要的數(shù)學(xué)方法。1938年，美國數(shù)學(xué)家、信息論創(chuàng)始人香農(nóng)(C. Shannon)發(fā)表了著名的論文 繼電器和開關(guān)電路的符號分析(A Symbolic Analysis of

33、Relay and Switching Circuits),首次用布爾代數(shù)進(jìn)行開關(guān)電路分析。由于布爾代數(shù)只有0和1兩個值，恰好與二進(jìn)制數(shù)對應(yīng)，香農(nóng)把它運(yùn)用于以脈沖方式處理信息的繼電器開關(guān)。并證明布爾代數(shù)的邏輯運(yùn)算，可以通過繼電器電路來實現(xiàn)，明確地給出了實現(xiàn)加、 減、乘、除等運(yùn)算的電子電路的設(shè)計方法， 從而從理論到技術(shù)徹底改變了數(shù)字電 路的設(shè)計方向。這篇論文成為開關(guān)電路理論的開端， 在現(xiàn)代電子數(shù)字計算機(jī)史上 具有劃時代的意義。香農(nóng)在貝爾實驗室工作中進(jìn)一步證明，可以采用能實現(xiàn)布爾代數(shù)運(yùn)算的繼電、 器或電子元件來制造計算機(jī)。香農(nóng)的理論還為計算機(jī)邏輯功能的設(shè)計奠定了基礎(chǔ)，從而使電子計算機(jī)既能用于數(shù)值計

34、算，又具有各種非數(shù)值應(yīng)用功能，使得以后的計算機(jī)在幾乎任何領(lǐng)域中，都得到廣泛應(yīng)用。今天，所有的電子計算機(jī)芯片里使用的成千上萬個微小的邏輯部件，都是由各種布爾邏輯元件一邏輯門和觸發(fā)器組成的。由邏輯元件可以組成各種邏輯網(wǎng) 絡(luò)，這樣任何復(fù)雜的邏輯關(guān)系都可以由邏輯元件經(jīng)過相應(yīng)的組合來實現(xiàn)，使其具有復(fù)雜的邏輯判斷功能。5、半群與文法及形式語言。計算機(jī)可以完成很多任務(wù)。但是給定一個任務(wù)，我們面臨的第一個問題是： 它是否可以用計算機(jī)來解決？若可以的話，我們就要考慮第二個問題：如何解決。 這些問題的回答都和計算模型有關(guān)。一般有三種類型的計算模型：文法(Grammars)、有限狀態(tài)機(jī)(Finite-state M

35、achines)和圖靈機(jī)(Turing Machines)。其中文法是用來生成一門語言的所有詞 匯和判斷一個詞匯是否在一門語言中。文法產(chǎn)生形式語言，而形式語言既為象英 語這樣的自然語言提供了模型，又為像 PASCALC, PROLOG JAVA這樣的編程 語言提供了模型。在編譯原理和匯編程序的創(chuàng)造中，文法有著不可替代的作用。12百度文庫設(shè)三是一個非空有限集合，稱為字母表，由三中有限個字母組成的有序集合 (即字符串)稱為三上的一個字，用中的字母個數(shù) m稱為字長，m=0時，稱為空字，記為。上 表示三上的字的集合，E 上的連接運(yùn)算 定義為a, BCZ2 : a B = a B，則E , 是一個代數(shù)系

36、統(tǒng)，而且是一個獨異點。E的任一子集就稱為語言。、我們將利用文法來給定一門語言。一個文法給出了一個字母表(用來產(chǎn)生語 言中詞的符號集合)，和一個產(chǎn)生詞的規(guī)則集。一個文法是一個四元組G=(E, T, s, P),其中三是字母表、T是三的子集， 它的元素是終止符(它不能再被三中其它字符代替),s是三的一個元素，它是 初始符，P是所謂生成規(guī)則的集合(生成規(guī)則實質(zhì)上就是語言的短語構(gòu)成規(guī)則， 它們決定匯*中的一個字符串可以被三*中的哪個符號用替換)。N=E-T中的元素 稱為非終止符(它能被三中其它字符代替)，P中的每個產(chǎn)生式的左端至少要有 一非終止符。定義了一門語言的文法后，利用產(chǎn)生式，我們就可以從初始符

37、號s出發(fā)演繹 出一個一個詞，從而確定由該文法產(chǎn)生出來的語言。設(shè)G=(!2, T, s, P)是一個文法，則由G產(chǎn)生的語言L (G)就是能由初始 符號s演繹出來的所有字符串的集合，即 L (G) = 丁 | s * 。6、糾錯碼中的群碼。由于在計算機(jī)中和通訊系統(tǒng)中信號傳遞非常頻繁與廣泛，因此如何防止傳輸 錯誤是一件很重要的事情。當(dāng)然，要解決這個問題可以有不同的途徑。其中的一個途徑就是采用糾錯碼(Error Correcting Code) ,即從編碼上下 功夫，使得二進(jìn)制數(shù)碼一旦在傳遞過程中出錯， 接收端的糾錯碼裝置就能立即發(fā) 現(xiàn)錯誤，并將其糾正。當(dāng)二進(jìn)制信號用從發(fā)送端發(fā)出時， 需要按規(guī)定生成具

38、有干 擾能力的糾錯碼，然后才能發(fā)送出去。在接收端，當(dāng)接收到二進(jìn)制信號審后立即 對收到的糾錯碼進(jìn)行檢查，檢查是否失真，若失真則要負(fù)責(zé)糾正。這就是在計算 機(jī)和數(shù)據(jù)通訊系統(tǒng)中被廣泛采用的方法。13百度文庫我們先舉一個日常生活中的實例。如果你發(fā)出一個通知：”明天14: 00-16 : 00開會”，但在通知過程中由于某種原因產(chǎn)生了錯誤，變成“明天10: 00-16 :00開會”。別人收到這個錯誤通知后由于無法判斷其正確與否，就會按這個錯 誤時間去行動。為了使收者能判斷正誤，可以在發(fā)通知內(nèi)容中增加“下午”兩個 字，即改為：“明天下午14:00-16:00開會”，這時，如果仍錯為：“明天下 午10:00-16:00 開會”，則收到此通知后根據(jù)“下午”兩字即可判斷出其中 “10:00”發(fā)生了錯誤。但仍不能