命題邏輯自然演繹系統(tǒng)課件

1、 第四章 命題邏輯的自然演繹系統(tǒng)自然演繹系統(tǒng)NP命題邏輯的自然演繹系統(tǒng)NP是由形式語(yǔ)言L 和一組推導(dǎo)（變形）規(guī)則構(gòu)成的。其中形式語(yǔ)言L 包括初始符號(hào)、形成規(guī)則和定義。 構(gòu)建命題邏輯的形式系統(tǒng)，可以采用公理化方法，也可采用自然演繹的方法。為接近人們?nèi)粘Ｋ季S的實(shí)踐，采用自然演繹的方法來(lái)構(gòu)建命題邏輯的一個(gè)形式系統(tǒng)NP。7/16/20222初始符號(hào)(1)甲類(lèi)符號(hào)：p1, p2, p3, ；(2)乙類(lèi)符號(hào)：，；(3)丙類(lèi)符號(hào)：(，)。這些符號(hào)構(gòu)成的有窮長(zhǎng)的序列叫做符號(hào)串，例如:p, pq，pq, pq；(pq)r，p(qr)，；(pqpq)，(pqr)， 按照形成規(guī)則形成的符號(hào)串稱(chēng)為合式公式。7/16/

2、20223形成規(guī)則(1)任何單個(gè)的命題變?cè)猵是合式公式；(2)如果A是合式公式，則(A)是合式公式；(3)如果A和B是合式公式，則(AB)、(AB)、(AB)是合式公式；只有（1）-到（3）形成的符號(hào)串是合式公式。7/16/20224定義定義是用來(lái)表示縮寫(xiě)的，定義兩邊的符號(hào)串可以相互代替。如：(AB)=df(AB)(BA)。形式語(yǔ)言L 的全體合式公式記為Form(L )。形式語(yǔ)言L 是我們研究對(duì)象，叫對(duì)象語(yǔ)言。討論對(duì)象語(yǔ)言的語(yǔ)言叫元語(yǔ)言或語(yǔ)法語(yǔ)言。7/16/20225形成規(guī)則的作用（1）以遞歸的方式定義合式公式。（2）提供一種能行、可判定的方法判定任一符號(hào)串是不是合式公式。（3）檢驗(yàn)合式公式的

3、性質(zhì)。如:(pq)(p)q)的形成過(guò)程是：p，q，(pq)，(p)，(pq)(p)，q ，(pq)(p)q)。這個(gè)字符串是反復(fù)運(yùn)用形成規(guī)則而形成的，因此它是合式公式。7/16/20226合式公式的子公式合式公式的子公式：在生成合式公式的過(guò)程中，每一步所生成的公式都是這一生成的合式公式的子公式。如： A的子公式是A和A； AB 的子公式是A、B和AB； AB 的子公式是A、B和AB； AB 的子公式是A、B和AB。如：p，q，（pq），(p)，(pq)(p)，(pq)(p)q)都是(pq)(p)q)的子公式。主聯(lián)結(jié)詞：轄域最大的聯(lián)結(jié)詞。(pq)(p)q)的主聯(lián)結(jié)詞是。省略括號(hào)的約定：(1)公式最

4、外層的括號(hào)可以省略。(2)聯(lián)結(jié)詞的結(jié)合力依下列次序遞減：，。如：(pq)(p)q)可簡(jiǎn)記為(pq)pq。7/16/20227推演規(guī)則（1）整推規(guī)則（2）置換規(guī)則（3）條件證明規(guī)則（4）間接證明規(guī)則7/16/20228整推規(guī)則1.合取引入規(guī)則(記為+)： 從A和B推出AB；2.合取消去規(guī)則(記為_(kāi)): 從AB推出A；從AB推出B；3.析取引入規(guī)則(記為+)： 從A推出AB；從B推出AB；4.析取消去規(guī)則(記為_(kāi)): 從AB和A推出B；從AB和B推出A；5.肯定前件（記為MP) 從AB和A推出B;6.否定后件規(guī)則（記為MT); 從AB和B推出A;7/16/20229條件證明規(guī)則5.蘊(yùn)涵引入規(guī)則(記

5、為+)： 條件證明 如果從公式集和A推出B，則從推出AB；7/16/202210例1： R（HT） RH TS H HS R（HT） 前提 RH 前提 TS 前提 H 前提 R 否后 HT 肯前 HS 假言三段論7/16/202211例2：BA B（CD） AC D BA BA 前提 B（CD） 前提 AC 前提 B 化簡(jiǎn) CD 化簡(jiǎn) A 肯前 C 否析 D 肯前7/16/202212例3：FG（H（IK） HI HMF IK FG（H（IK） 前提 HI 前提 HMF 前提 H 化簡(jiǎn) HM 附加 F 肯前 FG 附加 H（IK） 肯前 IK 肯前7/16/202213練習(xí)：1. M（NL）

6、JK M M（NJ） LK 7/16/202214 M（NL） 前提 JK 前提 M 前提 M（NJ） 前提 NL 肯前 NJ 否析 LK 二難推理7/16/2022152. P（RQ） PQ SRQ S R 7/16/202216 P（RQ） 前提 PQ 前提 SRQ 前提 S 前提 SR 附加 Q 肯前 P 否后 RQ 肯前 R 否后7/16/2022173. PQ（RS） P （RS）（TU） U T 7/16/202218 PQ（RS） 前提 P 前提 （RS）（TU） 前提 U 前提 PQ 附加 （RS） 肯前 TU 否析 T 否后7/16/202219條件證明規(guī)則 步 驟： 1.引

7、入假設(shè) 2.撤銷(xiāo)假設(shè) （適用于蘊(yùn)含式）7/16/202220蘊(yùn)涵引入規(guī)則(記為+) 又稱(chēng)條件證明規(guī)則或演繹定理，是把從推出AB的推理轉(zhuǎn)化為從和臨時(shí)的假設(shè)A推出B的推理。即：（AB）（AB） 本規(guī)則實(shí)質(zhì)就是條件輸入（輸出）規(guī)則的運(yùn)用 最適于證明結(jié)論為蘊(yùn)涵式的推論。 前提集結(jié)論假設(shè)前提7/16/202221蘊(yùn)涵引入規(guī)則(記為+)例1：FG HF GH FG 前提 HF 前提 G 條件假設(shè) G 雙重否定 F 否析律 F 雙重否定 H 否后律 H 雙重否定 GH 條件證明7/16/202222蘊(yùn)涵引入規(guī)則(記為+)例2：AB CB(DE) A(DE) AB 前提 CB(DE) 前提 A 條件假設(shè) B

8、肯前律 CB 附加 DE 肯前律 A(DE) 條件證明7/16/202223間接證明規(guī)則 否定消去規(guī)則(記為_(kāi))： 間接證明 如果從和A推出BB，則從推出A。 步驟： 1.否定結(jié)論 2.提出矛盾 3.肯定結(jié)論7/16/202224否定消去規(guī)則(記為_(kāi)) 又稱(chēng)間接證明或反證法，是把由推出A的推理轉(zhuǎn)化為由和臨時(shí)的假設(shè)A推出BB的推理。 最適于證明結(jié)論不是蘊(yùn)涵式的推論。7/16/202225否定消去規(guī)則(記為_(kāi))例1：AB AB A(1) AB 前提(2) AB 前提 (3) A 間接假設(shè) (4) A (3)，_ (5) B (1)，(4)，_ (6) B (2)，(4)，_ (7) BB (5)，

9、(6)，+(8) A (3)(7)，間接證明7/16/202226否定消去規(guī)則(記為_(kāi))例2：A(BC)(CD)，CD / A(1) A(BC) (CD) A1(2)CD A2(3) C (2)_ (4) D (2)_ (5) A H1 (6) A (5)_ (7) (BC)(CD) (1)，(6)_ (8) CD (7)_ (9) D (3)，(8)_ (10) DD (4)，(9)+(11)A (5)(10)- (消去H1) 7/16/202227蘊(yùn)涵引入（條件證明）規(guī)則與 否定消去（間接證明）規(guī)則在做題過(guò)程中二者可以交替使用，既可以先用蘊(yùn)涵引入（條件證明）規(guī)則再用否定消去（間接證明）規(guī)則

10、，也可以先用否定消去（間接證明）規(guī)則再用蘊(yùn)涵引入（條件證明）規(guī)則。7/16/202228練習(xí)1、XYZ ZX XY 7/16/202229 XYZ 前提 ZX 前提 X 條件假設(shè) YZ 肯前律 X 雙重否定 Z 否后率 Y 否析律 XY 條件證明7/16/202230練習(xí)：2. E(JK) J(KE) E7/16/202231 E(JK) 前提 J(KE) 前提 E 間接假設(shè) JK 否析律 J 化簡(jiǎn) KE 肯前律 E 化簡(jiǎn) EE 合取 E 間接證明7/16/202232作業(yè)：1. XY XZ ZW YW 2. EFG EH IK FJI K 7/16/2022333. FG HF GH4. E

11、(JK) J(KE) E7/16/202234置換規(guī)則的涵義 對(duì)于任何命題P，無(wú)論它是以整個(gè)命題出現(xiàn)，還是作為一個(gè)命題的一部分出現(xiàn)，都可用與它重言等值的命題Q來(lái)替換。7/16/202235置換規(guī)則T18(a) (AB)A B(記為DeM.)T18(b) (AB)A B(記為DeM.)7/16/202236德摩根律的證明T18(a) (AB) A B的證明先證(AB) AB:(1) (AB) A (2) (AB) H1 (3) A H2 (4) AB (3)，+ (5)(AB)(AB) (2),(4),+ (6) A (3)(5),_(消去H2) (7) B H3 (8)AB (7)，+ (9)

12、(AB)(AB) (2)，(8)，+ (10) B (7)(9)，_(消去H3) (11)AB (6)，(10), + (12)(AB)(AB) (1)，(11), +(13) AB (2)(12)，_(消去H1)7/16/202237德摩根律的證明T18(a) (AB) A B的證明再證AB (AB)：(1) AB A (2) (AB) H (3) AB (2)，_ (4) A (3)，_ (5) B (3)，_ (6) A (4)，+(7) B (1),(6),_ (8)BB (5),(7),+(9)(AB) (2)(8),_(消去H)7/16/202238置換規(guī)則交換律T21(a) AB

13、BAT21(b) ABBA結(jié)合律T22(a) A(BC)(AB)CT22(b) A(BC)(AB)C7/16/202239置換規(guī)則分配律T23(a) A(BC)(AB)(AC)T23(b) A(BC)(AB)(AC)蘊(yùn)析律（A B) (AB)德 摩 根 律(AB) (A B)(AB) (AB) 7/16/202240置換規(guī)則的證明T21(b) ABBA的證明先證AB BA(1) AB A (2) A H1 (3) BA (2)，+ (4) ABA (2)(3)，+（消去H1） (5) B H2 (6) BA (5)，+(7) BBA (5)(6)，+（消去H2）(8) BA (1)，(4)，(

14、7)，D.C.同理，可證BAAB。7/16/202241NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系T24(a) (B)AB T24(b) AB(AB) T25(a) ABAB (蘊(yùn)析律)T25(b) ABAT26(a) (AB)AT26(b) A(A)T27(a) A(A)T27(b) A(A)T28(b) AB,AC,BCA(二難推理)T28(c) AC，BD，ABCDT28(d) AC，BD，CDAB7/16/202242NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系T29(a) ABCACB(反三段論)T29(b) ABCBCAT30 ABC A(BC)(條件輸出)T31 A(BC) ABC(條件輸入)T32

15、A(BC)B(AC)(條件互易)T33 A(BC)(AB)(AC)（蘊(yùn)涵分配） T34 A(AB)AB (條件融合)T35(a) AB ACBC (前件附加)T35(b) AB ACBCT35(c) AB (CA)(CB)T36 （AB）C BC 7/16/202243NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系T37 AB，BA AB (+)T38(a) AB AB (_)T38(b) AB BAT39 AC,BC ABC (前件合取) T40 AB,AC ABC (后件合取) T41 ABC(AC)(BC)T42 ABC(AC)(BC)T43 ABC(AB)(AC)T44 ABC(AB)(AC)7/1

16、6/202244NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系應(yīng)用實(shí)例(一)如果不換8號(hào)上場(chǎng)（p）或者12號(hào)上場(chǎng)(q)，甲隊(duì)的形勢(shì)不會(huì)好轉(zhuǎn)(r)。教練沒(méi)有換8號(hào)上場(chǎng)，也沒(méi)有換12號(hào)上場(chǎng)。所以，甲隊(duì)的形勢(shì)不會(huì)好轉(zhuǎn)。首先，將前提和結(jié)論形式化： A1：(pq)r A2：pq B：r(1) (pq)r A1(2) pq A2(3) (pq) (2)，DeM.(4) r (1)，(3)，_7/16/202245NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系應(yīng)用實(shí)例(二)如果線段L有存在無(wú)窮多個(gè)點(diǎn)，那么，如果這些點(diǎn)有長(zhǎng)度，則線段L將無(wú)窮長(zhǎng)，而且，如果這些點(diǎn)都沒(méi)有長(zhǎng)度,則線段L也不會(huì)有長(zhǎng)度。但是，一條線段既不會(huì)無(wú)窮長(zhǎng),也不會(huì)沒(méi)有長(zhǎng)度。

17、所以L上不會(huì)有無(wú)窮多個(gè)點(diǎn)。前題和結(jié)論符號(hào)化：A1：p(qr)(qs)A2：rsB：p7/16/202246(1) p(qr)(qs) A1(2) rs A2 (3) p H (4) p (3), _ (5) (qr)(qs) (1)，(4)，_ (6) qr (5),_ (7) qs (5),_ (8) r (2),_ (9) s (2),_ (10) q (6),(8), M.T. (11) q (7),(9), M.T. (12) qq (10),(11),+(13) p (3)(12)，_,(消去H)7/16/202247NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系應(yīng)用實(shí)例(三)如果貨幣供應(yīng)量保持現(xiàn)

18、狀，而貨幣需求量增加，則銀行利率就會(huì)上升。如果貨幣需求量增加導(dǎo)致銀行利率上升，則在銀行存款更被看好。主管部門(mén)已宣布貨幣供應(yīng)總是保持不變。因此，在銀行存款更被看好。A1：pqrA2：(qr)sA3： pB： s7/16/202248NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系應(yīng)用實(shí)例(三)方法一：（1） pqr A1（2）（qr）s A2（3） p A3 (4) q H1 (5) pq (3)，(4)，+ (6) r (1)，(5)，_(7)qr (4)(6)，+(消去H1)(8)s (2)，(7)，_7/16/202249NP系統(tǒng)中的語(yǔ)法(語(yǔ)形)推出關(guān)系應(yīng)用實(shí)例(三)方法二：（1） pqr A1（2）（qr）s A2（3）