真值树系统课件.ppt
真值樹系統,真值表法所談論的是命題之間的語意蘊涵關係(semantic entailment relation)。接下來，我們要學習的是命題之間的語法蘊涵關係(syntactic entailment relation)。,在研究語意蘊涵關係時，我們關心的是前提與結論的真假值之間的關係。然而，研究語法蘊涵關係所關心的是演算系統的建立，也就是證明命題之間的推論關係。也就是說，如何從前提開始，一步一步證明可以得到結論。,從古典邏輯的發展歷史來看，有三種經常被提到的語法演算系統：(1)公理系統(Axiom System)(2)自然演繹法(Natural Deduction System)(3)真值樹系統(Tableaux System),關於證明的兩種策略：(1)如果能夠從前提開始，藉由推論規則逐步得到結論，則證明前提蘊涵結論。(2)假設前提與結論的否定是一致的，如果藉由推論規則得到矛盾，就表示前提蘊涵結論。真值樹系統即採取此策略。,語法蘊涵關係的記號： “”如果以句式 1 , 2 , , n 作為前提，能夠經由推論規則得到結論 ，則稱1, 2, , n 語法上蘊涵 。記法： 1 , 2 , , n ,真值樹的基本結構：前提和結論的否定構成樹根(root)。根據推論規則逐步分解。當真值樹成長到無法再以推論規則進行分解，則稱為該真值樹已經完全展開。,真值樹的圖示 ：(root) ,真值樹的圖示說明：每個點都代表一個句式(formula)。每個分枝(branch)都代表一個結構。,在真值樹的分枝上，如果同時出現某個句式與該句式的否定句，則該分枝即為封閉的，以符號 表示。 ,推論規則的兩種類型：(1) (2) 1 1 2 2,類型(1)：由句式 分解為 1 和 2，且1 和 2 在同一分枝上。從結構的觀點來看，就是句式 要為真，必須在 1 和 2 均為真的情況下。因此類型(1)用在主要連接詞是連言的情況。類型(2)：由句式 分解為 1 和 2，且1 和 2 在不同分枝上。從結構的觀點來看，就是句式 要為真，只要 1 或 2 為真即可。因此類型(2)用在主要連接詞是選言的情況。,推論規則的兩種類型實例：(1) (2) ,根據真值函映完備性的證明，古典邏輯的連接詞可以用、定義之，因此每個複合句式都可以找到主要連接詞為連言或選言的等值語句。,首先，我們要介紹推論規則(i)，即和五個連接詞直接相關的推論規則。(i-1)：(i-2)：(i-3)：(i-4)： (i-5)：,推論規則(i)： ,以真值表證明 PQ 等值於 PQ。,以真值表證明 PQ 等值於(PQ)(PQ) 。,推論規則(i)： ,接下來，我們要介紹的是推論規則(ii)，是出現在推論規則(i)中的句型加上否定號的推論規則：(ii-1)： ()(ii-2)： ()(ii-3)： () (ii-4)： (),以真值表證明(PQ)等值於PQ。,以真值表證明(PQ)等值於PQ。,推論規則(ii)： () () ,以真值表證明(PQ)等值於 PQ。,以真值表證明(PQ)等值於(PQ)(PQ) 。,推論規則(ii)： () () ,真值樹系統的優點：(1)能夠決定論證是否為有效論證。(2)一旦證明某個論證為無效論證，可以掌握其反例結構。(3)推論規則只需分解，毋須考慮組合。,實例說明：(a) (AB)C, CD, BD A(b) P(QR), R(QP), QR PQ(c) Q (Q(RS)(RS)(d) S(QP), QP, P(RS) S,(a) (AB)C, CD, BD A (AB)C CD BD A A B 由於所有的分枝均封閉，所以這 D 個論證為有效論證，或者說，前 提語法上蘊涵結論。 C D (AB) C A B ,(b) P(QR), R(QP), QR PQ P(QR) R(QP) QR (PQ) 由於所有的分枝都是封閉的， P P 所以這個論證為有效論證。 Q Q R (QP) R (QP) P (QR) Q P (QR) Q P P Q R Q R Q R ,(c) Q (Q(RS)(RS) Q (Q(RS)(RS) (Q(RS) (RS) 由於所有分枝都是封閉的， 所以這個論證為有效論證。 RS R S Q RS R S ,(d) S(QP), QP, P(RS) S S(QP) QP P(RS) S 由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP P Q R S F T T F S QP Q P Q P ,(d) S(QP), QP, P(RS) S S(QP) QP P(RS) S 由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP P Q R S F T F F S QP Q P Q P ,(d) S(QP), QP, P(RS) S S(QP) QP P(RS) S 由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP P Q R S F T F F S QP Q P Q P ,(d) S(QP), QP, P(RS) S S(QP) QP P(RS) S 由於有些分枝不是封閉的， P RS 所以這個論證為無效論證。 Q P R 反例(counterexample)： S Q S QP P Q R S F T T F S QP Q P Q P ,從語法的觀點而言，如果沒有任何前提的句式是有效論證的話，那麼該句式就稱為定理(theorem)。定理的語法形式為 “ ”。另外，如果所有前提會構成封閉的真值樹，那麼這些前提就是彼此不一致(inconsistent)的。以 代表前提句式的集合，其語法形式為 “ ”,對任一句式 ，可以用真值樹的方法證明 是恆真句、矛盾句或者偶真句。欲證明 是恆真句，就以 為樹根運算，若得到封閉的真值樹，則句式 為恆真句。,欲證明 是矛盾句，就直接以 為樹根進行運算，若得到封閉的真值樹，則句式 為矛盾句。若句式 既不是恆真句，也不是矛盾句，那麼句式 即為偶真句。,請用真值樹法證明下列句式何者為恆真句？何者為矛盾句？何者為偶真句？(e) (PQ)(QP)(f) M(NM)(g) (SS)(RR)(h) A(BA)(i) (CD)C,(e) (PQ)(QP) (PQ)(QP) PQ (PQ) 由於所有的分枝都是封閉的， (QP) QP 所以(PQ)(QP)是恆真 句。或者，從語法的觀點而 Q P 言，(PQ)(QP)是定理， P Q 記為 (PQ)(QP) P Q Q P ,(f) M(NM) (M(NM) M 由於所有的分枝都是封閉的， (NM) 所以M(NM)是恆真句。 或者，從語法的觀點而言， N M(NM) 是定理， M 記為 M(NM) ,(g) (SS)(RR) (SS)(RR) SS 由於所有的分枝都不是封閉的， (RR) 證明(SS)(RR)不是恆真句。 R R S S R S S,(g) (SS)(RR) (SS)(RR) (SS) RR 由於所有的分枝都是封閉的， 證明(SS)(RR)是矛盾句。 S R S R ,(h) A(BA) (A(BA) A (BA) 由於所有的分枝都不是封閉的， 證明A(BA)不是恆真句。 BA B A,(h) A(BA) A(BA) A 由於所有的分枝都是封閉的， (BA) 證明A(BA)是矛盾句。 B A ,(i) (CD)C (CD)C) CD 由於所有的分枝都不是封閉的， C 所以(CD)C不是恆真句。 C D,(i) (CD)C (CD)C (CD) C 由於所有的分枝都不是封閉的， 證明(CD)C不是矛盾句。 C 經過上述的證明， (CD)C D 既不是恆真句，也不是矛盾句， 所以，(CD)C是偶真句。,對某個句式集合 而言， 是一致的，若且唯若，至少有一個結構能夠使 中所有的句式皆為真。對某個句式集合 而言， 是不一致的，若且唯若，沒有任何結構能夠使 中所有句式同時為真。,以真值樹的方法證明一致性：想要確定某個句式集合 是否一致，只要將 中所有的句式作為樹根運算，如果得到封閉的真值樹，則 是不一致的。反之，如果有任何一個分枝是開放的，那麼， 就是一致的。,以真值樹的方法證明下列各組句式是否一致？(j) HD, DS, HS(k) K(LM), MK, LM(l) SC, CD, DW, WS, W,(j) HD, DS, HS HD DS HS H 由於真值樹的所有分枝都是 S 封閉的，因此這些句式之 間是不一致的。 H D D S ,(k) K(LM), MK, LM K(LM) MK LM K LM 由於真值樹並非封閉的， M K L 表示這些句式是一致的。 M 使句式集合一致的結構： L L M M M K K L M T T T L L F F F M M ,(l) SC, CD, DW, WS, W SC CD DW WS 由於真值樹的所有分枝都是 W 封閉的，因此這些句式之間 C 是不一致的。 D W S D W D S S C C ,
