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

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

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

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

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

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

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

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

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

8大于12。

1+101=110。

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

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

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

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

等價(jià)詞

第21頁22/49﹁P讀作“非P”

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

PTFFT真值表

例P：雪是黑色。

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

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

≠

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

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

QTTTTFFFTFFFF

例

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

Q：今天下雨。

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

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

QTTTTFTFTTFFF例

P:他會(huì)英語。

Q：他會(huì)法語。

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

第25頁26/49可兼“或”——不可兼“或”PQP∨QTTTTFTFTTFFF他會(huì)英語或法語。PQP∨Q

(P∧﹁

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

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

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

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

P→Q：假如我心情好，那么1＝2。第29頁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頁31/49P

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

QTTTTFFFTFFFT例

P:2+3＝5

Q:e是無理數(shù)

P

Q

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

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

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

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

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

TTTFFFTFTF永真恒等否定

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

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

f14為或非↓f1為與非

第35頁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頁37/491.1.3合式公式合式公式為以下定義式子，簡稱為公式：任何命題變?cè)枪?；假如P為公式，則

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

P

Q,P

Q,P

Q,P

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

Q)

(PQ)三元公式((P

Q)

R)

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

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

﹃

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

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

P)

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

Q：2+2＝4。

R：烏鴉是白色。

求以下公式真值：

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

R)

(2)(

P∨R)

(P∧

R)

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

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

((QP)

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

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

P1,P2,

…,Pn

問題：n元公式

有多少個(gè)完全解釋？1.2.1解釋假如對(duì)每個(gè)命題變?cè)o予一個(gè)確定值，則稱對(duì)公式

給了一個(gè)完全解釋；假如僅對(duì)部分變?cè)o予確定值，則稱對(duì)公式

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

=(P

Q)

R

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

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

取值真解釋，均稱為

成真解釋。凡使得

取值假解釋，均稱為

成假解釋。第46頁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頁48/49永真公式與永假公式定義：假如一個(gè)公式全部完全解釋例

永假公式P∧

P永真公式P∨

PP

P(P

Q)

(

Q

P)均為成真解釋，則稱該公式為永真公式或稱為重言式。均為成假解釋，則稱該公式為永假公式或稱為予盾式。第48頁49/49可滿足公式與非永真公式定義：假如一個(gè)公式例P

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

和

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

和

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

和

有2n個(gè)解釋。假如對(duì)每個(gè)解釋，

和

永取相同真假值，則稱

和

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

=

。真值表相同第51頁52/60例問：PP=

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

PP

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

否命題為：

P

Q，

逆否命題為：

Q

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

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頁59/60例判斷以下公式類型

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

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

((QP)Q)(PQ)

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

(PQ)

((

Q

P)

R)

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

原式=

(FQ)

(