語句邏輯的證明系統 - 啊啊哲學

PS系統的推論規則：Modus Ponens（MP）. 由├A→B和├A可以得到├B，或者; A→B, A├B. 有了公理和推論規則後，就可以推論出其它定理（theorem）（因為還沒證明語句 ... skiptomain| skiptosidebar ##EasyReadMore## 2.12.2011 語句邏輯的證明系統  （這裡用的A、B、C可以替換成其他合法的語句） 證明系統裡有公理（axiom）和推論規則（ruleofinference）這兩個部分。

Kiki上課時用的證明系統（PS系統）裡只用了兩個連接詞，¬和→。

不過我忘記要怎麼證明這兩個連接詞就夠用了。

另外，Kiki有提到其實只要「｜」這個連接詞*1就夠用。

證明系統的公理越少，以後在證明健全性和完備性時會比較簡單，但是做推論時會比較麻煩，要寫好幾行才能推論出想要的東西。

PS系統裡會用到「├」這個符號，如果我沒記錯的話這個符號的名字是singletermstyle。

證明（proof）：├A 意思是A是公理，或A是由公理和推論規則產生的。

A不需要任何前提就能堆論出來。

推導（deduction）：Γ├A 意思是A是由Γ這組前提，以及公理和推論規則產生的語句。

Γ是由語句們形成的集合。

當Γ├A裡的Γ是空集合時，它就是├A。

一致（consistency）： Γ是個一致的集合，若且唯若，對於某個語句A而言，不會有Γ├A而且Γ├¬A的情況發生。

PS系統的公理： ├A→(B→A) ├(A→(B→C))→((A→B)→(A→C)) ├(¬A→¬B)→(B→A) PS系統的推論規則：ModusPonens（MP） 由├A→B和├A可以得到├B，或者 A→B, A├B 有了公理和推論規則後，就可以推論出其它定理（theorem）（因為還沒證明語句邏輯的健全性和完備性，所以不能用語句的真假值來證明這些定理）： 推導├A→A。

├A→((A→A)→A)                     公理1 ├(A→((A→A)→A))→((A→(A→A))→(A→A)) 公理2 ├(A→(A→A))→(A→A)                 1,2,MP ├A→(A→A)                         公理1 ├A→A                             3,4,MP 推導Γ, A├B若且唯若Γ├A→B（這是後設定理，因為在語句邏輯的語法裡沒有說「Γ」、「若且唯若」是合法的語句邏輯符號）。

1.如果Γ├A→B則Γ, A├B。

當Γ├A→B時，如果在前提裡加進A，讓前提從Γ變成Γ,A，那麼除了 Γ,A├A→B以外我們還可以得到Γ,A├A。

根據MP規則，從Γ,A├A→B和Γ,A├A我們可以推論出Γ,A├B。

2.如果Γ, A├B則Γ├A→B。

這時候要用到數學歸納法。

用推導的長度為Γ, A├B的推導們排序（例如之前推導├A→A時推導的長度是五行）。

BaseCase： 證明當Γ, A├B推導的長度是一行時，Γ, A├B則Γ├A→B會成立。

Γ, A├B推導的長度是一時，要嘛B和A是同一個語句，要嘛B是公理或Γ裡的某個語句。

B和A是同一個語句： 那麼根據├A→A這個定理，Γ├A→B會成立。

B是公理： 因此Γ├B。

加上公理1Γ├B→(A→B)，使用MP規則可以得到Γ├A→B。

B是Γ裡的某個語句： 因此Γ├B。

加上公理1Γ├B→(A→B)，使用MP規則可以得到Γ├A→B。

InductiveHypothesis： 假設當Γ, A├B的推導長度小於n時，Γ, A├B則Γ├A→B會成立。

InductiveCase： 利用InductiveHypothesis證明當Γ, A├B推導的長度是n行時，Γ, A├B則Γ├A→B會成立。

Γ, A├B推導的長度是n時，要嘛B和A是同一個語句，要嘛B是公理或Γ裡的某個語句，要嘛B是用MP規則推論出來的。

B和A是同一個語句：證明方式和BaseCase一樣。

B是公理：同上。

B是Γ裡的某個語句：同上。

B是用MP規則推論出來的： 也就是說，B是這樣推論出來的： 第1行：Γ, A├某個句子 第2行：Γ, A├某個句子 … 第i行：Γ, A├C→B … 第j行：Γ, A├C … 第n行：Γ, A├B（根據第i行、第j行及MP） 因為第i行和第j行的推論長度都小於第n行，所以它們都可以使用InductiveHypothesis做推論。

所以Γ, A├C→B使用IH後我們得到Γ├A→(C→B)。

Γ, A├C使用IH後得到Γ├A→C。

再使用公理2Γ├(A→(C→B))→((A→C)→(A→B))和MP規則，就可以得到Γ├A→B。

其他PS系統裡的後設定理（大概不只這些）： Idempotence：Γ, A├A Monotonicity（單調性）：如果Γ├A，那麼Γ, Σ├A Cut：如果Γ, A├B而且Γ, A, B, Σ├C，那麼Γ, A, Σ├C 其他PS系統裡的定理：→的傳遞性：A→B, B→C├A→C ├¬A→(A→B) 如果某組前提可以推論出A也可以推論出¬A（也就是說，這組前提不一致），那麼根據MP規則及這個定理，這組前提可以推論出任何語句。

├¬¬A→A ├A→¬¬A ├A→((A→B)→B) ├(A→B)→(¬B→¬A) ├(A→¬A)→¬A 懶得列了，就這樣。

有興趣的人可以試試看自己推導這些定理。

不過我幾乎都證不出來，嘛哈。

參考資料：中正哲學所九十九學年度第一學期進階邏輯Kiki的講義。

Note： 這個連接詞的真值表如下： A｜B TFT TTF FTT FTF postedby rossignol lable 哲學, 邏輯 9comments: AnonymousMarch29,2011at9:44AM看不懂.不過文章最後Note中似有矛盾.ReplyDeleteRepliesReplyrossignolMarch30,2011at12:56AM我目前還不曉得要怎麼寫它才會比較好懂…哪裡有矛盾？ReplyDeleteRepliesReplyAnonymousMarch31,2011at1:37AM矛盾是指"|"連接詞真值表的末兩行.應該是typoReplyDeleteRepliesReplyrossignolMarch31,2011at8:26AM你覺得末兩行應該怎麼修正才不會矛盾？不過，「｜」的真值表是被規定成這樣的，你頂多只能說這個規定很奇怪，不能說這樣規定是不可行的。

ReplyDeleteRepliesReplyAnonymousMarch31,2011at9:17AM嗯我不知這"|"是一個怎樣的運算但看到同一組A,B輸入值(F,T),產生不同的輸出值就覺得不對.要不在定義上就可以說它對(F,T)輸入沒有定義.是否我有基本觀念上的錯誤?謝謝撥空回覆.ReplyDeleteRepliesReplyrossignolApril1,2011at1:47AM這個運算符號的定義可以寫成這樣：v'(φ|ψ)=1iffv'(φ)=0orv'(ψ)=0v'(φ|ψ)=0iffv'(φ)=1andv'(ψ)=1那些奇怪的符號的意思可以參考這篇文章的語意的部分。

ReplyDeleteRepliesReplyAnonymousApril1,2011at8:29AM定義中,v'(φ|ψ)=1iffv'(φ)=0orv'(ψ)=0包含3種情況:A,B,A|BFFTFTTTFTv'(φ|ψ)=0iffv'(φ)=1andv'(ψ)=1則僅指A,B,A|BTTF按照這連接詞「｜」定義則真值表最後一行則應改為:FFT且不論定義為何原來的3,4行FTTFTF就衝突有趣的連接詞我還沒找到應用題ReplyDeleteRepliesReplyisaacstnApril1,2011at12:18PM@Anonymous你大概誤會了,原文的最後兩行並不是「同一組輸入值」。

你的輸入輸出的寫法是：[輸入],[輸入],[輸出]。

而Note裡的寫法則是[輸入],[輸出],[輸入]。

所以沒有衝突。

ReplyDeleteRepliesReplyAnonymousApril1,2011at11:17PM啊誤會誤會尷尬ReplyDeleteRepliesReplyAddcommentLoadmore... 為了避免辛辛苦苦寫的留言送出後就不見，你可以在送出前把它複製到別處。

如果留言一直沒顯示，可能是被系統當成垃圾留言擋下來。

你可以寄信到右上角的信箱叫我處理。

NewerPost OlderPost Home Subscribeto: PostComments(Atom) 啊啊安萍｜閒聊版｜-字體+ 啊啊哲學站內搜尋 中文分析哲學搜尋 哲學 (42) 邏輯 (22) 趣事 (17) 基本概念 (13) 中正哲學 (12) 嘉義大學史地學系 (11) 語言哲學 (10) 順便想到 (10) 閱讀 (9) 活動 (6) 啊啊哲學 (5) 形上 (5) 倫理學 (4) 學哲學 (4) 心靈哲學 (4) 知識論 (3) 地球與環境科學 (1) 科學哲學 (1) ###recentComment### 其他哲學部落格 哲學哲學雞蛋糕 線上哲學課｜厭女： 5monthsago Wenson的隨筆網站 優等生的現實 9monthsago 無法哲學 《高低階快樂與享樂主義的悖論》 10monthsago 幹哲學 愛的理由 4yearsago 哲與思 連結 TED 概念趴 簡單哲學作業簿 烏鴉邦 中正大學課程表 Posts Atom Posts Comments Atom Comments ►  2013 (3) ►  April (3) ►  2012 (1) ►  November (1) ▼  2011 (26) ►  October (3) ►  September (1) ►  August (3) ►  July (1) ►  June (2) ►  May (2) ►  March (2) ▼  February (9) 應觀眾要求 0.1是循環小數 碼書：編碼與解碼的戰爭 語句邏輯的完備性 語句邏輯的健全性 數學歸納法 語句邏輯的證明系統 語句邏輯的語法和語意 一百年中正哲學碩班甄試邏輯試題試答 ►  January (3) ►  2010 (50) ►  December (3) ►  November (1) ►  October (2) ►  September (2) ►  July (1) ►  June (3) ►  May (6) ►  April (7) ►  March (9) ►  February (10) ►  January (6) ►  2009 (26) ►  December (6) ►  November (4) ►  October (4) ►  August (4) ►  June (5) ►  April (3) 如果做到以下這三點，歡迎摘錄或轉貼啊啊哲學的文章而不必告知我： 1.標示「啊啊哲學」和原文章連結。

2.不能作商業用途。

3.可以更改這裡的文章，但要註明你有改過，而且更改後的成品也要採用和這裡一樣的授權方式。

更多詳情請點上方創用CC貼紙的連結。