ch3命題邏輯的推理理論

1、1主要內(nèi)容推理的形式結(jié)構(gòu)推理的正確與錯誤推理的形式結(jié)構(gòu)判斷推理正確的方法推理定律自然推理系統(tǒng)P形式系統(tǒng)的定義與分類自然推理系統(tǒng)P在P中構(gòu)造證明:直接證明法、附加前提證明法、歸謬法第三章 命題邏輯的推理理論23.1 推理的形式結(jié)構(gòu)定義3.1 設(shè)A1, A2, , Ak, B為命題公式. 若對于每組賦值，A1A2 Ak 為假，或當(dāng)A1A2Ak為真時，B也為真，則稱由前提A1, A2, , Ak推出結(jié)論B的推理是有效的或正確的, 并稱B是有效結(jié)論.定理3.1 由命題公式A1, A2, , Ak 推B的推理正確當(dāng)且僅當(dāng)A1A2AkB為重言式注意: 推理正確不能保證結(jié)論一定正確3推理的形式結(jié)構(gòu)2. A1

2、A2AkB 若推理正確, 記為A1 A2 Ak B3. 前提： A1, A2, , Ak 結(jié)論： B判斷推理是否正確的方法: 真值表法 等值演算法 主析取范式法推理的形式結(jié)構(gòu)1. A1, A2, , Ak B 若推理正確, 記為A1,A2,An B4推理實(shí)例例1 判斷下面推理是否正確(1) 若今天是1號，則明天是5號. 今天是1號. 所以, 明天是5號. (2) 若今天是1號，則明天是5號. 明天是5號. 所以, 今天是1號. 解 設(shè) p：今天是1號，q：明天是5號. (1) 推理的形式結(jié)構(gòu): (pq)pq用等值演算法 (pq)pq (pq)p)q pqq 1 由定理3.1可知推理正確5推理實(shí)

3、例(2) 推理的形式結(jié)構(gòu):(pq)qp 用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 結(jié)果不含m1, 故01是成假賦值，所以推理不正確6推理定律重言蘊(yùn)涵式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) 等價三段論8. (AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB) B 構(gòu)造性二難(特殊形式)9. (AB)(CD)( BD) (AC)

4、破壞性二難每個等值式可產(chǎn)生兩個推理定律如, 由AA可產(chǎn)生 AA 和 AA73.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=, 其中是 I 的形式語言系統(tǒng), 是 I 的形式演算系統(tǒng).自然推理系統(tǒng): 無公理, 即AX(I)=公理推理系統(tǒng) 推出的結(jié)論是系統(tǒng)中的重言式, 稱作定理8自然推理系統(tǒng)P定義3.3 自然推理系統(tǒng) P 定義如下:1. 字母表 (1) 命題變項(xiàng)符號

5、：p, q, r, , pi, qi, ri, (2) 聯(lián)結(jié)詞符號：, , , , (3) 括號與逗號：(, ), ，2. 合式公式（同定義1.6）3. 推理規(guī)則 (1) 前提引入規(guī)則 (2) 結(jié)論引入規(guī)則 (3) 置換規(guī)則9推理規(guī)則(4) 假言推理規(guī)則 (6) 化簡規(guī)則 (8) 假言三段論規(guī)則 AB AB AAB AB A(5) 附加規(guī)則 (7) 拒取式規(guī)則 (9) 析取三段論規(guī)則 AB BA AB BCACAB BA10推理規(guī)則(10) 構(gòu)造性二難推理規(guī)則 (11) 破壞性二難推理規(guī)則 (12) 合取引入規(guī)則 AB CD AC BD AB CD BD AC A BAC11在自然推理系統(tǒng)P中

6、構(gòu)造證明P中構(gòu)造證明就是由一組P中公式作為前提，利用P中的規(guī)則，推出結(jié)論。構(gòu)造形式結(jié)構(gòu)A1A2Ak B 的推理的書寫方法：前提： A1,A2,Ak 結(jié)論： B證明方法：直接證明法 附加前提法歸謬法（或稱反證法）12直接證明法實(shí)例例2 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：前提：pq, rq ,rs 結(jié)論：ps pq 前提引入 pq 置換 rq 前提引入 qr 置換 pr 假言三段論 rs 前提引入 ps 假言三段論 13 q qr r r(pq)例3 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明:(1) 前提: pq,qr,ps,s 結(jié)論: r(pq)qrr(pq)spqpspqrpq證明: ps s

7、 p pq 合取假言推理拒取式析取三段式前提引入前提引入 拒取式前提引入析取三段式前提引入假言推理合取14(2) 前提: pq, rq, rs 結(jié)論: ps證明: pq pq rq qr pr rs pspr假言三段論pqrqrspsrspqqr置換置換假言三段論前提引入置換前提引入置換 假言三段論前提引入假言三段論15直接證明法實(shí)例例4 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：前提：p（qr）, pq 結(jié)論： rs p（qr） 前提引入 pq 前提引入 p 化簡 q 化簡 qr 假言推理 r 假言推理 rs 附加 rs置換16證明: ps p s p(qr) 例5 在自然推理系統(tǒng)P中構(gòu)造下面推

8、理的證明: 若數(shù)a 是實(shí)數(shù), 則它不是有理數(shù)就是無理數(shù)。若a不能表示成分?jǐn)?shù), 則它不是有理數(shù)。a 是實(shí)數(shù)且它不能表示成分?jǐn)?shù), 所以a是無理數(shù)。解: 令 p: a是實(shí)數(shù); q: a是有理數(shù); r: a是無理數(shù); s: a能表示成分?jǐn)?shù).前提: p(qr), s q, p s 結(jié)論: r qr s q q rp(qr)s qp srqpsqr析取三段論假言推理p化簡假言推理前提引入化簡 化簡 前提引入假言推理前提引入假言推理析取三段論17直接證明法實(shí)例例6 構(gòu)造下面推理的證明： 若明天是星期一或星期三，我明天就有課. 若我明天有 課，今天必備課. 我今天沒備課. 所以，明天不是星期一、 也不是星期三

9、. 解 (1) 設(shè)命題并符號化 設(shè) p：明天是星期一，q：明天是星期三， r：我明天有課，s：我今天備課 前提：(pq)r, rs, s 結(jié)論：pq18直接證明法實(shí)例(2) 寫出證明的形式結(jié)構(gòu) 前提：(pq)r, rs, s 結(jié)論：pq(3) 證明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置換19附加前提證明法附加前提證明法 適用于結(jié)論為蘊(yùn)涵式欲證 前提：A1, A2, , Ak 結(jié)論：CB等價地證明 前提：A1, A2, , Ak, C 結(jié)論：B理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2Ak

10、C)B20附加前提證明法實(shí)例例6 構(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 21附加前提證明法實(shí)例 (3) 證明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段論 p 拒取式 pq 前提引入 q 析取三段論22 例7 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： 如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影

11、。小王去看電影。所以，當(dāng)小趙去看電影時，小李必定也去。解：令 p: 小張去看電影；q: 小王去看電影； r: 小李去看電影； s: 小趙去看電影。 前提：(pq) r, sp, q結(jié)論：sr證明：用附加前提法。 s sp p q pq (pq)r rr(pq) rspqspqp假言推理合取析取三段論附加前提引入前提引入 析取三段論前提引入 合取前提引入 假言推理附加前提證明法23 前提：(pq) r, sp, q 結(jié)論：sr證明： sp s p (pq)r pqr q pr s r s r(pq) rspq析取三段論直接證明法s pp rpqr置換置換假言三段論前提引入 置換前提引入置換前提引

12、入 析取三段論 假言三段論24歸謬法（反證法）歸謬法 (反證法)欲證 前提：A1, A2, , Ak 結(jié)論：B做法 在前提中加入B，推出矛盾.理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB025歸謬法實(shí)例例8 前提：(pq)r, rs, s, p 結(jié)論：q證明 用歸繆法 q 結(jié)論否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段論 pq 置換 p 析取三段論 p 前提引入 pp 合取26 如果小張守第一壘并且小李向B隊(duì)投球，則A 隊(duì)將取勝?；蛘逜隊(duì)未取勝，或者A隊(duì)成為聯(lián)賽第一名。A隊(duì)沒有成為聯(lián)賽第一名

13、。小張守第一壘。因此，小李沒向 B隊(duì)投球。例9在自然推理系統(tǒng)P 中構(gòu)造下面推理的證明：解：令 p: 小張守第一壘； q: 小李向B隊(duì)投球； r: A隊(duì)取勝； s: A隊(duì)成為聯(lián)賽第一名。前提：(pq) r, rs, s, p結(jié)論：q(pq) rrsspqr(pq)pqq證明：(1)用歸謬法（2）直接證明qq析取三段論拒取式析取三段論附加前提合取27證明：用歸謬法 q 結(jié)論否定引入 (pq) 拒取式 rs 前提 pq 置換 s 前提 p 前提 r 析取三段論 q 析取三段論 (pq) r 前提 qq 合取因 qq 0 ，故原推理正確。直接證明 rs 前提 (pq) 拒取式 s 前提 pq 置換 r

14、 析取三段論 p 前提 (pq) r 前提 q 析取三段論28第三章 習(xí)題課主要內(nèi)容推理的形式結(jié)構(gòu)判斷推理是否正確的方法 真值表法 等值演算法 主析取范式法推理定律自然推理系統(tǒng)P構(gòu)造推理證明的方法 直接證明法 附加前提證明法 歸謬法(反證法)29基本要求理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 結(jié)論：B熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）牢記 P 系統(tǒng)中各條推理規(guī)則熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬 法會解決實(shí)際中的簡單推理問題30練習(xí)1：判斷推理是否正確1. 判斷下面推理是否正確

15、: (1) 前提：pq, q 結(jié)論：p 解 推理的形式結(jié)構(gòu):(pq)qp 方法一：等值演算法 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq易知10是成假賦值，不是重言式，所以推理不正確.31練習(xí)1解答方法二：主析取范式法， (pq)qp (pq)q)p pq M2 m0m1m3未含m2, 不是重言式, 推理不正確.32練習(xí)1解答方法三 真值表法 不是重言式, 推理不正確111001110100(pq)qpqppq 0 1 1 1(pq)q 0 0 1 0方法四 直接觀察出10是成假賦值33練習(xí)1解答用等值演算法 (qr)(pr)(qp) (qr)(pr)(qp) (qr)(pr)(qp) (qp)(qr)(rp)(qp) (qp)(qr)(rp)(qp)1推理正確(2) 前提：qr, pr 結(jié)論：qp 解 推理的形式結(jié)構(gòu)：(qr)(pr)(qp) 34練習(xí)2：構(gòu)造證明2.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和 園游人太多，就不去頤和園. 今天是周六，并且頤和園游 人太多. 所以, 我們?nèi)A明園或