命題邏輯的推理理論目錄

第一節(jié)：推理的形式結(jié)構(gòu)第二節(jié)：自然推理系統(tǒng)P第三章:命題邏輯的推理理論主要內(nèi)容推理的形式結(jié)構(gòu)推理的正確與錯(cuò)誤推理的形式結(jié)構(gòu)判斷推理正確的方法推理定律自然推理系統(tǒng)P形式系統(tǒng)的定義與分類自然推理系統(tǒng)P在P中構(gòu)造證明:直接證明法、附加前提證明法、歸謬法3.1推理形式結(jié)構(gòu)邏輯(語義)蘊(yùn)涵：給定A1,…,Ak和B符號(hào)：{A1,…,Ak}?B對(duì)任意賦值v:如果v(Ai)=T,則v(B)=T或者存在Ai使得v(Ai)=F稱由前提A1,…,Ak推出結(jié)論B的推理是有效的B為有效結(jié)論討論蘊(yùn)涵跟蘊(yùn)涵式的關(guān)系？注意:推理正確不能保證結(jié)論一定正確例子{p,p

q}?q{p,q

p}?qpqp(p

q)qp(q

p)qFFFFFFFTFTFTTFFFTFTTTTTT3.1推理形式結(jié)構(gòu)定理：{A1,…,Ak}?B當(dāng)且僅當(dāng)

A1

…

Ak

B

為重言式證明必要性：任意v,v(Ai)=T則v(B)=T

所以v(A1

…

Ak

B)=T

充分性：任意v,v(A1

…

Ak

B)=T如果v(Ai)=T則v(B)=T3.1推理形式結(jié)構(gòu)蘊(yùn)涵元符號(hào)：

A1

…

Ak

B代表{A1,…,Ak}?B推理形式結(jié)構(gòu)前提A1,…,Ak結(jié)論：B3.1推理形式結(jié)構(gòu)判斷推理是否正確方法真值表法等值演算法主析取范式法3.1推理形式結(jié)構(gòu)9推理實(shí)例例1

判斷下面推理是否正確(1)若今天是1號(hào)，則明天是5號(hào).今天是1號(hào).所以,明天是5號(hào).(2)若今天是1號(hào)，則明天是5號(hào).明天是5號(hào).所以,今天是1號(hào).解設(shè)p：今天是1號(hào)，q：明天是5號(hào).(1)推理的形式結(jié)構(gòu):(p

q)

p

q用等值演算法

(p

q)

p

q

((

p

q)

p)

q

p

q

q

1

由定理3.1可知推理正確10推理實(shí)例(2)推理的形式結(jié)構(gòu):(p

q)

q

p

用主析取范式法

(p

q)

q

p

(

p

q)

q

p

((

p

q)

q)

p

q

p

(

p

q)

(p

q)

(p

q)

(p

q)

m0

m2

m3

結(jié)果不含m1,故01是成假賦值，所以推理不正確推理定律A

(A

B)(A

B)

A(A

B)

A

B(A

B)

B

A(A

B)

B

A(A

B)

(B

C)

(A

C)

(A

B)

(B

C)

(A

C)

(A

B)

(C

D)

(A

C)

(B

D)(A

B)

(

A

B)

B(A

B)

(C

D)

(

B

D)

(

A

C)附加律破壞性二難構(gòu)造性二難（特殊形式）構(gòu)造性二難等價(jià)三段論假言三段論析取三段論拒取式假言推理化簡律3.1推理形式結(jié)構(gòu)推理定律A

(A

B)(A

B)

A(A

B)

A

B(A

B)

B

A(A

B)

B

A(A

B)

(B

C)

(A

C)

(A

B)

(B

C)

(A

C)

(A

B)

(C

D)

(A

C)

(B

D)(A

B)

(

A

B)

B(A

B)

(C

D)

(

B

D)

(

A

C)附加律破壞性二難構(gòu)造性二難（特殊形式）構(gòu)造性二難等價(jià)三段論假言三段論析取三段論拒取式假言推理化簡律3.1推理形式結(jié)構(gòu)證明：(AB)

(BC)

(AC)

((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

A)

((BC)C))(B

A)

(BC)T3.1推理形式結(jié)構(gòu)3.2自然推理系統(tǒng)P從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯推理規(guī)則推出結(jié)論的過程為什么要自然演繹(naturaldeduction)？給出驗(yàn)證的推理過程需要引入證明的概念自然演繹模擬人類的推理A1

…

Ak

B3.2自然推理系統(tǒng)P定義3.2

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

(1)非空的字母表，記作A(I).(2)A(I)中符號(hào)構(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)>是I的形式語言系統(tǒng),<AX(I),R(I)>是I的形式演算系統(tǒng).自然推理系統(tǒng):無公理,即AX(I)=

公理推理系統(tǒng)推出的結(jié)論是系統(tǒng)中的重言式,稱作定理感興趣的可以閱讀《GEB－－一條永恒的金帶》有一位理發(fā)師聲稱，他給所有不給自己理發(fā)的人理發(fā)愛皮梅尼特是一個(gè)克里特島人。他說：“所有的克里特島人都撤謊。”第一類集合不能以自己為元素，也就是說自己不能屬于自己，我們稱為r型。第二類集合可以以自己為元素，我們稱為s型。證明《數(shù)學(xué)原理》所定義的系統(tǒng)既是一致的(無矛盾)又是完備的(該系統(tǒng)的理論框架中容納了每個(gè)正確的數(shù)論命題)。這就是數(shù)學(xué)史上著名的希爾伯特綱領(lǐng)。自然推理系統(tǒng)P定義3.3自然推理系統(tǒng)P定義如下:1.字母表

(1)命題變項(xiàng)符號(hào)：p,q,r,…,pi,qi,ri,…(2)聯(lián)結(jié)詞符號(hào)：

,

,

,

,

(3)括號(hào)與逗號(hào)：(,),，2.合式公式（同定義1.6）3.推理規(guī)則

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

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

(3)置換規(guī)則3.2自然推理系統(tǒng)P假言推理規(guī)則

A

B

A

結(jié)論：B(A

B)

A

BAllmenaremortalSocratesisaman

ThereforeSocratesismortal3.2自然推理系統(tǒng)P附加規(guī)則

A

結(jié)論：A

BA

(A

B)3.2自然推理系統(tǒng)P化簡規(guī)則

A

B

結(jié)論：A合取引入規(guī)則A

B

結(jié)論：A

B(A

B)

A3.2自然推理系統(tǒng)P證明p,q,p

q

r?r

p

q

p

qp

q

rr推理過程可以寫成證明樹3.2自然推理系統(tǒng)P拒取式規(guī)則

A

B

B

結(jié)論：A假言三段式規(guī)則A

B

B

C

結(jié)論：A

C(A

B)

B

A(A

B)

(B

C)

(A

C)

3.2自然推理系統(tǒng)P析取三段式規(guī)則

A

B

B

結(jié)論：A構(gòu)造二難推理規(guī)則A

B

C

DA

C

結(jié)論：B

D(A

B)

B

A(A

B)

(C

D)

(A

C)

(B

D)3.2自然推理系統(tǒng)P破壞性二難推理規(guī)則

A

B

C

D

B

D

結(jié)論：

A

C

(A

B)

(C

D)

(

B

D)

(

A

C)3.2自然推理系統(tǒng)P形式推演(語法蘊(yùn)涵)：給定A1,…,Ak和B符號(hào)：{A1,…,Ak}?B存在公式序列C1,C2,…,Cn，對(duì)每個(gè)i(i=1,…,n),Ci是某個(gè)Aj或者Ci是有序列中前面的公式應(yīng)用推理規(guī)則得到Cn=B稱C1,…,Cn是有A1,…,Ak推B的證明

3.2自然推理系統(tǒng)P例：考慮下述論證如果這里有球賽，則通行是困難的如果他們按時(shí)到達(dá)，則通行是不困難的他們按時(shí)到達(dá)了所以這里沒有球賽設(shè)p:這里有球賽q:通行是困難的r:他們按時(shí)到達(dá)p

q

r

qr

p

3.2自然推理系統(tǒng)P證明前提：p

q，r

q，r結(jié)論：

p

解：

r

r

q

q

p

q

p前提引入前提引入假言推理前提引入拒取式3.2自然推理系統(tǒng)P證明c

d,c

r,d

s

?r

s

解：

c

d

c

d

d

s

c

s

c

r

r

c

r

s

r

s前提引入前提引入假言三段論前提引入置換規(guī)則置換規(guī)則假言三段論置換規(guī)則3.2自然推理系統(tǒng)P構(gòu)造證明的方法附加前提證明法歸謬法

3.2自然推理系統(tǒng)P附加前提證明法對(duì)形如(A1…Ak)(A

B)的證明

為什么呢？

轉(zhuǎn)化為：

A1,…,Ak,A?B3.2自然推理系統(tǒng)P證明((p

(q

s))

(?r

p)

q)

(r

s)

解：

r

?r

p

r

p

p

p

(q

s)

q

s

q

s前提引入前提引入假言推理前提引入置換規(guī)則假言推理假言推理前提引入練習(xí)P53,14(6)P5415(2)3.2自然推理系統(tǒng)P歸謬法對(duì)形如(A1…Ak)

B的證明

轉(zhuǎn)化為：

A1…Ak

B為矛盾式3.2自然推理系統(tǒng)P證明

((r?q)

(r∨s)

(s

q)

(p

q))

p解：

p

p

q

q

s

q

q

s

s

r∨s

r

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

1.(A1

A2

…

Ak)

B2.前提：A1,A2,…,Ak

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

p

q,

q

結(jié)論：

p解推理的形式結(jié)構(gòu):(

p

q)

q

p方法一：等值演算法

(

p

q)

q

p

((p

q)

q)

p

(

p

q)

q

p

((

p

q)

(

q

q))

p

p

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

(

p

q)

q

p((p

q)q)p

p

q

M2

m0

m1

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

不是重言式,推理不正確111001110100(

p

q)

q

pqp

p

q0111(p

q)

q0010方法四直接觀察出10是成假賦值練習(xí)1解答用等值演算法

(q

r)

(p

r)(q

p)(q

r)(p

r)(q

p)

((q

r)(p

r))(q

p)

((q

p)(q

r)(r

p))(q

p)((q

p)(q

r)(r

p))(q

p)1推理正確(2)前提：q

r,p

r

結(jié)論：q

p

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

r)

(p

r)(q

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

(1)設(shè)p：今天是周六，q：到頤和園玩，

r：到圓明園玩，s：頤和園游人太多

t：到動(dòng)物園玩

(2)前提：p

(q

r),s

q,p,s

結(jié)論：r

t練習(xí)2解答(3)證明：①p

(q

r)前提引入②p