數(shù)學：離散數(shù)學基礎.doc

《數(shù)學：離散數(shù)學基礎.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第一講引言一、課程內(nèi)容·數(shù)理邏輯：是計算機科學的基礎，應熟練掌握將現(xiàn)實生活中的條件化成邏輯公式，并能做適當?shù)耐评?，這對程序設計等課程是極有用處的。·集合論：數(shù)學的基礎，對于學習程序設計、數(shù)據(jù)結構、編譯原理等幾乎所有計算機專業(yè)課程和數(shù)學課程都很有用處。熟練掌握有關集合、函數(shù)、關系等基本概念?！ご鷶?shù)結構：對于抽象數(shù)據(jù)類型、形式語義的研究很有用處。培養(yǎng)數(shù)學思維，將以前學過的知識系統(tǒng)化、形式化和抽象化。熟練掌握有關代數(shù)系統(tǒng)的基本概念，以及群、環(huán)、域等代數(shù)結構的基本知識。·圖論：對于解決許多實際問題很有用處，對于學習數(shù)據(jù)結構、編譯原理課程也很有幫助。要求掌握有關圖、樹的基本概

2、念，以及如何將圖論用于實際問題的解決，并培養(yǎng)其使用數(shù)學工具建立模型的思維方式?！ぶv課時間為兩個學期，第一學期講授數(shù)理邏輯與集合論，第二學期講授代數(shù)結構和圖論?？荚噧?nèi)容限于書中的內(nèi)容和難度，但講課內(nèi)容不限于書中的內(nèi)容和難度。二、數(shù)理邏輯發(fā)展史1.目的·了解有關的背景，加深對計算機學科的全面了解，特別是理論方面的了解，而不限于將計算機看成是一門技術或工程性的學科?！ねㄟ^重要的歷史事件，了解計算機科學中的一些基本思維方式和一些基本問題。2.數(shù)理邏輯的發(fā)展前期·前史時期——古典形式邏輯時期：亞里斯多德的直言三段論理論·初創(chuàng)時期——邏輯代數(shù)時期（17世紀末）·資本主義生產(chǎn)力大

3、發(fā)展，自然科學取得了長足的進步，數(shù)學在認識自然、發(fā)展技術方面起到了相當重要的作用?！と藗兿Ｍ褂脭?shù)學的方法來研究思維，把思維過程轉(zhuǎn)換為數(shù)學的計算。·萊布尼茲(Leibniz,1646~1716)完善三段論，提出了建立數(shù)理邏輯或者說理性演算的思想：·提出將推理的正確性化歸于計算，這種演算能使人們的推理不依賴于對推理過程中的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則?！な褂靡环N符號語言來代替自然語言對演算進行描述，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規(guī)律，而與其含義無關?！げ紶?G.Boole,1815~1864)代數(shù)：將有關數(shù)學運算的研

4、究的代數(shù)系統(tǒng)推廣到邏輯領域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。3.數(shù)理邏輯的奠基時期·弗雷格(G.Frege,1848~1925)：《概念語言——一種按算術的公式語言構成的純思維公式語言》(1879)的出版標志著數(shù)理邏輯的基礎部分——命題演算和謂詞演算的正式建立?！て喼Z(GiuseppePeano,1858~1932)：《用一種新的方法陳述的算術原理》(1889)提出了自然數(shù)算術的一個公理系統(tǒng)?！ち_素(BertrandRussell,1872~1970)：《數(shù)學原理》(與懷特黑合著，1910,1912,1913)從命題演算和謂詞演算開始，然后通過一元和二

5、元命題函項定義了類和關系的概念，建立了抽象的類演算和關系演算。由此出發(fā)，在類型論的基礎上用連續(xù)定義和證明的方式引出了數(shù)學（主要是算術）中的主要概念和定理。·邏輯演算的發(fā)展：甘岑(G.Gentzen)的自然推理系統(tǒng)(NaturalDeductionSystem)，邏輯演算的元理論：公理的獨立性、一致性、完全性等。·各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis,1883~1964)的模態(tài)邏輯，實質(zhì)蘊涵怪論和嚴格蘊涵、相干邏輯等，盧卡西維茨的多值邏輯等。4.集合論的發(fā)展·看待無窮集合的兩種觀點：實無窮與潛無窮·康托爾(G.Cantor,1845~1918)：以實無窮的思

6、想為指導，建立了樸素集合論·外延原則（集合由它的元素決定）和概括原則（每一性質(zhì)產(chǎn)生一集合）?！た蓴?shù)集和不可數(shù)集，確定無窮集合的本質(zhì)在于集合本身能與其子集一一對應。能與正整數(shù)集合對應的集合是可數(shù)的，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對角線法證明了實數(shù)集合是不可數(shù)的?！こF基數(shù)和超窮序數(shù)·樸素集合論的悖論：羅素悖論·公理集合論的建立：ZFC系統(tǒng)6.第三次數(shù)學危機與邏輯主義、直覺主義與形式主義·集合論的悖論使得人們覺得數(shù)學產(chǎn)生了第三次危機，提出了數(shù)學的基礎到底是什么這樣的問題?！ち_素等的邏輯主義：數(shù)學的基礎是邏輯，倡導一切數(shù)學可從邏輯符號推出，《數(shù)學原理》一書是

7、他們這一思想的體現(xiàn)。為解決悖論產(chǎn)生了邏輯類型論。·布勞維爾(Brouwer,1881~1966)的直覺主義：數(shù)學是心靈的構造，只承認可構造的數(shù)學，強調(diào)構造的能行性，與計算機科學有重要的聯(lián)系。堅持潛無窮，強調(diào)排中律不能用于無窮集合。海丁(Heyting)的直覺主義邏輯?！は柌?D.Hilbert)的形式主義：公理化方法與形式化方法，元數(shù)學和證明論，提倡將邏輯演算和數(shù)學證明本身形式化，把用普通的語言傳達的內(nèi)容上的數(shù)學科學變?yōu)橛脭?shù)學符號和邏輯符號按一定法則排列的一堆公式。為了消除悖論，要數(shù)學建立在公理化基礎上，將各門數(shù)學形式化，構成形式系統(tǒng)，并證明其一致性，這是希