真值树系统课件.ppt

1、 真值表法所談論的是命題之間的語意蘊涵關係(semantic entailment relation)。接下來，我們要學習的是命題之間的語法蘊涵關係(syntactic entailment relation)。在研究語意蘊涵關係時，我們關心的是前提與結論的真假值之間的關係。然而，研究語法蘊涵關係所關心的是演算系統的建立，也就是證明命題之間的推論關係。也就是說，如何從前提開始，一步一步證明可以得到結論。從古典邏輯的發展歷史來看，有三種經常被提到的語法演算系統：(1)公理系統(Axiom System)(2)自然演繹法(Natural Deduction System)(3)真值樹系統(Tabl

2、eaux System)關於證明的兩種策略：(1)如果能夠從前提開始，藉由推論規則逐步得到結論，則證明前提蘊涵結論。(2)假設前提與結論的否定是一致的，如果藉由推論規則得到矛盾，就表示前提蘊涵結論。真值樹系統即採取此策略。語法蘊涵關係的記號：“”如果以句式 1,2,n 作為前提，能夠經由推論規則得到結論，則稱1,2,n 語法上蘊涵。記法：1,2,n 真值樹的基本結構：前提和結論的否定構成樹根(root)。根據推論規則逐步分解。當真值樹成長到無法再以推論規則進行分解，則稱為該真值樹已經完全展開。真值樹的圖示 ：(root)真值樹的圖示說明：每個點都代表一個句式(formula)。每個分枝(bra

3、nch)都代表一個結構。在真值樹的分枝上，如果同時出現某個句式與該句式的否定句，則該分枝即為封閉的，以符號 表示。推論規則的兩種類型：(1)(2)1 1 2 2 類型(1)：由句式 分解為 1 和 2，且1 和 2 在同一分枝上。從結構的觀點來看，就是句式 要為真，必須在 1 和 2 均為真的情況下。因此類型(1)用在主要連接詞是連言的情況。類型(2)：由句式 分解為 1 和 2，且1 和 2 在不同分枝上。從結構的觀點來看，就是句式 要為真，只要 1 或 2 為真即可。因此類型(2)用在主要連接詞是選言的情況。推論規則的兩種類型實例：(1)(2)根據真值函映完備性的證明，古典邏輯的連接詞可以

4、用、定義之，因此每個複合句式都可以找到主要連接詞為連言或選言的等值語句。首先，我們要介紹推論規則(i)，即和五個連接詞直接相關的推論規則。(i-1)：(i-2)：(i-3)：(i-4)：(i-5)：推論規則(i)：以真值表證明 PQ 等值於 PQ。PQP Q P QTTT F TTFF F FFTT T TFFT T T以真值表證明 PQ 等值於(PQ)(PQ)。PQP Q(P Q)(P Q)TTT T T F F FTFF F F F F TFTF F F T F F FFT F T T T T 推論規則(i)：接下來，我們要介紹的是推論規則(ii)，是出現在推論規則(i)中的句型加上否定號

5、的推論規則：(ii-1)：()(ii-2)：()(ii-3)：()(ii-4)：()以真值表證明(PQ)等值於PQ。PQ (P Q)P QTT F T F F F TF T F F T TFT T F T T FFF T F T T T以真值表證明(PQ)等值於PQ。PQ (P Q)P QTT F T F F F TF F T F F TFT F T T F FFF T F T T T 推論規則(ii)：()()以真值表證明(PQ)等值於 PQ。PQ (P Q)P QTT F T F FTF T F T TFT F T F FFF F T F T以真值表證明(PQ)等值於(PQ)(PQ)。PQ

6、 (P Q)(P Q)(P Q)TT F T F F F F F TF T F T T T F F FT T F F F T T T FF F T F T F T F 推論規則(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 個論證為有

7、效論證，或者說，前 提語法上蘊涵結論。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 反例(cou

8、nterexample)：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

9、 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)的。以 代表前提句式的集合，其語法形式為“”對任一句式，可以用真值樹的方法證明 是恆真句、矛盾句或者偶真句。欲證明 是恆真句，就以

10、為樹根運算，若得到封閉的真值樹，則句式 為恆真句。欲證明 是矛盾句，就直接以 為樹根進行運算，若得到封閉的真值樹，則句式 為矛盾句。若句式 既不是恆真句，也不是矛盾句，那麼句式 即為偶真句。請用真值樹法證明下列句式何者為恆真句？何者為矛盾句？何者為偶真句？(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(N

11、M)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

12、(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是偶真句。對某個句式集合 而言，是一致的，若且唯若，至少有一個結構能夠使 中所有的句式皆為真。對某個句式集合 而言，是不一致的，若且唯若，沒有任何結構能夠使 中所有句式同時為真。以真值樹的方法證明一致性：想要確定某個句式集合 是否一致，只要將 中所有的句式作為樹根運算，如果得到封閉的真值樹，則 是不一致的。反之，如果有任

13、何一個分枝是開放的，那麼，就是一致的。以真值樹的方法證明下列各組句式是否一致？(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