命題演算(推理理論)[自動(dòng)保存的].ppt
1,第四講命題邏輯的推理理論,命題邏輯的推理理論也稱為命題演算主要內(nèi)容一、推理的形式結(jié)構(gòu)二、推理定律和推理規(guī)則三、邏輯證明方法,2,數(shù)理邏輯的推理理論主要研究推理的“思維過(guò)程”,為推理提供一定的推理規(guī)則。它只關(guān)心從前提得到結(jié)論這種推理的正確有效性。無(wú)論前提是否真得正確,它總是假設(shè)其是成立的。所以推理的正確性和結(jié)論的正確性可能是不一致的。推理理論在應(yīng)用上常常是將一些定理,定律,公理和條件作為前提,通過(guò)推理得到新的定理。,引言,3,一、推理的形式結(jié)構(gòu),定義1設(shè)A1,A2,Ak,B為命題公式.若對(duì)于每組賦值,A1A2Ak為假,或當(dāng)A1A2Ak為真時(shí),B也為真,則稱由前提A1,A2,Ak推出結(jié)論B的推理是有效的或正確的,并稱B是有效結(jié)論或稱B可由A1,A2,Ak邏輯推出.,定理1由命題公式A1,A2,Ak推B的推理正確當(dāng)且僅當(dāng)A1A2AkB為重言式,4,推理的形式結(jié)構(gòu),2.A1A2AkB若推理正確,記為A1A2AkB3.前提:A1,A2,Ak結(jié)論:B,推理的形式結(jié)構(gòu)1.A1,A2,AkB若推理正確,記為A1,A2,AnB,5,二、推理定律重言蘊(yùn)涵式,1.A(AB)附加律2.(AB)A化簡(jiǎn)律3.(AB)AB假言推理4.(AB)BA拒取式5.(AB)BA析取三段論6.(AB)(BC)(AC)假言三段論7.(AB)(BC)(AC)等價(jià)三段論8.(AB)(CD)(AC)(BD)構(gòu)造性二難(AB)(AB)B構(gòu)造性二難(特殊形式)9.(AB)(CD)(BD)(AC)破壞性二難每個(gè)等值式可產(chǎn)生兩個(gè)推理定律如,由AA可產(chǎn)生AA和AA,6,推理規(guī)則,(1)前提引入規(guī)則(P)在推理過(guò)程中,可以隨時(shí)引入已知的前提。(2)結(jié)論引入規(guī)則(T)在推理過(guò)程中,前面已推出的有效結(jié)論都可作為后續(xù)推理的前提引用。(3)置換規(guī)則(R)在推理過(guò)程中,命題公式中的子公式都可以用與之等值的命題公式置換,得到證明的公式序列的另一公式。(4)代入規(guī)則(S)在推理過(guò)程中,重言式中的任一命題變?cè)伎梢杂靡幻}公式代入,得到的仍是重言式。,7,推理規(guī)則,(4)假言推理規(guī)則(6)化簡(jiǎn)規(guī)則(8)假言三段論規(guī)則,(5)附加規(guī)則(7)拒取式規(guī)則(9)析取三段論規(guī)則,8,推理規(guī)則,(10)構(gòu)造性二難推理規(guī)則(12)合取引入規(guī)則,(11)破壞性二難推理規(guī)則,9,三、邏輯證明方法,判斷有效結(jié)論的過(guò)程就是論證過(guò)程?;痉椒ǎ海?)真值表法(2)直接證明法(3)間接證明法(反證法)具體:等值演算、主析取范式、構(gòu)造證明法等,10,例:判斷下列推理是否正確。今天楊尚樹(shù)或去網(wǎng)吧或去教室。他沒(méi)去教室,所以他去網(wǎng)吧了。設(shè)p:楊尚樹(shù)去網(wǎng)吧。q:楊尚樹(shù)去教室。則,前提:pq,q結(jié)論:p推理的形式結(jié)構(gòu):(pq)q)p,真值表法,11,真值表法,該命題公式為重言式,說(shuō)明推理正確,所以楊尚樹(shù)去網(wǎng)吧,(pq)q)p,12,推理實(shí)例,例1判斷下面推理是否正確(1)若今天是1號(hào),則明天是5號(hào).今天是1號(hào).所以,明天是5號(hào).(2)若今天是1號(hào),則明天是5號(hào).明天是5號(hào).所以,今天是1號(hào).,解設(shè)p:今天是1號(hào),q:明天是5號(hào).(1)推理的形式結(jié)構(gòu):,(pq)pq,用等值演算法(pq)pq(pq)p)qpqq1由定理1可知推理正確,13,推理實(shí)例,(2)推理的形式結(jié)構(gòu):,(pq)qp,用主析取范式法(pq)qp(pq)qp(pq)q)pqp(pq)(pq)(pq)(pq)m0m2m3結(jié)果不含m1,故01是成假賦值,所以推理不正確,14,例2構(gòu)造下面推理的證明:若明天是星期一或星期三,我明天就有課.若我明天有課,今天必備課.我今天沒(méi)備課.所以,明天不是星期一、也不是星期三.解(1)設(shè)命題并符號(hào)化設(shè)p:明天是星期一,q:明天是星期三,r:我明天有課,s:我今天備課,(2)寫出證明的形式結(jié)構(gòu)前提:(pq)r,rs,s結(jié)論:pq,15,直接證明法,(2)寫出證明的形式結(jié)構(gòu)前提:(pq)r,rs,s結(jié)論:pq(3)證明(證明過(guò)程三列式)序號(hào)當(dāng)前得到的結(jié)論當(dāng)前得到結(jié)論的理由rsP(前提引入)sPrTI(拒取式)(pq)rP(pq)TE(拒取式)pqTE德摩根率,16,附加前提證明法,附加前提證明法適用于結(jié)論為蘊(yùn)涵式(CP規(guī)則)欲證前提:A1,A2,Ak結(jié)論:CB等價(jià)地證明前提:A1,A2,Ak,C結(jié)論:B理由:(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,17,附加前提證明法實(shí)例,例3構(gòu)造下面推理的證明2是素?cái)?shù)或合數(shù).若2是素?cái)?shù),則是無(wú)理數(shù).若是無(wú)理數(shù),則4不是素?cái)?shù).所以,如果4是素?cái)?shù),則2是合數(shù).解用附加前提證明法構(gòu)造證明(1)設(shè)p:2是素?cái)?shù),q:2是合數(shù),r:是無(wú)理數(shù),s:4是素?cái)?shù)(2)推理的形式結(jié)構(gòu)前提:pq,pr,rs結(jié)論:sq,18,附加前提證明法實(shí)例,(3)證明sCP規(guī)則prPrsPpsTI(假言三段論)pTI(拒取式)pqPqTI(析取三段論),19,歸謬法(反證法),歸謬法(反證法)欲證前提:A1,A2,Ak結(jié)論:B做法在前提中加入B,推出矛盾.理由A1A2AkB(A1A2Ak)B(A1A2AkB)(A1A2AkB)0A1A2AkB0,20,歸謬法實(shí)例,例4前提:(pq)r,rs,s,p結(jié)論:q證明用歸繆法qP(附加前提)rsPsPrTI(拒取式)(pq)rP,21,(pq)TI(析取三段論)pqTE德摩根率pTI(析取三段論)pPpp(矛盾)TI(合取引入)反證法,11p,