數(shù)學(xué)：離散數(shù)學(xué)基礎(chǔ)

《數(shù)學(xué)：離散數(shù)學(xué)基礎(chǔ)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

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

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

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

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

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

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