離散數(shù)學(xué)研究對(duì)象市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

離散數(shù)學(xué)研究對(duì)象

由于數(shù)字電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu)，它只能處理離散或離散化了數(shù)量關(guān)系，因此，無論計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)當(dāng)代科學(xué)研究領(lǐng)域，都面臨著如何對(duì)離散結(jié)構(gòu)建立相應(yīng)數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來數(shù)學(xué)模型離散化，從而可由計(jì)算機(jī)加以處理。離散數(shù)學(xué)(DiscreteMathematics)是計(jì)算機(jī)專業(yè)一門主要基礎(chǔ)課。它所研究對(duì)象是離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)結(jié)構(gòu)模型。第1頁第1頁離散數(shù)學(xué)主要內(nèi)容

到當(dāng)前為止，離散數(shù)學(xué)所研究準(zhǔn)確范圍并沒有嚴(yán)格定義，它和其它許多純正數(shù)學(xué)以及應(yīng)用數(shù)學(xué)分支之間有著廣泛交叉和互相滲入。但是作為給計(jì)算機(jī)專業(yè)本科生開設(shè)一門專業(yè)基礎(chǔ)課，其內(nèi)容相對(duì)來說較為明確，主要包括數(shù)理邏輯、集合論、代數(shù)系統(tǒng)以及圖論等幾部分。離散數(shù)學(xué)是數(shù)字電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)、算法分析與設(shè)計(jì)、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)等專業(yè)課程基礎(chǔ)。第2頁第2頁數(shù)理邏輯數(shù)理邏輯是用數(shù)學(xué)辦法研究關(guān)于推理、證實(shí)等問題學(xué)科，也叫做符號(hào)邏輯。它本質(zhì)是研究如何通過利用純正公理系統(tǒng)和符號(hào)演算以及推理辦法來代替人們思維中邏輯推理過程，并由此將整個(gè)數(shù)學(xué)建立在這樣一個(gè)邏輯基礎(chǔ)之上。歷史上諸多數(shù)學(xué)家努力和推動(dòng)，尤其是萊布尼茨、布爾、希爾伯特、羅素、圖靈、哥德爾等人工作，部分地實(shí)現(xiàn)了這一形式化數(shù)學(xué)夢(mèng)想，但同時(shí)也發(fā)覺了數(shù)學(xué)基礎(chǔ)本身存在巨大困難。第3頁第3頁集合論集合論是德國(guó)著名數(shù)學(xué)家康托爾于19世紀(jì)末創(chuàng)建。康托對(duì)于無窮集元素個(gè)數(shù)問題進(jìn)行了卓越研究，引領(lǐng)數(shù)學(xué)研究進(jìn)入了一個(gè)全新領(lǐng)域。他提出用一一對(duì)應(yīng)準(zhǔn)則來比較無窮集元素個(gè)數(shù)，將元素間能建立一一對(duì)應(yīng)集合稱為個(gè)數(shù)相同（也稱作等勢(shì)）。并證實(shí)了無窮集勢(shì)之間存在著差異，有著不同數(shù)量級(jí)，可分為不同層次。問題：試判斷自然數(shù)集合{x|x=1,2,3,…}和奇數(shù)集合{x|x=1,3,5,…}哪個(gè)集合元素個(gè)數(shù)多？第4頁第4頁圖論“圖論”是數(shù)學(xué)一個(gè)分支，它以圖為研究對(duì)象。圖論中圖是由若干給定點(diǎn)及連接兩點(diǎn)線所構(gòu)成圖形，這種圖形通慣用來描述一些事物之間某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)線表示相應(yīng)兩個(gè)事物間含有這種關(guān)系。圖論起源于著名柯尼斯堡七橋問題。歐拉在1736年處理了這個(gè)問題，他用抽象分析法將這個(gè)問題化為第一個(gè)圖論問題。歐拉證實(shí)了柯尼斯堡七橋問題是無解，并推廣了這個(gè)問題，給出了對(duì)于一個(gè)給定圖能夠某種方式走遍鑒定法則。這使得歐拉成為圖論﹝及拓?fù)鋵W(xué)﹞創(chuàng)始人。第5頁第5頁學(xué)習(xí)離散數(shù)學(xué)辦法

概念定理多：首先要準(zhǔn)確嚴(yán)格地掌握好概念和術(shù)語，正確理解他們內(nèi)涵和外延。由于公理、定理或定律基石都是概念，只有正確地理解了概念，才干把握定理實(shí)質(zhì)，純熟地將公理、定理應(yīng)用于處理問題。抽象思維多：完全、準(zhǔn)確掌握一個(gè)概念好主意是首先要深刻理解概念內(nèi)涵，然后舉一些屬于和不屬于該概念外延正反兩方面實(shí)例。假如對(duì)一些似是而非例子也能區(qū)別話，應(yīng)當(dāng)說這個(gè)概念正真理理解了。只需要中學(xué)數(shù)學(xué)基礎(chǔ)。第6頁第6頁第一部分?jǐn)?shù)理邏輯先看著名物理學(xué)家愛因斯坦出過一道題：

一個(gè)土耳其商人想找一個(gè)十分聰明助手幫助他經(jīng)商，有兩人前來應(yīng)聘，這個(gè)商人為了試試哪個(gè)更聰明些，就把兩個(gè)人帶進(jìn)一間漆黑屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色，三頂是黑色，現(xiàn)在，我把燈關(guān)掉，并且把帽子擺位置弄亂，然后我們?nèi)齻€(gè)人每人摸一頂帽子戴在自己頭上，在我開燈后，請(qǐng)你們盡快說出自己頭上戴帽子是什么顏色?！闭f完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時(shí)商人將余下兩頂帽子藏了起來，接著把燈打開。這時(shí)，那兩個(gè)應(yīng)試者看到商人頭上戴是一頂紅帽子，其中一個(gè)人便喊道：“我戴是黑帽子。”

第7頁第7頁

請(qǐng)問這個(gè)人說得對(duì)嗎？他是怎么推導(dǎo)出來呢？

要回答這樣問題，事實(shí)上就是看由一些諸如“商人戴是紅帽子”這樣前提能否推出“猜出答案應(yīng)試者戴是黑帽子”這樣結(jié)論來。這又需要經(jīng)歷下列過程：

(1)什么是前提？有哪些前提？

(2)結(jié)論是什么？

(3)依據(jù)什么進(jìn)行推理？

(4)怎么進(jìn)行推理？

下面第一章，第二章回答第一個(gè)問題。第三章回答第二、三個(gè)問題。第8頁第8頁下圖給出了邏輯部分知識(shí)體系第9頁第9頁例1.1判斷下列句子是否為命題。

(1)4是素?cái)?shù)。

(2)是無理數(shù)。

(3)x不小于y。

(4)月球上有冰。

(5)21元旦是晴天。

(6)π不小于嗎？

(7)請(qǐng)不要吸煙！

(8)這朵花真美麗啊！

(9)我正在說假話。能鑒定真假陳說句稱為命題作為命題陳說句所表示判斷結(jié)果稱為命題真值，真值只取兩個(gè)值：真或假。真值為真命題稱為真命題，真值為假命題稱為假命題。任何命題真值都是唯一。

判斷給定句子是否為命題，應(yīng)當(dāng)分兩步：首先鑒定它是否為陳說句，另一方面判斷它是否有唯一真值。第10頁第10頁解:本題(9)個(gè)句子中，(6)是疑問句，(7)是祈使句，(8)是感慨句，因而這3個(gè)句子都不是命題。剩下6個(gè)句子都是陳說句，但(3)無確定真值，依據(jù)x,y不同取值情況它可真可假，即無唯一真值，因而不是命題。若(9)真值為真，即“我正在說假話”為真，也就是“我正在說真話”，則又推出(9)真值應(yīng)為假；反之，若(9)真值為假，即“我正在說假話”為假，也就是“我正在說假話”，則又推出(9)真值應(yīng)為真。于是(9)既不為真又不為假，因此它不是命題。像(9)這么由真推出假，又由假推出真陳說句稱為悖論。凡是悖論都不是命題。本例中，只有(1)，(2)，(4)，(5)是命題。(1)為假命題，(2)為真命題。即使今天我們不知道(4)，(5)真值，但它們真值客觀存在，而且是唯一，未來總會(huì)知道(4)真值，到21元旦(5)真值就真相大白了。第11頁第11頁羅素悖論一天，薩維爾村剪發(fā)師掛出一塊招牌：“村里所有不自己剪發(fā)男人都由我給他們剪發(fā)，我也只給這些人剪發(fā)?！庇谑怯行┤藛査骸澳^發(fā)由誰理呢?”剪發(fā)師頓時(shí)啞口無言。由于，假如他給自己剪發(fā)，那么他就屬于自己給自己剪發(fā)那類人。但是，招牌上闡明他不給這類人剪發(fā)，因此他不能自己理。假如由另外一個(gè)人給他剪發(fā)，他就是不給自己剪發(fā)人，而招牌上明明說他要給所有不自己剪發(fā)男人剪發(fā)，因此，他應(yīng)當(dāng)自己理。由此可見，無論如何推論，剪發(fā)師所說話總是自相矛盾。第12頁第12頁有趣對(duì)話。甲對(duì)乙說：“你會(huì)回答我‘不對(duì)’，對(duì)不對(duì)？請(qǐng)用‘對(duì)’或‘不對(duì)’往返答！”第13頁第13頁例1.2是有理數(shù)是不對(duì)；2是偶素?cái)?shù)；2或4是素?cái)?shù)；如果2是素?cái)?shù)，則3也是素?cái)?shù)；2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。全是命題。定義1.1

設(shè)p為命題，復(fù)合命題“非p”(或“p否認(rèn)”)稱為p否認(rèn)式,記作┐p，符號(hào)┐稱作否認(rèn)聯(lián)結(jié)詞。并要求┐p為真當(dāng)且僅當(dāng)p為假。

定義1.2

設(shè)p,q為二命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞。并要求p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。定義1.3

設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞。并要求p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假。

注意：按定義1.3在析取式p∨q中，若p，q都為真，則p∨q為真?！盎颉鄙杏辛硗庖粋€(gè)使用辦法：當(dāng)p，q都為真時(shí)，析取起來為假。前者稱為相容或，后者稱為排斥或(排異或)。第14頁第14頁例1.3將下列命題符號(hào)化。

(1)張曉靜愛唱歌或愛聽音樂。

(2)張曉靜是江西人或安徽人。

(3)張曉靜只能挑選202或203房間。

解在解題時(shí)，先將原子命題符號(hào)化。

(1)p：張曉靜愛唱歌。

q：張曉靜愛聽音樂。

顯然(1)中“或”為相容或，即p與q能夠同時(shí)為真，符號(hào)化為p∨q.第15頁第15頁

(2)r：張曉靜是江西人。

s：張曉靜是安徽人。

易知，(2)中“或”應(yīng)為排斥或，但r與s不能同時(shí)為真，因而也能夠符號(hào)化為r∨s.

(3)t：張曉靜挑選202房間。

u：張曉靜挑選203房間。

由題意可知，(3)中“或”應(yīng)為排斥或。t，u聯(lián)合取值情況有四種：同真，同假，一真一假(兩種情況)。假如也符號(hào)化為t∨u，張曉靜就也許同時(shí)得到兩個(gè)房間，這違反題意。因而不能符號(hào)化為t∨u.如何達(dá)到只能挑一個(gè)房間要求呢？能夠使用多個(gè)聯(lián)結(jié)詞，符號(hào)化為

(t∧┐u)∨(┐t∧u)第16頁第16頁定義1.4

設(shè)p，q為二命題，復(fù)合命題“假如p，則q”稱作p與q蘊(yùn)涵式，記作p→q，→稱作蘊(yùn)涵聯(lián)結(jié)詞。并要求p→q為假當(dāng)且僅當(dāng)p為真q為假。

注意：在使用聯(lián)結(jié)詞→時(shí)，要尤其注意以下幾點(diǎn)：

1．在自然語言里，尤其是在數(shù)學(xué)中，q是p必要條件有許多不同敘述方式。比如，“只要p，就q”，“因?yàn)閜，因此q”，“p僅當(dāng)q”，“只有q才p”，“除非q才p”，“除非q，不然非p”等等。以上各種敘述方式表面看來有所不同，但都表示是q是p必要條件，因而所用聯(lián)結(jié)詞均應(yīng)符號(hào)化為→，上述各種敘述方式都應(yīng)符號(hào)化為p→q.

2．在自然語言中，“假如p，則q”中前件p與后件q往往含有某種內(nèi)在聯(lián)絡(luò)。而在數(shù)理邏輯中，p與q能夠無任何內(nèi)在聯(lián)絡(luò)。

3．在數(shù)學(xué)或其它自然科學(xué)中，“假如p，則q”往往表示是前件p為真，后件q也為真推理關(guān)系。但在數(shù)理邏輯中，作為一個(gè)要求，當(dāng)p為假時(shí)，不論q是真是假，p→q均為真。也就是說，只有p為真q為假這一個(gè)情況使得復(fù)合命題p→q為假。第17頁第17頁定義1.5

設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q等價(jià)式，記作p?

q，稱作等價(jià)聯(lián)結(jié)詞。并要求p?

q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。

以上定義了五種最基本、最慣用、也是最主要聯(lián)結(jié)詞┐，∧，∨，→，?，將它們構(gòu)成一個(gè)集合{┐，∧，∨，→，?}，稱為一個(gè)聯(lián)結(jié)詞集。其中┐為一元聯(lián)結(jié)詞，其余都是二元聯(lián)結(jié)詞。第18頁第18頁

通慣用1表示真，用0表示假，復(fù)合命題真假值如表1.1。表1.1基本復(fù)合命題真值

聯(lián)結(jié)詞能夠嵌套使用，在嵌套使用時(shí)，要求下列優(yōu)先順序：()，┐，∧，∨，→，?

，對(duì)于同一優(yōu)先級(jí)聯(lián)結(jié)詞，先出現(xiàn)者先運(yùn)算。第19頁第19頁例1.7

令p：北京比