命題邏輯04(證明方法).ppt
《命題邏輯04(證明方法).ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《命題邏輯04(證明方法).ppt(30頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
第一部分?jǐn)?shù)理邏輯,MathematicalLogic,1.4命題邏輯的推理理論,內(nèi)容:命題公式的蘊(yùn)涵式基本蘊(yùn)涵式直接證明法間接證明法反證法/歸謬法目標(biāo):熟記基本蘊(yùn)涵式熟練利用上述各種證明法論證任意推理的有效性,命題邏輯的蘊(yùn)涵式,例1.符號化下列命題并確定真值1.如果自然數(shù)N是偶數(shù),那么N+1也是偶數(shù)。2.如果2是偶數(shù),那么3也是偶數(shù)。3.如果4能夠整除整數(shù)K,那么2也能整除K。,例題解(1),1.如果自然數(shù)N是偶數(shù),那么N+1也是偶數(shù)。解:設(shè)p:自然數(shù)N是偶數(shù)。q:N+1是偶數(shù)。命題符號化為:pq此命題的真值根據(jù)N的取值確定。,例題解(2),2.如果2是偶數(shù),那么3也是偶數(shù)。解:設(shè)p:2是偶數(shù)。q:3是偶數(shù)。命題符號化為:pq因?yàn)閜為真命題,q為假命題,所以此命題為永假命題,例題解(3),3.如果4能夠整除整數(shù)K,那么2也能整除K。解:設(shè)p:4能夠整除整數(shù)K。q:2也能整除K。命題符號化為:pq此命題為永真命題。即有pq,命題公式的關(guān)系,邏輯等值(logicallyequivalent)AB設(shè)A、B是公式,如果在任意解釋下,AB是重言式,則稱公式A、B是等值的。邏輯蘊(yùn)涵(logicallyimply)AB設(shè)A、B是公式,如果在任意解釋下,AB是重言式,則稱公式A邏輯蘊(yùn)涵B。,基本蘊(yùn)涵式,(1)化簡律:AB=A,AB=B(2)附加律:A=AB,B=AB(3)假言推理:A(AB)=B(4)拒取式:(AB)B=A(5)析取三段論:(AB)B=A(6)假言三段論:(AB)(BC)=AC(7)等價(jià)三段論:(AB)(BC)=AC(8)二難推理:(AC)(AB)(CB)=B(9)構(gòu)造性二難:(AB)(CD)(AC)=BD(10)破壞性二難:(AB)(CD)(BD)=AC,邏輯推理,1.如果下雨,則菜價(jià)會(huì)上漲。菜價(jià)上漲了,因此下了雨。2.如果麗莎今年工作表現(xiàn)好,她會(huì)得到獎(jiǎng)金。如果她得到獎(jiǎng)金,她會(huì)去度假。如果她去度假,她會(huì)去航海。麗莎沒有去航海,因此她沒有得到獎(jiǎng)金。3.如果我的辦公桌上有支票簿,則說明我已經(jīng)付過電話費(fèi)。我在吃早飯時(shí)查看電話賬單或在辦公室查看電話賬單。如果在早餐時(shí)查看電話賬單,則支票簿在早餐桌上,說明我沒有付電話費(fèi)。如果我在辦公室查看電話賬單,則支票簿在我的辦公桌上,支票簿到底在哪里?,推理的形式結(jié)構(gòu),有限命題序列A1,A2,Ak,B稱為推理(或論證(argument)。A1,A2,Ak稱為推理的前提(premise),B稱為推理的結(jié)論(conclusion)。當(dāng)且僅當(dāng)A1A2AkB為重言式時(shí),稱由前提A1,A2,Ak推出B的推理是有效的(或正確的),并稱B是該前提的有效結(jié)論。形式結(jié)構(gòu)記為:A1A2Ak=B或?yàn)锳1,A2,Ak|-B。,重言式的證明方法,真值表法等值演算法主析取范式法形式演算系統(tǒng)(1)自然推理系統(tǒng)-從任意給定的前提出發(fā),應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算,得到的公式是推理的結(jié)論。(2)公理推理系統(tǒng)-只能從若干給定的公理出發(fā),應(yīng)用系統(tǒng)中推理規(guī)則進(jìn)行推理演算,得到的結(jié)論是系統(tǒng)中的重言式,稱為定理。,推理證明,1.如果下雨,則菜價(jià)會(huì)上漲。菜價(jià)上漲了,因此下了雨。證明:設(shè)p:下雨。q:菜價(jià)上漲。推理形式化:pq,qp(pq)q)p(pq)q)p(pq)qp(pq)qpqp非重言式,推理證明,2.如果麗莎今年工作表現(xiàn)好,她會(huì)得到獎(jiǎng)金。如果她得到獎(jiǎng)金,她會(huì)去度假。如果她去度假,她會(huì)去航海。麗莎沒有去航海,因此她沒有得到獎(jiǎng)金。證明:設(shè)p:麗莎工作表現(xiàn)好。q:麗莎得到了獎(jiǎng)金。r:麗莎去度假。s:麗莎去航海。推理的形式化為:pq,qr,rs,sq,自然推理系統(tǒng),定義3.2一個(gè)形式系統(tǒng)I記為:由下面四個(gè)部分組成:(1)非空的字符表集,記作A(I)。(2)A(I)中符號構(gòu)造的合式公式集,記作E(I)。(3)E(I)中一些特殊的公式組成的公理集,記作AX(I)。(4)推理規(guī)則集,記作R(I)。,定義3.3自然推理系統(tǒng)P定義,1字母表(1)命題變項(xiàng)符號:p,q,r,,pi,qi,ri,(2)聯(lián)結(jié)詞符號:,(3)括號和逗號:(,),2合式公式同前面定義3推理規(guī)則(1)前提引入規(guī)則:在證明的任何步驟上都可以引入前提。(2)結(jié)論引入規(guī)則:在證明的任何步驟上所得到的結(jié)論都可以作為后繼證明的前提。(3)置換規(guī)則:在證明的任何步驟上,命題公式中的子公式都可以用與之等值的公式置換,得到公式序列中的又一個(gè)公式。,定義3.3自然推理系統(tǒng)P定義(續(xù)),(4)假言推理規(guī)則(或稱分離規(guī)則):若證明的公式序列中已出現(xiàn)過AB和A,則由假言推理定律(AB)A=B可知,B是AB和A的有效結(jié)論。由結(jié)論引入規(guī)則可知,可將B引入到命題序列中來。用圖式表示為如下形式:,定義3.3自然推理系統(tǒng)P定義(續(xù)),(5)附加規(guī)則:,(6)化簡規(guī)則:,定義3.3自然推理系統(tǒng)P定義(續(xù)),(7)拒取式規(guī)則:,(8)假言三段論規(guī)則:,定義3.3自然推理系統(tǒng)P定義(續(xù)),(9)析取三段論規(guī)則:,(10)構(gòu)造性二難推理:,定義3.3自然推理系統(tǒng)P定義(續(xù)),(11)合取引入規(guī)則:,(12)破壞性二難推理規(guī)則:,自然推理系統(tǒng),例2:設(shè)p:麗莎工作表現(xiàn)好。q:麗莎得到了獎(jiǎng)金。r:麗莎去度假。s:麗莎去航海。推理的形式化為:pq,qr,rs,sq證明:qr前提引入rs前提引入qs假言三段論s前提引入q拒取式,證明推理的有效性,例4:如果麗莎有天賦且努力工作,在可以找到好工作。如果她找到好工作,則她會(huì)幸福。因此,如果她不幸福,那么她沒有努力工作或她沒有天賦。證明:設(shè)p:麗莎有天賦。q:麗莎努力工作。r:麗莎找到好工作。s:麗莎幸福。則推理的形式化為:(pq)r,rs,spqs前提引入rs前提引入r拒取式(pq)r前提引入(pq)拒取式pq置換規(guī)則,證明技術(shù),直接證明法(directproof)(A1A2Ak)B1間接證明法(indirectproof)(A1A2Ak)(AB)(A1A2AkA)B1反證法/歸謬法(proofbycontradiction)1(A1A2Ak)B(A1A2AkB)(A1A2AkB)0,間接證明法,例:pq,rq,rs=psp附加前提引入pq前提引入q析取三段論rq前提引入r析取三段論rs前提引入s假言推理pscp規(guī)則,論證下述推理的有效性,已知一起盜竊案的事實(shí)如下:A或B盜竊了x;若A盜竊了x,則作案時(shí)間不能發(fā)生在午夜前;若B證詞正確,則在午夜時(shí)屋里燈光未滅;若B證詞不正確,則作案時(shí)間發(fā)生在午夜前;午夜時(shí)屋里燈光滅了。B盜竊了x。證明:設(shè)P:A盜竊了x;Q:B盜竊了x;R:作案時(shí)間發(fā)生在午夜前;S:B證詞正確;T:在午夜時(shí)屋里燈光未滅。則推理形式化為:PQ,PR,ST,SR,TQ,反證法(歸謬法),例:PQ,PR,ST,SR,TQ證明:(1)Q附加前提引入(2)PQ前提引入(3)P(1)(2)析取三段論(4)PR前提引入(5)R(3)(4)假言推理(6)SR前提引入(7)S(5)(6)拒取式(8)ST前提引入(9)T(7)(8)假言推理(10)T前提引入(11)TT(9)(10)合取,推理證明,3.如果我的辦公桌上有支票簿,則說明我已經(jīng)付過電話費(fèi)。我在吃早飯時(shí)查看電話賬單或在辦公室查看電話賬單。如果在早餐時(shí)查看電話賬單,則支票簿在早餐桌上,說明我沒有付電話費(fèi)。如果我在辦公室查看電話賬單,則支票簿在我的辦公桌上,支票簿到底在哪里?解:設(shè)p:支票簿在我的辦公桌上。q:我已經(jīng)付過電話費(fèi)。r:我在吃早飯時(shí)查看電話賬單。s:我在辦公室查看電話賬單。t:支票簿在早餐桌上。推理形式化為:pq,rs,(rt)q,sp?(port),直接證明法,前提:pq,rs,(rt)q,spsp前提引入pq前提引入sq假言三段論(rt)q前提引入q化簡s拒取式rs前提引入r析取三段論rt化簡t假言推理結(jié)論:支票簿在早餐桌上,作業(yè),能夠應(yīng)用自然推理系統(tǒng)的證明方法,論證任意推理的有效性。,規(guī)則名稱中英對照,(1)化簡規(guī)則(conjunctivesimplification)(2)附加規(guī)則(disjunctiveaddition)(3)合取引入規(guī)則(conjunctiveaddition)(4)析取三段論規(guī)則(disjunctivesyllogism)(5)假言推理規(guī)則(methodofaffirming)(6)拒取式規(guī)則(methodofdenying)(7)假言三段論規(guī)則(hypotheticalsyllogism)(8)二難推理規(guī)則(dilemma),- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 命題邏輯 04 證明 方法
鏈接地址:http://ioszen.com/p-11525055.html