命題邏輯的推理理論

第一頁，共三十五頁，編輯于2023年，星期日數(shù)理邏輯的主要任務(wù)是用數(shù)學的方法來研究數(shù)學中的推理。推理是指從前提出發(fā)推出結(jié)論的思維過程。前提是已知命題公式集合。結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。證明是描述推理正確或錯誤的過程。要研究推理，首先應(yīng)該明確什么樣的推理是有效的或正確的。第二頁，共三十五頁，編輯于2023年，星期日定義1.24

設(shè)A1,A2,…,Ak和B都是命題公式，若對于A1,A2,…,Ak和B中出現(xiàn)的命題變項的任意一組賦值，

（1）或者A1∧A2∧…∧Ak為假;

（2）或者當A1∧A2∧…∧Ak為真時，B也為真;

則稱由前提A1,A2,…,Ak推出B的推理是有效的或正確的，并稱B是有效結(jié)論。有效推理的定義即：（A1∧A2∧…∧Ak）→B為重言式第三頁，共三十五頁，編輯于2023年，星期日關(guān)于有效推理的說明＝{A1，A2，…，Ak}

由推B的推理記為┣B

若推理是正確的，記為

╞

B

若推理是不正確的，記為

B由前提A1，A2，…，Ak推結(jié)論B的推理是否正確與諸前提的排列次序無關(guān)。第四頁，共三十五頁，編輯于2023年，星期日設(shè)A1，A2，…，Ak，B中共出現(xiàn)n個命題變項，對于任何一組賦值α1α2…αn(αi=0或者1，i=1,2,…,n)，前提和結(jié)論的取值情況有以下四種：

(1)A1∧A2∧…∧Ak為0，B為0。

(2)A1∧A2∧…∧Ak為0，B為1。

(3)A1∧A2∧…∧Ak為1，B為0。

(4)A1∧A2∧…∧Ak為1，B為1。只要不出現(xiàn)(3)中的情況，推理就是正確的，因而判斷推理是否正確，就是判斷是否會出現(xiàn)(3)中的情況。推理正確，并不能保證結(jié)論B一定為真。

第五頁，共三十五頁，編輯于2023年，星期日

(1){p,p→q}├q

(2){p,q→p}├q

例1

判斷下列推理是否正確。（真值表法）pqp(p→q)qp(q→p)q000000010101100010111111正確不正確第六頁，共三十五頁，編輯于2023年，星期日當推理正確時，形式（1）記為╞

B。形式（2）記為A1A2…AkB。

表示蘊涵式為重言式。

={A1,A2,…,Ak}，記為┣B。

A1A2…AkB前提：A1,A2,…,Ak

結(jié)論：B說明推理的形式結(jié)構(gòu)第七頁，共三十五頁，編輯于2023年，星期日

真值表法等值演算法主析取范式法判斷推理是否正確的方法是否有其他的證明方法？思考當命題變項較少時,這三種方法比較方便。說明第八頁，共三十五頁，編輯于2023年，星期日

下午馬芳或去看電影或去游泳。她沒去看電影，所以，她

去游泳了。例2

判斷下列推理是否正確。（等值演算法）

解：設(shè)p:馬芳下午去看電影，q:馬芳下午去游泳。 前提：p∨q，┐p

結(jié)論：q

推理的形式結(jié)構(gòu)：((p∨q)∧┐p)→q((p∨q)∧┐p)→q

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

)∧(┐q∨p))∨

q(┐q∨p)∨

q

1例題第九頁，共三十五頁，編輯于2023年，星期日(1)A(A∨B)

附加律(2)(A∧B)A

化簡律(3)

(A→B)∧AB

假言推理(4)(A→B)∧┐B┐A

拒取式(5)(A∨B)∧┐BA

析取三段論(6)

(A→B)∧(B→C)(A→C)

假言三段論(7)

(AB)∧(BC)(AC) 等價三段論(8)

(A→B)∧(C→D)∧(A∨C)(B∨D)

構(gòu)造性二難(9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破壞性二難

推理定律--重言蘊含式第十頁，共三十五頁，編輯于2023年，星期日關(guān)于推理定律的幾點說明A,B,C為元語言符號，代表任意的命題公式。若一個推理的形式結(jié)構(gòu)與某條推理定律對應(yīng)的蘊涵式一致，則不用證明就可斷定這個推理是正確的。1.3節(jié)給出的24個等值式中的每一個都派生出兩條推理定律。例如雙重否定律A

A產(chǎn)生兩條推理定律A

A和

AA。由九條推理定律可以產(chǎn)生九條推理規(guī)則,它們構(gòu)成了推理系統(tǒng)中的推理規(guī)則。第十一頁，共三十五頁，編輯于2023年，星期日構(gòu)造性證明方法判斷推理是否正確的三種方法：真值表法、等值演算法和主析取范式法。當推理中包含的命題變項較多時，上述三種方法演算量太大。對于由前提A1,A2,…,Ak推B的正確推理應(yīng)該給出嚴謹?shù)淖C明。證明是一個描述推理過程的命題公式序列，其中的每個公式或者是前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論（中間結(jié)論或推理中的結(jié)論）。第十二頁，共三十五頁，編輯于2023年，星期日常用的推理規(guī)則（1）前提引入規(guī)則：在證明的任何步驟上，都可以引入前提。（2）結(jié)論引入規(guī)則：在證明的任何步驟上，所證明的結(jié)論都可以作為后續(xù)證明的前提。（3）置換規(guī)則：在證明的任何步驟上，命題公式中任何子命題公式都可以用與之等價的命題公式置換。第十三頁，共三十五頁，編輯于2023年，星期日（4）假言推理規(guī)則

AB

A

B（5）附加規(guī)則

A

AB（6）化簡規(guī)則

AB

A（4）若今天下雪,則將去滑雪。今天下雪，所以去滑雪。

（5）現(xiàn)在氣溫在冰點以下。因此，要么現(xiàn)在氣溫在冰點以下，要么現(xiàn)在下雨。（6）現(xiàn)在氣溫在冰點以下并且正在下雨。因此，現(xiàn)在氣溫在冰點以下。第十四頁，共三十五頁，編輯于2023年，星期日（7）拒取式規(guī)則

AB

B

A（8）

假言三段論規(guī)則

AB

BC

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

AB

B

A第十五頁，共三十五頁，編輯于2023年，星期日（10）構(gòu)造性二難推理規(guī)則

AB

CD

AC

BD（11）破壞性二難推理規(guī)則

AB

CD

BD

AC（12）合取引入規(guī)則

A

B

AB第十六頁，共三十五頁，編輯于2023年，星期日構(gòu)造證明構(gòu)造證明就是由一組公式作為前提，利用自然推理系統(tǒng)中的規(guī)則，推出結(jié)論。構(gòu)造形式結(jié)構(gòu)A1A2…AkB的推理的書寫方法：

前提：A1,A2,…,Ak

結(jié)論：B證明方法：直接證明法附加前提法歸謬法（或稱反證法）第十七頁，共三十五頁，編輯于2023年，星期日例3.1

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

前提：┐p∨q,r∨┐q,r→s

結(jié)論：p→s①┐p∨q

前提引入②p→q

①置換③r∨┐q

前提引入④q→r

③置換⑤p→r

②④假言三段論⑥r(nóng)→s

前提引入⑦p→s

⑤⑥假言三段論

第十八頁，共三十五頁，編輯于2023年，星期日例題例3.2

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

前提：p→（q→r）,p∧q

結(jié)論：┐r→s①p→（q→r）

前提引入②p∧q

前提引入③p

②化簡④q

②化簡⑤q→r

①③假言推理⑥r(nóng)

④⑤假言推理⑦r∨s

⑥附加⑧┐r→s ⑦置換第十九頁，共三十五頁，編輯于2023年，星期日技巧一：附加前提證明法(A1∧A2∧…∧Ak)→(A→B)

等價于

(A1∧A2∧…∧Ak∧A)→B即原來結(jié)論中的前件變成前提了！第二十頁，共三十五頁，編輯于2023年，星期日例4

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

如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當小趙去看電影時，小李也去看電影。構(gòu)造證明：（1）將簡單命題符號化：設(shè) p:小張去看電影。

q:小王去看電影。

r:小李去看電影。

s:小趙去看電影。

第二十一頁，共三十五頁，編輯于2023年，星期日（2） 形式結(jié)構(gòu)：

前提：(p∧q)→r,┐s∨p,q

結(jié)論：s→r（3）證明：用附加前提證明法

①s

附加前提引入②┐s∨p

前提引入

③p

①②析取三段論④(p∧q)→r 前提引入⑤q

前提引入

⑥p∧q

③⑤合取

⑦r

④⑥假言推理

第二十二頁，共三十五頁，編輯于2023年，星期日技巧二：歸謬法(A1∧A2∧…∧Ak)→B等價于┐（A1∧A2∧…∧Ak∧┐B）因此，若A1∧A2∧…∧Ak與┐B不相容（即A1∧A2∧…∧Ak∧┐B為矛盾式，或┐（A1∧A2∧…∧Ak∧┐B）為重言式），則說明B是A1∧A2∧…∧Ak的邏輯結(jié)論。這種將┐B作為附加前提推出矛盾的證明方法成為歸謬法。第二十三頁，共三十五頁，編輯于2023年，星期日例5

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

如果小張守第一壘并且小李向B隊投球，則A隊將取勝；或者A隊未取勝，或者A隊獲得聯(lián)賽第一名；A隊沒有獲得聯(lián)賽的第一名；小張守第一壘。因此，小李沒有向B隊投球。構(gòu)造證明：（1）將簡單命題符號化：設(shè)p:小張守第一壘。 q:小李向B隊投球。

r:A隊取勝。 s:A隊獲得聯(lián)賽第一名。（2）形式結(jié)構(gòu)：

前提：(p∧q)→r,┐r∨s,┐s,p

結(jié)論：┐q

第二十四頁，共三十五頁，編輯于2023年，星期日例題（3）證明：用歸謬法①q

結(jié)論的否定引入②┐r∨s

前提引入③┐s

前提引入④┐r

②③析取三段論⑤(p∧q)→r 前提引人⑥┐(p∧q)

④⑤拒取式⑦┐p∨┐q

⑥置換⑧p

前提引入⑨┐q

⑦⑧析取三段論⑩q∧┐q

①⑨合取由于最后一步為矛盾式，所以推理正確。

小節(jié)結(jié)束第二十五頁，共三十五頁，編輯于2023年，星期日本節(jié)主要內(nèi)容推理的形式結(jié)構(gòu)：

推理的前提

推理的結(jié)論

推理正確判斷推理是否正確的方法：

真值表法

等值演算法

主析取范式法

對于正確的推理，給予構(gòu)造證明:

1.常用的推理規(guī)則：

2.附加前提證明法

3.歸謬法第二十六頁，共三十五頁，編輯于2023年，星期日本章學習要求理解并記住推理的形式結(jié)構(gòu)的三種等價形式，即

①{A1,A2,…,Ak}├B

②A1∧A2∧…∧Ak→B

③前提：A1,A2,…,Ak

結(jié)論：B在判斷推理是否正確時，用②；在系統(tǒng)中構(gòu)造證明時用③。

熟練掌握判斷推理是否正確的三種方法（真值表法，等值演算法，主析取范式法）。

牢記各條推理規(guī)則。

對于給定的正確推理，要求在系統(tǒng)中給出嚴謹?shù)淖C明序列。

會用附加前提證明法和歸謬法。

第二十七頁，共三十五頁，編輯于2023年，星期日典型例題1、用不同的方法驗證下面推理是否正確。對于正確的推理還要在系統(tǒng)中給出證明。（1）前提：pq,q結(jié)論：p（2）

前提：qr,pr結(jié)論：qp

第二十八頁，共三十五頁，編輯于2023年，星期日（1）不正確。驗證答案，只需證明(pq)qp不是重言式。方法一等值演算(pq)qp

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

pq易知10是成假賦值，故(pq)qp不是重言式，所以推理不正確。第二十九頁，共三十五頁，編輯于2023年，星期日方法二主析取范式法經(jīng)過演算后可知(pq)qp

m0m1m3未含m2,故(pq)qp不是重言式。方法三直接觀察出10是成假賦值。第三十頁，共三十五頁，編輯于2023年，星期日方法四真值表法(pq)qp的真值表為pq(pq)qp001101010111結(jié)論（不正確）是對的。第三十一頁，共三十五頁，編輯于2023年，星期日（2）推理正確方法一真值表法（自己做）方法二等值演算法（自己做）方法三主析取范式法（自己做）方法四