命題邏輯04(證明方法).ppt

《命題邏輯04(證明方法).ppt》由會員分享，可在線閱讀，更多相關(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ù)。命題符號化為：p→q此命題的真值根據(jù)N的取值確定。,例題解（2）,2.如果2是偶數(shù)，那么3也是偶數(shù)。解：設(shè)p：2是偶數(shù)。q：3是偶數(shù)。命題符號化為：p→q因?yàn)閜為真命題，q為假命題，所以此命題為永假命題,例題解（3）,3.如果4能夠整除整數(shù)K，那么2也能整除K。解：設(shè)p：4能夠整除整數(shù)K。q：2也能整除K。命題符號化為：p→q此命題為永真命題。即有p?q,命題公式的關(guān)系,邏輯等值（logicallyequivalent）A?B設(shè)A、B是公式，如果在任意解釋Ｉ下，A?B是重言式，則稱公式A、B是等值的。邏輯蘊(yùn)涵（logicallyimply）AB設(shè)A、B是公式，如果在任意解釋Ｉ下，A→B是重言式，則稱公式A邏輯蘊(yùn)涵B。,基本蘊(yùn)涵式,(1)化簡律：A?B=>A,A?B=>B(2)附加律：A=>A?B,B=>A?B(3)假言推理：A?(A?B)=>B(4)拒取式：(A?B)??B=>?A(5)析取三段論：(A?B)??B=>A(6)假言三段論：(A?B)?(B?C)=>A?C(7)等價(jià)三段論：(A?B)?(B?C)=>A?C(8)二難推理：(A?C)?(A?B)?(C?B)=>B(9)構(gòu)造性二難：(A?B)?(C?D)?(A?C)=>B?D(10)破壞性二難：(A?B)?(C?D)?(?B??D)=>?A??C,邏輯推理,1.如果下雨，則菜價(jià)會上漲。菜價(jià)上漲了，因此下了雨。2.如果麗莎今年工作表現(xiàn)好，她會得到獎金。如果她得到獎金，她會去度假。如果她去度假，她會去航海。麗莎沒有去航海，因此她沒有得到獎金。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)A1∧A2∧…∧Ak→B為重言式時(shí)，稱由前提A1,A2,…Ak推出B的推理是有效的（或正確的），并稱B是該前提的有效結(jié)論。形式結(jié)構(gòu)記為：A1∧A2∧…∧Ak=>B或?yàn)閧A1,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à)會上漲。菜價(jià)上漲了，因此下了雨。證明：設(shè)p:下雨。q:菜價(jià)上漲。推理形式化：p→q,q?p((p→q)∧q)→p??((?p∨q)∧q)∨p??(?p∨q)∨?q∨p?(p∧?q)∨?q∨p??q∨p—非重言式,推理證明,2.如果麗莎今年工作表現(xiàn)好，她會得到獎金。如果她得到獎金，她會去度假。如果她去度假，她會去航海。麗莎沒有去航海，因此她沒有得到獎金。證明：設(shè)p:麗莎工作表現(xiàn)好。q：麗莎得到了獎金。r：麗莎去度假。s：麗莎去航海。推理的形式化為：p→q,q→r,r→s,?s??q,自然推理系統(tǒng),定義3.2一個形式系統(tǒng)I記為:由下面四個部分組成：(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ī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個公式。,定義3.3自然推理系統(tǒng)P定義（續(xù)）,（4）假言推理規(guī)則（或稱分離規(guī)則）：若證明的公式序列中已出現(xiàn)過A→B和A，則由假言推理定律(A→B)∧A=>B可知，B是A→B和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：麗莎得到了獎金。r：麗莎去度假。s：麗莎去航海。推理的形式化為：p→q,q→r,r→s,?s??q證明：①q→r前提引入②r→s前提引入③q→s①②假言三段論④?s前提引入⑤?q③④拒取式,證明推理的有效性,例4：如果麗莎有天賦且努力工作，在可以找到好工作。如果她找到好工作，則她會幸福。因此，如果她不幸福，那么她沒有努力工作或她沒有天賦。證明：設(shè)p:麗莎有天賦。q：麗莎努力工作。r：麗莎找到好工作。s：麗莎幸福。則推理的形式化為：(p∧q)→r,r→s,?s??p∨?q①?s前提引入②r→s前提引入③?r①②拒取式④(p∧q)→r前提引入⑤?(p∧q)③④拒取式⑥?p∨?q置換規(guī)則,證明技術(shù),直接證明法（directproof）（A1∧A2∧…∧Ak)→B?1間接證明法（indirectproof）(A1∧A2∧…∧Ak)→(A→B)?(A1∧A2∧…∧Ak∧A)→B?1反證法/歸謬法（proofbycontradiction）1?(A1∧A2∧…∧Ak)→B??(A1∧A2∧…∧Ak∧?B)(A1∧A2∧…∧Ak∧?B)?0,間接證明法,例：┐p∨q,r∨┐q,r→s=>p→s①p附加前提引入②┐p∨q前提引入③q①②析取三段論④r∨┐q前提引入⑤r③④析取三段論⑥r(nóng)→s前提引入⑦s⑤⑥假言推理[⑧p→scp規(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í)屋里燈光未滅。則推理形式化為：P∨Q，P→?R，S→T，?S→R，?T?Q,反證法(歸謬法),例:P∨Q，P→?R，S→T，?S→R，?T?Q證明:（1）?Q附加前提引入（2）P∨Q前提引入（3）P(1)(2)析取三段論（4）P→┐R前提引入（5）?R(3)(4)假言推理（6）?S→R前提引入（7）S(5)(6)拒取式（8）S→T前提引入（9）T(7)(8)假言推理(10)?T前提引入(11)T∧?T(9)(10)合取,推理證明,3.如果我的辦公桌上有支票簿，則說明我已經(jīng)付過電話費(fèi)。我在吃早飯時(shí)查看電話賬單或在辦公室查看電話賬單。如果在早餐時(shí)查看電話賬單，則支票簿在早餐桌上，說明我沒有付電話費(fèi)。如果我在辦公室查看電話賬單，則支票簿在我的辦公桌上，支票簿到底在哪里？解：設(shè)p:支票簿在我的辦公桌上。q:我已經(jīng)付過電話費(fèi)。r:我在吃早飯時(shí)查看電話賬單。s:我在辦公室查看電話賬單。t:支票簿在早餐桌上。推理形式化為：p→q，r∨s，(r→t)∧?q，s→p??(port),直接證明法,前提：p→q，r∨s，(r→t)∧?q，s→p①s→p前提引入②p→q前提引入③s→q①②假言三段論④(r→t)∧?q前提引入⑤┐q④化簡⑥┐s③⑤拒取式⑦r∨s前提引入⑧r⑥⑦析取三段論⑨r→t④化簡⑩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),