離散數(shù)理邏輯全部課件我的

1第三章命題邏輯的推理理論北京理工大學(xué)計算機學(xué)院劉瓊昕2主要內(nèi)容推理的形式結(jié)構(gòu)推理的正確與錯誤推理的形式結(jié)構(gòu)判斷推理正確的方法推理定律自然推理系統(tǒng)P形式系統(tǒng)的定義與分類自然推理系統(tǒng)P在P中構(gòu)造證明:直接證明法、附加前提證明法、歸謬法33.1推理的形式結(jié)構(gòu)定義3.1

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

Ak

為假，或當(dāng)A1A2…Ak為真時，B也為真，則稱由前提A1,A2,…,Ak推出結(jié)論B的推理是有效的或正確的,并稱B是有效結(jié)論.推理的形式結(jié)構(gòu)1：{A1,A2,…,Ak}B若推理正確,記為{A1,A2,,An}B否則記為{A1,A2,,An}B4實例判斷下列推理是否正確：{q,

p→q}

p{q,

p→q}

p方法1：假定q

(p

→

q)為1,則q

為1,且(p

→

q)為1。由于q

為0,(p

→

q)為1，則必須p

為0,故p為1。方法2：假定p

為0,則p

為1.若q

為0,則p→q

為0,q

(p→q)為0.若q

為1,則q

為0,q(p→q)為0.5實例判斷下列推理是否正確：{p→q,

q}

ppqp→qqp00111011011001011100{q,

p→q}

ppq(p→q)qp0011010110001100pq(p→q)qp0010111011116推理的形式結(jié)構(gòu)定理3.1

由命題公式A1,A2,…,Ak

推B的推理正確當(dāng)且僅當(dāng)A1A2…AkB為重言式。推理的形式結(jié)構(gòu)2：A1A2…AkB若推理正確,記為A1A2…AkB也可以采用下述形式前提：A1,A2,…,Ak結(jié)論：B注意：推理正確不能保證結(jié)論一定正確。7判斷推理是否正確的方法真值表法等值演算法主析取范式法8真值表法從真值表上找出A1,A2,…,Ak真值均為1的行，對每一個這樣的行，若B

的真值也為

1,則

A1A2…AkB成立。或者看B為0的行,在每個這樣的行中，A1,A2,…,Ak真值中至少有一個為0，

則A1A2…AkB成立。9推理實例考察B

是否是下列前提A1,A2

的有效結(jié)論？A1:p→q

A2:pB:qA1:p→q

A2:pB:qA1:p→q

A2:qB:p是否否10推理實例例1

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

(pq)pq

((pq)p)q((pq)p)q

pqq

1

由定理3.1可知推理正確12推理實例(2)若今天是1號，則明天是5號.明天是5號.所以,今天是1號.推理的形式結(jié)構(gòu):(pq)qp用主析取范式法

(pq)qp(pq)qp

((pq)q)p

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

m0m2m3

結(jié)果不含m1,故01是成假賦值，所以推理不正確13推理定律——重言蘊涵式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)等價三段論14推理定律——重言蘊涵式8.(AB)(CD)(AC)(BD)構(gòu)造性二難

(AB)(AB)

B

構(gòu)造性二難(特殊形式)(AB)(CD)(BD)(AC)

破壞性二難10.每個等值式可產(chǎn)生兩個推理定律.15實例判斷下面推理是否正確現(xiàn)在氣溫在零度以下。所以現(xiàn)在氣溫在零度以下或者正在下雨?，F(xiàn)在氣溫在零度以下并且正在下雨。以現(xiàn)在氣溫在零度以下。現(xiàn)在氣溫在零度以下或者正在下雨?，F(xiàn)在氣溫不在零度以下。所以現(xiàn)在正在下雨。A

(AB)附加律(AB)

A

化簡律(AB)B

A

析取三段論16實例現(xiàn)在氣溫在零度以下或者正在下雨。所以現(xiàn)在正在下雨。若今天下雨，則我們今天將不野餐。若我們今天不野餐，則我們明天將野餐。因此，若今天下雨，則我們明天將野餐。(AB)(BC)(AC)假言三段論推理錯誤173.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=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I),AX(I),R(I)>是I的形式語言系統(tǒng).18自然推理系統(tǒng)P自然推理系統(tǒng):無公理,即AX(I)=.公理推理系統(tǒng):推出的結(jié)論是系統(tǒng)中的重言式,稱作定理.19自然推理系統(tǒng)P定義3.3自然推理系統(tǒng)P定義如下:1.

字母表

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

推理規(guī)則

(1)前提引入規(guī)則

(2)結(jié)論引入規(guī)則

(3)置換規(guī)則20推理規(guī)則(4)假言推理規(guī)則

(6)化簡規(guī)則

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

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

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

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

AB

B∴AABBC∴ACAB

B∴A21推理規(guī)則(10)構(gòu)造性二難規(guī)則(11)破壞性二難規(guī)則

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

ABCDAC∴BDABCDBD∴ACAB∴AC22在自然推理系統(tǒng)P中構(gòu)造證明設(shè)前提A1,A2,,Ak,結(jié)論B及公式序列C1,C2,,Cl.如果每一個Ci(1il)是某個Aj,或者可由序列中前面的公式應(yīng)用推理規(guī)則得到,并且Cl=B,則稱這個公式序列是由A1,A2,,Ak推出B的證明.可以證明，存在由A1,A2,,Ak推出B的證明的充要條件是B是A1,A2,,Ak的有效結(jié)論，即A1

A2

Ak

B.23說明證明的合理性引理1:設(shè)A,C1,C2是公式.如果A

C1,A

C2,則A

C1C2.引理2：如果A

B，B

C，則A

C.定理:設(shè)A是公式集合，B是一個公式。于是，從A證明出B的充要條件是B是A的有效結(jié)論。24說明證明的合理性證明：必要性，設(shè)存在從A推出B的證明，令C1，…，Ck=B是這個證明序列。對任意Ci

(i=1，…，k)，往證Ci是A的有效結(jié)論。對i用歸納法:(1)當(dāng)i=1時，因C1A，顯然,C1

…

C1

是恒真公式，故AC1，即C1是A的有效結(jié)論。(2)設(shè)i<n時，命題成立。(3)當(dāng)i=n時，若CnA，則ACn，歸納法完成25說明證明的合理性若Cn是某些Cj(j<n)的有效結(jié)論，不妨設(shè)(Cj1

…Cjh)Cn(1)其中j1，…，jh都小于n。由歸納假設(shè)知，A

Cjm

，m=1，…，h。由引理1知：A

(Cji

…Cjh)(2)根據(jù)(1)，(2)式及引理2，得A

Cn

即Cn是A的有效結(jié)論，歸納完成。26說明證明的合理性充分性，若B是A的有效結(jié)論，則存在如下的序列：

C1，…，Ck，B

其中

C1，…，Ck

是A中所有公式，且

C1…

CkB，

這個序列就是由A到B的證明。證畢。27實例例2

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

r：我明天有課，s：我今天備課28直接證明法(2)寫出證明的形式結(jié)構(gòu)前提：(pq)r,rs,s

結(jié)論：pq(3)證明

①rs

前提引入②s

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

前提引入⑤(pq) ③④拒取式⑥pq ⑤置換29附加前提證明法附加前提證明法適用于結(jié)論為蘊涵式欲證前提：A1,A2,…,Ak

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

結(jié)論：B理由：(A1A2…Ak)(CB)

(A1A2…Ak)(CB)

(A1A2…AkC)B(A1A2…AkC)B30附加前提證明法實例例3

構(gòu)造下面推理的證明

2是素數(shù)或合數(shù).若2是素數(shù)，則π是無理數(shù).若π是無理數(shù)，則4不是素數(shù).所以，如果4是素數(shù)，則2是合數(shù).解用附加前提證明法構(gòu)造證明

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

r：π是無理數(shù)，s：4是素數(shù)

(2)推理的形式結(jié)構(gòu)前提：pq,pr,rs

結(jié)論：sq

31附加前提證明法實例(3)證明①s

附加前提引入②pr

前提引入③rs

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

前提引入⑦q ⑤⑥析取三段論32歸謬法（反證法）歸謬法(反證法)欲證前提：A1,A2,…,Ak

結(jié)論：B做法在前提中加入B，推出矛盾.理由:A1A2…AkB

(A1A2…Ak)B

(A1A2…AkB)

(A1A2…AkB)0

A1A2…AkB033歸謬法實例例4

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

結(jié)論：q證明用歸繆法①q

結(jié)論否定引入②rs

前提引入③s

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

前提引入⑥(pq) ④⑤析取三段論34歸謬法實例⑦pq⑥置換⑧p①⑦析取三段論⑨p

前提引入pp⑧⑨合取35第三章習(xí)題課主要內(nèi)容推理的形式結(jié)構(gòu)判斷推理是否正確的方法真值表法等值演算法主析取范式法推理定律自然推理系統(tǒng)P構(gòu)造推理證明的方法直接證明法附加前提證明法歸謬法(反證法)36基本要求理解并記住推理形式結(jié)構(gòu)的兩種形式：

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

結(jié)論：B熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）牢記P系統(tǒng)中各條推理規(guī)則熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬法會解決實際中的簡單推理問題37練習(xí)1：判斷推理是否正確1.判斷下面推理是否正確：(1)前提：pq,q

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

(pq)qp

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

pq

易知10是成假賦值，不是重言式，所以推理不正確.38練習(xí)1解答方法二：主析取范式法，

(pq)qp((pq)q)ppqM2m0m1m3未含m2,不是重言式,推理不正確.39練習(xí)1解答方法三真值表法

111001110100(pq)qpqppq0111(pq)q0010方法四直接觀察出10是成假賦值不是重言式,推理不正確40練習(xí)1(2)前提：qr,pr

結(jié)論：qp

解推理的形式結(jié)構(gòu)：(qr)(pr)(qp)用等值演算法

(qr)(pr)(qp)(qr)(pr)(qp)

((qr)(pr))(qp)

((qp)(qr)(rp))(qp)((qp)(qr)(rp))(qp)1推理正確41練習(xí)2：構(gòu)造證明2.在系統(tǒng)P中構(gòu)造下面推理的證明：如果今天是周六，我們就到頤和園或圓明園玩.如果頤和園游人太多，就不去頤和園.今天是周六，并且頤和園游太多.所以,我們?nèi)A明園或動物園玩.證明：