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

1、邏輯思考概論GE39033024: 1命題邏輯的自然演譯系統(tǒng)4.1自然演繹系統(tǒng)的特徵自然演繹系統(tǒng)(system of natural deduction)的產(chǎn)生是針對公理系統(tǒng) (axiomsystem)而來，公理系統(tǒng)中的證明比較難建立，而且比較冘長。公理系統(tǒng)除了為數(shù)很少的公理之外，它的推論規(guī)則也相當(dāng)少，在證明的建立上，困難相對增加。還有一個(gè)重要的難題，就是選擇什麼句式當(dāng)作公理，這個(gè)問題本身是一個(gè)爭論的議題。公理是自明的 (self-evident)，公理本身不需要任何證明。公理經(jīng)過語意學(xué)的解釋之後必然為真。自然演繹系統(tǒng)可以說是只由一組推論規(guī)則所構(gòu)成的演繹系統(tǒng)。這種演繹系統(tǒng)不需要預(yù)設(shè)任何公理，它

2、只在證明時(shí)假定一些句式為真，再利用推論規(guī)則去導(dǎo)出所要的句式。由假定 (assumption)而得到證明的這種概念，是自然演繹法的基本概念。例如先假定 ，再從這個(gè)假定推理出 。句式 的真假並不是自然演繹法的重點(diǎn)。它所注重的是， 的真是根據(jù) 的真，亦即 為真。在這個(gè)推論中，可以結(jié)論出 為真，而不論 為真或假。由於 的真不保證 的真，所以 不再是 的前提。在這個(gè)推論得出 時(shí)，就從 的前提中 去前提化 (discharged)。這個(gè)論證型同時(shí)也是一語句連詞的 引進(jìn)規(guī)則 (introduction rule)： (n):(n)因?yàn)?在第 n 個(gè)步驟的證明中會去前提化，所以用括號 括起來。應(yīng)用上述規(guī)則後被

3、去前提化的假設(shè)以自然數(shù) n 加以標(biāo)示，表示在第 n 個(gè)步驟時(shí)會應(yīng)用這個(gè)規(guī)則，同時(shí)將去前提化。在自然演繹系統(tǒng)中，又稱之為條件句的引進(jìn)規(guī)則 (簡稱 I)。除了引進(jìn)規(guī)則之外，還有所謂的語句連詞的 消去規(guī)則 (elimination rule)。例如條件句的消去規(guī)則：邏輯思考概論GE39033024: 2建立自然演繹系統(tǒng)的目標(biāo)是將這類的推理有系統(tǒng)的普遍化，也就是針對語句連詞找出成對的引進(jìn)規(guī)則與消去規(guī)則。在公理系統(tǒng)中，導(dǎo)出都是由公理開始的，經(jīng)由公理從推論規(guī)則導(dǎo)出的是定理，定理是由公理導(dǎo)出的句式，所以是公理系統(tǒng)中導(dǎo)出的基本概念。在自然演繹系統(tǒng)中 ，導(dǎo)出則是由假設(shè)開始的 。自然演繹系統(tǒng)是由假設(shè)開始 ，所以

4、才是基本的，定理 是特例。自然演繹系統(tǒng)不需要預(yù)設(shè)公理，所以不需要對公理加以證成。構(gòu)成自然演繹系統(tǒng)的一組規(guī)則是基於語句連詞的語意性質(zhì)而設(shè)立的。相對於公理系統(tǒng)，由這種規(guī)則所進(jìn)行的邏輯導(dǎo)出 (推理 )是直接且自然的。自然演繹系統(tǒng)中的推理也比較簡化而且容易建立。4.2自然演繹系統(tǒng)的推論規(guī)則自然演繹系統(tǒng)有許多不同的表達(dá)方式，常見的兩種是：(1)提出基本推論規(guī)則，以引進(jìn)規(guī)則與消去規(guī)則這兩類的推論規(guī)則為主，加上RAA( 歸謬法 ) 等規(guī)則。(2)將推論規(guī)則不分基本與衍生(derived)一併提出，取而代之的是語句涵蘊(yùn)規(guī)則與語句等值規(guī)則的區(qū)分。這裏將選擇第一種方式，另外會在附錄中依據(jù)第二種表達(dá)方式列出一些衍生

5、規(guī)則。自然演繹系統(tǒng)的原型自然演繹系統(tǒng)中的結(jié)構(gòu)規(guī)則與上一章所提出來的相同：(1)假設(shè)規(guī)則 (Ass.)弱化規(guī)則 (Thin)如果 ，則 , 捷徑規(guī)則 (Cut)如果 且 , ，則 , 我們先將自然演繹系統(tǒng)的一個(gè)原型(prototype)描述如下：( E)( I)Modus Ponendo Ponens(MP)Rule of conditional proof (CP) ,假定 ，則可以得到 邏輯思考概論GE39033024: 3(?I)Rule of ?-introduction , ?(?E)Rule of ?-elimination ?； ? (?I)Rule of ?-introducti

6、on ；? ?(?E)Rule of ?-elimination如果 , ，且, ，則 , ?這一組推論規(guī)則再加上前述的結(jié)構(gòu)規(guī)則就成為自然演繹系統(tǒng)的一個(gè)原型。( E)是上一節(jié)介紹的條件句的消去規(guī)則，( I)是條件句引進(jìn)規(guī)則。底下我們先定義什麼是論證的證明。定義(論證的證明 )論證的證明意謂著我們可以從一組前提的集合(可以是空集合 ) ，經(jīng)由形變規(guī)則(結(jié)構(gòu)規(guī)則與推論規(guī)則 )導(dǎo)出結(jié)論。我們還會使用邏輯歸結(jié) (logical consequence)的概念，其定義如下：定義(邏輯歸結(jié) )當(dāng)句串 ; 是一有效論證時(shí)，可以說是 的邏輯歸結(jié)。可以用一簡單的證明來例示條件句的消去規(guī)則( E)與並言的引進(jìn)規(guī)則

7、 (?I) ，論證 P, P QP?Q 的證明：1(1)P2 (2)P Q1,2(3)Q1,2(4)P ?QPP1,2,1,3, ?IE論證 P Q, QR PR的證明可以例示 ( I)規(guī)則：1(1)P QP2 (2)Q RP3(3)PA邏輯思考概論GE39033024: 41,3(4)Q1,3, E1,2,3(5)R2,4,E1,2(6)P R3,5,I第三步驟是依據(jù)假設(shè)規(guī)則(A)而假設(shè)的句式，可以當(dāng)作臨時(shí)前提，所以左側(cè)給予前提號 3。右側(cè)以 A 表示它是一假設(shè)。第六步驟是條件句引進(jìn)規(guī)則( I)的例示，要注意的是第三個(gè)前提P 要去前提化，所以第六步驟的前提只剩下1, 2 。以論證 P?Q,

8、QR? SS 來例示並言消去規(guī)則 (?E)：1(1)P ?Q2 (2)Q R?S1(3)Q1,2(4)R ?S1,2(5)SPP1, ?E2,3,4, ?EE(?I) 與(?E)分別是選言的引進(jìn)規(guī)則與消去規(guī)則。應(yīng)用(?I)規(guī)則，我們隨時(shí)可以從 P 導(dǎo)出 P?Q。這和 (?I) 規(guī)則不同，我們需要兩個(gè)命題 P 與 Q，才可以導(dǎo)出 P?Q?？梢杂谜撟C P, P?Q RR?S 來例示 (?I)：1(1)PP2(2)P ?QRP1(3)P ?Q1, ?I1,2(4)R2,3, E1,2(5)R ?S4, ?I例題4.1：證明PQ, Q?R SPS。(?E)的例子比較複雜，可以用論證P?Q, PR, Q

9、RR 例示：1(1)P ?Q2 (2)P R3 (3)Q RPPP邏輯思考概論GE39033024: 54(4)PA2,4(5)R2,4,E6(6)QA3,6(7)R3,6,E1,2,3(8)R1,4,5,6,7, ?E第四與第六步驟是 (?E)規(guī)則所需要用到的假設(shè)。第五步驟的句式是第二與第四步驟的邏輯歸結(jié)；第七步驟的句式是第三與第六步驟的邏輯歸結(jié)。在這個(gè)證明中， (?E)規(guī)則所要用到的步驟是1,4,5,6,7，前提中的 4,6 必須去前提化，所以結(jié)論的前提剩下 1,2,3 。否定號的一些規(guī)則應(yīng)用在否定號上的規(guī)則有許多不同主張，我們選擇的規(guī)則比較接近博斯塔克(David Bostock) 。一

10、共有五條： DNI 、DNE 、RAA 、TND 、EFQ 。(DNI )(DNE )(RAA )(TND )(EFQ ) ? ?如果 ?；則可以得到 ?如果 且 ? ；則可以得到 , ? (DNI )是雙否定的引進(jìn)規(guī)則， (DNE )是雙否定消去規(guī)則。我們會在RAA 規(guī)則的例示之後，再例示DNE 規(guī)則。(RAA )是所謂的歸謬法 (reductio ad absurdum)，以論證 P Q, ?Q ?P來例示：1(1) PQ2(2)? Q3(3)PPPA邏輯思考概論GE39033024: 61,3(4)Q1,3, E1,2,3(5)Q ?Q2,4, ?I1,2(6)? P3,5, RAA以句

11、式 P 這個(gè)假設(shè)導(dǎo)出矛盾句式Q?Q，然後將導(dǎo)出這個(gè)矛盾的假設(shè)加以否定而得到 ?P。一句式與自己的否定句式以並言連起來，是一矛盾句。根據(jù) (RAA ) 規(guī)則，如果一前提 (或假設(shè) )會導(dǎo)出矛盾，則可以導(dǎo)出該前提的否定。被否定的前提需要去前提化。接下來例示 DNE 規(guī)則，論證 ?Q, ?PQ P 的證明：1(1)? QP2(2) ?P QP3(3)? PA2,3(4)Q2,3, E1,2,3(5)Q ?Q1,4, ?I1,2(6)? ?P3,5, RAA1,2(7)P6, DNE當(dāng)我們使用 RAA 規(guī)則，以前提 3 的否定為新的結(jié)論時(shí) ，得到的是 ?P，而不是 P。因?yàn)榍疤? 的否定是在 ?P 前

12、再加上一個(gè)否定號，這才稱為前提3 的否定，而不是拿掉否定號。(TND )(tertium non datur)意謂著排中律的邏輯歸結(jié)必然為真。排中律 ?表示一句式為真時(shí)，它的否定為假；這一句式為假時(shí)，它的否定為真。一句式與它的否定之間沒有第三種可能。 ?是邏輯真理，是恆真句，恆真句的邏輯歸結(jié)也一定是恆真句。也就是說，如果 ?，則 。1 我們可以用 (TND )來證明下面這個(gè)論證PQ, ?P Q Q1 David Bostock,Intermediate Logic(Oxford: Oxford University Press, 1997), p.212.我們可以說如果 是排中律 ?的邏輯歸結(jié)

13、的話，則是個(gè)定理 ()。邏輯思考概論GE39033024: 71(1) PQP2 (2)?P QP3(3)PA1,3(4) Q1,3,E5(5)? PA2,5 (6)Q2,5,E1,2(7)Q3,4,5,6, TND這個(gè)證明中的 (3)與(5)是兩個(gè)臨時(shí)前提，使用 (TND )規(guī)則時(shí)，要將這兩個(gè)前提去前提化。這表示 (TND )所導(dǎo)出句式的真不是由臨時(shí)前提的真所保證的。(EFQ )(ex falso quodlibet)意謂不一致的前提可以導(dǎo)出任何句式。論證 P?Q, ?P Q 是一選言三段論 (disjunctive syllogism)，它的證明可以用來例示 (EFQ )規(guī)則：1(1)P

14、?Q2(2)? P3(3)P2,3(4)Q5(5)Q1,2(6)QPPA2,3, EFQA1,3,4,5, ?E例題 4.2：證明 ?PQ ?(?P? ?Q)(建議：可以用 RAA) 。雙條件句的規(guī)則有些自然演繹系統(tǒng)不把雙條件句當(dāng)作基本語句連詞，只用雙條件句的定義來處理它。這裏將雙條件句當(dāng)作基本語句連詞，有一對規(guī)則：(?E)如果 ?，則 ()?()(?I)如果 ()?()，則 ?邏輯思考概論GE39033024: 8雷蒙 (E. J. Lemmon)把雙條件句用定義加以處理： ?若且唯若 ()?()。雙條件句規(guī)則的例示論證：P?Q , Q P。1(1) P?Q2(2)Q1(3)( PQ)?(Q

15、P)1(4) QP1,2(5)PPP1, ?E3, ?E2,4, E推論規(guī)則的總結(jié)除了雙條件句的引進(jìn)規(guī)則(?I) 與消去規(guī)則 (?E) 之外，將上述的規(guī)則做一個(gè)表：(?I) (?E ) ?(?E ) ? ?lr(n) (n)(?I l)(?Ir)(?E) ? (n) ? ? (n)( I)(n)( E)(DNI )(DNE )?邏輯思考概論GE39033024: 9(n) ?(RAA )(n)? (n)?(n)(TND )(n)(EFQ)?4.3證明的例子論證 P?Q, ?Q?R P R，可以用 I加以證明，並且會用到結(jié)構(gòu)規(guī)則中的弱化 (Thin) 規(guī)則：1(1)P ?QP2(2)? Q?RP

16、3(3)PA1,3(4)P ?(P?Q)1,3, ?I1,3(5)P4, ?E2(6)R2, ?E1,2,3(7)P ?R5,6, ?I1,2,3(8)R7, ?E1,2(9)P R3,8, I第 4、5 步驟是弱化規(guī)則的應(yīng)用，這是為了將前提1 變成句式 P 的前提。第7、8 步驟也是弱化規(guī)則的應(yīng)用，這是為了將前提1, 3 變成句式 R 的前提。當(dāng)有效論證的前提的集合是空集合，而僅僅只有結(jié)論句式時(shí)，具備這 種邏 輯型 的句 串，稱 為 定 理 (theorem) 。它 是不 依靠 任何 前提 就 能夠被導(dǎo)出的句式。例如句串P(PQ)Q)1(1)PA邏輯思考概論GE39033024: 102(2

17、)P QA1,2(3)Q1,2,E1(4)(P Q) Q2,3,I (5)P (P Q)Q)1,4,I接下來的例子會用到RAA 規(guī)則，但情況比較複雜 。證明句串：P Q ?Q?P，會先假設(shè) I規(guī)則所需要的前提 ?Q，由這個(gè)假設(shè)，我們希望導(dǎo)出 ?P。為了導(dǎo)出 ?P，需要使用 RAA 規(guī)則。1(1) P QP2(2)? QA3(3)PA1,3(4)Q1,3, E1,2,3(5)Q ?Q2,4, ?I1,2(6)? P3,5, RAA1(7)? Q?P2,6, I例題4.3：證明P R, ?Q P P?Q(建議：可以用TND規(guī)則，且需要用到弱化規(guī)則 )。例題 4.4：證明 P?Q (P R)R?S)

18、。例題 4.5：證明 P?Q ?(PQ)Exercises for4命題邏輯的自然演譯系統(tǒng)證明底下的論證：(1) P?Q (?Q (PR)(建議：可以用 EFQ 導(dǎo)出 PR)(2)P?Q, QRPR(建議：需要用到弱化規(guī)則 )(3)P?Q ?(P?Q)(建議：可以用 RAA)邏輯思考概論GE39033024: 11附錄 1自然演繹中衍生的推論規(guī)則衍生的推論規(guī)則可以用基本推論規(guī)則加以證明，所以它們不是必要的?？梢酝耆粧裼茫部梢話裼靡徊糠?。但是基本推論規(guī)則的要求就不是那麼寬鬆，它們必須能證明所有形式有效的論證，也就是它們所構(gòu)成的演繹系統(tǒng)必須是完備的。下列衍生的推論規(guī)則將分成語句涵蘊(yùn)規(guī)則與語句等

19、值規(guī)則。一語句涵蘊(yùn)規(guī)則Modus Tollens (MTT)( 否定後件因而否定前件 ) , ? ? ? , ? Disjunctive Syllogism (DS)(選言三段論 )? , ? ? , ? ? ? , ? ,Hypothetical Syllogism (HS)(假言三段論 ) ,一般常見的 MP 規(guī)則，就是前面的 E規(guī)則。二語句等值規(guī)則在介紹語句等值規(guī)則之前，先引進(jìn)一個(gè)導(dǎo)出記號的反向符號，這個(gè)符號只用來與正向符號並列為 ，形成的新符號意謂可以從左句式導(dǎo)出右句式，同時(shí)也可以從右句式導(dǎo)出左句式。當(dāng)左右句式有上述關(guān)係時(shí)，我們稱它們語句等值的(sentential equivalen

20、t)。這表示它們在任何解釋下，真假值相等。語句等值的關(guān)係也可以用雙條件句表示。DeMorgan s Law(DeM)( 狄摩根律 )邏輯思考概論GE39033024: 12?( ? ) ? ?( ? ) ? ?Commutation (Com)(交換律 ) ? ? ? ?Association (Assoc)(結(jié)合律 )?( ? ) )?( ?( ? ) )?( ?( ? ) ) ?( ?)?( ? ) (?)?( ?)Idempotent Law (Idem)(冪等律 ) ? ?Contraposition (Contra)(異質(zhì)位換律 ) ? ?Exportation (Exp)(移出律 )() ?Conditional-Disjunction (CD)( 條件句與選言之等值律 )? ?Biconditional- Conditional (BC)( 雙條件句與條件句之等值律) ? ( ()?)Biconditional-Disjunction (BD)( 雙條件句與選言之等值律)? ( )?(? ?)邏輯思考概論GE39033024: 13附錄 2：邏輯思考概論一百零四學(xué)年第二學(xué)期期中考模擬試題1依照下述有效論證的邏輯型，給出一個(gè)前提皆真的健全論證：(邏輯型不可改變