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

第一部分數(shù)理邏輯,MathematicalLogic,1.4命題邏輯的推理理論,內(nèi)容：命題公式的蘊涵式基本蘊涵式直接證明法間接證明法反證法/歸謬法目標：熟記基本蘊涵式熟練利用上述各種證明法論證任意推理的有效性,命題邏輯的蘊涵式,例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ù)。解：設p：自然數(shù)N是偶數(shù)。q：N+1是偶數(shù)。命題符號化為：pq此命題的真值根據(jù)N的取值確定。,例題解（2）,2.如果2是偶數(shù)，那么3也是偶數(shù)。解：設p：2是偶數(shù)。q：3是偶數(shù)。命題符號化為：pq因為p為真命題，q為假命題，所以此命題為永假命題,例題解（3）,3.如果4能夠整除整數(shù)K，那么2也能整除K。解：設p：4能夠整除整數(shù)K。q：2也能整除K。命題符號化為：pq此命題為永真命題。即有pq,命題公式的關系,邏輯等值（logicallyequivalent）AB設A、B是公式，如果在任意解釋下，AB是重言式，則稱公式A、B是等值的。邏輯蘊涵（logicallyimply）AB設A、B是公式，如果在任意解釋下，AB是重言式，則稱公式A邏輯蘊涵B。,基本蘊涵式,(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)等價三段論：(AB)(BC)=>AC(8)二難推理：(AC)(AB)(CB)=>B(9)構造性二難：(AB)(CD)(AC)=>BD(10)破壞性二難：(AB)(CD)(BD)=>AC,邏輯推理,1.如果下雨，則菜價會上漲。菜價上漲了，因此下了雨。2.如果麗莎今年工作表現(xiàn)好，她會得到獎金。如果她得到獎金，她會去度假。如果她去度假，她會去航海。麗莎沒有去航海，因此她沒有得到獎金。3.如果我的辦公桌上有支票簿，則說明我已經(jīng)付過電話費。我在吃早飯時查看電話賬單或在辦公室查看電話賬單。如果在早餐時查看電話賬單，則支票簿在早餐桌上，說明我沒有付電話費。如果我在辦公室查看電話賬單，則支票簿在我的辦公桌上，支票簿到底在哪里？,推理的形式結構,有限命題序列A1,A2,Ak,B稱為推理（或論證（argument）。A1,A2,Ak稱為推理的前提（premise），B稱為推理的結論（conclusion）。當且僅當A1A2AkB為重言式時，稱由前提A1,A2,Ak推出B的推理是有效的（或正確的），并稱B是該前提的有效結論。形式結構記為：A1A2Ak=>B或為A1,A2,Ak|-B。,重言式的證明方法,真值表法等值演算法主析取范式法形式演算系統(tǒng)（1）自然推理系統(tǒng)-從任意給定的前提出發(fā)，應用系統(tǒng)中的推理規(guī)則進行推理演算，得到的公式是推理的結論。（2）公理推理系統(tǒng)-只能從若干給定的公理出發(fā)，應用系統(tǒng)中推理規(guī)則進行推理演算，得到的結論是系統(tǒng)中的重言式，稱為定理。,推理證明,1.如果下雨，則菜價會上漲。菜價上漲了，因此下了雨。證明：設p:下雨。q:菜價上漲。推理形式化：pq,qp(pq)q)p(pq)q)p(pq)qp(pq)qpqp非重言式,推理證明,2.如果麗莎今年工作表現(xiàn)好，她會得到獎金。如果她得到獎金，她會去度假。如果她去度假，她會去航海。麗莎沒有去航海，因此她沒有得到獎金。證明：設p:麗莎工作表現(xiàn)好。q：麗莎得到了獎金。r：麗莎去度假。s：麗莎去航海。推理的形式化為：pq,qr,rs,sq,自然推理系統(tǒng),定義3.2一個形式系統(tǒng)I記為:由下面四個部分組成：(1)非空的字符表集，記作A(I)。(2)A(I)中符號構造的合式公式集，記作E(I)。(3)E(I)中一些特殊的公式組成的公理集，記作AX(I)。(4)推理規(guī)則集，記作R(I)。,定義3.3自然推理系統(tǒng)P定義,1字母表（1）命題變項符號：p，q，r，,pi，qi，ri，（2）聯(lián)結詞符號：,（3）括號和逗號：(,)，2合式公式同前面定義3推理規(guī)則（1）前提引入規(guī)則：在證明的任何步驟上都可以引入前提。（2）結論引入規(guī)則：在證明的任何步驟上所得到的結論都可以作為后繼證明的前提。（3）置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個公式。,定義3.3自然推理系統(tǒng)P定義（續(xù)）,（4）假言推理規(guī)則（或稱分離規(guī)則）：若證明的公式序列中已出現(xiàn)過AB和A，則由假言推理定律(AB)A=>B可知，B是AB和A的有效結論。由結論引入規(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）構造性二難推理：,定義3.3自然推理系統(tǒng)P定義（續(xù)）,（11）合取引入規(guī)則：,（12）破壞性二難推理規(guī)則：,自然推理系統(tǒng),例2：設p:麗莎工作表現(xiàn)好。q：麗莎得到了獎金。r：麗莎去度假。s：麗莎去航海。推理的形式化為：pq,qr,rs,sq證明：qr前提引入rs前提引入qs假言三段論s前提引入q拒取式,證明推理的有效性,例4：如果麗莎有天賦且努力工作，在可以找到好工作。如果她找到好工作，則她會幸福。因此，如果她不幸福，那么她沒有努力工作或她沒有天賦。證明：設p:麗莎有天賦。q：麗莎努力工作。r：麗莎找到好工作。s：麗莎幸福。則推理的形式化為：(pq)r,rs,spqs前提引入rs前提引入r拒取式(pq)r前提引入(pq)拒取式pq置換規(guī)則,證明技術,直接證明法（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ī)則,論證下述推理的有效性,已知一起盜竊案的事實如下：A或B盜竊了x；若A盜竊了x，則作案時間不能發(fā)生在午夜前；若B證詞正確，則在午夜時屋里燈光未滅；若B證詞不正確，則作案時間發(fā)生在午夜前；午夜時屋里燈光滅了。B盜竊了x。證明：設P：A盜竊了x；Q：B盜竊了x；R：作案時間發(fā)生在午夜前；S：B證詞正確；T：在午夜時屋里燈光未滅。則推理形式化為：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)付過電話費。我在吃早飯時查看電話賬單或在辦公室查看電話賬單。如果在早餐時查看電話賬單，則支票簿在早餐桌上，說明我沒有付電話費。如果我在辦公室查看電話賬單，則支票簿在我的辦公桌上，支票簿到底在哪里？解：設p:支票簿在我的辦公桌上。q:我已經(jīng)付過電話費。r:我在吃早飯時查看電話賬單。s:我在辦公室查看電話賬單。t:支票簿在早餐桌上。推理形式化為：pq，rs，(rt)q，sp?(port),直接證明法,前提：pq，rs，(rt)q，spsp前提引入pq前提引入sq假言三段論(rt)q前提引入q化簡s拒取式rs前提引入r析取三段論rt化簡t假言推理結論:支票簿在早餐桌上,作業(yè),能夠應用自然推理系統(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),