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

1、 第四章 命題邏輯的自然演繹系統(tǒng)2022年2月15日星期二2自然演繹系統(tǒng)自然演繹系統(tǒng)NP命題邏輯的自然演繹系統(tǒng)NP是由形式語言形式語言L L 和一組推導(dǎo)（變形）規(guī)則構(gòu)成的。其中形式語言L L 包括初始符號(hào)、形成規(guī)則和定義。 構(gòu)建命題邏輯的形式系統(tǒng)，可以采用公理化方法，構(gòu)建命題邏輯的形式系統(tǒng)，可以采用公理化方法，也可采用自然演繹的方法。為接近人們?nèi)粘Ｋ季S的實(shí)也可采用自然演繹的方法。為接近人們?nèi)粘Ｋ季S的實(shí)踐，采用自然演繹的方法來構(gòu)建命題邏輯的一個(gè)形式踐，采用自然演繹的方法來構(gòu)建命題邏輯的一個(gè)形式系統(tǒng)系統(tǒng)NPNP。2022年2月15日星期二3初始符號(hào)初始符號(hào)(1)甲類符號(hào)：p1, p2, p3, ；

2、(2)乙類符號(hào)：，；(3)丙類符號(hào)：(，)。這些符號(hào)構(gòu)成的有窮長的序列叫做符號(hào)串，例如:p, pq，pq, pq；(pq)r，p(qr)，；(pqpq)，(pqr)， 按照形成規(guī)則形成的符號(hào)串稱為合式公式。2022年2月15日星期二4形成規(guī)則形成規(guī)則(1)任何單個(gè)的命題變元p是合式公式；(2)如果A是合式公式，則(A)是合式公式；(3)如果A和B是合式公式，則(AB)、(AB)、(AB)是合式公式；只有（1）-到（3）形成的符號(hào)串是合式公式。2022年2月15日星期二5定義定義定義是用來表示縮寫的，定義兩邊的符號(hào)串可以相定義是用來表示縮寫的，定義兩邊的符號(hào)串可以相互代替?；ゴ妗Ｈ纾?AB)=

3、df(AB)(BA)。形式語言L L 的全體合式公式記為Form(L L )。形式語言L L 是我們研究對象，叫對象語言。討論對象語言的語言叫元語言或語法語言。2022年2月15日星期二6形成規(guī)則的作用形成規(guī)則的作用（1）以遞歸的方式定義合式公式。（2）提供一種能行、可判定的方法判定任一符號(hào)串是不是合式公式。（3）檢驗(yàn)合式公式的性質(zhì)。如:(pq)(p)q)的形成過程是：p，q，(pq)，(p)，(pq)(p)，q ，(pq)(p)q)。這個(gè)字符串是反復(fù)運(yùn)用形成規(guī)則而形成的，因此它是合式公式。2022年2月15日星期二7合式公式的子公式合式公式的子公式合式公式的子公式：合式公式的子公式：在生成合

4、式公式的過程中，每一步所生成的公式都是這一生成的合式公式的子公式。如： 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é)詞：轄域最大的聯(lián)結(jié)詞。(pq)(p)q)的主聯(lián)結(jié)詞是。省略括號(hào)的約定：省略括號(hào)的約定：(1)公式最外層的括號(hào)可以省略。(2)聯(lián)結(jié)詞的結(jié)合力依下列次序遞減：，。如：(pq)(p)q)可簡記為(pq)pq。2022年2月15日星期二8推演規(guī)則（1）整推規(guī)則整推規(guī)則（2）置換規(guī)則置換規(guī)則（3）條件證明規(guī)則

5、條件證明規(guī)則（4）間接證明規(guī)則間接證明規(guī)則2022年2月15日星期二9整推規(guī)則1.合取引入規(guī)則(記為+)： 從A和B推出AB；2.合取消去規(guī)則(記為_): 從AB推出A；從AB推出B；3.析取引入規(guī)則(記為+)： 從A推出AB；從B推出AB；4.析取消去規(guī)則(記為_): 從AB和A推出B；從AB和B推出A；5.肯定前件（記為MP) 從AB和A推出B;6.否定后件規(guī)則（記為MT); 從AB和B推出A;2022年2月15日星期二10條件證明規(guī)則條件證明規(guī)則5.蘊(yùn)涵引入規(guī)則(記為+)： 條件證明 如果從公式集和A推出B，則從推出AB；2022年2月15日星期二11例例1： R（HT） RH TS H

6、 HS R（HT） 前提前提 RH 前提前提 TS 前提前提 H 前提前提 R 否后否后 HT 肯前肯前 HS 假言三段論假言三段論2022年2月15日星期二12例例2：BA B（CD） AC D BA BA 前提前提 B（CD） 前提前提 AC 前提前提 B 化簡化簡 CD 化簡化簡 A 肯前肯前 C 否析否析 D 肯前肯前2022年2月15日星期二13例例3：FG（H（IK） HI HMF IK FG（H（IK） 前提前提 HI 前提前提 HMF 前提前提 H 化簡化簡 HM 附加附加 F 肯前肯前 FG 附加附加 H（IK） 肯前肯前 IK 肯前肯前2022年2月15日星期二14練習(xí)：1

7、. M（NL） JK M M（NJ） LK 2022年2月15日星期二15 M（NL） 前提前提 JK 前提前提 M 前提前提 M（NJ） 前提前提 NL 肯前肯前 NJ 否析否析 LK 二難推理二難推理2022年2月15日星期二162. P（RQ） PQ SRQ S R 2022年2月15日星期二17 P（RQ） 前提前提 PQ 前提前提 SRQ 前提前提 S 前提前提 SR 附加附加 Q 肯前肯前 P 否后否后 RQ 肯前肯前 R 否后否后2022年2月15日星期二183. PQ（RS） P （RS）（TU） U T 2022年2月15日星期二19 PQ（RS） 前提前提 P 前提前提 （

8、RS）（TU） 前提前提 U 前提前提 PQ 附加附加 （RS） 肯前肯前 TU 否析否析 T 否后否后2022年2月15日星期二20條件證明規(guī)則條件證明規(guī)則 步步 驟：驟： 1 1.引入假設(shè)引入假設(shè) 2.2.撤銷假設(shè)撤銷假設(shè) （適用于蘊(yùn)含式）（適用于蘊(yùn)含式）2022年2月15日星期二21蘊(yùn)涵引入規(guī)則(記為+) 又稱條件證明規(guī)則或演繹定理?xiàng)l件證明規(guī)則或演繹定理，是把從推出AB的推理轉(zhuǎn)化為從和臨時(shí)的假設(shè)A推出B的推理。即：（AB）（AB） 本規(guī)則實(shí)質(zhì)就是條件輸入（輸出）規(guī)則的運(yùn)用本規(guī)則實(shí)質(zhì)就是條件輸入（輸出）規(guī)則的運(yùn)用 最適于證明最適于證明結(jié)論為蘊(yùn)涵式結(jié)論為蘊(yùn)涵式的推論。的推論。 前提集前提集結(jié)

9、論結(jié)論假設(shè)前提假設(shè)前提2022年2月15日星期二22蘊(yùn)涵引入規(guī)則(記為+)例1：FG HF GH FG 前提前提 HF 前提前提 G 條件假設(shè)條件假設(shè) G 雙重否定雙重否定 F 否析律否析律 F 雙重否定雙重否定 H 否后律否后律 H 雙重否定雙重否定 GH 條件證明條件證明2022年2月15日星期二23蘊(yùn)涵引入規(guī)則(記為+)例2：AB CB(DE) A(DE) AB 前提 CB(DE) 前提 A 條件假設(shè) B 肯前律 CB 附加 DE 肯前律 A(DE) 條件證明2022年2月15日星期二24間接證明規(guī)則間接證明規(guī)則 否定消去規(guī)則(記為_)： 間接證明 如果從和A推出BB，則從推出A。 步驟

10、： 1.否定結(jié)論 2.提出矛盾 3.肯定結(jié)論2022年2月15日星期二25否定消去規(guī)則(記為_) 又稱間接證明或反證法間接證明或反證法，是把由推出A的推理轉(zhuǎn)化為由和臨時(shí)的假設(shè)A推出BB的推理。 最適于證明最適于證明結(jié)論不是蘊(yùn)涵式結(jié)論不是蘊(yùn)涵式的推論。的推論。2022年2月15日星期二26否定消去規(guī)則(記為_)例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)，(6)，+(8) A (3)(7)，間接證明2022年2月15日星期二27否定消去規(guī)則(記為_)例2

11、：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) 2022年2月15日星期二28蘊(yùn)涵引入（條件證明）規(guī)則與 否定消去（間接證明）規(guī)則在做題過程中二者可以交替使用，既可以先用蘊(yùn)涵引入（條件證明）規(guī)則再用否定消去（間接證明）規(guī)則，也可以先用否定消去（間接證明）規(guī)則再用蘊(yùn)涵引入（條件證明）規(guī)則。2022年2

12、月15日星期二29練習(xí)1 1、XYZ ZX XY 2022年2月15日星期二30 XYZ 前提前提 ZX 前提前提 X 條件假設(shè)條件假設(shè) YZ 肯前律肯前律 X 雙重否定雙重否定 Z 否后率否后率 Y 否析律否析律 XY 條件證明條件證明2022年2月15日星期二31練習(xí)：2. E(JK) J(KE) E2022年2月15日星期二32 E(JK) 前提前提 J(KE) 前提前提 E 間接假設(shè)間接假設(shè) JK 否析律否析律 J 化簡化簡 KE 肯前律肯前律 E 化簡化簡 EE 合取合取 E 間接證明間接證明2022年2月15日星期二33作業(yè)：1. XY XZ ZW YW 2. EFG EH IK

13、FJI K 2022年2月15日星期二343. FG HF GH4. E(JK) J(KE) E2022年2月15日星期二35置換規(guī)則的涵義置換規(guī)則的涵義 對于任何命題P，無論它是以整個(gè)命題出現(xiàn)，還是作為一個(gè)命題的一部分出現(xiàn)，都可用與它重言等值的命題Q來替換。2022年2月15日星期二36置換規(guī)則置換規(guī)則T18(a) (AB)A B(記為DeM.)T18(b) (AB)A B(記為DeM.)2022年2月15日星期二37德摩根律的證明德摩根律的證明T18(a) (AB) A B的證明的證明先證(AB) AB:(1) (AB) A (2) (AB) H1 (3) A H2 (4) AB (3)，

14、+ (5)(AB)(AB) (2),(4),+ (6) A (3)(5),_(消去H2) (7) B H3 (8)AB (7)，+ (9)(AB)(AB) (2)，(8)，+ (10) B (7)(9)，_(消去H3) (11)AB (6)，(10), + (12)(AB)(AB) (1)，(11), +(13) AB (2)(12)，_(消去H1)2022年2月15日星期二38德摩根律的證明德摩根律的證明T18(a) (AB) A B的證明的證明再證AB (AB)：(1) AB A (2) (AB) H (3) AB (2)，_ (4) A (3)，_ (5) B (3)，_ (6) A (

15、4)，+(7) B (1),(6),_ (8)BB (5),(7),+(9)(AB) (2)(8),_(消去H)2022年2月15日星期二39置換規(guī)則置換規(guī)則交換律T21(a) ABBAT21(b) ABBA結(jié)合律T22(a) A(BC)(AB)CT22(b) A(BC)(AB)C2022年2月15日星期二40置換規(guī)則分配律T23(a) A(BC)(AB)(AC)T23(b) A(BC)(AB)(AC)蘊(yùn)析律（A A B) (AB)德德 摩摩 根根 律律(AB) (A B)(AB) (AB) 2022年2月15日星期二41置換規(guī)則的證明置換規(guī)則的證明T21(b) ABBA的證明的證明先證AB

16、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)，(7)，D.C.同理，可證BAAB。2022年2月15日星期二42NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(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(

17、c) AC，BD，ABCDT28(d) AC，BD，CDAB2022年2月15日星期二43NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(guān)系T29(a) ABCACB(反三段論)T29(b) ABCBCAT30 ABC A(BC)(條件輸出)T31 A(BC) ABC(條件輸入)T32 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 2022年2月15日星期二44NP系統(tǒng)中的語法系統(tǒng)中的語法

18、(語形語形)推出關(guān)系推出關(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)2022年2月15日星期二45NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(guān)系應(yīng)用實(shí)例應(yīng)用實(shí)例(一一)如果不換8號(hào)上場（p）或者12號(hào)上場(q)，甲隊(duì)的形勢不會(huì)好轉(zhuǎn)(r)。教練沒有換8號(hào)上場，也沒有換12號(hào)上場。所以，甲隊(duì)的形勢不會(huì)好轉(zhuǎn)。首先，將前提和結(jié)論形式化： A1：

19、(pq)r A2：pq B：r(1) (pq)r A1(2) pq A2(3) (pq) (2)，DeM.(4) r (1)，(3)，_2022年2月15日星期二46NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(guān)系應(yīng)用實(shí)例應(yīng)用實(shí)例(二二)如果線段L有存在無窮多個(gè)點(diǎn)，那么，如果這些點(diǎn)有長度，則線段L將無窮長，而且，如果這些點(diǎn)都沒有長度,則線段L也不會(huì)有長度。但是，一條線段既不會(huì)無窮長,也不會(huì)沒有長度。所以L上不會(huì)有無窮多個(gè)點(diǎn)。前題和結(jié)論符號(hào)化：A1：p(qr)(qs)A2：rsB：p2022年2月15日星期二47( (1) p(qr)(qs) A1(2) rs A2 (3) p H (4

20、) 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)2022年2月15日星期二48NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(guān)系應(yīng)用實(shí)例應(yīng)用實(shí)例(三三)如果貨幣供應(yīng)量保持現(xiàn)狀，而貨幣需求量增加，則銀行利率就會(huì)上升。如果貨幣需求量增加導(dǎo)致銀行利率上升，則在銀行存款更被看好。主管部門已宣布貨幣供應(yīng)總是保持不變。因此，在銀行存款更被看好。A1：pqrA2：(qr)sA3： pB： s2022年2月15日星期二49NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(guān)系應(yīng)用實(shí)例應(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)，_2022年2月15日星期二50NP系統(tǒng)中的語法系統(tǒng)中的語法(語形語形)推出關(guān)系推出關(guān)系應(yīng)用實(shí)例應(yīng)用實(shí)例(三三)方法二：（1） pqr A1（2）（qr）s A2（3） p A3(4)s H(5)（