真值树系统课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,真值樹系統,真值樹系統,真值表法所談論的是命題之間的語意蘊涵關係,(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)：由句式 分解為 1 和 2，且1 和,推論規則的兩種類型實例：,(1),(2), ,真值树系统课件,根據真值函映完備性的證明，古典邏輯的連接詞可以用、定義之，因此每個複合句式都可以找到主要連接詞為連言或選言的等值語句。,真值树系统课件,首先，我們要介紹推論規則,(i),，即和五個連接詞直接相關的推論規則,。,(i-1),：,(i-2),：,(i-3),：,(i-4),：,(i-5),：,首先，我們要介紹推論規則(i)，即和五個連接詞直接相關的推論,推論規則,(i),：, ,真值树系统课件,以真值表證明,PQ,等值於,PQ,。,P,Q,P, Q, P Q,T,T,T,F,T,T,F,F,F,F,F,T,T,T,T,F,F,T,T,T,PQP Q P QTTT F TT,以真值表證明,PQ,等值於,(PQ)(PQ),。,P,Q,P, Q,(P, Q,), ( P Q),T,T,T,T,T,F,F,F,T,F,F,F,F,F,F,T,F,T,F,F,F,T,F,F,F,F,T,F,T,T,T,T,PQP Q(P Q) ( P Q)TT,推論規則,(i),：, , ,真值树系统课件,接下來，我們要介紹的是推論規則,(ii),，是出現在推論規則,(i),中的句型加上否定號的推論規則：,(ii-1),：,(),(ii-2),： ,(),(ii-3),：,(),(ii-4),：,(),接下來，我們要介紹的是推論規則(ii)，是出現在推論規則(i,以真值表證明,(PQ),等值於,PQ,。,P,Q,(P, Q,), P Q,T,T,F,T,F,F,F,T,F,T,F,F,T,T,F,T,T,F,T,T,F,F,F,T,F,T,T,T,PQ (P Q) P QTT F,以真值表證明,(PQ),等值於,PQ,。,P,Q,(P, Q,), P Q,T,T,F,T,F,F,F,T,F,F,T,F,F,T,F,T,F,T,T,F,F,F,F,T,F,T,T,T,PQ (P Q) P QTT F,推論規則,(ii),：,(),(), ,真值树系统课件,以真值表證明,(PQ),等值於,PQ,。,P,Q,(P, Q,),P Q,T,T,F,T,F,F,T,F,T,F,T,T,F,T,F,T,F,F,F,F,F,T,F,T,PQ (P Q) P QTT F,以真值表證明,(PQ),等值於,(PQ)(PQ),。,P,Q,(P, Q,),(P, Q,), ( P Q),T,T,F,T,F,F,F,F,F,T,F,T,F,T,T,T,F,F,F,T,T,F,F,F,T,T,T,F,F,F,T,F,T,F,T,F,PQ (P Q) (P Q) ( P ,推論規則,(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, ,(a) (AB)C, CD, BD A,(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, ,(b) P(QR), R(QP), QR P,(c) Q (Q(RS)(RS),Q,(Q(RS)(RS),(Q(RS),(RS),由於所有分枝都是封閉的，,所以這,個論證為有效論證。,RS,R,S,Q RS,R S, ,(c) Q (Q(RS)(RS),(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) ,(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) ,(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) ,(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) ,從語法的觀點而言，如果沒有任何前提的句式是有效論證的話，那麼該句式就稱為定理,(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,(e) (PQ)(QP),(f) M(NM),(M(NM),M,由於所有的分枝都是封閉的，,(NM),所以,M(NM),是恆真句。,或者，從語法的觀點而言，,N,M(NM),是定理，,M,記為, M(NM),(f) M(NM),(g),(SS)(RR),(SS)(RR),SS,由於所有的分枝都不是封閉的，,(RR),證明,(SS)(RR),不是恆真句。,R ,R,S S,R,S S,(g) (SS)(RR),(g),(SS)(RR),(SS)(RR),(SS),RR,由於所有的分枝都是封閉的，,證明,(SS)(RR),是矛盾句。,S R,S,R, ,(g) (SS)(RR),(h) A(BA),(A(BA),A (BA),由於所有的分枝都不是封閉的，,證明,A(BA),不是恆真句。,BA,B A,(h) A(BA),(h) A(BA),A(BA),A,由於所有的分枝都是封閉的，,(BA),證明,A(BA),是矛盾句。,B,A,(h) A(BA),(i) (CD)C,(CD)C),CD,由於所有的分枝都不是封閉的，,C,所以,(CD)C,不是恆真句。,C D,(i) (CD)C,(i) (CD)C,(CD)C,(CD) C,由於所有的分枝都不是封閉的，,證明,(CD)C,不是矛盾句。,C,經過上述的證明，,(CD)C,D,既不是恆真句，也不是矛盾句，,所以，,(CD)C,是偶真句。,(i) (CD)C,對某個句式集合,而言，,是一致的，若且唯若，至少有一個結構能夠使,中所有的句式皆為真。,對某個句式集合,而言，,是不一致的，若且唯若，沒有任何結構能夠使,中所有句式同時為真。,真值树系统课件,以真值樹的方法證明一致性：,想要確定某個句式集合,是否一致，只要將,中所有的句式作為樹根運算，如果得到封閉的真值樹，則,是不一致的。反之，如果有任何一個分枝是開放的，那麼，,就是一致的。,真值树系统课件,以真值樹的方法證明下列各組句式是否一致？,(j) HD, DS, H,S,(k) K(LM),MK, LM,(l) SC, CD,D,W, W,S,W,真值树系统课件,(j) HD, DS, H,S,HD,DS,H,S,H,由於真值樹的所有分枝都是,S,封閉的，因此這些句式之,間是不一致的。,H D,D S, ,(j) HD, DS, HS,(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,(k) K(LM), MK, LM,(l) SC, CD,D,W, W,S,W,SC,CD,D,W,W,S,由於真值樹的所有分枝都是,W,封閉的，因此這些句式之間,C,是不一致的。,D,W S,D W,D,S S,C C, ,(l) SC, CD, DW, WS, W,