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

Slides:



Advertisements
Similar presentations
大綱 1. 三角函數的導函數. 2. 反三角函數的導函數. 3. 對數函數的導函數. 4. 指數函數的導函數.
Advertisements

思維方法 課程網頁: 第八週: 真值表法Ⅲ:判斷論證的有效性.
有趣的謎語 非常有趣 哦 ~~ 答對了 嗎 ??. 目錄 1. 蚊子不叮什麼 ? 2. 多拉 A 夢是什麼顏色 ? 3. 考試了 ~~ 4. 總統府 5. 放鬆一下 ~~~
第四課 Dialogue I: Talking about Hobbies
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
如果光想著一件事情的難度而遲遲不肯行動 ,那麼將永遠不會成功 ,但只要你肯踏出第一步, 你就可能成功。
第二章 命题逻辑(上) 主讲人:耿国华.
認識倍數(一) 設計者:建功國小 盧建宏.
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
邏輯與批判思考 課程網頁:
【本著作除另有註明外,採取創用CC「姓名標示-非商業性-相同方式分享」臺灣3.0版授權釋出】
題目:十六對一多工器 姓名:李國豪 學號:B
Chapter 5 迴圈.
命 题 # 判 断 复合命题. 命 题 # 判 断 复合命题 一、复合命题概述 1.定义 复合命题(compound proposition) ,就是以命题作为直接构成成分的命题,或者,包含有其他命题成分的命题。 例如: ① 并非所有去过作案现场的人都是作案人; ② 张××是法官,并且,张××是中共党员;
西洋哲學史 西洋哲學的創始:古希臘哲學 (一)
模仿、認識與現象學 臺北醫學大學通識教育中心 林文琪副教授
9/28號專題報告 Web網頁遊戲 曾建瑋.
2-3 基本數位邏輯處理※.
101北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备.
Unit 7 公理法與自然演繹法 授課教師:傅皓政 老師
以下這個謎題無法透過宮摒除法完成解題。 但可透過「區塊宮摒除法」或「行列摒除法」完成 By TTHsieh
第十單元 Comment compter en français ?
第 一 單 元 不定積分.
數學與文化:以數學小說閱讀為進路 洪萬生 台灣師範大學數學系退休教授
第二講:初步認識釋迦摩尼佛的生平與教學 授課教師:國立臺灣大學哲學系 蔡耀明 教授
Survey of Selected Western Classics Unit 6: 聖經中的詩- Psalms
1.3 在整除性問題之應用 附加例題 3 © 文達出版 (香港 )有限公司.
虎克定律與簡諧運動 教師:鄒春旺 日期:2007/10/8
BCY行動研究2011之後 上課日誌 隔週上課前兩天以 時間: 年 月 日  紀錄者: 檔案名: 上課日期+學生名字
歐盟法與生命文化 (二) 第八單元 Protestantism Spirit of Reformation
第二次電腦實習課 說明者:吳東陽 2003/10/07.
授課時間:2012年10月25日(四)16:30~18:20 授課地點:博雅教學館 405、406室
Operations Management Unit 3: Project Management (2)
學習單元:N6 數的性質 學習單位:N6-3 用短除法求H.C.F. 和 L.C.M. 學習重點 : 1. 複習因數分解法求
How to use Edmodo Alice Lin 8-12th Grade Valencia High School
Unit 5 真值表法 授課教師:傅皓政 老師 【本著作除另有註明外,採取創用CC「姓名標示-非商業性-相同方式分享」台灣3.0版授權釋出】
演繹法(2):現代邏輯的真值表法.
第一講:課程介紹 授課教師:國立臺灣大學哲學系 蔡耀明 教授
授課教師:國立臺灣大學 政治學系 王業立 教授
網頁資料知多少? 事 實 ? 謠言?.
臺灣現代主義小說 Reading Taiwan's Modernism Fiction 第一講:課程簡介
法學入門 第 1 單元:法學入門 【本著作除另有註明外,採取創用CC「姓名標示-非商業性-相同方式分享」台灣3.0版授權釋出】
【本著作除另有註明外,採取創用CC「姓名標示-非商業性-相同方式分享」臺灣3.0版授權釋出】
小學四年級數學科 8.最大公因數.
新高中 通識教育科 教案設計分享會 沙田循道衛理中學 許文忠老師 2019/4/25.
101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 Nan.
Unit 4 語意學基本預設及語句連接詞 授課教師:傅皓政 老師
Array I 授課教師 Wanjiun Liao
算獨教學 范國祥製作 於新湖國小 算獨資料來源
數字獨樂樂 --數獨原來這麼簡單.
中三生物科 生物的七個特徵.
一 什麼是思考方法? 思考方法(method of thinking)的意義為研究使人思考正確的一門學科。
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
交流電路(R-L) R-L Series Circuits ATS電子部製作.
MiRanda Java Interface v1.0的使用方法
Operations Management Unit 4: Developing a Process Strategy
Operations Management Unit 5: Analyzing Processes (1)
第二單元(2):Case Study- Li & Fung
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
【本著作除另有註明外,採取創用CC「姓名標示-非商業性-相同方式分享」臺灣3.0版授權釋出】
1757: Secret Chamber at Mount Rushmore
歸納法(1):歸納法的類別.
离散数学─逻辑和证明 南京大学计算机科学与技术系
2.1 一元一次不等式 定 義 設a、b為兩個實數。.
有趣的計算 如果令A、B、C、D……X、Y、Z這26個英文 字母,分别等於百分之1、2、3、4……24、
ABC ( )已知 ,則下列哪些是x6-7x5-8x4 的因 式?(複選) (A) x+1 (B) 2x+2 (C) x3(x+1)
Presentation transcript:

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

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

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

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。有沒有一個方法,是不需要靠天賦能夠證出來,邏輯學家也在找這樣的方法。如果我把樂高教給這位謝同學,一隻恐龍,請他建成房子,這時謝同學心想:我應該先把這隻恐龍先拆了,再裝成一棟房子。假設謝同學很沒有概念,組不成房子,怎麼辦?這是邏輯學家在研究的過程中,剛好邏輯學家找到一個系統,只要負責拆,不用組合。只要拆不需要組合,一方面不需要像前面兩個方法,需要天分,一方面只需要拆不需要組合。比其他系統來的更有力。

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

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

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

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

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

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

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

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

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

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

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 ,把它換成等值語句後,就可以理解演算規則的意思了。

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

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,除非你不愛我,否則買鑽石給我。

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) 。

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

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

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。

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 另一個笛摩根定律的等值語句。

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

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

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

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

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

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個。

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。 於是整棵樹都封閉,我們就說任何結構若假設前提成立,結論不成立,會使每一結構都產生矛盾,意思是沒有任何結構能滿足設定,因此此論證為有效論證,或說語法蘊涵關係成立。 樹根的組合是由前提前提前提,以及結論的否定組成。做題目的原則是盡量不要有分枝,越簡單越好。

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α,因此一定要有分枝。都是封閉的,是有效論證。

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

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可以,但是一定要填。

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

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

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

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

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

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

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

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 × × × ×

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

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

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

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

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

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

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

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

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

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 這有三句話,請問這是不是一致的。提醒各位這三句話均非恆真句與矛盾句。

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

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表示這些語句彼此是一致的,而且還可以找到使它一致的結構,而且不只一個。

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