Unit 6 真值樹系統 授課教師：傅皓政 老師 【本著作除另有註明外，採取創用CC「姓名標示－非商業性－相同方式分享」台灣3.0版授權釋出】

Presentation on theme: "Unit 6 真值樹系統 授課教師：傅皓政 老師 【本著作除另有註明外，採取創用CC「姓名標示－非商業性－相同方式分享」台灣3.0版授權釋出】"— Presentation transcript:

1 Unit 6 真值樹系統 授課教師：傅皓政 老師 【本著作除另有註明外，採取創用CC「姓名標示－非商業性－相同方式分享」台灣3.0版授權釋出】

2 Unit 6 真值樹系統 真值表法所談論的是命題之間的語意蘊 涵關係(semantic entailment relation)。
接下來，我們要學習的是命題之間的語 法蘊涵關係(syntactic entailment relation) 。 前面所提到的真值表，都是在談論語句之間語意的蘊涵關係。 接下來要做的是語法的蘊涵關係，意思是根據推論規則逐步證明，這叫語法的蘊涵關係。亦即從前提開始，根據給定的推論規則，可逐步推論至結論，若成功，則稱語法蘊涵關係成立，若否，則不成立。 除了要知道其語意蘊涵關係，還要知道其語法蘊涵關係。

3 Unit 6 真值樹系統 在研究語意蘊涵關係時，我們關心的是 前提與結論的真假值之間的關係。
然而，研究語法蘊涵關係所關心的是演 算系統的建立，也就是證明命題之間的 推論關係。也就是說，如何從前提開始 ，一步一步證明可以得到結論。 0211 在語法的蘊涵關係上，我們想要建立一個演算系統，能不能把前提經由演算系統，經由結論，一步步得到結論，就是證明。在古典邏輯中，會介紹三種演算系統。

4 Unit 6 真值樹系統 從古典邏輯的發展歷史來看，有三種經 常被提到的語法演算系統： (1)公理系統(Axiom System)
(2)自然演繹法(Natural Deduction System) (3)真值樹系統(Tableaux System) 古典邏輯中，我們通常會介紹三種。 (1)公理系統：這是在邏輯剛建立時，當時邏輯學家都用這個來做證明，期中考後會介紹。這個系統蘊含一件事，就是你好像要很天才，如同你看到有些人對數學很厲害，隨便想想就證出來，公理系統的證明有點像這樣，有點靠天賦。 (2)自然演繹法：大概是在三零年代由Gentzen建立，自然演繹法的出現，對公理系統是一大進步，引進很多推論規則，可以用的東西多，證明的步驟就越簡單，可用規則越少，步驟就更複雜。公理系統的規則只有一條。自然演繹法通常有兩種：introduction rule、elimination rule跟 Natural Deduction System。 (3)真值樹系統：像一棵倒過來的樹，樹根在上往下長，在這所有系統中最有力的系統，它比前兩者優越的地方在於能決定論證是否有效，不過它還是有限制的，非所有一階邏輯都辦得到。前兩者的困難在於在作證明時，需要天賦，如果你證不出來，如何說它是有效或無效論證，在決定論證是否有效，決定性是薄弱的。 1.公理系統：會設定一些各位都會接受的公理，再藉由公理與其所認可的規則逐步做推論，可推論出的便稱定理(theory)，用這方式演算的便是公理系統。 2.自然演繹法：各位想想看何謂自然演繹法，其理想是如此：不用公理，拿掉它，增加各位認可的推論規則，做成一個演算系統。 3.真值樹系統：想法是說前面兩個系統有點讓人擔憂，各位高中都做過數學證明，有一種人，明明就是很難的題目，看兩眼就會了，如果請那位同學教我，他很認真教你，可是怎麼教都不懂，各位都有沒有這經驗？ 在那個做證明的時代，有一點是我們都尚未克服的，好像能不能做出這題目需要天賦，這種人在哲學中，我們稱之為inside。有沒有一個方法，是不需要靠天賦能夠證出來，邏輯學家也在找這樣的方法。如果我把樂高教給這位謝同學，一隻恐龍，請他建成房子，這時謝同學心想：我應該先把這隻恐龍先拆了，再裝成一棟房子。假設謝同學很沒有概念，組不成房子，怎麼辦？這是邏輯學家在研究的過程中，剛好邏輯學家找到一個系統，只要負責拆，不用組合。只要拆不需要組合，一方面不需要像前面兩個方法，需要天分，一方面只需要拆不需要組合。比其他系統來的更有力。

5 Unit 6 真值樹系統 關於證明的兩種策略： (1)如果能夠從前提開始，藉由推論規 則逐步得到結論，則證明前提蘊涵結論。
(2)假設前提與結論的否定是一致的， 如果藉由推論規則得到矛盾，就表示前 提蘊涵結論。真值樹系統即採取此策略。 證明有兩種策略，一是直接證法，由前提思考如何得到結論，二是歸謬證法/間接證法，先假設結論不成立，再往前推，得到矛盾，得到結論是成立的。真值樹系統採取的是後者的策略，公理系統與自然演繹法雖然也有歸謬證法的部分，大部分由直接證法的概念來。 (1)常稱為直接證明法，大部分的公理法與自然演繹法採取這樣的思考方向。 (2) 從反面來，RAA(歸謬證法)或間接證法，先假設結論的否定與前提放在一起，若做出來會導致矛盾，意思是前提成立的情況下，結論一定要成立。以反向思考。

6 Unit 6 真值樹系統 語法蘊涵關係的記號： “⊢”
如果以句式 1 , 2 , ……, n 作為前提， 能夠經由推論規則得到結論 ，則稱 「1, 2, ……, n 語法上蘊涵 」。 記法： 1 , 2 , ……, n ⊢  ⊢：turnstile。 記號是用turnstile，用它來表示蘊涵關係，語法上蘊涵。 或稱 是1 到 n 的derivation。

7 Unit 6 真值樹系統 真值樹的基本結構： 前提和結論的否定構成樹根(root)。 根據推論規則逐步分解。
當真值樹成長到無法再以推論規則進行 分解，則稱為該真值樹已經完全展開。 先假設前提跟結論的否定，然後假設前提與結論都成立，若把它們分解到最後得到矛盾，那就是我們假設前提都成立，結論的否定成立，這件事是不成立的。所以在前提都成立時，結論一定要成立。 等到真值樹無法再分解，我們稱這棵樹已完全展開。 目標是把前提跟結論的否定放在一起，看看它成立否。第二件是用推論規則推論。推到無法再分解，何謂無法再分解？就是推到只剩下命題符號與命題符號的否定，就說這棵樹已經完全展開。便可判斷是否為有效論證。 如果只剩下命題符號與命題符號的否定，我們便說這棵樹已經完全展開

8 Unit 6 真值樹系統 真值樹的圖示 ：(root)      
     完全展開後，如果你發現最後產生矛盾的地方，我們就會把branch關起來，如果所有都關起來，表示它是矛盾的，因此前提與結論的關係成立。如果有一個branch是打開的，就說至少有一個結構是讓前提都成立而結論不成立，顯然它構成無效論證，它是反例。

9 Unit 6 真值樹系統 真值樹的圖示說明： 每個點都代表一個句式(formula)。 每個分枝(branch)都代表一個結構。
結構指的是所有的命題符號的真假值的組合。 在一個結構裡不能出現矛盾， 若產生矛盾，就會關起來。

10 Unit 6 真值樹系統 在真值樹的分枝上，如果同時出現某個 句式與該句式的否定句，則該分枝即為 封閉的，以符號「 × 」表示。  
在某個branch出現這個情況： 、 同時出現，便是封閉。 為什麼？因為我們說過了，從語意學的情況就能想像，如果在一個結構中，同時出現 、 ，表示要忍受 是真，又要忍受是假，表示這個結構本身是矛盾的。 有人喜歡活在矛盾的世界嗎？各位覺得這世界充滿矛盾請舉手，請問簡同學為何世界充滿矛盾？某個人做事這一刻跟下一刻可能完全不一樣，對不對？各位想想看，這是有趣的現象，如果某個人這一秒做的事跟下一秒完全不一樣， 你會跟這個人說；「你這個人充滿矛盾。」你這要說的意思是什麼？ 表示你前後不一 ，非常矛盾，表示這個人行為是非理性的，「你不能有矛盾的，你要理性點。」你是要告訴他這件事。 你這個人充滿矛盾，事實上是理性的，所以我會要求你理性點。事實上我們認為這世界是不應有矛盾的，因為我們不想忍受矛盾。難道有人表現矛盾時，你會說：「很好，我喜歡。」 矛盾令我們覺得可怕的地方在那？ 就是他非理性，所謂非理性就是任意的，所有行為都會變成任意的，因為所有結論都都成立，只要前面有矛盾或不一致，所有結論都成立，所以我們為何會害怕矛盾，因為假設一個人承認他矛盾的，那他不管做什麼都可以，沒有任何可預測性，不可預測對我們而言是可怕的。比如說你們會預期老師等一下要做什麼，你們覺得老師是理性的，所以我會很認真在這上課，假設我是不理性的，說不定下一秒我跳上桌子，更不要說到了期末，老師開始要打成績時，各位一定覺得老師是要理性的。 我們對於人理性的要求是一定是要可預測的，所以雖然我們覺得這世界充滿矛盾，但我們一直在努力告訴他這樣是不好的。 所以我們希望整個結構若是矛盾的，就把它封閉，因為他非我們理性中所容許的結構。

11 Unit 6 真值樹系統 推論規則的兩種類型： (1)  (2)  1 1 2 2
(1)  (2)   1 2 2 在真值樹中，有兩種基本規則，一是直線走的，表示1、2是相關的；二是分成兩邊的，表示1、2是不相關的。 第一種type叫，分解出來，1、2會在同一個branch上，第二種叫，表示要分開，變成兩個分支，分別是1、2，規則只有兩種，這兩種type是什麼意思呢？第一種指的是conjunction，兩句話要綁在一起，第二種是disjunction，是分開的，只要有一個為真就夠了。 第一種可以把它放在同一branch，根據推論規則，我們有個構想，我們把所有的formula的main connective通通變成conjunction或disjunction。

12 Unit 6 真值樹系統 類型(1)：由句式  分解為 1 和 2，且 1 和 2 在同一分枝上。從結構的觀點 來看，就是句式  要為真，必須在 1 和 2 均為真的情況下。因此類型(1)用 在主要連接詞是連言的情況。 類型(2)：由句式  分解為 1 和 2，且 1 和 2 在不同分枝上。從結構的觀點 來看，就是句式  要為真，只要 1 或 2 為真即可。因此類型(2)用在主要連 接詞是選言的情況。 一：連言意思是就是1跟2， 二：表示 1的真假無法由2決定，意思要為真，只要其中一個為真就好了，意思就是選言的情況。 第一種類型講的就是conjunction。 第二種類型講的是disjunction，只要有一為真就可以。

13 Unit 6 真值樹系統 推論規則的兩種類型實例： (1)  (2)     
(1)  (2)      我們把所有的formula的main connective 變成conjunction或disjunction

14 Unit 6 真值樹系統 根據真值函映完備性的證明，古典邏輯 的連接詞可以用、、定義之，因 此每個複合句式都可以找到主要連接詞 為連言或選言的等值語句。 只要用到、就好，只會用到double negation的規則。

15 Unit 6 真值樹系統 (i-1)： (i-2)： (i-3)： (i-4)： (i-5)：
根據我們truth functional的complete的principle，曾說過我們可以根據negation、and、or來定義truth functional的operator，就是真值涵映的連接詞通通可以用這三個連接詞定義，可見這系統是完備的。簡單來說，可以用這個系統做演算。 每一個formula都可以找到它的主要連接詞是conjunction或disjunction ，把它換成等值語句後，就可以理解演算規則的意思了。

16 Unit 6 真值樹系統 推論規則(i)：         第一個： ，我不是不愛你，推論下來就是我愛你。
        第一個： ，我不是不愛你，推論下來就是我愛你。 第二個：在同一個branch。 第三個：分成兩個branch。

17 Unit 6 真值樹系統 以真值表證明 PQ 等值於 PQ。 P Q P  Q  P  Q T F T F F F T T
Main connective是，用第二類分解。 接下來要做的是if…then，我們的規則只有連言跟選言，所以要設法把if…then變成連言獲或言的formula， PQ 可以變成 PQ，兩者真假值一樣，因此是等值的。 這我們已經練習很多次了，「如果你愛我的話，那你就要買鑽石給我 。」換成PQ，就是「你不愛我，或者買鑽石給我。」是不是一樣？大致上是一樣的，在當代邏輯中有問題，只是非本課程範圍。 我們通常不會說：「你不愛我，或者買鑽石給我。」我們會用一個更厲害的字眼：unless，除非你不愛我，否則買鑽石給我。

18 Unit 6 真值樹系統 以真值表證明 PQ 等值於 (PQ)(PQ) 。 P Q P  Q
T T F F F F F F F F T F F T F F F T T T T 要證明 PQ 等值於(PQ)(PQ) 。

19 Unit 6 真值樹系統 推論規則(i)：        

20 Unit 6 真值樹系統 接下來，我們要介紹的是推論規則(ii)， 是出現在推論規則(i)中的句型加上否 定號的推論規則：
接下來第二組規則，是加了negation，目標是去找到這些語句的等值語句，而且該等值語句的main connective是連言或選言。

21 Unit 6 真值樹系統 以真值表證明(PQ)等值於PQ。 P Q  (P  Q)  P   Q T F T F F F
F T T T T F T T T (ii-1) ：()的等值語句是PQ 這個規則是一個有名的邏輯學家笛摩根找到的，所以就稱為笛摩根定律。and跟or有個有趣的現象，(PQ) 、PQ是一對， 這對東西是若把放在()，展開後，and要改成or，or要改成and，個別加上negation。

22 Unit 6 真值樹系統 以真值表證明(PQ)等值於PQ。 P Q  (P  Q)  P   Q T F T F F F
F F T T F F T F T T T 另一個笛摩根定律的等值語句。

23 Unit 6 真值樹系統 推論規則(ii)： () ()     以上兩個推論規則的表示方法。

24 Unit 6 真值樹系統 以真值表證明(PQ)等值於 PQ。 P Q  (P  Q) P   Q T F T F F F
T T F T 邏輯教我們一件事，如何說真話，又不得罪人。甚至我們可以講到別人不知道原來是等值的，只要他沒學過邏輯的話。講真話而且同時不得罪人並不是困難的事。

25 Unit 6 真值樹系統 以真值表證明(PQ)等值於 (PQ)(PQ) 。 P Q (P  Q)
F T F F F F F F T F T T T F F F F T T T F T F T F

26 Unit 6 真值樹系統 推論規則(ii)： () ()      
() ()       記得推論規則只有兩種type，一是連言，二是選言。其二，在分解時，一定是針對每句話的主要連接詞。

27 Unit 6 真值樹系統 真值樹系統的優點： (1)能夠決定論證是否為有效論證。 (2)一旦證明某個論證為無效論證，可 以掌握其反例結構。
(3)推論規則只需分解，毋須考慮組合。 一、若用公理系統跟自然演繹法，若證不出來，就無法說明論證是否成立。萬一你證不出來呢？ 不能說它是無效論證，答案只能寫，我會跟不會，因為我不曉得該論證是否有效，真值樹系統提供給我們這樣的能力 ，在命題邏輯中可以證明某個論證是否有效，若是無效論證，並且可以舉出其反例結構，比前面兩個系統更powerful。

28 Unit 6 真值樹系統 實例說明： (a) (AB)C, CD, BD ⊢ A
(b) P(QR), R(QP), QR ⊢ PQ (c) Q ⊢ (Q(RS))(RS) (d) S(QP), QP, P(RS) ⊢ S (a)畫真值表大概要畫16個。

29 Unit 6 真值樹系統 (a) (AB)C, CD, BD ⊢ A (AB)C CD BD A A
提語法上蘊涵結論。 C D × (AB) C A B × × 兩個原則： 一是從簡單的開始做。推論規則沒有規定從那個句式開始分解，從那裡開始都可以。 二是盡量從不會造成分枝的句式開始進行分解。 根據以上原則，先從AB開始做。接下來，觀察一下，從可以被封閉的接著做，於是接著做CD。 於是整棵樹都封閉，我們就說任何結構若假設前提成立，結論不成立，會使每一結構都產生矛盾，意思是沒有任何結構能滿足設定，因此此論證為有效論證，或說語法蘊涵關係成立。 樹根的組合是由前提前提前提，以及結論的否定組成。做題目的原則是盡量不要有分枝，越簡單越好。

30 Unit 6 真值樹系統 (b) P(QR), R(QP), QR ⊢ PQ P(QR) R(QP) QR
由於所有的分枝都是封閉的， P P 所以這個論證為有效論證。 Q Q R (QP) R (QP) P (QR) Q P (QR) Q × P P Q R × Q R Q R × × × × × × × 原則從最簡單的做。首先，這四個都沒有typeα，因此一定要有分枝。都是封閉的，是有效論證。

31 Unit 6 真值樹系統 (c) Q ⊢ (Q(RS))(RS) Q ((Q(RS))(RS))
所以這個論證為有效論證。 RS R S Q RS × R S × ×

32 Unit 6 真值樹系統 (d) S(QP), QP, P(RS) ⊢ S S(QP) QP P(RS)
由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP × P Q R S F T T F S QP Q P × Q P 由於出現四個open branch (當然，只要出現一個open branch就足以證明)，顯示這個論證為無效論證。 反例寫法是找到任意open branch，如果在這個open branch中出現的是proposition letter，就賦予(assign)該命題符號為真(true)，如果出現的是命題符號的否定(negation)，則賦予(assign)該命題符號為假(false)。 最後，由於R沒有出現，填true或false可以，但是一定要填。

33 Unit 6 真值樹系統 (d) S(QP), QP, P(RS) ⊢ S S(QP) QP P(RS)
由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP × P Q R S F T F F S QP Q P × Q P

34 Unit 6 真值樹系統 (d) S(QP), QP, P(RS) ⊢ S S(QP) QP P(RS)
由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP × P Q R S F T F F S QP Q P × Q P

35 Unit 6 真值樹系統 (d) S(QP), QP, P(RS) ⊢ S S(QP) QP P(RS)
由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP × P Q R S F T T F S QP Q P × Q P

36 Unit 6 真值樹系統 從語法的觀點而言，如果沒有任何前提 的句式是有效論證的話，那麼該句式就 稱為「定理(theorem)」。定理的語法 形式為 “ ⊢ ”。 另外，如果所有前提會構成封閉的真值 樹，那麼這些前提就是彼此「不一致 (inconsistent)」的。以 Γ 代表前提句式 的集合，其語法形式為 “ Γ ⊢ ” 如果從一個語句來看， 各位應該記得，在真值表中，若所有情況皆真，叫恆真句。若一formula沒有任何前提， 卻成立，稱之為定理。 何謂不一致，若所有前提構成一封閉的真值樹，表示前提彼此不一致，沒有任何結構可以滿足這些語句，因此彼此不一致。

37 Unit 6 真值樹系統 對任一句式 ，可以用真值樹的方法證 明  是恆真句、矛盾句或者偶真句。
欲證明  是恆真句，就以  為樹根運 算，若得到封閉的真值樹，則句式  為恆真句。

38 Unit 6 真值樹系統 欲證明  是矛盾句，就直接以  為樹 根進行運算，若得到封閉的真值樹，則 句式  為矛盾句。
欲證明  是矛盾句，就直接以  為樹 根進行運算，若得到封閉的真值樹，則 句式  為矛盾句。 若句式  既不是恆真句，也不是矛盾 句，那麼句式  即為偶真句。 若是偶真句，本身不封閉，negation也不封閉。

39 Unit 6 真值樹系統 請用真值樹法證明下列句式何者為恆真句？何者為 矛盾句？何者為偶真句？ (e) (PQ)(QP)
(f) M(NM) (g) (SS)(RR) (h) A(BA) (i) (CD)C 黑板上的語句與恆真句的形式一樣，我們說過，此種形式均為恆真句。

40 Unit 6 真值樹系統 (e) (PQ)(QP) ((PQ)(QP)) PQ (PQ) 由於所有的分枝都是封閉的，
(QP) QP 所以(PQ)(QP)是恆真 句。或者，從語法的觀點而 Q P 言，(PQ)(QP)是定理， P Q 記為 ⊢ (PQ)(QP) P Q Q P × × × ×

41 Unit 6 真值樹系統 (f) M(NM) (M(NM)) M 由於所有的分枝都是封閉的，
或者，從語法的觀點而言， N M(NM) 是定理， M 記為 ⊢ M(NM) ×

42 Unit 6 真值樹系統 (g) (SS)(RR) ((SS)(RR)) SS 由於所有的分枝都不是封閉的，
非封閉的真值樹，可見非恆真句，會不會是偶真句呢？

43 Unit 6 真值樹系統 (g) (SS)(RR) (SS)(RR) (SS) RR 由於所有的分枝都是封閉的，
× × 若用它本身來做，是封閉的，表示是矛盾句。

44 Unit 6 真值樹系統 (h) A(BA) (A(BA)) A (BA) 由於所有的分枝都不是封閉的，

45 Unit 6 真值樹系統 (h) A(BA) A(BA) A 由於所有的分枝都是封閉的，
×

46 Unit 6 真值樹系統 (i) (CD)C ((CD)C) CD 由於所有的分枝都不是封閉的，

47 Unit 6 真值樹系統 (i) (CD)C (CD)C (CD) C 由於所有的分枝都不是封閉的，

48 Unit 6 真值樹系統 對某個句式集合 Γ 而言，Γ 是一致的， 若且唯若，至少有一個結構能夠使 Γ 中 所有的句式皆為真。
對某個句式集合 Γ 而言，Γ 是不一致的， 若且唯若，沒有任何結構能夠使 Γ 中所 有句式同時為真。

49 Unit 6 真值樹系統 以真值樹的方法證明一致性：
想要確定某個句式集合 Γ 是否一致， 只要將 Γ 中所有的句式作為樹根運算， 如果得到封閉的真值樹，則 Γ 是不一致 的。反之，如果有任何一個分枝是開放 的，那麼， Γ 就是一致的。

50 Unit 6 真值樹系統 以真值樹的方法證明下列各組句式是否 一致？ (j) HD, DS, HS
(k) K(LM), MK, LM (l) SC, CD, DW, WS, W 這有三句話，請問這是不是一致的。提醒各位這三句話均非恆真句與矛盾句。

51 Unit 6 真值樹系統 (j) HD, DS, HS HD DS HS H 由於真值樹的所有分枝都是
間是不一致的。 H D × D S × × 運算結果，得到封閉的真值樹，表示沒有任何情況使這些語句同時為真，那就表示這些語句彼此間不一致，找不到情況讓他們為真，這樣的情況就稱為不一致。

52 Unit 6 真值樹系統 (k) K(LM), MK, LM K(LM) MK LM K LM
由於真值樹並非封閉的， M K L 表示這些句式是一致的。 × M 使句式集合一致的結構： L L M M M K K L M × × T T T L L F F F M M × 有open表示這些語句彼此是一致的，而且還可以找到使它一致的結構，而且不只一個。

53 Unit 6 真值樹系統 (l) SC, CD, DW, WS, W SC CD DW
S S C C × × 全部封閉，因此是不一致的。