第三章 命題邏輯的推理理論

1、2021-7-161主要內(nèi)容主要內(nèi)容推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)l 推理的正確與錯(cuò)誤推理的正確與錯(cuò)誤l 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)l 判斷推理正確的方法判斷推理正確的方法l 推理定律推理定律自然推理系統(tǒng)自然推理系統(tǒng)Pl 形式系統(tǒng)的定義與分類形式系統(tǒng)的定義與分類l 自然推理系統(tǒng)自然推理系統(tǒng)Pl 在在P中構(gòu)造證明中構(gòu)造證明:直接證明法、附加前提證明法、歸謬法直接證明法、附加前提證明法、歸謬法第三章第三章 命題邏輯的推理理論命題邏輯的推理理論2021-7-1623.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)定義定義3.1 設(shè)設(shè)A1, A2, , Ak, B為命題公式為命題公式. 若對(duì)于每組賦值，若對(duì)于每組賦

2、值，A1 A2 Ak 為假，或當(dāng)為假，或當(dāng)A1 A2 Ak為真時(shí)，為真時(shí)，B也為真，也為真，則稱由則稱由前提前提A1, A2, , Ak推出推出結(jié)論結(jié)論B的的推理推理是是有效的有效的或或正確正確的的, 并稱并稱B是是有效結(jié)論有效結(jié)論.定理定理3.1 由命題公式由命題公式A1, A2, , Ak 推推B的推理正確當(dāng)且僅當(dāng)?shù)耐评碚_當(dāng)且僅當(dāng)A1 A2 AkB為重言式為重言式注意注意: 推理正確不能保證結(jié)論一定正確推理正確不能保證結(jié)論一定正確數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法研究推理數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法研究推理.所謂所謂推理推理是指從是指從前提出發(fā)推出結(jié)論的思維過(guò)程前提出發(fā)推出結(jié)論的思維過(guò)

3、程,而而前提前提是已知的命題公式集合是已知的命題公式集合,結(jié)結(jié)論論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式.2021-7-163推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)2. A1 A2 AkB 若推理正確若推理正確, 記為記為A1 A2 Ak B (即即 表示蘊(yùn)涵式為重言式表示蘊(yùn)涵式為重言式)3. 前提：前提： A1, A2, , Ak 結(jié)論：結(jié)論： B判斷推理是否正確的方法判斷推理是否正確的方法: 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)1. A1, A2, , Ak B 若推理正確若推理正確, 記為記為A1,A2,

4、An B2021-7-164推理實(shí)例推理實(shí)例例例1 判斷下面推理是否正確判斷下面推理是否正確(1) 若今天是若今天是1號(hào)，則明天是號(hào)，則明天是5號(hào)號(hào). 今天是今天是1號(hào)號(hào). 所以所以, 明天是明天是5號(hào)號(hào). (2) 若今天是若今天是1號(hào)，則明天是號(hào)，則明天是5號(hào)號(hào). 明天是明天是5號(hào)號(hào). 所以所以, 今天是今天是1號(hào)號(hào). 解解 設(shè)設(shè) p：今天是：今天是1號(hào)，號(hào)，q：明天是：明天是5號(hào)號(hào). (1) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): (pq) pq用等值演算法用等值演算法 (pq) pq ( p q) p) q ( p q) q pq q 1 由定理由定理3.1可知推理正確可知推理正確2021-7-

5、165推理實(shí)例推理實(shí)例(2) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu):(pq) qp 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p ( p q) q) p (分配律) (p q) q ) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 結(jié)果不含結(jié)果不含m1, 故故01是成假賦值，所以推理不正確是成假賦值，所以推理不正確(吸收律)另解另解: (pq) qp ( p q) qp qp (吸收律吸收律) q p p q M1 m0 m2 m32021-7-166推理定律推理定律重言蘊(yùn)涵式重言蘊(yùn)涵式1. A (A B) 附加律附加律 2. (

6、A B) A 化簡(jiǎn)律化簡(jiǎn)律3. (AB) A B 假言推理假言推理4. (AB)B A 拒取式拒取式 5. (A B)B A 析取三段論析取三段論6. (AB) (BC) (AC) 假言三段論假言三段論7. (AB) (BC) (AC) 等價(jià)三段論等價(jià)三段論8. (AB) (CD) (A C) (B D) 構(gòu)造性二難構(gòu)造性二難 (AB) ( AB) B 構(gòu)造性二難構(gòu)造性二難(特殊形式特殊形式)9. (AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難每個(gè)等值式可產(chǎn)生兩個(gè)推理定律每個(gè)等值式可產(chǎn)生兩個(gè)推理定律如如, 由由AA可產(chǎn)生可產(chǎn)生 AA 和和 AA2021-7-1673.2 自然

7、推理系統(tǒng)自然推理系統(tǒng)P定義定義3.2 一個(gè)一個(gè)形式系統(tǒng)形式系統(tǒng) I 由下面四個(gè)部分組成：由下面四個(gè)部分組成： (1) 非空的字母表，記作非空的字母表，記作 A(I). (2) A(I) 中符號(hào)構(gòu)造的合式公式集，記作中符號(hào)構(gòu)造的合式公式集，記作 E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作中一些特殊的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作推理規(guī)則集，記作 R(I). 記記I=, 其中其中是是 I 的的形式語(yǔ)言系統(tǒng)形式語(yǔ)言系統(tǒng), 是是 I 的的形式演算系統(tǒng)形式演算系統(tǒng).自然推理系統(tǒng)自然推理系統(tǒng): 無(wú)公理無(wú)公理, 即即AX(I)=公理推理系統(tǒng)公理推理系統(tǒng)

8、推出的結(jié)論是系統(tǒng)中的重言式推出的結(jié)論是系統(tǒng)中的重言式, 稱作稱作定理定理2021-7-168自然推理系統(tǒng)自然推理系統(tǒng)P定義定義3.3 自然推理系統(tǒng)自然推理系統(tǒng) P 定義定義如下如下:1. 字母表字母表 (1) 命題變項(xiàng)符號(hào)：命題變項(xiàng)符號(hào)：p, q, r, , pi, qi, ri, (2) 聯(lián)結(jié)詞符號(hào)：聯(lián)結(jié)詞符號(hào)： , , , , (3) 括號(hào)與逗號(hào)：括號(hào)與逗號(hào)：(, ), ，2. 合式公式（同定義合式公式（同定義1.6）3. 推理規(guī)則推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則 (2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則 (3) 置換規(guī)則置換規(guī)則2021-7-169推理規(guī)則推理規(guī)則(4) 假言推理規(guī)則假

9、言推理規(guī)則 (6) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(guī)則 (8) 假言三段論規(guī)則假言三段論規(guī)則 AB AB AA B A B A(5) 附加規(guī)則附加規(guī)則 (7) 拒取式規(guī)則拒取式規(guī)則 (9) 析取三段論規(guī)則析取三段論規(guī)則 AB B A AB BCACA B BA2021-7-1610推理規(guī)則推理規(guī)則(10) 構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則 (11) 破壞性二難推理規(guī)則破壞性二難推理規(guī)則 (12) 合取引入規(guī)則合取引入規(guī)則 AB CD A C B D AB CD BD A C A BA B2021-7-1611在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造證明中構(gòu)造證明設(shè)前提設(shè)前提A1, A2, Ak,結(jié)論結(jié)論B及公式

10、序列及公式序列C1, C2, Cl. 如果每如果每一個(gè)一個(gè)Ci(1 i l)是某個(gè)是某個(gè)Aj, 或者可由序列中前面的公式應(yīng)用推理或者可由序列中前面的公式應(yīng)用推理規(guī)則得到規(guī)則得到, 并且并且Cl =B, 則稱這個(gè)公式序列是由則稱這個(gè)公式序列是由A1, A2, Ak推推出出B的的證明證明例例2 構(gòu)造下面推理的證明：構(gòu)造下面推理的證明： 若明天是星期一或星期三，我明天就有課若明天是星期一或星期三，我明天就有課. 若我明天有若我明天有 課，今天必備課課，今天必備課. 我今天沒(méi)備課我今天沒(méi)備課. 所以，明天不是星期一、所以，明天不是星期一、 也不是星期三也不是星期三. 解解 (1) 設(shè)命題并符號(hào)化設(shè)命題

11、并符號(hào)化 設(shè)設(shè) p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三， r：我明天有課，：我明天有課，s：我今天備課：我今天備課2021-7-1612直接證明法直接證明法(2) 寫出證明的形式結(jié)構(gòu)寫出證明的形式結(jié)構(gòu) 前提：前提：(p q)r, rs, s 結(jié)論：結(jié)論： pq(3) 證明證明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換P49 例例3.42021-7-1613附加前提證明法附加前提證明法附加前提證明法附加前提證明法 適用于結(jié)論為蘊(yùn)涵式適用于結(jié)論為蘊(yùn)涵式欲證欲證 前提：前提：A

12、1, A2, , Ak 結(jié)論：結(jié)論：CB等價(jià)地證明等價(jià)地證明 前提：前提：A1, A2, , Ak, C 結(jié)論：結(jié)論：B理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B2021-7-1614附加前提證明法實(shí)例附加前提證明法實(shí)例例例3 構(gòu)造下面推理的證明構(gòu)造下面推理的證明 2是素?cái)?shù)或合數(shù)是素?cái)?shù)或合數(shù). 若若2是素?cái)?shù)，則是素?cái)?shù)，則 是無(wú)理數(shù)是無(wú)理數(shù). 若若 是無(wú)理是無(wú)理數(shù)，則數(shù)，則4不是素?cái)?shù)不是素?cái)?shù). 所以，如果所以，如果4是素?cái)?shù)，則是素?cái)?shù)，則2是合數(shù)是合數(shù). 解解 用附加前提證明法構(gòu)造證明用附加前提證明法

13、構(gòu)造證明 (1) 設(shè)設(shè) p：2是素?cái)?shù)，是素?cái)?shù)，q：2是合數(shù)，是合數(shù)， r： 是無(wú)理數(shù)，是無(wú)理數(shù)，s：4是素?cái)?shù)是素?cái)?shù) (2) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 前提：前提：p q, pr, rs 結(jié)論：結(jié)論：sq 2222021-7-1615附加前提證明法實(shí)例附加前提證明法實(shí)例 (3) 證明證明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段論假言三段論 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論2021-7-1616歸謬法（反證法）歸謬法（反證法）歸謬法歸謬法 (反證法反證法)欲證欲證 前提：前提：A1, A2, , Ak 結(jié)

14、論：結(jié)論：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB) (A1 A2 AkB) 0 A1 A2 AkB02021-7-1617歸謬法實(shí)例歸謬法實(shí)例例例4 前提：前提： (p q) r, rs, s, p 結(jié)論：結(jié)論： q證明證明 用歸繆法用歸繆法 q 結(jié)論否定引入結(jié)論否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q) r 前提引入前提引入 (p q) 析取三段論析取三段論 pq 置換置換 p 析取三段論析取三段論 p 前提引入前提引入 p p 合取合取2021-7-

15、1618第三章第三章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)l 判斷推理是否正確的方法判斷推理是否正確的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系統(tǒng)自然推理系統(tǒng)Pl 構(gòu)造推理證明的方法構(gòu)造推理證明的方法 直接證明法直接證明法 附加前提證明法附加前提證明法 歸謬法歸謬法(反證法反證法)2021-7-1619基本要求基本要求l 理解并記住推理形式結(jié)構(gòu)的兩種形式：理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：Bl 熟練掌握判斷推理是否正確的不

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

17、算法 ( pq)qp (p q)q)p ( pq) qp ( p q) ( q q)p p q易知易知10是成假賦值，不是重言式，所以推理不正確是成假賦值，不是重言式，所以推理不正確.2021-7-1621練習(xí)練習(xí)1解答解答方法二：主析取范式法，方法二：主析取范式法， ( pq)qp (p q)q)p (pq)p (分配律分配律) p qp p q M2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正確推理不正確.2021-7-1622練習(xí)練習(xí)1解答解答方法三方法三 真值表法真值表法 不是重言式不是重言式, 推理不正確推理不正確111001110100( pq)qpqp pq

18、 0 1 1 1( pq)q 0 0 1 0方法四方法四 直接觀察出直接觀察出10是成假賦值是成假賦值2021-7-1623練習(xí)練習(xí)1解答解答用等值演算法用等值演算法 (qr) (pr)(qp) ( q r) ( pr)( qp) (qr) (p r)( qp) (q p) (q r) ( r p)( qp) (q p) (q r) ( r p) ( qp)1推理正確推理正確(2) 前提：前提：qr, pr 結(jié)論：結(jié)論：qp 解解 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： (qr) (pr)(qp) 2021-7-1624練習(xí)練習(xí)2：構(gòu)造證明：構(gòu)造證明2. 在系統(tǒng)在系統(tǒng)P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和如果頤和 園游人太多，就不去頤和園園游人太多，就不去頤和園. 今天是周六，并且頤和園游今天是周六，并且頤和園游 人