離散數(shù)學(xué)(5)省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)

1/491/60離散數(shù)學(xué)

DiscreteMathematics計(jì)算機(jī)科學(xué)與工程學(xué)院袁夏E-mail:yxlucker@163.com第1頁(yè)2/49課程說(shuō)明課程類(lèi)型：計(jì)算機(jī)科學(xué)專(zhuān)業(yè)基礎(chǔ)課學(xué)分：4.5學(xué)分教學(xué)方式：理論教學(xué)考評(píng)方式：閉卷筆試成績(jī)?cè)u(píng)定：平時(shí)成績(jī)20%，期末成績(jī)80%教材與教學(xué)參考書(shū)：（1）離散數(shù)學(xué)（第2版），朱保平，金忠等，北京理工大學(xué)出版社，（2）離散數(shù)學(xué)概念、題解與自測(cè)，朱保平，金忠等，北京理工大學(xué)出版社，第2頁(yè)3/49課件與作業(yè)參考答案請(qǐng)進(jìn)入郵箱文件中心下載用戶名：cs_lisanshuxue@163.com密碼：lisanshuxue

課件每次課后上傳更新，作業(yè)參考答案不定時(shí)上傳更新第3頁(yè)4/49第4頁(yè)5/49離散數(shù)學(xué)——研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型數(shù)學(xué)分支統(tǒng)稱(chēng)古代數(shù)學(xué)——整數(shù)、整數(shù)比近代數(shù)學(xué)——連續(xù)數(shù)量概念（實(shí)數(shù)），處理連續(xù)數(shù)量關(guān)系數(shù)學(xué)（微積分）Discrete?第5頁(yè)6/49對(duì)計(jì)算機(jī)專(zhuān)業(yè)系統(tǒng)知識(shí)輻射作用胡慧君，劉茂福，武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

《計(jì)算機(jī)光盤(pán)軟件與應(yīng)用》188-189,第6頁(yè)7/49主要內(nèi)容數(shù)理邏輯(1-5)集合論(6-8)圖論(9-10)代數(shù)(11-12)沒(méi)有預(yù)修課程。學(xué)習(xí)數(shù)理邏輯時(shí)會(huì)包括一點(diǎn)中學(xué)階段學(xué)習(xí)集合知識(shí)。第7頁(yè)8/49數(shù)理邏輯——數(shù)學(xué)化邏輯學(xué)德國(guó)G.W.Leibniz(1626-1716)把數(shù)學(xué)引入形式邏輯，明確提出用數(shù)學(xué)方法研究推理。英國(guó)G.Boole(1815-1864)等創(chuàng)建了邏輯代數(shù)，1847年Boole實(shí)現(xiàn)了命題演算。德國(guó)G.Frege(1848-1925)在1879年建立了第一個(gè)謂詞演算系統(tǒng)。英國(guó)B.Russell(1872-1970)等從邏輯學(xué)基本法則建立了自然數(shù)理論、實(shí)數(shù)理論及解析幾何學(xué)等。英國(guó)AlanM.Turing(1912-1954)在1936年提出一個(gè)抽象計(jì)算模型（數(shù)學(xué)邏輯機(jī)），引入圖靈機(jī)——一個(gè)理想計(jì)算機(jī)第8頁(yè)9/49數(shù)理邏輯學(xué)習(xí)“我現(xiàn)在年紀(jì)大了，搞了這么多年軟件，錯(cuò)誤不知犯了多少，現(xiàn)在覺(jué)悟了。我想，假如我早年在數(shù)理邏輯上好好下點(diǎn)工夫話，我就不會(huì)犯這么多錯(cuò)誤。不少東西邏輯學(xué)家早就說(shuō)過(guò)了，可是我不知道。要是我能年輕二十歲話，我就去學(xué)邏輯?！?/p>

——Edsger.W.Dijkstra1972年Turing獎(jiǎng)取得者

(1930-)帶權(quán)圖最短通路算法第9頁(yè)10/49數(shù)理邏輯第一章命題演算基礎(chǔ)第二章命題演算推理理論第三章謂詞演算基礎(chǔ)第四章謂詞演算推理理論第五章遞歸函數(shù)論第10頁(yè)11/49大數(shù)據(jù)技術(shù)：情感分類(lèi)現(xiàn)在是晚上十一點(diǎn)，天很暖。假如我考試經(jīng)過(guò)了，那么我很高興。假如我高興，那么陽(yáng)光燦爛。并非假如只有考試經(jīng)過(guò)才能心情好那么我心情好。？QQ心情謎語(yǔ)第11頁(yè)12/49

(一)命題定義凡是能夠判斷真假陳說(shuō)句稱(chēng)為命題。命題值

真,用T(或1)表示假,用F(或0)表示第12頁(yè)13/49例：以下句子都是命題嗎？雪是白。雪是黑。好大雪??！

8大于12。

1+101=110。

?????第13頁(yè)14/49例：以下句子都是命題嗎？21世紀(jì)末，人類(lèi)將住在月球。大于2偶數(shù)可表示成兩個(gè)素?cái)?shù)之和。X<0。假如x大于3，則x2大于9。我正在說(shuō)謊。?????悖論第14頁(yè)15/49命題真假問(wèn)題在數(shù)理邏輯學(xué)習(xí)中，不能去糾纏各種詳細(xì)命題真假問(wèn)題，而是將命題當(dāng)成數(shù)學(xué)概念來(lái)處理，看成一個(gè)抽象形式化概念，把命題定義成非真必假陳說(shuō)句．第15頁(yè)16/49帶聯(lián)結(jié)詞命題今晚我看書(shū)。今晚我玩網(wǎng)絡(luò)游戲。今晚我不看書(shū)。今晚我不玩網(wǎng)絡(luò)游戲。今晚我不看書(shū)，我玩網(wǎng)絡(luò)游戲。今晚我看書(shū)，或者我玩網(wǎng)絡(luò)游戲。否定而且或者第16頁(yè)17/49(二)原子命題和復(fù)合命題原子命題——不可剖開(kāi)或分解為更簡(jiǎn)單命題命題，也稱(chēng)為簡(jiǎn)單命題。復(fù)合命題——由原子命題利用聯(lián)結(jié)詞組成命題約定用大寫(xiě)字母表示第17頁(yè)18/49復(fù)合命題例子（1）并非雪是白。（2）今晚我看書(shū)或者去看電影。（3）假如天氣好，那么我去接你。（4）偶數(shù)a是質(zhì)數(shù)，當(dāng)且僅當(dāng)a=2（a是常數(shù)）。（5）2是偶數(shù)且3也是偶數(shù)。

（6）你去了學(xué)校，我去了工廠。第18頁(yè)19/49(三)命題變?cè)?dāng)P表示任意命題時(shí)，稱(chēng)P為命題變?cè)Ｗ帜窹命題——詳細(xì)、特定命題，有確定真值命題變?cè)我饷}，沒(méi)有確定真值

第19頁(yè)20/49命題變?cè)冇蛞粋€(gè)命題變?cè)狿可能取值有兩種情況：真T，或假F。P變域={T，F(xiàn)}兩個(gè)命題變?cè)狿、Q可能取值有幾個(gè)情況？怎么表示這些情況？P、Q變域={？}第20頁(yè)21/491.1.2聯(lián)結(jié)詞否定詞﹁

合取詞∧析取詞∨蘊(yùn)含詞

等價(jià)詞

第21頁(yè)22/49﹁P讀作“非P”

，是指命題：“P否定”。P

PTFFT真值表

例P：雪是黑色。

﹁P：并非雪是黑色。雪不是黑色。第22頁(yè)23/49否定聯(lián)結(jié)詞使用標(biāo)準(zhǔn)將真命題變成假命題，將假命題變成真命題。但這并不是簡(jiǎn)單隨意加個(gè)不字就能完成。例P:這些人都是學(xué)生。

﹃P(guān)：這些人不都是學(xué)生

≠

這些人都不是學(xué)生

第23頁(yè)24/49P∧Q讀作“P合取Q”，是指命題：“P而且Q”。PQP

QTTTTFFFTFFFF

例

P:今天刮風(fēng)。

Q：今天下雨。

P∧Q：今天刮風(fēng)，下雨。真值表第24頁(yè)25/49P∨Q讀作“P析取Q”

，是指命題：“P或者Q”。PQP

QTTTTFTFTTFFF例

P:他會(huì)英語(yǔ)。

Q：他會(huì)法語(yǔ)。

P∨Q：他會(huì)英語(yǔ)或者法語(yǔ)。

第25頁(yè)26/49可兼“或”——不可兼“或”P(pán)QP∨QTTTTFTFTTFFF他會(huì)英語(yǔ)或法語(yǔ)。PQP∨Q

(P∧﹁

Q)∨(﹁P∧Q)TTTFTFTTFTTTFFFF今晚我去看電影，或去看球賽。第26頁(yè)27/49P→Q讀作“P蘊(yùn)含Q”

，是指命題：“假如P，則Q”。例假如1+1=3，則雪是黑。PQP

QTTTTFFFTTFFT真值表第27頁(yè)28/49注1.前件為假時(shí)，蘊(yùn)含式命題為真假如蘊(yùn)含前件P是假命題，那么不論Q是什么命題，命題P→Q在邏輯中都被認(rèn)為是真命題。第28頁(yè)29/49注2.蘊(yùn)含式前件、后件能夠毫不相關(guān)在日常語(yǔ)言中“假如……則……”所聯(lián)結(jié)句子之間表現(xiàn)是一個(gè)因果關(guān)系，但在數(shù)理邏輯中，盡管說(shuō)前件蘊(yùn)涵后件，但兩個(gè)命題能夠是毫不相關(guān)。例

P：我心情好。Q：1=2。

P→Q：假如我心情好，那么1＝2。第29頁(yè)30/49靈活敘述蘊(yùn)含詞例子設(shè)R：天下雨，

H：我回家，試表示以下命題：只要天下雨，我就回家。只有天下雨，我才回家。除非天下雨，不然我不回家。僅當(dāng)日下雨，我才回家。R→HH→R或﹃R→﹃H

能夠?qū)⑻N(yùn)含看作充分條件.假如A是充分條件前件,B是后件,那么A蘊(yùn)含B意思就是有A必有B第30頁(yè)31/49P

Q讀作“P等價(jià)于Q”,是指命題：“P當(dāng)且僅當(dāng)Q”。PQP

QTTTTFFFTFFFT例

P:2+3＝5

Q:e是無(wú)理數(shù)

P

Q

：2+3＝5充要條件是e是無(wú)理數(shù)

第31頁(yè)32/49是否命題？是否復(fù)合命題？例Tom和John是弟兄。例

假如x>0，則x2>0。例

若兩圓面積相等，則它們半徑相等，反之亦然。

??????第32頁(yè)33/49真值函項(xiàng)定義——以真假為定義域并以真假為值域函數(shù)（映射）。{T,F}{T,F}2={(T,T),(T,F),(F,T),(F,F)}第33頁(yè)34/49一元真值函項(xiàng)——一元聯(lián)結(jié)詞{T,F}{T,F}fPf0(P)f1(P)f2(P)f3(P)

TTTFFFTFTF永真恒等否定

P永假第34頁(yè)35/49二元真值函項(xiàng)——二元聯(lián)結(jié)詞f4為析取

f2為蘊(yùn)含f8為等價(jià)f11為合取

f14為或非↓f1為與非

第35頁(yè)36/49三元聯(lián)結(jié)詞共有多少個(gè)？f0f1f2…………f?(0,0,0)010…………1(0,0,1)001…………1(0,1,0)000…………1(0,1,1)000…………1(1,0,0)000…………1(1,0,1)000…………1(1,1,0)000…………1(1,1,1)000…………128第36頁(yè)37/491.1.3合式公式合式公式為以下定義式子，簡(jiǎn)稱(chēng)為公式：任何命題變?cè)枪?；假如P為公式，則

P為公式；假如P，Q為公式，則

P

Q,P

Q,P

Q,P

Q為公式；當(dāng)且僅當(dāng)經(jīng)過(guò)有限次使用①、②、③所組成符號(hào)串才是公式，不然不為公式。Wellformedformulae第37頁(yè)38/49n元公式——有n個(gè)不一樣命題變?cè)?。例一元公式P(PP)二元公式(P

Q)

(PQ)三元公式((P

Q)

R)

(PQ)第38頁(yè)39/49優(yōu)先級(jí)約定∧、∨、、

優(yōu)先級(jí)相同

﹃

比其它聯(lián)結(jié)詞有更高優(yōu)先級(jí)括號(hào)（）內(nèi)運(yùn)算優(yōu)先第39頁(yè)40/49命題符號(hào)化分析出簡(jiǎn)單命題，符號(hào)化用聯(lián)結(jié)詞聯(lián)結(jié)簡(jiǎn)單命題例將下述命題符號(hào)化:

假如只有知道希臘文才能了解柏拉圖，那么我不了解柏拉圖解：令P表示“我知道希臘文”，Q表示“我了解柏拉圖”則原句符號(hào)化為(Q

P)

Q第40頁(yè)41/49真值例令P：北京比天津人口多。

Q：2+2＝4。

R：烏鴉是白色。

求以下公式真值：

(1)(Q∨R)→(P→

R)

(2)(

P∨R)

(P∧

R)

第41頁(yè)42/49真值表及其應(yīng)用？P:我考試經(jīng)過(guò)Q:我心情好

((QP)Q)TTFTFTFTFFFT并非假如只有考試經(jīng)過(guò)就能心情好那么我心情好。我心情不好。第42頁(yè)43/49真值表及其應(yīng)用？P:我考試經(jīng)過(guò)Q:我心情好

((QP)

Q)TTTTFFFTFFFF并非假如只有考試經(jīng)過(guò)才能心情好那么我心情不好。我心情好，而且考試經(jīng)過(guò)。第43頁(yè)44/491.2真假性定義：設(shè)n元公式

中全部不一樣命題變?cè)獮?/p>

P1,P2,

…,Pn

問(wèn)題：n元公式

有多少個(gè)完全解釋?zhuān)?.2.1解釋假如對(duì)每個(gè)命題變?cè)o予一個(gè)確定值，則稱(chēng)對(duì)公式

給了一個(gè)完全解釋?zhuān)患偃鐑H對(duì)部分變?cè)o予確定值，則稱(chēng)對(duì)公式

給了一個(gè)部分解釋。第44頁(yè)45/49例考查公式

=(P

Q)

R

PQR(PQ)R真值(P,Q,R)TTTT完全解釋TTFF完全解釋TT*?部分解釋F**T第45頁(yè)46/49成真解釋與成假解釋定義：對(duì)于任何公式

，PQR(PQ)R真值(P,Q,R)TTTT成真解釋TTFF成假解釋TT*?F**T成真解釋凡使得

取值真解釋?zhuān)Q(chēng)為

成真解釋。凡使得

取值假解釋?zhuān)Q(chēng)為

成假解釋。第46頁(yè)47/49例考查公式

=(P

Q)

R

PQR(PQ)R真值(P,Q,R)TTTT1個(gè)成真解釋TTFF1個(gè)成假解釋TT*?1個(gè)成真解釋1個(gè)成假解釋F**T?個(gè)成真解釋*F*T第47頁(yè)48/49永真公式與永假公式定義：假如一個(gè)公式全部完全解釋例

永假公式P∧

P永真公式P∨

PP

P(P

Q)

(

Q

P)均為成真解釋?zhuān)瑒t稱(chēng)該公式為永真公式或稱(chēng)為重言式。均為成假解釋?zhuān)瑒t稱(chēng)該公式為永假公式或稱(chēng)為予盾式。第48頁(yè)49/49可滿足公式與非永真公式定義：假如一個(gè)公式例P

Q可滿足公式，非永真公式PQ可滿足公式，非永真公式存在成真解釋?zhuān)瑒t稱(chēng)該公式為可滿足公式；存在成假解釋?zhuān)瑒t稱(chēng)該公式為非永真公式。第49頁(yè)50/601.2.2等價(jià)公式邏輯等值(等價(jià))概念幾組主要等值(等價(jià))公式利用等值(等價(jià))公式，對(duì)公式進(jìn)行化簡(jiǎn)，以求解公式成真解釋、成假解釋第50頁(yè)51/60邏輯相等=定義給定兩個(gè)公式

和

，設(shè)P1，P2，……，Pn為

和

全部命題變?cè)?，那?/p>

和

有2n個(gè)解釋。假如對(duì)每個(gè)解釋?zhuān)?/p>

和

永取相同真假值，則稱(chēng)

和

是邏輯等價(jià)(等值、相等)，記為

=

。真值表相同第51頁(yè)52/60例問(wèn)：PP=

P?從真值表，能夠看出：PP=

PP

PPPTFTF=FFTFT=T考查真值表以下第52頁(yè)53/60等值公式第53頁(yè)54/60等值公式第54頁(yè)55/60⑥等值變換、否定深入公式第55頁(yè)第56頁(yè)57/60原命題、逆命題、否命題、逆否命題設(shè)原命題為蘊(yùn)含式：PQ，則逆命題為：QP，

否命題為：

P

Q，

逆否命題為：

Q

P，于是PQ=QPQP=PQ真值表法等值變換法第57頁(yè)58/60例判斷以下公式類(lèi)型

Q∨((P∨Q)∧P)解:Q∨

((P∨Q)∧P) =Q∨(

(P∨Q))∨

P =Q∨(P

∧

Q))∨

P=(Q∨P)∨P

=Q

∨(P∨P)

=Q∨T=

T所以，它是永真。

第58頁(yè)59/60例判斷以下公式類(lèi)型

(P∨P)((Q∧Q)∧R)解:(P∨P)((Q∧Q)∧R) =T(F∧R) =F∧R =F所以，它是永假。第59頁(yè)60/60例((QP)Q)=(PQ)

Q)記P:我考試經(jīng)過(guò),Q:我心情好PQ

((QP)Q)(PQ)

Q)TTFFTFTTFTFFFFTT并非假如只有考試經(jīng)過(guò)才能心情好那么我心情好=假如只要考試經(jīng)過(guò)就能心情好那么我心情不好也能夠利用等值公式證實(shí)。第60頁(yè)61/60成真解釋和成假解釋求解方法（1）否定深入：即把否定詞一直深入至命題變?cè)?；?）部分解釋?zhuān)哼x定某個(gè)出現(xiàn)次數(shù)最多變?cè)獙?duì)它作真或假兩種解釋從而得公式；（3）化簡(jiǎn)；（4）依次類(lèi)推，直至產(chǎn)生公式全部解釋。前提是公式中沒(méi)有蘊(yùn)含詞、等價(jià)詞第61頁(yè)62/60例(p7)試判定公式

(PQ)

((

Q

P)

R)

永真性和可滿足性。解：對(duì)P=F進(jìn)行解釋并化簡(jiǎn)。

原式=

(FQ)

(