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

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

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

2、譯原理課程也很有幫助。要求掌握有關(guān)圖、樹的基本概念，以及如何將圖論用于實(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)的背景，加深對(duì)計(jì)算機(jī)學(xué)科的全面了解，特別是理論方面的了解，而不限于將計(jì)算機(jī)看成是一門技術(shù)或工程性的學(xué)科。?通過重要的丿力史事件，了解計(jì)算機(jī)科學(xué)中的一些基木思維方式和一些基木問題。2.數(shù)理邏輯的發(fā)展前期?前史時(shí)期——古典形式邏輯時(shí)期

3、：亞里斯多德的直言三段論理論?初創(chuàng)時(shí)期——邏輯代數(shù)時(shí)期(17世紀(jì)末)?資本主義生產(chǎn)力大發(fā)展，自然科學(xué)取得了長(zhǎng)足的進(jìn)步，數(shù)學(xué)在認(rèn)識(shí)口然、發(fā)展技術(shù)方面起到了相當(dāng)重要的作用。?人們希望使用數(shù)學(xué)的方法來研究思維，把思維過程轉(zhuǎn)換為數(shù)學(xué)的計(jì)算。?萊布尼茲(Leibniz,1646^1716)完善三段論，提岀了建立數(shù)理邏輯或者說理性演算的思想：?提出將推理的止確性化歸于計(jì)算，這種演算能使人們的推理不依賴于對(duì)推理過程屮的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。?使用i種符號(hào)語言來代替口然語言對(duì)演算進(jìn)行描述，將符號(hào)的形式和其含義分開。使得

4、演算從很大程度上取決與符號(hào)的組合規(guī)律，而與其含義無關(guān)。?布爾(G.Boole,1815?1864)代數(shù)：將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。1.數(shù)理邏輯的奠基時(shí)期?弗雷格(G.Frege,1848^1925)：《概念語言一一一種按算術(shù)的公式語言構(gòu)成的純思維公式語言》仃879)的岀版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分一一命題演算和謂詞演算的正式建立。?皮亞諾(GiuseppePeano,1858^1932):《用一種新的方法陳述的算術(shù)原理》(1889)提出1了自然數(shù)算術(shù)的一個(gè)公理系統(tǒng)。?羅

5、1*(BertrandRussell,1872^1970)：《數(shù)學(xué)原理》(與懷特黑合著，1910,1912,1913)從命題演算和謂詞演算開始，然后通過一元利二元命題函項(xiàng)定義了類和關(guān)系的概念，建立了抽象的類演算和關(guān)系演算。山此岀發(fā)，在類型論的基礎(chǔ)上用連續(xù)定義和證明的方式引出了數(shù)學(xué)(主要是算術(shù))屮的主要概念和定理。?邏輯演算的發(fā)展：甘岑(G.Gcntzen)的自然推理系統(tǒng)(NaturalDeductionSystem),邏輯演算的元理論：公理的獨(dú)立性、一致性、完全性等。?各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis,1883^19

6、64)的模態(tài)邏輯，實(shí)質(zhì)蘊(yùn)涵怪論和嚴(yán)格蘊(yùn)涵、相干邏輯等，盧卡西維茨的多值邏輯等。2.集合論的發(fā)展?看待無窮集合的兩種觀點(diǎn)：實(shí)無窮與潛無窮?康托爾(G.Cantor,1845^1918):以實(shí)無窮的思想為指導(dǎo)，建立了樸素集合論?外延原則(集合由它的元素決定)和概括原則(每一性質(zhì)產(chǎn)主一集合)。?可數(shù)集和不可數(shù)集，確定無窮集合的本質(zhì)在于集合本身能耳其子集對(duì)應(yīng)。能■正整數(shù)集合對(duì)應(yīng)的集合是可數(shù)的，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對(duì)角線法證明了實(shí)數(shù)集合是不可數(shù)的。?超窮基數(shù)和超窮序數(shù)?樸素集合論的悖論：羅素悖論?公理集合論的建立：Z

7、FC系統(tǒng)6.第三次數(shù)學(xué)危機(jī)與邏輯主義、直覺主義與形式主義?集合論的悖論使得人們覺得數(shù)學(xué)產(chǎn)牛了第三次危機(jī)，提出了數(shù)學(xué)的基礎(chǔ)到底是什么這樣的問題。?羅素等的邏輯主義：數(shù)學(xué)的基礎(chǔ)是邏輯，出導(dǎo)一切數(shù)學(xué)可從邏輯符號(hào)推出，《數(shù)養(yǎng)原理》一書是他們這一思想的體現(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)排中律不能用于無窮集合。海丁(Ileyting)的直覺主義邏輯。?希爾伯特(D.Hilbert)的形式

8、主義：公理化方法與形式化方法，元數(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)，并證明其