第三章命題邏輯的推理理論課件

2023/6/613.1推理的形式結(jié)構(gòu)

所謂推理是指從前提出發(fā)推出結(jié)論的思維過程.

本節(jié)所要研究的內(nèi)容是以什么樣的形式來進(jìn)行推理,什么樣的推理過程才是正確的推理過程,也就是說什么樣的推理才是有效的推理.2023/6/623.1推理的形式結(jié)構(gòu)

定義3.1設(shè)A1,A2,…,Ak,B都是命題公式，若對于A1,A2,…,Ak,B中出現(xiàn)的命題變項的任意一組賦值，或者A1∧A2∧…∧Ak為假，或者當(dāng)A1∧A2∧…∧Ak為真時，B也為真，則稱由前提A1,A2,…,Ak推出B的推理是有效的或正確的，并稱B是有效的結(jié)論。2023/6/633.1推理的形式結(jié)構(gòu)關(guān)于定義3.1的說明：（1）由前提A1，A2，…Ak推B的推理記作{A1，A2，…Ak}├B,稱為推理的形式結(jié)構(gòu)。若推理正確，記作{A1，A2，…Ak}|=B，否則：記作{A1，A2，…Ak}|≠B。2023/6/643.1推理的形式結(jié)構(gòu)(2)對于任一組賦值，前提和結(jié)論的取值有以下四種情況：①{A1，A2，…Ak}為0，B為0。②{A1，A2，…Ak}為0，B為1。③{A1，A2，…Ak}為1，B為0。④{A1，A2，…Ak}為1，B為1。結(jié)論: ①②④情況下的推理是正確的. ③情況下的推理是錯誤的.2023/6/653.1推理的形式結(jié)構(gòu)（3）推理正確,并不能保證結(jié)論B一定為真,這與數(shù)學(xué)上的推理是不同的.判斷下列推理是否正確(1){p,pq}├q(2){p,qp}├q2023/6/663.1推理的形式結(jié)構(gòu)pq00011011p∧(pq)qp∧(qp)q0001001100011011結(jié)論:(1)式正確.(2)式推理不正確.2023/6/67

定理3.1命題公式A1，A2，…Ak推B的推理正確當(dāng)且僅當(dāng)(A1∧

A2∧

…∧Ak)B為重言式。（證明參見課本） 本書中,一般采用(A1

∧A2

∧…∧Ak)B作為推理的形式結(jié)構(gòu),并且把它寫成下面的形式.

前提：p,pq

結(jié)論：q

推理的形式結(jié)構(gòu)：

(p

∧(pq))q2023/6/68

只要證明蘊(yùn)涵式(p∧(pq))q為重言式即可。三種方式證明：真值表、等值演算、主析取范式。例：判斷下列推理是否正確。1、今天小李或去網(wǎng)吧或去教室。他沒去教室，所以他去網(wǎng)吧了。 設(shè)p：小李去網(wǎng)吧。q：小李去教室。則前提：p∨q,

q結(jié)論：p推理的形式結(jié)構(gòu)：

((p∨q)

∧

q)p2023/6/69pqp∨qq(p∨q)∧q((p∨q)∧q)p000101011001101111111001（1）真值表2023/6/610（2）等值演算法：((p∨q)

∧q)p((p∧q)∨(q∧q))p

(p∧q)p

(p∧q)∨p

p∨q∨

p

1所以，推理正確，即((p∨q)∧q)

p2023/6/611（3）主析取范式法：((p∨q)

∧q)p

((p∨q)∧q)∨

p

(p∨q)∨

q

∨

p

(p∧

q)∨

q

∨

p

(p∧

q)∨q∧(p∨p)∨p∧(q∨q

)

(p∧q)∨(q∧p)∨(q∧p)∨(p∧q)∨(

p∧q

)

m0∨

m1∨

m2∨

m3所以，推理正確，即((p∨q)∧q)

p2023/6/612例：判斷下列推理是否正確。2、若a能被4整除，則天下雨?，F(xiàn)在天下雨，所以a能被4整除。 設(shè)p：a能被4整除。q：天下雨。則，前提：pq,q

結(jié)論：p

推理的形式結(jié)構(gòu)：

((pq)

∧q)p答案：此推理不正確2023/6/6133、若下午氣溫超過30?C，則王小燕必去游泳。若她去游泳，她就不去看電影了。所以，若王小燕沒去看電影，下午氣溫必超過了30?C。p：下午氣溫超過30?Cq：王小燕去游泳r：王小燕去看電影前提：pq，qr結(jié)論：

rp形式結(jié)構(gòu)：((pq)(qr))(rp)2023/6/614推理定律1.附加律A(A∨B)2.化簡律(A∧B)A3.假言推理(A→B)∧AB4.拒取式(A→B)∧

B

A5.析取三段論(A∨B)∧

BA6.假言三段論(A→B)∧(B→C)(A→C)7.等價三段論(AB)

∧(B

C)((AC)

2023/6/6158.構(gòu)造性二難(A→B)∧(C→D)∧(A∨C)(B∨D)(特殊形式)(A→B)∧(

A→B)∧(A∨

A)B9.破壞性二難(A→B)∧(C→D)∧(B∨D) (

A∨

C)

判斷推理是否正確，上述三種方法演算量太大，故而應(yīng)給出嚴(yán)謹(jǐn)?shù)淖C明。證明是一個描述推理過程的命題公式的序列，其中的每個公式或者是已知前提，或者由某些前提應(yīng)用推理規(guī)則得到的結(jié)論.要構(gòu)造出嚴(yán)謹(jǐn)?shù)淖C明必須在形式系統(tǒng)中證明。2023/6/6163.2自然推理系統(tǒng)P定義3.2一個形式系統(tǒng)I

由下列四個部分組成：（1）非空的字母表集，記作A（I）。（2）A(I)符號構(gòu)造的合式公式集，記作E(I)。（3）E(I)中一些特殊的公式組成的公理集,記作AX(I)。（4）推理規(guī)則集，記作R(I)。可以將I

記作為4元組<A(I),E(I),AX(I),R(I)>其中<A(I)，E(I)>是I

的形式語言系統(tǒng)

<AX(I)，R(I)>為I

的形式演算系統(tǒng)2023/6/617自然推理系統(tǒng)P定義如下：1、字母表（1）命題變項符號：p,q,r,…

（2）聯(lián)結(jié)詞符號：，∧，∨，，

（3）括號與逗號：(),2、合式公式定義同1.63、推理規(guī)則2023/6/618推理規(guī)則

(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則

A?BA

\B(5)附加規(guī)則

A

\AúB

(6)化簡規(guī)則

AùB

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

A?B

?B

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

A?B

B?C

\A?C

2023/6/619推理規(guī)則(續(xù))(11)破壞性二難推理規(guī)則

A?B

C?D

?Bú?D

\?Aú?C(12)合取引入規(guī)則

A

B

\AùB

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

AúB

?B

\A(10)構(gòu)造性二難推理規(guī)則

A?B

C?D

AúC

\BúD2023/6/620推理的形式結(jié)構(gòu)為：A1∧A2∧…∧AkB證明時，要求首先寫出： 前提：A1

∧A2

∧…∧Ak

結(jié)論：Ｂ例1：在自然推理系統(tǒng)中構(gòu)造下列推理的證明。前提：p∨q,q

r,ps,s結(jié)論：r∧(p∨q)2023/6/621證明：①ps前提引入②s前提引入③

p①②拒取式④p∨q前提引入⑤q③④析取三段論⑥q

r前提引入⑦r⑤⑥假言推理⑧r∧(p∨q)④⑦合取2023/6/622例2：在自然推理系統(tǒng)中構(gòu)造下列推理的證明。若a是實數(shù)，則它不是有理數(shù)就是無理數(shù)。若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)。A是實數(shù)且它不能表示成分?jǐn)?shù)，所以a是無理數(shù)。

p：a是實數(shù)。q：a是有理數(shù)。

r：a是無理數(shù)。s：a能表示成分?jǐn)?shù)。

前提：p(qr),s

q,ps結(jié)論：r2023/6/623兩種特殊的證明方法——附加前提證明法適用于此類蘊(yùn)涵式的證明

(A1

∧A2

∧…∧Ak

)

(AB)(*)

欲證明(*)式，只需證明

(A1

∧A2

∧…∧Ak

∧

A)B

即可，因為2023/6/624(*)式(A1

∧A2

∧…∧Ak

)∨

(AB)(A1

∧A2

∧…∧Ak

)∨

(A∨B)(A1

∨

A2

∨…∨

Ak

)∨

(A∨B)A1

∨

A2

∨…∨

Ak

∨

A∨B(A1

∨

A2

∨…∨

Ak

∨

A)∨B(A1

∧A2

∧…∧Ak

∧A)∨

B(A1

∧A2

∧…∧Ak

∧A)

B2023/6/625前提：p(qr),s

p,q結(jié)論：s

r證明：①s

p前提引入②s附加前提引入③p①②假言推理④p(qr)前提引入⑤qr③④假言推理⑥q前提引入⑦r⑤⑥假言推理2023/6/626兩種特殊的證明方法——?dú)w謬法適用于此類蘊(yùn)涵式的證明

(A1

∧A2

∧…∧Ak

)

B將

B加入前提，若推出矛盾，則得證推理正確.理由:

(A1

∧A2

∧…∧Ak

)

∨B(A1∧A2

∧…∧Ak