1、第三章 命題邏輯的推理理論,本章的主要內(nèi)容 推理的形式結(jié)構(gòu) 自然推理系統(tǒng)P 本章與其他章的聯(lián)系 本章是第五章的特殊情況和先行準(zhǔn)備,3.1 推理的形式結(jié)構(gòu),一、何為推理？何為證明？ 1例（1）正項級數(shù)收斂當(dāng)且僅當(dāng)部分和有上界 （2）若AB且CD，則ACBD （3）若今天是星期一，則明天是星期二 （4）若ACBD，則AB且CD,2推理從前提出發(fā)推出結(jié)論的思維過程 上例中，（1），（2），（3）是正確的推理，而（4）是錯誤的推理.,3證明描述推理正確或錯誤的過程。,二、推理的形式結(jié)構(gòu)及證明方法,1推理的正確與錯誤 定義3.1 設(shè)A1, A2, , Ak, B為命題公式 （1）若對于每組賦值，或者A1

2、A2 Ak 均為假，或者當(dāng)A1A2Ak為真時，B也為真，則稱由前提A1, A2, , Ak推出B的推理正確，并稱B是有效結(jié)論； （2）否則稱推理不正確（錯誤）；,定理3.1 命題公式A1, A2, , Ak 推B的推理正確當(dāng)且僅當(dāng) A1A2AkB為重言式,2推理的形式結(jié)構(gòu)（多種形式） （1）設(shè)= A1, A2, , Ak B （2）A1A2AkB （3）前提： A1, A2, , Ak 結(jié)論： B,說明： 當(dāng)推理正確時， （1）中記為 B， （2）中記為A1A2AkB,3判斷推理是否正確的方法（多種） （1）真值表法 （2）等值演算法 （3）主析取范式法 （4）構(gòu)造證明法,說明： 當(dāng)命題變項少

3、時，（1）（3）方便 （1），（2）, （3）用形式結(jié)構(gòu)（2） 構(gòu)造證明法用形式結(jié)構(gòu)（3）,例 判斷下面推理是否正確?（1）若今天是1號，則明天是5號. 今天是1號. 所以明天是5號. （2）若今天是1號，則明天是5號. 明天是5號. 所以今天是1號.,解 設(shè)p：今天是1號，q：明天是5號. 證明的形式結(jié)構(gòu)采用（2）. （1）(pq)pq （2）(pq)qp,證明（1）（用等值演算法） (pq)pq (pq)p)q pqq 1 由定理3.1可知推理正確,證明：（2）（用主析取范式法） (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 結(jié)果不含m

4、1, 故01是成假賦值,所以推理不正確,4.推理定律 （1）推理定律重言蘊涵式 （2）重要的推理定律 A (AB) 附加律 (AB) A 化簡律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段論 (AB)(BC) (AC) 假言三段論 (AB)(BC) (AC) 等價三段論 (AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB)(AA)B 構(gòu)造性二難(特殊形式) (AB)(CD)( BD) (AC) 破壞性二難,3.2 自然推理系統(tǒng)P,一、形式系統(tǒng) 1形式系統(tǒng)的定義 定義3.2 一個形式系統(tǒng)I由下面四個部分組成： （1）非空的字母表，記作A(I). （2）

5、A(I)中符號構(gòu)造的合式公式集，記作E(I). （3）E(I)中一些特殊的公式組成的公理集，記作AX(I). （4）推理規(guī)則集，記作R(I).,2形式系統(tǒng)的分類 （1）自然推理系統(tǒng) （2）公理系統(tǒng),二、自然推理系統(tǒng)P 定義3.3 P的定義如下 1字母表 （1）命題變項符號：p, q, r, , pi, qi, ri, （2）聯(lián)結(jié)詞符號：, , , , （3）括號與逗號：(, ), ， 2合式公式（同定義1.6）,3推理規(guī)則,（4）假言推理規(guī)則,（5）附加規(guī)則：,（1）前提引入規(guī)則,（2）結(jié)論引入規(guī)則,（3）置換規(guī)則,AB,A,B,A,AB,（6）化簡規(guī)則：,（7）拒取式規(guī)則：,AB,A,AB,

6、B,A,（8）假言三段論規(guī)則：,AB,BC,AC,（9）析取三段論規(guī)則：,AB,B,A,（10）構(gòu)造性二難推理規(guī)則：,AB,CD,AC,BD,(11) 破壞性二難推理規(guī)則：,AB,CD,BD,AC,（12）合取引入規(guī)則：,A,B,AB,三、在自然推理系統(tǒng)P中構(gòu)造證明,1直接證明法,例：證明 (pq) , (pr) ,(qs) sr,思路：由前提出發(fā)，通過形式推理，往結(jié)論上靠 （1） pq 前提引入 （2） p q (1) 置換 （3） q s 前提引入 （4） p s (2) ,(3) ,假言三段論 （5） s p (4) ,置換 （6） pr 前提引入 （7） s r (5),(6),假言三

7、段論 （8） sr (7) ,置換,例：證明pq,q(rs),r(t u), ptu,證明： (1)pq 前提引入 (2)q(rs) 前提引入 (3)p(rs) (1),(2)假言三段論 (4)pt 前提引入 (5)p (4),化簡 (6) (rs) (5),(3),假言推理,(7)r (6),化簡 (8) r(t u) 前提引入 (9) (rt) u (8),置換 (10)t (4),化簡 (11) rt (7),(10),合取 (12) u (9),(11),析取三段論,例 用直接證明法構(gòu)造下面推理的證明： 若明天是星期一或星期三，我就有課。 若有課，今天必備課。我今天下午沒備課. 所以，

8、說明天是星期一或星期三是不對的。,構(gòu)造證明（1）設(shè)p：明天是星期一，q：明天是星期三，r：我有課，s：我備課 （2）形式結(jié)構(gòu)： 前提：(pq)r, rs, s 結(jié)論：(p q),（3）證明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式,練習(xí)： 1.證明：(pr),qs ,p,q rs 2.在自然推理系統(tǒng)中構(gòu)造下面推理的證明： 若小張喜歡數(shù)學(xué)，則小李或小趙也喜歡數(shù)學(xué)。若小李喜歡數(shù)學(xué)，他也喜歡物理。小張確實喜歡數(shù)學(xué)，可小李不喜歡物理，所以小趙喜歡數(shù)學(xué)。,練習(xí)： 3.如果樂隊不能演奏搖滾樂或者點心沒有準(zhǔn)時送上來，那么新年音樂會就將取消，并且瑪麗會很生氣。如果音樂會

9、取消，那么就要辦理退款。沒有辦理退款。所以樂隊能演奏搖滾樂。,2. 附加前提證明法 （1）欲證： 前提：A1, A2, , Ak 結(jié)論：CB,（2）等價地證明 前提: A1, A2, , Ak, C 結(jié)論： B,（3）理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,例 構(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

10、結(jié)論：sq,（3）證明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段論 p 拒取式 pq 前提引入 q 析取三段論,請用直接證明法證明之,練習(xí)：證明： (1)p(qr)，(uv)r，q(ps)qu (2)p（qs），rp，q， rs,3歸謬法（或稱反證法） （1）欲證 A1A2AkB 前提：A1, A2, , Ak 結(jié)論：B,（2）將B當(dāng)前提，推出矛盾，得證（1）正確,（3）理由： A1A2AkB (A1A2Ak)B (A1A2AkB) 括號內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1A2AkB)為重言式,例 前提：(pq)r, rs, s, p結(jié)論：q,證明（用歸繆法） q 結(jié)論否定引入

11、 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段論 pq 置換 p 析取三段論 p 前提引入 pp 合取,請用直接證明法證明之,練習(xí)： 證明： (1)pq，(qr)r，(ps)s (2) (pq) (qr) p,第三章 小 結(jié),一、本章的主要內(nèi)容及要求 1主要內(nèi)容 推理的形式結(jié)構(gòu)的不同形式 判斷推理是否正確的不同方法 真值表法 等值演算法 主析取范式法 構(gòu)造證明法 在自然推理系統(tǒng)P中構(gòu)造證明,2. 要求 理解并記住推理形式結(jié)構(gòu)的如下形式： (A1A2Ak)B 前提：A1, A2, , Ak 結(jié)論：B 熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法

12、、主析取范式法等） 牢記P系統(tǒng)中各條推理規(guī)則（內(nèi)容與名稱） 會用附加前提證明法及歸謬法,二、練習(xí) 1用不同的方法驗證下面推理是否正確. 對于正確的推理還要在P系統(tǒng)中給出證明. （1）前提：pq, q 結(jié)論：p （2）前提：qr, pr 結(jié)論：qp,解（1）答案：不正確。驗證答案，需將推理形式結(jié)構(gòu)改為另一種形式 (pq)qp () 只需證明()不是重言式,方法一 等值演算 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq 易知10是成假賦值，故()不是重言式，所以推理不正確.,方法二 主析取范式法經(jīng)過演算后可知 () m0m1m3未含m2, 故()不是重言式.,方法三 真值表法，()的真值表為,結(jié)論（不正確）是對的,方法四 直接觀察出10是成假賦值,解（2）答案：推理正確 方法一 真值表法（自己做） 方法二 等值演算法（自己做） 方法三 主析取范式法（自己做）,方法四 P系統(tǒng)中構(gòu)造證明 證明：（直接證明法） pr （前提引入） rp （置換） qr （前提引入） qp （假言三段論）,請用附加前提證明法證明之,2在P系統(tǒng)中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和園游人太多，就不去頤和園. 今天是周六，并且頤和園游人太多.