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

1、. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰12.4 命題邏輯推理理論n2.4.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)n推理及其形式結(jié)構(gòu)推理及其形式結(jié)構(gòu)n推理定律推理定律n2.4.2 自然推理系統(tǒng)自然推理系統(tǒng)Pn自然推理系統(tǒng)的定義自然推理系統(tǒng)的定義n證明方法證明方法. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰22.4.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)一、什么是推理一、什么是推理定義定義2.19 設(shè)設(shè)A1，A2 ， ，Ak ，B都是命題公式，若對于都是命題公式，若對于每組賦值每組賦值, A1 A2 Ak為假為假, 或者當(dāng)或者當(dāng)A1 A2 Ak為真時，為真時，B也為真也為真, 則稱由前提則稱由前提A1，A2，, Ak推

2、推B的的推推理有效理有效或或推理正確推理正確, 并稱并稱B是是有效的結(jié)論。有效的結(jié)論。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰3定理定理2.8 由前提由前提A1, A2, , Ak 推出推出B 的推理正確當(dāng)且僅當(dāng)?shù)耐评碚_當(dāng)且僅當(dāng) A1 A2 Ak B為重言式為重言式.12kAAAB如果把（如果把（A1 A2 Ak ） B為永真式記為：為永真式記為：上式的含義？上式的含義？. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰4二、推理的形式結(jié)構(gòu)二、推理的形式結(jié)構(gòu)定義定義2.20 稱（稱（A1 A2 Ak ） B為由前提為由前提 A1, A2, , Ak推結(jié)論推結(jié)論 B 的推理的形式結(jié)構(gòu)。的推理的形式結(jié)構(gòu)。推理的形

3、式結(jié)構(gòu)一般有以下三種：推理的形式結(jié)構(gòu)一般有以下三種： 形式形式(1) A1 A2 Ak B 形式形式(2) 前提前提: A1, A2, , Ak 結(jié)論結(jié)論: B 形式形式(3) A1， A2 ， ， Ak B. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰5n真值表法真值表法n等值演算法等值演算法n主析取范式法主析取范式法n構(gòu)造證明法構(gòu)造證明法判斷推理是否正確的方法判斷推理是否正確的方法:真值表的方法參見真值表的方法參見P.67例例2.23。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰6例例1 判斷下面推理是否正確判斷下面推理是否正確:(1) 若今天是若今天是1號號, 則明天是則明天是5號號. 今天是今天是1號號

4、. 所以所以, 明天明天是是5號號. ()pqpq解解 設(shè)設(shè) p: 今天是今天是1號號, q: 明天是明天是5號號 推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為證明證明 用等值演算法用等值演算法 ()()()()()()pqpqpqpqpqpqpqpqppqpqqpqT 所以，原推理正確。所以，原推理正確。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰7例例1 (2) 若今天是若今天是1號號, 則明天是則明天是5號號. 明天是明天是5號號. 所以所以, 今天是今天是1號。號。()pqqp解解 設(shè)設(shè) p: 今天是今天是1號號, q: 明天是明天是5號號 推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為證明證明 用主析取范式法用主析取

5、范式法 023()()()()()()pqqppqqppqqppqpqpqpqmmm 這不是一個永真式，這不是一個永真式，01是該公式成假的賦值，是該公式成假的賦值，所以推理不正確。所以推理不正確。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰8三、推理規(guī)則三、推理規(guī)則1、推理規(guī)則的定義、推理規(guī)則的定義BAAAn,21BAAAn21 是一個是一個推理規(guī)則推理規(guī)則，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ，其中其中, A1, A2, , An 稱稱為推理規(guī)則的為推理規(guī)則的前提前提，B 稱為推理規(guī)則的稱為推理規(guī)則的結(jié)論。結(jié)論。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰91）附加規(guī)則）附加規(guī)則2）化簡規(guī)則）化簡規(guī)則3）MP規(guī)則規(guī)則（假言

6、推理）（假言推理）4）拒取式）拒取式BAAABABBAA,ABBA,2、常用的推理規(guī)則、常用的推理規(guī)則. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰105）析取三段論）析取三段論6）假言三段論）假言三段論7）合取引入）合取引入8）構(gòu)造性二難）構(gòu)造性二難DBCADCBA,BABA,CACBBA,ABBA,2、常見的推理規(guī)則（續(xù)）、常見的推理規(guī)則（續(xù)）. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰11n注意：注意：（1）推理規(guī)則中出現(xiàn)的）推理規(guī)則中出現(xiàn)的A、B、C 等是元語言符號；等是元語言符號；（2）直接引用而不需證明，只要說明所引用規(guī)則的名稱；）直接引用而不需證明，只要說明所引用規(guī)則的名稱；（3）24個永真公式每

7、個都可以等效為個永真公式每個都可以等效為2個推理規(guī)則。個推理規(guī)則。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰122.4.2 自然推理系統(tǒng)自然推理系統(tǒng)P自然推理系統(tǒng)自然推理系統(tǒng)P由下述由下述3部分組成部分組成:1. 字母表字母表 (1) 命題變項符號命題變項符號: p,q,r, pi,qi,ri, (2) 聯(lián)結(jié)詞聯(lián)結(jié)詞: , , , , (3) 括號與逗號括號與逗號: ( ), ,2. 合式公式合式公式一、自然推理系統(tǒng)一、自然推理系統(tǒng)P的定義的定義. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰133. 推理規(guī)則推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則 (2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則 (3) 置換規(guī)則置換規(guī)則

8、 (4) 假言推理規(guī)則假言推理規(guī)則 (5) 附加規(guī)則附加規(guī)則 (6) 化簡規(guī)則化簡規(guī)則一、自然推理系統(tǒng)一、自然推理系統(tǒng)P的定義（續(xù)）的定義（續(xù)）(7) 拒取式規(guī)則拒取式規(guī)則 (8) 假言三段論規(guī)則假言三段論規(guī)則(9) 析取三段論規(guī)則析取三段論規(guī)則(10)構(gòu)造性二難推理構(gòu)造性二難推理規(guī)則規(guī)則(11) 破壞性二難推理破壞性二難推理規(guī)則規(guī)則 (12) 合取引入規(guī)則合取引入規(guī)則. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰14()()pqqrrp 證證例例2 證明證明前提前提前提前提、，假言三段，假言三段前提前提、，拒取式，拒取式pqqrprrp . 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰15二、證明方法二、證明方法

9、 用推理的概念說明一些證明方法的正確性。用推理的概念說明一些證明方法的正確性。 為了證明為了證明 ，只需證明，只需證明 A 永假永假即可。即可。（2）后件真證明法）后件真證明法 為了證明為了證明 ，只需證明，只需證明 B 永真永真即可。即可。（1）前件假證明法）前件假證明法BABA. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰16（3）直接證明法）直接證明法 為了證明為了證明 ，只需證明若，只需證明若 A 為真為真，則，則 B 亦為真亦為真。 為了證明為了證明 ，只需證明若，只需證明若 B 為假為假，則，則 A 亦為假。亦為假。（4）間接證明法）間接證明法BABA. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰17

10、（5）分情況證明法）分情況證明法只需證明對任意的只需證明對任意的 ，均有，均有 。為了證明為了證明 , （6）附加前提證明法）附加前提證明法只需證明只需證明為了證明為了證明 , BAi)(nii1BAAAn21BAAAAn21BAAAAn21. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰18附加前提證明法的說明：附加前提證明法的說明：理由理由: (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B欲證明欲證明 等價地證明等價地證明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C結(jié)論結(jié)論: CB 結(jié)論

11、結(jié)論: B. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰19不相容的概念：不相容的概念： 定義定義 若若 是可滿足式，則稱公是可滿足式，則稱公式集式集 是是相容的相容的（或（或一致的一致的），否），否則，稱之為則，稱之為不相容的不相容的。nAAA21nAAA,21. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰20（7）反證法（歸謬法）反證法（歸謬法）為了證明為了證明 BAAAn21即證明即證明是永假式是永假式BAAAn21只需證明只需證明是不相容的是不相容的,BAAAn21. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰21歸謬法歸謬法(反證法反證法)的說明的說明理由理由: A1 A2 AkB (A1 A2 Ak) B (A

12、1 A2 AkB)括號內(nèi)部為矛盾式當(dāng)且僅當(dāng)括號內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1 A2 AkB)為重言式為重言式欲證明欲證明前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B將將 B加入前提加入前提, 若推出矛盾若推出矛盾, 則得證推理正確則得證推理正確. . 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰22證證SPRSPQRQP,例例3 證明證明前提前提附加前提附加前提、，假言推理、，假言推理前提前提、，拒取式、，拒取式、，析取三段論、，析取三段論前提前提、，拒取式，拒取式、，CPPQRPQRQPQRSRSPS . 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰23證證PSRRQQP)(),(),(例例4 證明證明假設(shè)前

13、提假設(shè)前提，E1前提前提、，假言推理，假言推理前提前提、，析取三段論，析取三段論前提前提，化簡，化簡、，合取引入，合取引入 是一個永假式，因此，原推理正確。是一個永假式，因此，原推理正確。()PPPQQQRRRSRRR . 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰24直接證明法舉例直接證明法舉例例例5 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明:前提前提: 結(jié)論結(jié)論:證明：證明： ,()pq qr pssrpq(1)(2)(3)(4)(5)pssppqq前提前提前提前提(1)、(2)拒取式拒取式前提前提(3)、(4)析取三段論析取三段論. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰2

14、5(6)(7)(8)()qrrrpq前提前提(5)、(6)假言推理假言推理(7)、(4)合取合取. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰26例例6 構(gòu)造推理的證明構(gòu)造推理的證明: 若明天是星期一或星期三若明天是星期一或星期三, 我就有課我就有課. 若有課若有課, 今天必需備課今天必需備課. 我今天下午我今天下午沒備課沒備課. 所以所以, 明天不是星期一和星期三明天不是星期一和星期三. 解解 設(shè)設(shè) p:明天是星期一明天是星期一, q:明天是星期三，明天是星期三， r:我有課，我有課， s:我備課我備課前提前提: (p q)r, rs, s結(jié)論結(jié)論: pq pqr. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰2

15、7前提前提: (p q)r, rs, s結(jié)論結(jié)論: pq 證明：證明： rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換 結(jié)論有效結(jié)論有效, 即明天不是星期一和星期三即明天不是星期一和星期三. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰28附加前提證明法舉例附加前提證明法舉例欲證明欲證明 等價地證明等價地證明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C結(jié)論結(jié)論: CB 結(jié)論結(jié)論: B. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰29例例7 構(gòu)造下面推理的證明構(gòu)造下面推理的證明:前提前提: p

16、 q, q r, rs結(jié)論結(jié)論: ps證明：證明： p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段論析取三段論 q r 前提引入前提引入 r 析取三段論析取三段論 rs 前提引入前提引入 s 假言推理假言推理 推理正確推理正確, , ps是有效結(jié)論是有效結(jié)論. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰30歸謬法歸謬法(反證法反證法)舉例舉例欲證明欲證明前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B將將 B加入前提加入前提, 若推出矛盾若推出矛盾, 則得證推理正確則得證推理正確. . 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰31例例8 構(gòu)造下面推理的證明構(gòu)造下面推理的證明前提前提:

17、(p q) r, rs, s, p ；結(jié)論；結(jié)論: q證明：用歸繆法證明：用歸繆法 q 結(jié)論否定引入結(jié)論否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q) r 前提引入前提引入 (p q) 析取三段論析取三段論 pq 置換置換 p 析取三段論析取三段論. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰32 p 前提引入前提引入 p p 合取合取推理正確推理正確, , q是有效結(jié)論是有效結(jié)論. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰33應(yīng)用實例應(yīng)用實例1 分析下列事實分析下列事實“如果我有很高的收如果我有很高的收入，那么我就能資助許多貧困學(xué)生；如果我能資入，那么我就能資助許多貧困學(xué)

18、生；如果我能資助許多貧困學(xué)生，那么我很高興；但我不高興，助許多貧困學(xué)生，那么我很高興；但我不高興，所以我沒有很高的收入。所以我沒有很高的收入?！痹囍该髑疤岷徒Y(jié)論，試指明前提和結(jié)論，并給予證明。并給予證明。n課堂實訓(xùn)課堂實訓(xùn). 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰34應(yīng)用實例應(yīng)用實例2 將下列條件作為前提，驗證所得結(jié)論是將下列條件作為前提，驗證所得結(jié)論是否有效：否有效：(a) 明天或是天晴，或是下雨；明天或是天晴，或是下雨；(b) 如果是天晴，我去公園；如果是天晴，我去公園；(c) 如果我去公園，我就不看書。如果我去公園，我就不看書。結(jié)論：如果我在看書，則天下雨。結(jié)論：如果我在看書，則天下雨。. 武

19、漢大學(xué)國際軟件學(xué)院唐存琛 劉峰35三、公理系統(tǒng)三、公理系統(tǒng)1、公理系統(tǒng)的組成、公理系統(tǒng)的組成（1）初始符號：）初始符號：它們是不經(jīng)定義而直接使用的符號；它們是不經(jīng)定義而直接使用的符號；（2）形成規(guī)則：）形成規(guī)則：確定定義在初始符號上的哪些符號串確定定義在初始符號上的哪些符號串是合式公式；是合式公式；（3）公理集：）公理集：它們是不經(jīng)證明而直接認(rèn)為是恒真的命它們是不經(jīng)證明而直接認(rèn)為是恒真的命題；題；（4）推理規(guī)則：）推理規(guī)則：規(guī)定如何從公理和前面已推導(dǎo)出的合規(guī)定如何從公理和前面已推導(dǎo)出的合式公式經(jīng)過符號變形而推出其它公式。式公式經(jīng)過符號變形而推出其它公式。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰36

20、2、公理系統(tǒng)、公理系統(tǒng)L12,()ippp 公理系統(tǒng)公理系統(tǒng)L的定義：的定義：1、初始符號：、初始符號：2、形成規(guī)則：、形成規(guī)則：(1)(2)(3)(4)ipAAABAB（1in)是合式公式;若 是合式公式,則()是合式公式;若 和 是合式公式,則()是合式公式;只有通過有限次使用(1) (3)得到的符號串才是合式公式。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰373、公理集：、公理集：123()()()()()()()()()()LABALABCABACLABBA 4、推理規(guī)則：假言推理規(guī)則（、推理規(guī)則：假言推理規(guī)則（MP規(guī)則）。規(guī)則）。. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰38L證證L2L1(1)、(2)，MPL1(1)、(2)，MPL1(3)、(4)，MPL2)()(1121PPPP)()()()()()()()()(11211211121121321PPPPPPPPPPPPPP例例9 證明證明L2L1MP規(guī)則規(guī)則. 武漢大學(xué)國際軟件學(xué)院唐存琛 劉峰39證證LAAAAAAAAAAAAAAAA