命題邏輯的推理理論,證明方法

.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,1,2.4命題邏輯推理理論,2.4.1推理的形式結(jié)構(gòu)推理及其形式結(jié)構(gòu)推理定律2.4.2自然推理系統(tǒng)P自然推理系統(tǒng)的定義證明方法,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,2,2.4.1推理的形式結(jié)構(gòu),一、什么是推理,定義2.19設(shè)A1，A2，Ak，B都是命題公式，若對(duì)于每組賦值,A1A2Ak為假,或者當(dāng)A1A2Ak為真時(shí)，B也為真,則稱由前提A1，A2，,Ak推B的推理有效或推理正確,并稱B是有效的結(jié)論。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,3,定理2.8由前提A1,A2,Ak推出B的推理正確當(dāng)且僅當(dāng)A1A2AkB為重言式.,如果把（A1A2Ak）B為永真式記為：,上式的含義？,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,4,二、推理的形式結(jié)構(gòu),定義2.20稱（A1A2Ak）B為由前提A1,A2,Ak推結(jié)論B的推理的形式結(jié)構(gòu)。,推理的形式結(jié)構(gòu)一般有以下三種：形式(1)A1A2AkB形式(2)前提:A1,A2,Ak結(jié)論:B形式(3)A1，A2，AkB,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,5,真值表法等值演算法主析取范式法構(gòu)造證明法,判斷推理是否正確的方法:,真值表的方法參見P.67例2.23。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,6,例1判斷下面推理是否正確:(1)若今天是1號(hào),則明天是5號(hào).今天是1號(hào).所以,明天是5號(hào).,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,7,例1(2)若今天是1號(hào),則明天是5號(hào).明天是5號(hào).所以,今天是1號(hào)。,解設(shè)p:今天是1號(hào),q:明天是5號(hào)推理的形式結(jié)構(gòu)為證明用主析取范式法,這不是一個(gè)永真式，01是該公式成假的賦值，所以推理不正確。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,8,三、推理規(guī)則1、推理規(guī)則的定義,是一個(gè)推理規(guī)則，當(dāng)且僅當(dāng)，其中,A1,A2,An稱為推理規(guī)則的前提，B稱為推理規(guī)則的結(jié)論。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,9,1）附加規(guī)則,2）化簡規(guī)則,3）MP規(guī)則（假言推理）,4）拒取式,2、常用的推理規(guī)則,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,10,5）析取三段論,6）假言三段論,7）合取引入,8）構(gòu)造性二難,2、常見的推理規(guī)則（續(xù)）,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,11,注意：,（1）推理規(guī)則中出現(xiàn)的A、B、C等是元語言符號(hào)；（2）直接引用而不需證明，只要說明所引用規(guī)則的名稱；（3）24個(gè)永真公式每個(gè)都可以等效為2個(gè)推理規(guī)則。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,12,2.4.2自然推理系統(tǒng)P,自然推理系統(tǒng)P由下述3部分組成:1.字母表(1)命題變項(xiàng)符號(hào):p,q,r,pi,qi,ri,(2)聯(lián)結(jié)詞:,(3)括號(hào)與逗號(hào):(),2.合式公式,一、自然推理系統(tǒng)P的定義,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,13,3.推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則(6)化簡規(guī)則,一、自然推理系統(tǒng)P的定義（續(xù)）,(7)拒取式規(guī)則(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)破壞性二難推理規(guī)則(12)合取引入規(guī)則,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,14,證,例2證明,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,15,二、證明方法,用推理的概念說明一些證明方法的正確性。,為了證明，只需證明A永假即可。,（2）后件真證明法,為了證明，只需證明B永真即可。,（1）前件假證明法,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,16,（3）直接證明法,為了證明，只需證明若A為真，則B亦為真。,為了證明，只需證明若B為假，則A亦為假。,（4）間接證明法,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,17,（5）分情況證明法,只需證明對(duì)任意的，均有。,為了證明,（6）附加前提證明法,只需證明,為了證明,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,18,附加前提證明法的說明：,理由:(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,欲證明等價(jià)地證明前提:A1,A2,Ak前提:A1,A2,Ak,C結(jié)論:CB結(jié)論:B,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,19,不相容的概念：,定義若是可滿足式，則稱公式集是相容的（或一致的），否則，稱之為不相容的。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,20,（7）反證法（歸謬法）,為了證明,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,21,歸謬法(反證法)的說明,理由:A1A2AkB(A1A2Ak)B(A1A2AkB)括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng)(A1A2AkB)為重言式,欲證明前提：A1,A2,Ak結(jié)論：B將B加入前提,若推出矛盾,則得證推理正確.,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,22,證,例3證明,前提附加前提、，假言推理前提、，拒取式、，析取三段論前提、，拒取式、，CP,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,23,證,例4證明,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,24,直接證明法舉例,例5在自然推理系統(tǒng)P中構(gòu)造下面推理的證明:前提:結(jié)論:證明：,前提前提(1)、(2)拒取式前提(3)、(4)析取三段論,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,25,前提(5)、(6)假言推理(7)、(4)合取,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,26,例6構(gòu)造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必需備課.我今天下午沒備課.所以,明天不是星期一和星期三.,解設(shè)p:明天是星期一,q:明天是星期三，r:我有課，s:我備課前提:(pq)r,rs,s結(jié)論:pq,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,27,前提:(pq)r,rs,s結(jié)論:pq證明：rs前提引入s前提引入r拒取式(pq)r前提引入(pq)拒取式pq置換結(jié)論有效,即明天不是星期一和星期三.,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,28,附加前提證明法舉例,欲證明等價(jià)地證明前提:A1,A2,Ak前提:A1,A2,Ak,C結(jié)論:CB結(jié)論:B,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,29,例7構(gòu)造下面推理的證明:前提:pq,qr,rs結(jié)論:ps,證明：p附加前提引入pq前提引入q析取三段論qr前提引入r析取三段論rs前提引入s假言推理推理正確,ps是有效結(jié)論,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,30,歸謬法(反證法)舉例,欲證明前提：A1,A2,Ak結(jié)論：B將B加入前提,若推出矛盾,則得證推理正確.,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,31,例8構(gòu)造下面推理的證明前提:(pq)r,rs,s,p；結(jié)論:q,證明：用歸繆法q結(jié)論否定引入rs前提引入s前提引入r拒取式(pq)r前提引入(pq)析取三段論pq置換p析取三段論,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,32,p前提引入pp合取推理正確,q是有效結(jié)論,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,33,應(yīng)用實(shí)例1分析下列事實(shí)“如果我有很高的收入，那么我就能資助許多貧困學(xué)生；如果我能資助許多貧困學(xué)生，那么我很高興；但我不高興，所以我沒有很高的收入?！痹囍该髑疤岷徒Y(jié)論，并給予證明。,課堂實(shí)訓(xùn),.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,34,應(yīng)用實(shí)例2將下列條件作為前提，驗(yàn)證所得結(jié)論是否有效：明天或是天晴，或是下雨；如果是天晴，我去公園；如果我去公園，我就不看書。結(jié)論：如果我在看書，則天下雨。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,35,三、公理系統(tǒng)1、公理系統(tǒng)的組成,（1）初始符號(hào)：它們是不經(jīng)定義而直接使用的符號(hào)；（2）形成規(guī)則：確定定義在初始符號(hào)上的哪些符號(hào)串是合式公式；（3）公理集：它們是不經(jīng)證明而直接認(rèn)為是恒真的命題；（4）推理規(guī)則：規(guī)定如何從公理和前面已推導(dǎo)出的合式公式經(jīng)過符號(hào)變形而推出其它公式。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,36,2、公理系統(tǒng)L,公理系統(tǒng)L的定義：1、初始符號(hào)：,2、形成規(guī)則：,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,37,3、公理集：,4、推理規(guī)則：假言推理規(guī)則（MP規(guī)則）。,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,38,L,證,L2L1(1)、(2)，MP,L1(1)、(2)，MPL1(3)、(4)，MP,L2,例9證明,L2L1MP規(guī)則,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,39,證,L,例10證明,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,40,3、演繹定理,例11證明,證,假設(shè)L2(1)、(2)，MPL1假設(shè)(4)、(5)，MP(3)、(6)，MP,L,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,41,L的演繹定理：若,L,，則,L,。,推論：設(shè)A，B和C是L的任意合式公式，則,L,。,例12證明L,證,L1L3(1)、(2)，HS,.武漢大學(xué)國際軟件學(xué)院唐存琛劉峰,42,