大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)第一章命題邏輯.ppt
《大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)第一章命題邏輯.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)第一章命題邏輯.ppt(39頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
離散數(shù)學(xué),第一章命題邏輯,2/38,回顧,對(duì)偶原理定義,三條原理:非運(yùn)算與對(duì)偶,等價(jià),永真蘊(yùn)含析取范式和合取范式基本積,基本和基本和的積,基本積的和主析取范式和主合取范式極小項(xiàng)(積),極大項(xiàng)(和),基二進(jìn)制數(shù)十進(jìn)制數(shù)描述符極小項(xiàng)的和,極大項(xiàng)的積,兩者的關(guān)系。,3/38,求范式步驟:,(2)否定消去或內(nèi)移。,(3)利用分配律。,(1)消去聯(lián)結(jié)詞,回顧,4/38,1.7命題演算的推理理論,數(shù)理邏輯的一個(gè)主要任務(wù)就是提供一套推理規(guī)則,給定一些前提,利用所提供的推理規(guī)則,推導(dǎo)出一些結(jié)論來(lái),這個(gè)過(guò)程稱為演繹或證明。生活中:倘若認(rèn)定前提是真的,從前提推導(dǎo)出結(jié)論的論證是遵守了邏輯推理規(guī)則,則認(rèn)為此結(jié)論是真的,并且認(rèn)為這個(gè)論證過(guò)程是合法的。數(shù)理邏輯中:不關(guān)心前提的真實(shí)真值,把注意力集中于推理規(guī)則的研究,依據(jù)這些推理規(guī)則推導(dǎo)出的任何結(jié)論,稱為有效結(jié)論,而這種論證則被稱為有效論證。,5/38,有效結(jié)論,定義:設(shè)A和B是兩個(gè)命題公式,當(dāng)且僅當(dāng)AB是個(gè)永真式,即AB,則說(shuō)B是A的有效結(jié)論,或B由A可邏輯的推出??砂言摱x推廣到有n個(gè)前提的情況。,6/38,有效結(jié)論,定義:例:H1:今天周一或者今天下雨。H2:今天不是周一。C:今天下雨。,7/38,證明有效結(jié)論的方法,1,真值表法思路:“證明使前提集合取值為真的那些組真值指派,也一定使結(jié)論取值為真”。例:考察結(jié)論C是否是下列前提H1,H2,H3的結(jié)論。(1)H1:PQ,H2:P,C:Q,8/38,真值表法,(2)真值表構(gòu)造如下:,9/38,真值表法,(3),10/38,真值表法,例:一份統(tǒng)計(jì)表格的錯(cuò)誤或者是由于材料不可靠,或者是由于計(jì)算有錯(cuò)誤;這份統(tǒng)計(jì)表格的錯(cuò)誤不是由于材料不可靠,所以這份統(tǒng)計(jì)表格是由于計(jì)算有錯(cuò)誤。解:設(shè)P:一份統(tǒng)計(jì)表格的錯(cuò)誤是由于材料不可靠。Q:一份統(tǒng)計(jì)表格的錯(cuò)誤是由于計(jì)算有錯(cuò)誤。于是問(wèn)題可符號(hào)化為:(PQ)PQ,11/38,真值表法,PQ(PQ)PQ0000011110001101,12/38,證明有效結(jié)論的方法,2,直接證法在命題變?cè)^多的情況下,真值表法顯得不方便,我們采用直接證明法,為此先給出如下的定義定義:設(shè)S是一個(gè)命題公式的集合,從S推出命題公式C的推理過(guò)程是命題公式的一個(gè)有限序列:C1,C2,Cn。其中,Ci或者屬于S,或者是某些Cj(ji)的有效結(jié)論,并且Cn就是C。如何構(gòu)造這個(gè)推理序列以得出結(jié)論C呢?只要遵循下面的推理規(guī)則,使用列出的等價(jià)式或永真蘊(yùn)涵式,就能構(gòu)造出滿足要求的公式序列。為了幫助大家記憶,我們把常用的等價(jià)式和永真蘊(yùn)涵式再次列出來(lái)。,13/38,常用永真蘊(yùn)含式,I1:PQP,I2:PPQ,I3:PPQI4:QPQ,I5:(PQ)P,I6:(PQ)QI7:P,QPQ,I8:P,PQQ,I9:P,PQQI10:Q,PQP,I11:PQ,QRPRI12:PQ,PR,QRR公式中“,”代表“”,公式不必死記硬背,其證明均可從“”的定義出發(fā)。例如對(duì)I11前件為真時(shí)保證PQ和QR都必為真,PQ為真,則保證P為真時(shí)Q一定為真,而Q為真和QR為真則保證了R必為真,P為真,R為真自然保證了PR為真,問(wèn)題得證。,14/38,常用等價(jià)式,E1:PP,E2:PQQP,E3:PQQPE4:(PQ)RP(QR)E5:(PQ)RP(QR)E6:(PQ)R(PR)(QR)E7:(PQ)R(PR)(QR)E8:(PQ)PQE9:(PQ)PQE10:PPPE11:PPP,15/38,常用等價(jià)式,E12:R(PP)RE13:R(PP)RE14:R(PP)TE15:R(PP)FE16:PQPQE17:(PQ)PQE18:PQQPE19:P(QR)(PQ)RE20:(PQ)PQE21:PQ(PQ)(QP)E22:PQ(PQ)(PQ),16/38,常用等價(jià)公式,17/38,直接證法,直接證明法:使用推理規(guī)則和給定的等價(jià)式及永真蘊(yùn)涵式進(jìn)行推導(dǎo)證明。推理規(guī)則:規(guī)則P:在推導(dǎo)過(guò)程中,任何時(shí)候都可以引入前提。引入一個(gè)前提稱為使用一次P規(guī)則。規(guī)則T:在推導(dǎo)中,如果前面有一個(gè)或多個(gè)公式永真蘊(yùn)含公式S,則可以把公式S引進(jìn)推導(dǎo)過(guò)程中。換句話說(shuō),引進(jìn)前面推導(dǎo)過(guò)程中的推理結(jié)果稱為使用T規(guī)則。,18/38,直接證法,解:1(1)(PQ)P規(guī)則1(2)PQT規(guī)則(1)和E111(3)PQT規(guī)則(2)和E274(4)QRP規(guī)則4(5)QRT規(guī)則(4)和E271,4(6)PRT,(3),(5)和I127(7)RP規(guī)則1,4,7(8)PT,(6),(7)和I12,19/38,直接證法,例:證明公式SR可由公式PQ,PR,QS推出解:?jiǎn)栴}即證PQ,PR,QSSR1、PQP規(guī)則2、PQT規(guī)則和13、QSP規(guī)則4、QST規(guī)則和35、PST規(guī)則及2和46、SPT規(guī)則和57、PRP規(guī)則8、(PR)(RP)T規(guī)則和79、PRT規(guī)則和810、SRT規(guī)則及6和9;11、SRT規(guī)則和9得證。,20/38,直接證法,例:(PQ)(RS),(QP)R,RPQ1、RP規(guī)則2、(QP)RP規(guī)則3、QPT規(guī)則及1和24、RST規(guī)則及15、(PQ)(RS)P規(guī)則6、PQT規(guī)則及4和57、(PQ)(QP)T規(guī)則及3和68、PQT規(guī)則和7,21/38,直接證法,推理規(guī)則:CP規(guī)則:如果能從R和前提集合中推導(dǎo)出S來(lái),則就能夠從前提集合中推導(dǎo)出RS。換句話說(shuō),當(dāng)結(jié)論是RS的形式的時(shí)候,可以把結(jié)論的前件當(dāng)作一個(gè)附加前提使用,并且它和前提一起若能推出結(jié)論的后件,則問(wèn)題得證實(shí)際上恒等式E28就可以推出CP規(guī)則:(PQ)R(PQ)R(PQ)RP(QR)P(QR),22/38,直接證法,解:1(1)RP規(guī)則(附加前提)2(2)RPP規(guī)則1,2(3)PT規(guī)則,(1),(2)和I94(4)P(QS)P規(guī)則1,2,4(5)QST規(guī)則,(3),(4)和I106(6)QP規(guī)則1,2,4,6(7)ST規(guī)則,(5),(6)和I101,2,4,6(8)RSCP規(guī)則,(1),(7),23/38,例:證明RS是前提P(QS),R(PQ)的有效結(jié)論解:原證明即證:P(QS),R(PQ)RS1、RP規(guī)則(附加前提)2、R(PQ)P規(guī)則3、PQT規(guī)則及1和24、PT規(guī)則和35、P(QS)P規(guī)則6、QST規(guī)則及4和57、QT規(guī)則和38、ST規(guī)則及6和79、RSCP規(guī)則及1和8,直接證法,24/38,例:證明P(QR),Q,PSSR解:1、SP規(guī)則(附加前提)2、PSP規(guī)則3、PT規(guī)則及1和24、P(QR)P規(guī)則5、QRT規(guī)則及3和46、QP規(guī)則7、RT規(guī)則及5和68、SRCP規(guī)則及1和7,直接證法,25/38,證明有效結(jié)論的方法,3,間接證明法(反證法)定義:設(shè)公式H1,H2,Hm中的原子變?cè)荘1,P2,Pn。如果給各原子變?cè)狿1,P2,Pn指派某一個(gè)真值集合,能使H1H2Hm具有真值T,則命題公式集合H1,H2,Hm稱為一致的(或相容的);對(duì)于各原子變?cè)拿恳粋€(gè)真值指派,如果命題公式H1,H2,Hm中至少有一個(gè)是假,從而使得H1H2Hm是假,則稱命題公式集合是不一致的(或不相容的)。例如:令H1=P,H2=P,則H1H2=PP是矛盾式,所以P,P是不相容的。,26/38,反證法,定理:若存在一個(gè)公式R,使得H1H2HmRR則公式H1,H2,,Hm是不相容的。證明:設(shè),H1H2HmRR則意味著(H1H2Hm)(RR)是重言式,而RR是矛盾式,所以前件H1H2Hm必永假。因此,H1,H2,,Hm是不相容的。,27/38,反證法,定理:設(shè)命題公式集合H1,H2,Hm是一致的,于是從前提集合出發(fā)可以邏輯的推出公式C的充要條件是從前提集合H1,H2,Hm,C出發(fā),可以邏輯地推出一個(gè)矛盾(永假)式。證明:必要性:由于H1H2HmC,即H1H2HmC為永真式,因而使H1H2Hm為真的真值指派一定使C為真,C為假,從而使H1H2HmC為假。必要性證完。,28/38,反證法,證充分性:由于H1H2HmC可以邏輯地推出一個(gè)矛盾,即H1H2HmCF即H1H2HmCF為永真式,即H1H2HmC為假,由假設(shè)知H1,H2,Hm是一致的,所以任何使H1H2Hm為真的命題變?cè)恼嬷抵概杀厝皇笴為假,從而使C為真。故有H1H2HmC該定理說(shuō)明用直接證明法可以證明的結(jié)論,用間接證明法都可以證明,反之亦然。因此,為了證明B是A的結(jié)論,可以把A和B作為前提,然后推出一個(gè)矛盾,從而使問(wèn)題得證。下面用例子說(shuō)明。,29/38,反證法,F規(guī)則:如果前體集合和S不相容,那么可以從前提集合中推出S。例:證明(PQ)是PQ的有效結(jié)論。解:把(PQ)作為假設(shè)前提,并證明該假設(shè)前提導(dǎo)致一個(gè)永假式。1(1)(PQ)P規(guī)則(假設(shè)前提)1(2)PQT規(guī)則,(1)和E101(3)PT規(guī)則,(2)和I14(4)PQP規(guī)則4(5)PT規(guī)則,(4)和I11,4(6)PPT規(guī)則,(3),(5)和I161,4(7)(PQ)F規(guī)則,(1),(6),30/38,反證法,例:證明PQ,PR,QRR解:1、RP規(guī)則(假設(shè)前提)2、PRP規(guī)則3、PT規(guī)則及1和24、PQP規(guī)則5、QT規(guī)則及3和46、QRP規(guī)則7、RT規(guī)則及5和68、RRT規(guī)則及1和79、RF規(guī)則及1和8,31/38,反證法,例:足壇4支甲級(jí)隊(duì)進(jìn)行比賽,已知情況如下:前提:1、若大連萬(wàn)達(dá)獲冠軍,則北京國(guó)安和上海申花獲得亞軍2、若上海申花獲亞軍,則大連萬(wàn)達(dá)不能獲冠軍3、若陜西國(guó)力獲亞軍,則北京國(guó)安不能獲亞軍4、最后大連萬(wàn)達(dá)獲冠軍結(jié)論:5、陜西國(guó)力未獲亞軍,32/38,反證法,用推理的方法證明由1、2、3、4能否推出5解:首先將命題符號(hào)化令P:大連萬(wàn)達(dá)獲冠軍Q:北京國(guó)安獲亞軍R:上海申花獲亞軍S:陜西國(guó)力獲亞軍,33/38,反證法,于是問(wèn)題可符號(hào)化為:P(QR),RP,SQ,PS/*注意這里自然語(yǔ)言中的和表示的是排斥或,所以用來(lái)表示*/解:1、SP規(guī)則(假設(shè)前提)2、ST規(guī)則和13、SQP規(guī)則4、QT規(guī)則2和35、PP規(guī)則6、P(QR)P規(guī)則7、QRT規(guī)則5和68、RT規(guī)則4和79、RPP規(guī)則,34/38,反證法,10、PT規(guī)則8和911、PPT規(guī)則5和1012、SF規(guī)則1和11/*問(wèn)題得證*/,35/38,證明有效結(jié)論使用方法規(guī)律,當(dāng)要證明的結(jié)論是條件式時(shí),可考慮使用CP規(guī)則當(dāng)要證明的結(jié)論比較簡(jiǎn)單,而僅僅使用前提推導(dǎo)不明顯時(shí),可考慮使用間接證明法即F規(guī)則,以使推導(dǎo)過(guò)程變得簡(jiǎn)捷。,36/38,小結(jié),本章我們學(xué)習(xí)了命題的概念以及在命題集合上的運(yùn)算:、。但是這些邏輯聯(lián)結(jié)詞并不是必不可少的,于是引出了邏輯聯(lián)結(jié)詞最小全功能完備集的概念:,和,。,37/38,小結(jié),此外,我們完成了命題邏輯中的一個(gè)重要任務(wù):合式公式的判定求解方法:A:真值表法;B:等價(jià)公式變換法;C:利用對(duì)偶原理D:通過(guò)求主范式的方法。我們學(xué)習(xí)了一些常用的等價(jià)式和永真蘊(yùn)涵式及推理規(guī)則;目的是用命題邏輯解決推理問(wèn)題;我們介紹了P規(guī)則,T規(guī)則,CP規(guī)則,F(xiàn)規(guī)則的使用及使用我們介紹的等價(jià)式和蘊(yùn)含式及四條規(guī)則正確進(jìn)行推理的練習(xí)。,38/38,作業(yè),P25習(xí)題5(1),7(1):要求使用F規(guī)則9(1):要求使用F規(guī)則補(bǔ)充題:1,驗(yàn)證下列論述有效性如果李明學(xué)習(xí)努力,那么他成績(jī)好如果李明不熱衷于玩撲克,那么他就學(xué)習(xí)努力李明成績(jī)不好。所以,李明熱衷于玩撲克。,39/38,作業(yè)(續(xù)),2,證明下列各式的有效性,上機(jī)作業(yè):必做:任意輸入一個(gè)析取范式,計(jì)算并輸出其主析取范式選作:任意輸入一個(gè)命題公式,計(jì)算并輸出其真值表以及主析取和主合取范式。,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 大連理工大學(xué) 軟件 學(xué)院 離散數(shù)學(xué) 第一章 命題邏輯
鏈接地址:http://ioszen.com/p-11498708.html