1、第3章 命題邏輯的推理理論,聊城大學(xué)重點課程 離散數(shù)學(xué),本章說明,本章的主要內(nèi)容 推理的形式結(jié)構(gòu) 自然推理系統(tǒng)P 本章與后續(xù)各章的關(guān)系 本章是第五章的特殊情況和先行準備,3.1 推理的形式結(jié)構(gòu) 3.2 自然推理系統(tǒng)P 本章小結(jié) 習(xí)題 作業(yè),3.1 推理的形式結(jié)構(gòu),數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來研究數(shù)學(xué)中的推理。 推理是指從前提出發(fā)推出結(jié)論的思維過程。 前提是已知命題公式集合。 結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。 證明是描述推理正確或錯誤的過程。 要研究推理，首先應(yīng)該明確什么樣的推理是有效的或正確的。,定義3.1 設(shè)A1,A2,Ak和B都是命題公式，若對于A1,A2,Ak和B中出現(xiàn)

2、的命題變項的任意一組賦值，（1）或者A1A2 Ak為假;（2）或者當(dāng)A1A2 Ak為真時，B也為真;則稱由前提A1,A2,Ak推出B的推理是有效的或正確的，并稱B是有效結(jié)論。,有效推理的定義,關(guān)于有效推理的說明,A1，A2，Ak由 推B的推理記為B若推理是正確的，記為 B若推理是不正確的，記為 B,由前提A1，A2，Ak推結(jié)論B的推理是否正確與諸前提的排列次序無關(guān)。,關(guān)于有效推理的說明,設(shè)A1，A2，Ak，B中共出現(xiàn)n個命題變項，對于任何一組賦值12n(i=0或者1，i=1,2,n)，前提和結(jié)論的取值情況有以下四種： (1) A1A2 Ak為0，B為0。(2) A1A2 Ak為0，B為1。(3

3、) A1A2 Ak為1，B為0。(4) A1A2 Ak為1，B為1。 只要不出現(xiàn)(3)中的情況，推理就是正確的，因而判斷推理是否正確，就是判斷是否會出現(xiàn)(3)中的情況。 推理正確，并不能保證結(jié)論B一定為真。,(1) p,pq q (2) p,qp q,例3.1 判斷下列推理是否正確。（真值表法）,例題,正確,不正確,定理3.1 命題公式A1,A2,Ak推B的推理正確當(dāng)且僅當(dāng) (A1A2Ak )B 為重言式。,該定理是判斷推理是否正確的另一種方法。,說明,有效推理的等價定理,定理3.1的證明,(1)證明必要性。若A1,A2,Ak推B的推理正確， 則對于A1,A2,Ak,B中所含命題變項的任意一組

4、賦值，不會出現(xiàn)A1A2Ak為真，而B為假的情況， 因而在任何賦值下，蘊涵式(A1A2Ak )B均為真，故它為重言式。 (2)證明充分性。若蘊涵式(A1A2Ak)B為重言式， 則對于任何賦值此蘊涵式均為真，因而不會出現(xiàn)前件為真后件為假的情況， 即在任何賦值下，或者A1A2Ak為假， 或者A1A2Ak和B同時為真，這正符合推理正確的定義。,當(dāng)推理正確時， 形式（1）記為 B。 形式（2）記為A1A2AkB。 表示蘊涵式為重言式。,設(shè)= A1, A2, , Ak，記為B。 A1A2AkB 前提： A1, A2, , Ak 結(jié)論： B,說明,推理的形式結(jié)構(gòu),真值表法 等值演算法 主析取范式法,判斷推理

5、是否正確的方法,是否有其他的證明方法？,思考,當(dāng)命題變項較少時,這三種方法比較方便。,說明,（1） 下午馬芳或去看電影或去游泳。她沒去看電影，所以，她 去游泳了。,例3.2 判斷下列推理是否正確。（等值演算法）,解：設(shè)p:馬芳下午去看電影，q:馬芳下午去游泳。 前提： pq，p 結(jié)論： q 推理的形式結(jié)構(gòu)： (pq)p)q (pq)p)q (pq)p) q (pq)p) q (pp )(qp) q (qp) q 1,由定理 3.1可知，推理正確。,例題,（2）若今天是1號，則明天是5號。明天是5號，所以今天是1號。,例3.2 判斷下列推理是否正確。（主析取范式法 ）,(pq)qp, (pq)q

6、p, (pq)q)p, qp, (pq)(pq) (pq)(pq), m0m2m3,主析取范式不含m1，故不是重言式（01是成假賦值），所以推理不正確。,解：設(shè)p：今天是1號，q：明天是5號。 前提：pq，q 結(jié)論： p 推理的形式結(jié)構(gòu)： (pq)qp,例題,(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) (A C) 等價三段論 (8)(AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB)(AA) B

7、 構(gòu)造性二難 (特殊形式) (9)(AB)(CD)(BD) (AC) 破壞性二難,推理定律-重言蘊含式,小節(jié)結(jié)束,關(guān)于推理定律的幾點說明,A,B,C為元語言符號，代表任意的命題公式。 若一個推理的形式結(jié)構(gòu)與某條推理定律對應(yīng)的蘊涵式一致，則不用證明就可斷定這個推理是正確的。 2.1節(jié)給出的24個等值式中的每一個都派生出兩條推理定律。例如雙重否定律A A產(chǎn)生兩條推理定律A A和 AA。 由九條推理定律可以產(chǎn)生九條推理規(guī)則,它們構(gòu)成了推理系統(tǒng)中的推理規(guī)則。,3.2 自然推理系統(tǒng)P,判斷推理是否正確的三種方法：真值表法、等值演算法和主析取范式法。 當(dāng)推理中包含的命題變項較多時，上述三種方法演算量太大。

8、 對于由前提A1,A2,Ak推B的正確推理應(yīng)該給出嚴謹?shù)淖C明。 證明是一個描述推理過程的命題公式序列，其中的每個公式或者是前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論（中間結(jié)論或推理中的結(jié)論）。 要構(gòu)造出嚴謹?shù)淖C明就必須在形式系統(tǒng)中進行。,形式系統(tǒng)的定義,定義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元組 是I的形式語言系統(tǒng) 是I的形式演算系統(tǒng),形式系統(tǒng)的分類,（1）自然推理系統(tǒng) 從任意給定的前

9、提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進行推理演算，得到的最后命題公式是推理的結(jié)論（有時稱為有效的結(jié)論）。 （2）公理系統(tǒng) 從若干給定的公理出發(fā)，應(yīng)用系統(tǒng)中推理規(guī)則進行推理演算，得到的結(jié)論是系統(tǒng)中的定理。,本書只介紹自然推理系統(tǒng)P。,說明,自然推理系統(tǒng)的定義,定義3.3 自然推理系統(tǒng)P的定義 1. 字母表 （1） 命題變項符號：p， q， r， ， pi，qi，ri ， （2） 聯(lián)結(jié)詞符號： ， ， ， ， （3） 括號與逗號：( )， 2. 合式公式（同定義1.6）,自然推理系統(tǒng)的定義,3. 推理規(guī)則 （1）前提引入規(guī)則 在證明的任何步驟上都可以引入前提。 （2）結(jié)論引入規(guī)則 在證明的任何步驟上所得到

10、的結(jié)論都可以作為后繼證明的前提。 （3）置換規(guī)則 在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個公式。,自然推理系統(tǒng)的定義,（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)在氣溫在冰點以下。,自然推理系統(tǒng)的定義,（7）拒取式規(guī)則 AB B A （8）假言三段論規(guī)則 AB BC AC （9）析取三段論規(guī)則 AB B A,自然推理系統(tǒng)的定義,（10）

11、構(gòu)造性二難推理規(guī)則 AB CD AC BD （11）破壞性二難推理規(guī)則 AB CD BD AC （12） 合取引入規(guī)則 A B AB,在自然推理系統(tǒng)P中構(gòu)造證明,P中構(gòu)造證明就是由一組P中公式作為前提，利用P中的規(guī)則，推出結(jié)論。 構(gòu)造形式結(jié)構(gòu)A1A2Ak B 的推理的書寫方法：前提： A1,A2,Ak 結(jié)論： B 證明方法： 直接證明法 附加前提法 歸謬法（或稱反證法）,例題,例3.3 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：前提：pq, rq ,rs 結(jié)論：ps pq 前提引入 pq 置換 rq 前提引入 qr 置換 pr 假言三段論 rs 前提引入 ps 假言三段論,例題,例3.3 在自然推

12、理系統(tǒng)P中構(gòu)造下面推理的證明：前提：p（qr）, pq 結(jié)論： rs p（qr） 前提引入 pq 前提引入 p 化簡 q 化簡 qr 假言推理 r 假言推理 rs 附加 rs置換,例題,例3.4 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： 若數(shù)a是實數(shù)，則它不是有理數(shù)就是無理數(shù)；若a不能表示成分數(shù)，則它不是有理數(shù)；a是實數(shù)且它不能表示成分數(shù)。所以a是無理數(shù)。,構(gòu)造證明： （1）將簡單命題符號化： 設(shè) p：a是實數(shù)。 q：a是有理數(shù)。 r：a是無理數(shù)。 s：a能表示成分數(shù)。 （2）形式結(jié)構(gòu)： 前提：p(qr), sq, ps 結(jié)論：r, ps 前提引入 p 化簡 s 化簡 p(qr) 前提引入 qr

13、 假言推理 sq 前提引入 q 假言推理 r 析取三段論,例題,附加前提法,有時推理的形式結(jié)構(gòu)具有如下形式 ： 前提：A1, A2, , Ak 結(jié)論：CB 可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為B。 前提：A1, A2, , Ak, C 結(jié)論：B 理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,例題,例3.5 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。 如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影時，小李也去看電影。 構(gòu)造證明： （1）將簡單命題符號化： 設(shè) p:小張去看

14、電影。 q:小王去看電影。 r:小李去看電影。 s:小趙去看電影。,例題,（2）形式結(jié)構(gòu)： 前提：(pq)r,sp,q 結(jié)論：sr （3）證明：用附加前提證明法 s 附加前提引入 sp 前提引入 p 析取三段論 (pq)r 前提引入 q 前提引入 pq 合取 r 假言推理,歸謬法（反證法）,有時推理的形式結(jié)構(gòu)具有如下形式： 前提：A1, A2, , Ak 結(jié)論：B 如果將B作為前提能推出矛盾來，則說明推理正確。 前提：A1, A2, , Ak, B 結(jié)論：矛盾 理由：A1A2AkB (A1A2Ak)B (A1A2AkB) 若A1A2AkB為矛盾式，則說明(A1A2AkB) 為重言式。,例題,例

15、3.6 在自然推理系統(tǒng)P中構(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)： 前提：(pq)r,rs,s ,p 結(jié)論：q,例題,（3）證明：用歸謬法 q 結(jié)論的否定引入 rs 前提引入 s 前提引入 r 析取三段論 (pq)r 前提引人 (pq) 拒取式 pq 置換 p 前提引入 q 析取三段論 qq 合取 由于最后一步為矛盾

16、式，所以推理正確。,小節(jié)結(jié)束,本章主要內(nèi)容,推理的形式結(jié)構(gòu)：推理的前提推理的結(jié)論推理正確 判斷推理是否正確的方法：真值表法等值演算法主析取范式法 對于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明: 自然推理系統(tǒng)P的定義自然推理系統(tǒng)P的推理規(guī)則：附加前提證明法歸謬法,本章學(xué)習(xí)要求,理解并記住推理的形式結(jié)構(gòu)的三種等價形式，即A1,A2,AkBA1A2AkB前提：A1,A2,Ak 結(jié)論：B 在判斷推理是否正確時，用；在P系統(tǒng)中構(gòu)造證明時用。 熟練掌握判斷推理是否正確的三種方法（真值表法，等值演算法，主析取范式法）。 牢記P系統(tǒng)中的各條推理規(guī)則。 對于給定的正確推理，要求在P系統(tǒng)中給出嚴謹?shù)淖C明序列。 會用

17、附加前提證明法和歸謬法。,小節(jié)結(jié)束,習(xí)題,1、用不同的方法驗證下面推理是否正確。對于正確的推理還要在P系統(tǒng)中給出證明。 （1） 前提：pq, q 結(jié)論：p （2）前提：qr, pr 結(jié)論：qp,（1）不正確。 驗證答案，只需證明(pq)qp不是重言式。 方法一 等值演算 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq 易知10是成假賦值，故(pq)qp不是重言式，所以推理不正確。,方法二 主析取范式法 經(jīng)過演算后可知 (pq)qp m0m1m3 未含m2, 故(pq)qp不是重言式。,方法三 直接觀察出10是成假賦值。,方法四 真值表法 (pq)qp的真值表為,結(jié)論（不正確）是對的。,（2）推理正確 方法一 真值表法（自己做） 方法二 等值演算法（自己做） 方法三 主析取范式法（自己做） 方法四 P系統(tǒng)中構(gòu)造證明 證明： （直接證明法） pr （前提引入） rp （置換） qr （前提引入） qp （假言三段論