Unit 7 公理法與自然演繹法 授課教師：傅皓政 老師

Presentation on theme: "Unit 7 公理法與自然演繹法 授課教師：傅皓政 老師"— Presentation transcript:

1 Unit 7 公理法與自然演繹法 授課教師：傅皓政 老師
【本著作除另有註明外，採取創用CC「姓名標示－非商業性－相同方式分享」台灣3.0版授權釋出】

2 Unit 7 公理法與自然演繹法 截至目前為止，我們已經學習過如何以 真值樹法演算。
接下來要介紹的是兩個常被提到的演算 方法：公理法與自然演繹法。 m :15:04 接下來我們要談到的是公理法與自然演繹法。 這個有一點點小麻煩，為什麼？ 因為用這些方法解題需要有一點天賦，如果這個天賦你有的話，是讓我們非常羨慕和忌妒的。 到目前為止我們知道怎麼使用真值表法和真值樹系統解題。接下來我們要來介紹公理法。

3 Unit 7 公理法與自然演繹法 公理法的結構： (1)公理(axioms)：在任何系統中皆真的 句式。
(2)推論規則(rule of inference)：在推論 過程中能夠保存真值(truth-preserving) 的規則。 m :16:21 公理法的結構需要兩個裝備，第一個是公理(axioms)，什麼是axiom呢？ 在歐幾里得的幾何原本裡面，你會發現他通常會用什麼字眼？ 他在翻譯上是有點爭議的，有些書會直接翻譯成axiom，比較新的版本大部分都會翻譯成postulate。 一開始我們所訂axiom的想法是，他在所有的系統裡面都是真的，這個我們稱為axiom。 Postulate通常是用來指涉個別理論的預設。 當代邏輯的出現大約在19世紀末，由於非歐幾何的出現，使得當時的數學基礎搖搖欲墜，為了替數學找到更穩固的基礎，數學家們把目光投向邏輯。 當代邏輯的創建要歸功於非常令我們敬佩的數學家Frege，他是德國耶拿大學的教授。 因為當時數學上的危機，他開始去思考如何替數學找到一個基礎，因此他找到了邏輯，我們現在所學的邏輯系統，幾乎可以說是Frege一手建立起來的。 公理法的結構兩個，一個是公理，一個是所謂的推論規則。 當時的推論規則思考是這樣，在這個推論過程當中必須遵守真值保存(truth-preserving)的原則。

4 Unit 7 公理法與自然演繹法 公理： 推論規則： (A1)   (  )
(MP) 從  和(    )成立，可以推論出  成立。 m :20:38 接下來我們來看看公理。 公理是這樣，各位現在看到的公理已經是很簡單的，在Frege那個時代沒有這麼簡單。我們的想法是這樣，如果可以被導出來的我們就拿掉，那些不能被導出來的我們才拿來當公理用。簡單來講，不管是預設也好、公理也好，數量當然越少越好，只要可以導出來就好嘛。 比如說，上課我講三個例子你們就懂，那還需要講到五個例子嗎？ 不需要嘛，只要懂就可以了。 第二個問題有點邏輯上小麻煩，這個公理不是三個，而是無限多個， 無限的意思是說，我們這個、、其實是語句的變量，或是句式的變量，也就是你可以帶任何的語句進去，所以雖然只有三個公理形式，但是公理的數量其實是無限多個。 從推論規則來看，也就是我們從如果和→都成立的情況下，你可以推出是成立的。 不過，因為作為推論規則的工具太少，讓我們感覺有些施展不開，無法為所欲為，現在我來讓各位看看什麼叫做無法為所欲為。

5 Unit 7 公理法與自然演繹法 公理法的推論： 所有公理的取代句式均為真。 以(A1)   (  ))為例
P  ( Q  P ) (M  N)  ( K  (M  N)) ((S  T)  W)  ( ((B  C)  D)  ((S  T)  W) ) m :23:30 首先，公理法的推論是這樣。 第一個，所有公理的取代句是都為真，就是我剛剛講的跟，你只要都帶一樣的句子，都帶一樣的句子，都帶一樣的句子，只要遵守這樣的原則就可以了。 比如說像這樣。 紅色就是表示的替代語句，藍色則代表的替代語句。

6 Unit 7 公理法與自然演繹法 公理法的推論： 經由公理及推論規則得到的結論均為定 理(theorem)。 實例： (a) ⊢ P  P
(b) ⊢ P  (P  Q) m :24:26 第二個，經由公理即推論規則得到的結論都是定理(theorem)。 接著，我們要來證明以下的語句是定理 P→P。 ¬P→(P→Q)。

7 Unit 7 公理法與自然演繹法 (a) ⊢ P  P
1. (p ((pp) p))  (( p ( p  p))  ( p  p)) (A2) (   (    ))  ((    )  (    )) 2. p  ((pp)  p) (A1)   (    ) 3. (p (p  p)) ( p  p) ,2 (MP) : p ((p  p) p) : (p (p  p)) ( p  p) 4. p  (p  p) (A1)   (   ) 5. p  p ,4 (MP) m :24:43 這個怎麼證明？有沒有人可以根據剛剛的公理系統，很快地就知道怎麼做？他的證明是這樣。 第一步，有誰知道第一步要寫這個，知道才怪。 第二步，這個是A2底下有對照，我有幫各位做對照。 那這個是A1。那A1，就是P，就是P→P。這個是為了導出後面這個做準備，那為什麼想要導出後面這個？因為我想要導出這個。 接下來這個是1,2MP把它做出來，前面這個看起來就比較容易了，看起來像A1的情況。 這個是A1的情況對吧？為什麼？因為就是P，也是P。所以我們就可以證出P→P。請問這位柯同學你覺得困難在哪裡？ 柯同學：「第一個假設就設不出來了。」 你的困難跟我是一樣的。你怎麼知道那是第一個？那是需要有點天分的，當然你也可以經由你的經驗來補強，也就是多練習題目，這個公理法真的是相當不容易，所以你叫老師當場解題目，老師當下也不一定解得出來。

8 Unit 7 公理法與自然演繹法 (b) ⊢ P  (P  Q) 1. (QP)(PQ) (A3)
2. ((QP)(PQ))(P ((QP)(PQ))) (A1) 3. P ((QP)(PQ)) ,2 (MP) 4. (P ((QP)(PQ)))  ((P (QP))  (P (PQ))) (A2) 5. (P (QP))  (P (PQ)) ,4 (MP) 6. P (QP) (A1) 7. P (PQ) ,6 (MP) m :31:40 再讓各位看一下，這個怎麼證明？乍看之下有沒有很像A1？實際上是完全不一樣的。他其實要用到A3。然後再用A1，這個是最難的一步。為什麼要這個東西呢？因為我們只有一個規則叫做MP，所以你會發現無論你怎麼設計，他都有一個關鍵點是conditional的符號，這樣我們就可以經由MP來得到後面這個。其實我們的目的在最後面這個，這個是需要設計的，利用這個A2我們可以得到，可以得到後面這個condition，到這裡就很簡單了，這樣就看出這個是A1嘛，這個是A1你就可以推出我們所要的結論。各位有沒有看懂這樣的證明過程？ 我只需要各位看懂他是這樣的式子就可以了。

9 Unit 7 公理法與自然演繹法 經過證明得到的定理，例如 PP等， 就可以在推論過程作為前提使用。 實例：
(c) ⊢ (P(PQ))(PQ)

10 Unit 7 公理法與自然演繹法 (c) ⊢ (P(PQ))(PQ)
(1) (P(PQ))  ((PP)  (PQ)) (A2) (2) ((P(PQ))  ((PP)  (PQ)))  (((P(PQ))  (PP))  ((P(PQ))  (PQ))) (A2) (3) ((P(PQ))  (PP))  ((P(PQ))  (PQ)) 1,2 (MP) (4) (PP)  ((P(PQ))  (PP)) (A1) (5) (PP) (Pr) (6) (P(PQ))  (PP) ,5 (MP) (7) (P(PQ))  (PQ) ,6 (MP)

11 Unit 7 公理法與自然演繹法 從公理法的觀點定義論證的有效性：
某個論證是有效的，若且唯若，可以用 公理及推論規則，從前提推論得到結論。 (p.s. 如果前提是空集合，得到的結論就 是上述所說的定理。)

12 Unit 7 公理法與自然演繹法 實例： (d) P , Q(PR) ⊢ QR (e) P , PQ , QR ⊢ SR

13 Unit 7 公理法與自然演繹法 (d) P , Q(PR) ⊢ QR 1. P (Pr) 2. Q(PR) (Pr)
3. P(QP) (A1) 4. QP ,3 (MP) 5. (Q(PR)) ((QP) (QR)) (A2) 6. (QP) (QR) ,5 (MP) 7. (QR) ,6 (MP)

14 Unit 7 公理法與自然演繹法 (e) P , PQ , QR ⊢ SR 1. P (Pr) 2. PQ (Pr)
3. QR (Pr) 4. Q ,2 (MP) 5. R ,4 (MP) 6. R(SR) (A1) 7. SR ,6 (MP)

15 Unit 7 公理法與自然演繹法 自然演繹法：僅由適當的推論規則形成 的演算系統。 兩種常見的自然演繹法系統：
(1)引進規則(Introduction Rules)與消除 規則(Elimination Rules) (2)等值規則(Equivalence Rules)與蘊涵 規則(Implication Rules) m :00:00 今天我們要來談自然演繹法，包括兩種基本常見的自然演繹法，第一種是引進規則，第二種是消除規則。自然演繹法的構想大概是這樣，如果我們要從前提證出結論，我的想法是這樣，我們能不能夠把他從語法裡面拆解，利用拆解與組合的方式，從前提得到我要的東西。 第二類我通常把它稱為線性的推論，基本上他運用的是等值規則與蘊涵規則，這兩個方法基本上只是演算上不一樣，但基本構想上是一樣的。

16 Unit 7 公理法與自然演繹法 (1)引進規則與消除規則： (i) 連言符號的規則： m-1121 00:03:23
首先我們來看第一類，他的規則是這樣： 我們從連言符號開始，上面這個我們稱之為Introduction rule，如果我們在推論的過程當中，從某些前提一直推…一路可以推到φ，那他也可以一路推到ψ，那麼這個前提就可以推出φ、ψ，我們可以把兩邊做一個conjunction。 你們要運用你們的想像力就是，φ上面可能是有一堆推論，ψ上面可能也是有一堆推論。接下來這個是消除規則，把conjunction符號去掉，拆解的時候如果遇到φ、ψ，可以把這個去掉變成φ，或者是我直接拆掉變成ψ。

17 Unit 7 公理法與自然演繹法 (1)引進規則與消除規則： (ii) 條件句符號的規則： m-1121 00:04:43
接下來我們來看條件符號，條件符號就是說，什麼時候我們要引進conditional，當我們假設這個φ，一路可以讓我們得到ψ，我們假設φ可以得到ψ，這時候我們就可以得到φ→ψ。 再來是他的消除規則，他就是φ跟φ→ψ可以得到ψ，這個其實就是我們在公理法系統理面講到的MP規則是一樣的。

18 Unit 7 公理法與自然演繹法 (1)引進規則與消除規則： (iii) 等值符號的規則： m-1121 00:05:55
接下來是等值符號的規則，我們要想像前面可能有一堆推論， 推論最後得到φ→ψ這個結果，另外一邊一直推論得到ψ→φ的結果，然後把兩個合起來就會得到equivalence或是雙向的關係。 再來這個等值符號規則更簡單，既然是雙向的，它可以是φ→ψ，也可以是ψ→φ。

19 Unit 7 公理法與自然演繹法 (1)引進規則與消除規則： (iv) 否定號的規則： m-1121 00:06:43
接下來否定號稍微複雜一點，我們要如何把negation放進來？ 同學：用conjunction。用conjunction，所以是φ∧¬φ嗎？我們現在就是不能用到其他符號。現在negation要放進來的話，意思就是大概是什麼不成立？什麼時候我們會覺得¬φ成立？大概就是φ不成立對吧。 所以他的rule是這樣，假設φ一路走到矛盾，那這個¬φ就成立了。 特別介紹這個符號⊥，T跌倒了，T倒立了，所以⊥就是假嘛，所以我們把它稱為Falsity，所以這個符號就是矛盾的意思。 你要如何把negation去掉呢？如果這個推論推到他，這個推論推到¬φ， 那φ跟¬φ不就成立了嗎？那這時候這個negation就去掉了。那你要得到negation，你要把introduction rule放進來，就是你假設φ一路走到falsity，那麼這個¬φ就成立。 另外一個RAA規則，假設¬φ一路推到falsity，表示¬φ不成立，意思就是φ成立，我們這個規則只適用於古典邏輯系統。 如果你以後看到的規則不是這樣，那他可能是其他系統，比如說他是個多值的邏輯系統。在古典邏輯系統裡面強調的是，¬φ不成立，φ就成立，可是在多值邏輯系統裡面就不一定，它可以是很多值的。

20 Unit 7 公理法與自然演繹法 (1)引進規則與消除規則： (v) 選言符號的規則： m-1121 00:11:47
接下來選言符號，如果φ可以推出φ∨ψ，或者ψ可以推出φ∨ψ，這些各位都可以接受。 比較麻煩的是消除規則，這裡如果有φ∨ψ，我把這個φ拿過來可以導出χ，ψ拿出來也可以導出χ，那我們就可以說χ是成立的，所以∨就可以去掉，他畫錯了，這應該是∨的elimination。

21 Unit 7 公理法與自然演繹法 實例練習： (f) ⊢(QR)((PQ)(PR)) (g) P(QR) ⊢ (PQ)R
(h) AB, BC ⊢ AC (i) MN ⊢ NM (j) ⊢ PP m :12:35 接下來我們來做一些實例的練習， 我現在想要證他是一個定理，這裡有一個main connective是一個條件句，如果他是條件句的話，你就把前面這個當成是我們假設的φ，然後設法導出後面的ψ，根據introduction rule你就可以得到φ→ψ。 後面括號main connective也是條件句，所以其實我用這個也可以導出這個。 然後在裡面也是一個conditional，所以我可以假設P來導出Q，我的想法大概是這樣。 這個也一樣，這個是一個conditional，我可以假設這個，然後把前提放進來想辦法導出這個R。 那c呢，他是bi conditional，你看到這個是A↔C，那我就是要證明A→C，另外一邊要證明C→A，然後把它合起來。那d顯然就是假設¬N。 最不容易思考的大概是最後一題，根據我們∨的introduction rule，我只要證明P或是¬P就解決了，困難的地方在於它沒有前提，所以最後一題的策略，先假設他是否定，然後一路導出矛盾，就表示這個否定是矛盾的，所以他原來就是成立的，利用剛剛RAA的想法。

22 Unit 7 公理法與自然演繹法 (f) ⊢(QR)((PQ)(PR)) m-1121 00:16:35
所以我們先來看(a)，因為要讓各位看得更清楚的關係，我沒有把它劃掉，我來帶著各位劃掉。我要證明這個，所以我把前面這個當假設，後面這個是main connective，又是conditional，所以我把P→Q也當假設，更有趣的是，裡面這個也是conditional，所以我也把P當假設。 所以我就可以得到這樣一個過程，我先假設P，然後P→Q當假設，我可以得到Q，然後我可以從這個Q跟Q→R，可以得到這個R，我們就可以得到後面這個P→Q。 各位從假設P可以一路推到R，當你這邊寫P→R的時候，這邊就要把它劃掉，我這裡寫1，這裡寫1表示說，在這個假設裡面我把1去掉了。 接下來我們剛剛是不是也假設2？在這裡我把2拉下來，用introduction rule，就會變成P→Q可以一路做到P→R。 第3個我們也假設Q→R，我們一路拉下來也可以得到(Q→R)→((P→Q)→(P→R))。 那我們怎麼知道我們要拉1拉2還是3？ 各位要記得這叫作目標導向，你要拉哪一個是根據你要得到什麼結果來決定的，不是任意決定的。 也就是我先利用拆解的方式把它拆解，最後再把他組合回去，這就是我要的答案。

23 Unit 7 公理法與自然演繹法 (g) P(QR) ⊢ (PQ)R m-1121 00:20:36 比如像範例(b)，
這個做法是這樣，這個既然是conditional，前面這些都可以當前提用， 我們的目標是要導出R，那這個顯然可以得到P、Q，如果有P，我們就可以用剛剛的elimination rule得到Q→R，然後Q又進來了，我們再一次根據elimination rule，就可以得到R，這樣就達到我們的目的了。 所以我們先從P∧Q放進來先得到P，然後這個前提放進來之後，你會從P跟P→(Q→R)得到Q→R，這是他的elimination rule，然後你這邊又可以得到Q，Q放下來利用elimination rule你可以得到R，這樣就表示說你假設這個P∧Q，可以藉由這個前提的幫忙得到R，所以你最後就是(P∧Q)→R。 自然演繹法跟公理法的重大特徵在於，在解題過程當中，你需要一些策略應用，因為它們都沒有固定的程序或是方法，讓你決定某個論證到底是個有效論證或是無效論證。

24 Unit 7 公理法與自然演繹法 (h) AB, BC ⊢ AC m-1121 00:22:47 比如像這個怎麼辦？
這個證明當然就是要從A導到C，另外一邊是from C to A。 最後把兩邊combine起來就是這樣，假設A，一路證到C，我就可以證明出A→C。 另一邊是什麼？我假設C，一路證到A，那我就可以證明出C→A。 再把這兩邊利用equivalence的introduction rule結合起來，就是我們要的結果。

25 Unit 7 公理法與自然演繹法 (i) MN ⊢ NM m-1121 00:24:16
接下來這個更簡單，這個證明其實就是，我們利用前面這個MN設法得到NM，這個意思相當於是問要如何利用MN和N得到¬M呢？ 考慮一下，如果¬N放進來要得到falsity，就是要找到N，要找出N就要假設M，所以意思就是如果假設M會得到矛盾，那麼它的反面就會成立，根據剛剛的introduction rule。 如果從¬N一路可以推到¬M，那麼就可以得到¬N→¬M。所以這題的證明方式是假設M，利用elimination rule得到N，然後跟¬N放在一起，然後把假設的¬N放進來得到falsity，所以就表示假設M會得到矛盾，得到矛盾後，我們就可以利用的introduction rule得到¬M，最後，把預設前提¬N放進來，就可以得到¬N→¬M的結論。 比較難的策略大概是第5個實例。

26 Unit 7 公理法與自然演繹法 (j) ⊢ PP m-1121 00:26:14 這個例子稍微難一點點，因為他沒有前提。
各位要知道老師提供的不一定是唯一的解法，一定還有其他的方法。 我們既然沒有前提，代表所有都要靠假設，我們假設3要得到矛盾， 因此我們先假設¬P，下來是利用∨的introduction rule，然後可以跟這個結論的¬得到這個falsity，得到falsity之後，這個1就會變成P，然後再利用P得到falsity，同樣的道理會得到¬P，這兩個又是一個falsity，所以最後你會得到3他其實是一個會導致矛盾的。 策略大概是這樣，我只能從¬想辦法去找到他的矛盾出現。

27 Unit 7 公理法與自然演繹法 (2) 等值規則與蘊涵規則 (i) 等值規則
笛摩根定律 (DeM): (p  q)  (p  q) (p  q)  (p  q) 交換律 (Comm): (p  q)  (q  p) (p  q)  (q  p) 結合律 (Assoc): (p  (q  r))  ((p  q)  r) (p  (q  r))  ((p  q)  r) 分配律 (Dist): (p  (q  r))  ((p  q)  (p  r)) (p  (q  r))  ((p  q)  (p  r)) 雙重否定律 (DN): p  p m :29:27 接下來我們來看另外一個規則。 首先第一個是DeM rule，如果他是M的negation，小心這個negation在外面，(p  q)會等值於(p  q)，你把他放進去會是(¬p∨¬q)。一樣的，這是(p∨q)會等值於(¬p∧¬q)。 再來是交換律也很容易，就是(p∨q)跟(q∨p)是一樣的，或是(p∧q)跟(q∧p)是一樣的。 再來是結合律，如果兩個都是∨，他先括前面或是括後面都沒關係。 再來是分配律，這個大概是沒有什麼問題。 再來是Double negation，這個對各位來說是更簡單，就不用多說了。

28 Unit 7 公理法與自然演繹法 (2) 等值規則與蘊涵規則 (i) 等值規則
 異質位換律 (Contra): (p  q)  (q  p)  蘊涵律 (Impl): (p  q)  (p  q)  等值律 (Equiv): (p  q)  ((p  q)  (q  p)) (p  q)  ((p  q)  (p  q))  移出律 (Exp): ((p  q)  r)  (p  (q  r))  重言律 (Taut): p  p  p p  p  p m :31:50 這個稍微困難一點點，不過也可以接受，因為我們在學期初就講過了，(p→q)會等值於(¬q→¬p)。 再來是蘊涵律，這個我們在前面等值有證過，所以這個(p→q)可以等值於(¬p∨q)。 再來是等值律，這個我們也說過，(p↔q)可以變成((p→q) ∧(q→p))， 或者是(p↔q)可以變成((p∧q)(¬p∧¬q))。 再來是移出律，這個可能難一點，基本意思是說，((p∧q)→r)可以變成(p→(q→r))。 再來是恆真律，這個太簡單了，就是p可以變成(p∨p)，或是p可以變成(p∧p)。就是不管講幾次都是一樣的意思。請問這位林同學妳同意嗎？林同學：可是時間不一樣啊。說得太好了，我喜歡這個答案， 他是跟時間相關的，因為所謂愛這件事是可以跟著時間有所不同的， 如果她講的是對的，我們這個邏輯系統就不可以拿來處理這個答案， 我們需要另外一個邏輯系統，跟時間相關的邏輯。

29 Unit 7 公理法與自然演繹法 (2) 等值規則與蘊涵規則 (ii) 蘊涵規則  肯定前項律 (MP): p  q , p ⊢ q
 否定後項律 (MT): p  q , q ⊢ p  假言三段論 (HS): p  q , q  r ⊢ p  r  選言三段論 (DS): p  q , p ⊢ q p  q , q ⊢ p m :36:59 接下來蘊涵規則。 如果是MP規則，就告訴我們是p→q，然後跟p就可以推出q， 再來是MT規則， 它的意思是，如果條件句成立，經由後件的否定，我們就可以得到前件的否定。 再來是假言三段論， 如果我們在推論過程中出現p→q、q→r，那麼就可以得到p→r， 再來是選言三段論， 你就想像說甲或是乙是嫌疑犯， 那不是甲，就可以推論出是乙。 那如果不是乙，那就是甲嘛。 他的想法其實就是這樣子。

30 Unit 7 公理法與自然演繹法 (2) 等值規則與蘊涵規則 (ii) 蘊涵規則  簡化律 (Simp): p  q ⊢ p
p  q ⊢ q  添加律 (Add): p ⊢ p  q  連言律 (Conj): p , q ⊢ p  q 建構兩難律 (CD): (p  q)  (r  s) , p  r ⊢ q  s p  q , r  s , p  r ⊢ q  s m :39:22 簡化律就是， p∧q可以得到p；p∧q可以得到q。 再來是添加律， P可以推出p∨q，或是q∨p，這個也沒有問題。 再來是Conjunction， 推論過程出現p、q，那就可以得到p∧q。 再來是建構兩難律，這個是最麻煩的，應該有一半的同學會覺得看起來一點都不自然，為什麼看起來沒有那麼直覺？我想應該是太複雜的原因吧。就是如果(p→q) ∧(r→s)，我們假設p∨r，那我們就可以得到q∨s。剛剛講到總共有18個規則，10個等值規則，8個涵蘊規則， 等一下我們要用這些規則來練習。

31 Unit 7 公理法與自然演繹法 實例練習： (k) (AB)C , (DA)C, (AB)A ⊢ (DA)
(l) (PQ)R, R(PQ), RQ ⊢ RQ (m) M , NM , KL , (NK)O ⊢ ON (n) (GH)F, H ⊢ FG (o) (WS)(SW) , WS, S ⊢ WS m :42:53 我們幾個練習是這樣，在講之前我想先強調一點，在自然演繹法裡面我們會有前提，然後來證明他的結論對吧？

32 Unit 7 公理法與自然演繹法 (k) (AB)C , (DA)C, (AB)A ⊢ (DA) 1. (AB)C
目 標 (DA) m :43:11 比如說我們以第一題為例，我們有前提，然後有個目標我們想要得到這個東西，思考上我們是把這個前提放在那裡，然後我們是目標導向嘛，所以我們要想辦法把最後那一個語句導出來。那萬一沒有前提怎麼辦？這位同學要不要提供一點意見？ 同學：轉出前提來。 沒錯，有點道理，我們可以假設一些前提是吧， 如果後面結論是有conditional的，那conditional前面那個是可以拿來當前提用的，最後再把它劃進來，像剛剛那個introduction rule一樣對吧？ 那個證法我們會叫做條件證法。 另外一個，沒有前提，後面也不是conditional那怎麼辦？ 那就假設他的否定，設法導出矛盾，這個我們叫做間接證法。 接下來我們來思考一下，要怎麼從這三個前提得到下面這個結論。 各位看一下，前提中跟 (D↔A)相關的語句就是(DA)C， 所以要得到結論(D↔A)，就要先得到C，然後利用MT規則得到想要的結論。 那麼，你又要怎麼得到¬C呢？顯然你需要(AB)，因此，你應該要利用最後一個前提得到(AB)，經由這些步驟，就可以得到結論。

33 Unit 7 公理法與自然演繹法 (k) (AB)C , (DA)C, (AB)A ⊢ (DA)
1. (AB)C Pr 2. (DA)C Pr 3. (AB)A Pr 4. (AB) , Simp 5. C ,4, MP 6. (DA) , 5, MT m :46:57 所以他其實是這樣子的。 所以應該是說，我有這三個前提，第一個步驟，讓我們利用簡化律將(A∨B)拉下來，然後根據(A∨B)和前提1，利用MP規則得到¬C，再利用¬C和前提2的MT規則得到¬(D↔A)。

34 Unit 7 公理法與自然演繹法 (l) (PQ)R, R(PQ), RQ ⊢ RQ 1. (PQ)R
目 標 RQ m :47:26 第3個沒有check好，應該是¬R→Q。 如果我要得到¬R∧Q， 我就要證明¬R、Q，然後再把兩個conjunction。

35 Unit 7 公理法與自然演繹法 (l) (PQ)R, R(PQ), RQ ⊢ RQ 1. (PQ)R Pr
2. R(PQ) Pr 3. RQ Pr 4. (PQ) , Simp 5. R , 4, MT 6. Q , 5, MP 7. RQ , 6, Conj m :48:32 他的推論應該是這樣，我們一樣有這三個前提，然後這個先用Simplification規則得到(PQ)，再經過MT規則的運用得到¬R，得到¬R之後呢，就可以得到Q，因為前提3是¬R→Q，所以只要¬R出來，就可以得到Q，最後再把¬R和Q結合起來成為一個conjunction就可以了。 所以利用的規則，首先是簡化律把前面¬(P∨Q)拉下來，再來用MT規則，這個是第2個後件的否定，所以就可以得到前件的否定¬R，再利用第3個MP規則得到後件Q，然後把兩個conjunction起來就可以得到我們要的。 同學：如果第1個得到R不就矛盾了嗎？ 沒有錯，也就是說我其實有另外一個證法，所謂的間接證法。 我來寫一次間接證法給各位看，第1個¬(P∨Q) ∧R，就直接把R拿下來， 再透過第2個R得到(P∨Q)，然後把第1個¬(P∨Q) 放進來，(P∨Q) 跟¬(P∨Q)就會矛盾了，矛盾之後，就會得到¬R。 因為自然演繹法是目標導向，所要的是最短證明，所以我們就不需要多餘的步驟來證明。

36 Unit 7 公理法與自然演繹法 (m) M, NM, KL, (NK)O ⊢ ON 1. M 2. NM 3. KL
目 標 ON m :54:35 c的例子是這樣，如果你看到目標裡面出現∨，那就再簡單不過了，因為只要證出來一個就好，你利用添加律馬上就可以得到結果。

37 Unit 7 公理法與自然演繹法 (m) M, NM, KL, (NK)O ⊢ ON 1. M Pr 2. NM Pr
3. KL Pr 4. (NK)O Pr 5. N , 2, MT 6. K , Simp 7. NK , 6, Conj 8. O , 7, MP 9. ON , Add m :55:15 我們有4個前提，利用他們來得到結果，如果我們要得到Q就要先得到(¬N∧K)，所以就必須先得到¬N、K，K從第3個前提可以得到， ¬N要從第1、2前提可以得到，然後把他combine起來就可以得到我們要的結論。

38 Unit 7 公理法與自然演繹法 (n) (GH)F, H ⊢ FG 1. (GH)F 2. H 目 標 FG
m :55:57 這個就比較簡單，因為結論看到∨，所以只要證出一個就可以了。

39 Unit 7 公理法與自然演繹法 (n) (GH)F, H ⊢ FG 1. (GH)F Pr 2. H Pr
3. H , DN 4. HG , Add 5. GH , Comm 6. (GH) , DeM 7. F , 6, DS 8. FG , Add m :56:25 所以我們的證明大概是這樣，我們有兩個前提，先做¬¬H，再利用Add把G加進來得到HG，然後再把它做Commutation得到GH，再利用DeM得到(GH)的結果，接著，可以利用DS規則得到F，再利用Add就可以得到結論了。

40 Unit 7 公理法與自然演繹法 (o) (WS)(SW) , WS, S ⊢ WS 1. (WS)(SW)
目 標 WS m :57:26 再來是範例e， 各位會從哪裡下手？如果目標是要得到W∧¬S，那第3個前提已經有一個¬S，所以我們的目標顯然是要把W找出來。

41 Unit 7 公理法與自然演繹法 (o) (WS)(SW) , WS, S ⊢ WS 1. (WS)(SW) Pr
2. WS Pr 3. S Pr 4. WS , Simp 5. W , 4, MT 6. W , DN 7. WS , 6, Conj m :58:43 所以他的證明是這樣，先把第1個前提利用簡化律把WS拉下來， 因為第3個是¬S，所以會得到¬¬W，這樣才可以得到W。 在整個證明過程中沒有出現第2個前提，代表它是多餘的，不過並不影響整個推論。 以上就是線性的自然演繹法。