離散數學第三章 命題邏輯的推理理論

離散數學第三章命題邏輯的推理理論第一頁，共二十五頁，編輯于2023年，星期一13.1推理的形式結構定義3.1

設A1,A2,…,Ak,B為命題公式.若對于每組賦值，A1A2…

Ak

為假，或當A1A2…Ak為真時，B也為真，則稱由前提A1,A2,…,Ak推出結論B的推理是有效的或正確的,并稱B是有效結論.定理3.1由命題公式A1,A2,…,Ak推B的推理正確當且僅當A1A2…AkB為重言式注意:推理正確不能保證結論一定正確第二頁，共二十五頁，編輯于2023年，星期一2推理的形式結構2.A1A2…AkB

若推理正確,記為A1A2…AkB3.前提：A1,A2,…,Ak

結論：B判斷推理是否正確的方法:

真值表法等值演算法主析取范式法推理的形式結構1.{A1,A2,…,Ak}B

若推理正確,記為{A1,A2,,An}B第三頁，共二十五頁，編輯于2023年，星期一3推理實例例1

判斷下面推理是否正確(1)若今天是1號，則明天是5號.今天是1號.所以,明天是5號.(2)若今天是1號，則明天是5號.明天是5號.所以,今天是1號.解設p：今天是1號，q：明天是5號.(1)推理的形式結構:(pq)pq用等值演算法(pq)pq

((pq)p)q

pqq

1由定理3.1可知推理正確第四頁，共二十五頁，編輯于2023年，星期一4推理實例(2)推理的形式結構:(pq)qp用主析取范式法(pq)qp(pq)qp

((pq)q)p

qp(pq)(pq)(pq)(pq)

m0m2m3

結果不含m1,故01是成假賦值，所以推理不正確第五頁，共二十五頁，編輯于2023年，星期一5推理定律——重言蘊涵式1.A

(AB)附加律2.(AB)

A

化簡律3.(AB)A

B

假言推理4.(AB)B

A

拒取式5.(AB)B

A

析取三段論6.(AB)(BC)(AC)假言三段論7.(AB)(BC)(AC)等價三段論8.(AB)(CD)(AC)(BD)構造性二難

(AB)(AB)

B

構造性二難(特殊形式)9.(AB)(CD)(BD)(AC)破壞性二難每個等值式可產生兩個推理定律如,由AA可產生AA

和AA第六頁，共二十五頁，編輯于2023年，星期一63.2自然推理系統(tǒng)P定義3.2

一個形式系統(tǒng)I由下面四個部分組成：

(1)非空的字母表，記作A(I).(2)A(I)中符號構造的合式公式集，記作E(I).(3)E(I)中一些特殊的公式組成的公理集，記作AX(I).(4)推理規(guī)則集，記作R(I).

記I=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I)>是I的形式語言系統(tǒng),<AX(I),R(I)>是I的形式演算系統(tǒng).形式系統(tǒng)一般分為兩類：自然推理系統(tǒng):無公理,即AX(I)=公理推理系統(tǒng)推出的結論是系統(tǒng)中的重言式,稱作定理第七頁，共二十五頁，編輯于2023年，星期一7自然推理系統(tǒng)P定義3.3自然推理系統(tǒng)P定義如下:1.

字母表

(1)命題變項符號：p,q,r,…,pi,qi,ri,…(2)聯(lián)結詞符號：,,,,(3)括號與逗號：(,),，2.合式公式（同定義1.6）3.

推理規(guī)則:(1)—(12)

(1)前提引入規(guī)則:在證明的任何步驟都可以引入前提.(2)結論引入規(guī)則:在證明的任何步驟所得的結論都有可以作為后繼證明的前提.(3)置換規(guī)則:在證明的任何步驟,命題公式中的子公式都可以用等值的公式置換,得到公式序列中又一個公式.第八頁，共二十五頁，編輯于2023年，星期一8推理規(guī)則(4)假言推理規(guī)則

(6)化簡規(guī)則

(8)假言三段論規(guī)則

ABA∴BA∴ABAB∴A(5)附加規(guī)則

(7)拒取式規(guī)則

(9)析取三段論規(guī)則

AB

B∴AABBC∴ACAB

B∴A第九頁，共二十五頁，編輯于2023年，星期一9推理規(guī)則(10)構造性二難推理規(guī)則(11)破壞性二難推理規(guī)則

(12)合取引入規(guī)則

ABCDAC∴BDABCDBD∴ACAB∴AC第十頁，共二十五頁，編輯于2023年，星期一10在自然推理系統(tǒng)P中構造證明設前提A1,A2,,Ak,結論B及公式序列C1,C2,,Cl.如果每一個Ci(1il)是某個Aj,或者可由序列中前面的公式應用推理規(guī)則得到,并且Cl=B,則稱這個公式序列是由A1,A2,,Ak推出B的證明例2

構造下面推理的證明：若明天是星期一或星期四，我明天就有課.若我明天有課，今天必備課.我今天沒備課.所以，明天不是星期一、也不是星期四.解(1)設命題并符號化設p：明天是星期一，q：明天是星期四，

r：我明天有課，s：我今天備課第十一頁，共二十五頁，編輯于2023年，星期一11直接證明法(2)寫出證明的形式結構前提：(pq)r,rs,s

結論：pq(3)證明

①rs

前提引入②s

前提引入③r①②拒取式④(pq)r

前提引入⑤(pq)③④拒取式⑥pq⑤置換第十二頁，共二十五頁，編輯于2023年，星期一12附加前提證明法附加前提證明法適用于結論為蘊涵式欲證前提：A1,A2,…,Ak

結論：CB等價地證明前提：A1,A2,…,Ak,C

結論：B理由：

(A1A2…Ak)(CB)

(A1A2…Ak)(CB)

(A1A2…AkC)B(A1A2…AkC)B第十三頁，共二十五頁，編輯于2023年，星期一13附加前提證明法實例例3

構造下面推理的證明

2是素數或合數.若2是素數，則是無理數.若是無理數，則4不是素數.所以，如果4是素數，則2是合數.解用附加前提證明法構造證明

(1)設p：2是素數，q：2是合數，

r：是無理數，s：4是素數

(2)推理的形式結構前提：pq,pr,rs

結論：sq

第十四頁，共二十五頁，編輯于2023年，星期一14附加前提證明法實例

(3)證明①s

附加前提引入②pr

前提引入③rs

前提引入④ps②③假言三段論⑤p①④拒取式⑥pq

前提引入⑦q⑤⑥析取三段論第十五頁，共二十五頁，編輯于2023年，星期一15歸謬法（反證法）歸謬法(反證法)欲證前提：A1,A2,…,Ak

結論：B做法在前提中加入B，推出矛盾.理由

A1A2…AkB

(A1A2…Ak)B

(A1A2…AkB)

(A1A2…AkB)0

A1A2…AkB0第十六頁，共二十五頁，編輯于2023年，星期一16歸謬法實例例4

前提：(pq)r,rs,s,p

結論：q證明用歸繆法①q

結論否定引入②rs

前提引入③s

前提引入④r②③拒取式⑤(pq)r

前提引入⑥(pq)④⑤析取三段論⑦pq⑥置換⑧p①⑦析取三段論⑨p

前提引入

pp⑧⑨合取第十七頁，共二十五頁，編輯于2023年，星期一17第三章小結主要內容推理的形式結構判斷推理是否正確的方法真值表法等值演算法主析取范式法推理定律自然推理系統(tǒng)P構造推理證明的方法直接證明法附加前提證明法歸謬法(反證法)第十八頁，共二十五頁，編輯于2023年，星期一18基本要求理解并記住推理形式結構的兩種形式：

1.(A1A2…Ak)B2.前提：A1,A2,…,Ak

結論：B熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）牢記P系統(tǒng)中各條推理規(guī)則熟練掌握構造證明的直接證明法、附加前提證明法和歸謬法會解決實際中的簡單推理問題第十九頁，共二十五頁，編輯于2023年，星期一19練習1：判斷推理是否正確1.判斷下面推理是否正確:

(1)前提：pq,q

結論：p解推理的形式結構:(pq)qp方法一：等值演算法(pq)qp

((pq)q)p(pq)qp((pq)(qq))p

pq易知10是成假賦值，不是重言式，所以推理不正確.第二十頁，共二十五頁，編輯于2023年，星期一20練習1解答方法二：主析取范式法，(pq)qp((pq)q)ppqM2m0m1m3未含m2,不是重言式,推理不正確.第二十一頁，共二十五頁，編輯于2023年，星期一21練習1解答方法三真值表法

不是重言式,推理不正確111001110100(pq)qpqppq0111(pq)q0010方法四直接觀察出10是成假賦值第二十二頁，共二十五頁，編輯于2023年，星期一22練習1解答用等值演算法(qr)(pr)(qp)(qr)(pr)(qp)

((qr)(pr))(qp)

((qp)(qr)(rp))(qp)((qp)(qr)(rp))(qp)1推理正確(2)前提：qr,pr結論：q