##EasyReadMore##

2.25.2011

應觀眾要求

我在文章底下放了「讚」給手癢的讀者按。頌大俠去吧

沒有放「沒道理」或「看不懂」之類的選項是因為,只是按個鈕我怎麼知道文章是不是真的有問題、真的有問題的話是哪裡有問題勒。

2.24.2011

0.1是循環小數

數學系的集合論,黃英龍老師說0.1是循環小數,因為0.1可以寫成0.100000000000000000000...

真是嚇死我了。

2.20.2011

碼書:編碼與解碼的戰爭

這本書介紹了很多從以前到現在,隨著人們通訊技術發展因應而生的隱藏、加密和解密訊息的方式。例如,把訊息寫在信差剃光的頭皮上,等頭髮長長了信差再出發、用隱形墨水寫字、把訊息中的a用b替換,把b用c替換…把z用a替換後得到密碼文、網路上的公開鑰匙和私密鑰匙,以及量子電腦對密碼學可能的影響。其中也穿插了有趣的小故事、密碼學在軍事上應用的案例、加密者和解密者間的競賽。此外,書中有一章的內容是關於怎麼解讀古代文字。

有時候讀到密碼學家們解密的竅門時,真是讓我覺得,天啊這群人好聰明噢哈哈哈。我滿喜歡這本書的,喜歡到買了一本放在書櫃上。

以下節錄一些有趣的段落(括號的部分是我根據前後文加上去的):
  • (十六世紀末)西班牙的密碼專家,似乎比歐洲其他地方的對手天真。當他們發現法國人可以看透他們的訊息時,竟不願正視這件事實。西班牙國王菲力普二世甚且向梵諦岡陳情,宣稱維特(以破解西班牙密碼為樂的傢伙)之所以能破解西班牙密碼的唯一解釋是:「他是與撒旦結盟的魔王」。菲力普訴請樞機法庭審判維特的惡魔勾當。教宗深知自己的密碼分析家多年來也一向能破解西班牙的密碼,於是駁回他的陳情。這則新聞很快就傳到各國專家耳裡,西班牙的密碼專家頓時成為全歐洲的笑柄。
    .
  • (十九世紀後半期)民眾開始覺得需要保護它們高度敏感的私人通訊,必要時會進行加密,…(略)…一般大眾所用的密碼,對專業的密碼分析家而言是不堪一擊,但對付那些隨機窺探他人隱私的傢伙卻已綽綽有餘了。

    …(略)…有一次,惠斯頓(解碼專家)解譯了一名牛津學生刊在《泰唔士報》提議愛人與他一起私奔的啟事。幾天後,惠斯頓刊登他自己的啟事,也用同樣的密碼加密,勸告這對愛侶不要履行這項輕率、叛逆的計畫。稍後隨即出現第三則啟事,這次沒有加密,它是女方當事人發出的:「親愛的查理,不要再寫了。我們的密碼被發現了。」

2.19.2011

語句邏輯的完備性

如果你不太能理解這篇文章在幹嘛,建議先讀過下列文章。
完備性:如果Γ ⊧A,那麼Γ├A。如果不管語句們的真值設定是什麼,都不會出現Γ裡的語句都為真但A為假的情況,那麼Γ可以推導出某個語句A(Γ可以是空集合)(完備性是後設定理)。

PS系統的其中一種完備性證明:

證明簡介:
因為找不到方法為Γ ⊧A排序,所以不能像證明健全性那樣用數學歸納法做證明。不過,P→Q若且唯若¬Q→¬P,因此證明了
如果並非Γ├A,那麼並非Γ ⊧A
也就是證明了完備性。

另外,有人證明了
  • 並非Γ├A,若且唯若,Γ∪{¬A}是一致的,以及
  • 並非Γ ⊧A,若且唯若,Γ∪{¬A}有一個模型(model)。Γ∪{¬A}有一個模型的意思是,有個真值設定v,它的unique extension v'給Γ裡的語句和¬A的值都是1。
因此,證明了
如果Γ∪{¬A}是一致的,那麼Γ∪{¬A}有一個模型
 也就是證明了完備性。

假設前件(Γ∪{¬A}是一致的)為真,然後把Γ∪{¬A}擴充成最大化一致集合(maximal consistent set)Γ*,再根據Γ*做出一個真值設定v,而這個v會是Γ∪{¬A}的模型。得證如果Γ∪{¬A}是一致的,那麼Γ∪{¬A}有一個模型。得證語句邏輯的完備性。
  • 最大化一致集合的定義:Γ是最大化一致集合,若且唯若,Γ是一致的,而且對任何合法的語句A而言,如果A∉Γ,那麼Γ∪{A}是不一致的。
證明:

先證明跟最大化一致集合有關的兩個的引理(lemma)放著備用。
  1. 如果Γ是最大化一致集合,那麼對任何合法的語句A而言,要嘛A∈Γ,要嘛¬A∈Γ(Γ是最大化一致集合,所以不會有A∈Γ而且¬A∈Γ的情況)。

    使用反證法,假設前件成立而且後件不成立,如果能根據這些假設推導出矛盾的結果,就能得證前件成立時後件會成立。

    假設Γ是最大化一致集合,而且有個語句A,A∉Γ、¬A∉Γ。根據最大化一致集合的定義,Γ∪{A}和Γ∪{¬A}都是不一致的。根據一致的定義,從Γ∪{¬A}是不一致的這件事可以推論出會有某個語句B,Γ∪{¬A}├B而且Γ∪{¬A}├¬B。根據之前證明過的Γ, A├B若且唯若Γ├A→B定理,從Γ∪{¬A}├B而且Γ∪{¬A}├¬B,可以推論出Γ├¬A→B和Γ├¬A→¬B。

    根據├(¬A→B)→((¬A→¬B)→A)這條我目前還不知道是怎麼推論出來的定理,以及上一段最後一句的Γ├¬A→B和Γ├¬A→¬B,用MP規則可以推論出Γ├A。

    根據一致的定義,從Γ∪{A}是不一致的這件事可以推論出會有某個語句C,Γ∪{A}├C而且Γ∪{A}├¬C。根據A├B若且唯若Γ├A→B定理,從Γ∪{A}├C而且Γ∪{A}├¬C,可以推論出Γ├A→C和Γ├A→¬C。根據├A→¬¬A定理、Γ├A→C和Γ├A→¬C和MP規則,可以得到Γ├¬¬A→C和Γ├¬¬A→¬C。

    根據├(¬A→B)→((¬A→¬B)→A)定理,以及上一段最後一句的Γ├¬¬A→C和Γ├¬¬A→¬C,用MP規則可以推論出Γ├¬A。

    因此Γ├A而且Γ├¬A,Γ 不一致,Γ 不會是最大化一致集合。這個結果和我們的假設矛盾,得證如果Γ是最大化一致集合,那麼對任何合法的語句A而言,要嘛A∈Γ,要嘛¬A∈Γ。
    .
  2. 如果Γ是最大化一致集合,那麼對任何合法的語句A而言,如果Γ├A,那麼A∈Γ。

    用反證法。假設Γ是最大化一致集合,而且Γ├A而且A∉Γ。A∉Γ,根據最大化一致集合的定義,Γ∪{A}是不一致的。Γ∪{A}不一致,因此會有某個語句B,Γ∪{A}├B而且Γ∪{A}├¬B。根據A├B若且唯若Γ├A→B,可以得到Γ├A→B和Γ├→A¬B。根據Γ├A(假設)、Γ├A→B、Γ├→A¬B和MP,可以得到Γ├B和Γ├¬B。因此Γ不是最大化一致集合,和假設矛盾。
用Lindenbaum's lemma把Γ∪{¬A}擴充成最大化一致集合。
Lindenbaum's lemma:任何一致的集合Γ都可以擴充成最大化一致集合Γ*
證明:

找一個函數f,它的功能是把所有合法的語句從1開始編號。每個編號都不一樣。把Γ擴充成最大化一致集合Γ*的程序如下:
  • Γ0 = Γ(Γ0就是Γ)。
  • Γn+1 = Γn∪φn+1,如果Γn∪φn+1是一致的
    (如果Γn∪φn+1是一致的,那麼Γn+1 = Γn∪φn+1)。
    Γ1 = Γn,如果Γn∪φn+1是不一致的
    (如果Γn∪φn+1是不一致的,那麼Γn+1 = Γn)。
  • Γ* = ∪n∈ωΓn(Γ* = Γ0∪Γ1∪Γ2∪...Γn∪...,ω是指自然數的集合。根據定義不能聯集一串無限大的集合,所以Γ* = Γ0∪Γ1∪Γ2∪...Γn∪...的寫法是不合法的)。
證明對任何屬於ω的n來說,Γn是一致的(弱數學歸納法):
  • B.C.:Γ0根據預設是一致的。
  • I.H.:假設Γn是一致的。
  • I.C.:從Γn變成Γn+1有兩種情況。一,Γn∪φn+1是一致的,那麼Γn+1 = Γn∪φn+1,在這種情況下Γn+1是一致的。二,Γn∪φn+1是不一致的,那麼Γn+1 = Γn,根據I.H.,Γn+1是一致的。
故得證對任何屬於ω的n來說(for any n∈ω),Γn是一致的。

證明每個Γ*的子集合都是某些Γn的子集合(反證法):
假設有個Γ*的子集合α,α不是任何Γn的子集合,因此,α裡的某些語句φ不屬於任何Γn。然而,Γ* = ∪n∈ωΓn,所以屬於Γ*的語句一定會屬於某個Γn

證明Γ*是一致的(反證法):
假設Γ*是不一致的,因此對某個語句A而言Γ*├A而且Γ*├¬A。在推導是有限長的情況下,被拿來當前提的語句也會是有限多個。把推導出A的前提們稱做α,α是Γ*的子集合;把推導出¬A的前提們稱做β,β是Γ*的子集合。讓Γ等於α聯集β,Γ也會是Γ*的子集合,此外,Γ├A而且Γ├¬A。出現了有個Γ*的子集合是不一致的情況。然而根據之前證明過的,
  • 每個Γ*的子集合都是某些Γn的子集合
  • 對任何屬於ω的n來說,Γn是一致的
因此Γ會是一致的。產生矛盾,因此Γ*是一致的。

證明Γ*是最大化的(反證法):
假設Γ*不是最大化的,因此,會有某個語句A,A∉Γ*,而且Γ*∪{A}是一致的。然而,A會被標上某個編號,例如Am,因為Γ*∪{A}是一致的,所以A∈Γm,所以A∈Γ*。產生矛盾,因此Γ*是最大化的。
於是就證明了任何一致的集合Γ都可以擴充成最大化一致集合Γ*
用Γ*做出一個特別的真值設定v。
這個特別的真值設定v是長這樣的:
  • v(A) = 1,若且唯若,φ是原子語句而且φ∈Γ*
  • v(A) = 0,若且唯若,φ是原子語句而且φ∉Γ*
Henkin Lemma:這個特別的真值設定v的v',對任何合法語句φ而言,φ∈Γ*若且唯若v'(φ) = 1。
證明(強數學推納法,用φ裡的連接詞數量做排序):
  • B.C.:φ是原子語句,根據那個特別的真值設定v的定義,φ∈Γ*若且唯若v'(φ) = 1。
  • I.H.:假設,對所有連接詞數量小於n的合法語句而言,φ∈Γ*若且唯若v'(φ) = 1。
I.C.:當φ的連接詞數量是n的時候,要嘛φ = ¬ψ,要嘛φ = ψ→χ。
  1. φ = ¬ψ
    ψ的連接詞數量是n-1,根據I.H.,ψ∈Γ*若且唯若v'(ψ) = 1。v'(φ) = 1若且唯若v'(ψ) = 0,v'(ψ) = 0若且唯若ψ∉Γ*。因為Γ*是最大化一致集合,根據之前證的「如果Γ是最大化一致集合,那麼對任何合法的語句A而言,要嘛A∈Γ,要嘛¬A∈Γ」,ψ∉Γ*所以¬ψ∈Γ*。因此φ∈Γ*。 
  2. .
  3. φ = ψ→χ
    ψ和χ的連接詞數量都小於n。

    (如果φ∈Γ*則v'(φ) = 1)(反證法)
    假設φ∈Γ*而且v'(φ) = 0。v'(φ) = 0,所以v'(ψ) = 1而且v'(χ) = 0。v'(ψ) = 1而且v'(χ) = 0,根據I.H.,ψ∈Γ*而且χ∉Γ*。根據χ∉Γ*和「如果Γ是最大化一致集合,那麼對任何合法的語句A而言,要嘛A∈Γ,要嘛¬A∈Γ」,可以推論出¬χ∈Γ*。因為ψ∈Γ*和¬χ∈Γ*,所以Γ*├ψ而且Γ*├¬χ。根據定理├ψ→(¬χ→¬(ψ→χ))和MP,得到Γ*├¬(ψ→χ)。根據Γ*├¬(ψ→χ)和之前證的「如果Γ是最大化一致集合,那麼對任何合法的語句A而言,如果Γ├A,那麼A∈Γ」,可以得到¬(ψ→χ)∈Γ*。因此¬φ∈Γ*。因此φ∈Γ*而且¬φ∈Γ*,所以Γ*├φ而且Γ*├¬φ,Γ*是不一致的。這個結果和Γ*是一致的預設矛盾。
    .
    (如果v'(φ) = 1則φ∈Γ*
    假設v'(φ) = 1,所以v'(ψ) = 0或v'(χ) = 1。根據I.H.,ψ∉Γ*或χ∈Γ*

    1.ψ∉Γ*
    根據「如果Γ是最大化一致集合,那麼對任何合法的語句A而言,要嘛A∈Γ,要嘛¬A∈Γ」,¬ψ∈Γ*,因此Γ*├¬ψ。根據Γ*├¬ψ、定理├¬ψ→(ψ→χ)和MP可以得到Γ*├ψ→χ。根據Γ*├ψ→χ和「如果Γ是最大化一致集合,那麼對任何合法的語句A而言,如果Γ├A,那麼A∈Γ」,可以得到ψ→χ∈Γ*,也就是φ∈Γ*

    2.χ∈Γ*
    χ∈Γ*,所以Γ*├χ。根據公理├χ→(ψ→χ)和Γ*├χ和MP可以得到Γ*├ψ→χ。根據Γ*├ψ→χ和「如果Γ是最大化一致集合,那麼對任何合法的語句A而言,如果Γ├A,那麼A∈Γ」,可以得到ψ→χ∈Γ*,也就是φ∈Γ*
得證Henkin Lemma。
完備性:Γ ⊧A則Γ├A。
Γ ⊧A則Γ├A,若且唯若,並非Γ├A則並非Γ ⊧A,若且唯若,Γ∪{¬A}是一致的則Γ∪{¬A}有一個模型。

Γ∪{¬A}是一致的,所以可以用Lindenbaum's lemma把Γ∪{¬A}擴充成最大化一致集合Γ*,然後用Γ*做出一個特別的真值設定v。根據Henkin Lemma,因為Γ∪{¬A}裡的語句都屬於Γ*,所以這個v的v'給Γ∪{¬A}裡的語句的值都會是1,因此Γ∪{¬A}有一個模型。
得證語句邏輯的完備性。

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

2.14.2011

語句邏輯的健全性

如果你不太能理解這篇文章在幹嘛,建議先讀過下列文章。
健全性(soundness):如果Γ├A,那麼Γ ⊧A。如果某組語句Γ可以推導出某個語句A,那麼不管語句們的真值設定是什麼,都不會出現Γ裡的語句都為真但A為假的情況(Γ可以是空集合)(健全性是後設定理)。

PS系統的健全性證明:

使用強數學歸納法,用推論出A需要幾行證明為Γ├A排序。

B.C.當證明行數為1的時候,A要嘛是公理,要嘛是前提。
  • A是公理:
    1. 公理1:├A→(B→A)
      如果有個真值設定v讓v'(A→(B→A)) = 0(讓A→(B→A)為假),那麼v'(A) = 1而且v'(B→A) = 0。想讓v'(B→A) = 0,那麼v'(B) = 1而且v'(A) = 0。但是v'(A)在之前設定的值是1(畫底線的地方),所以找不到讓v'(A→(B→A)) = 0的真值設定。因此 ⊧A→(B→A)成立。
      .
    2. 公理2:├(A→(B→C))→((A→B)→(A→C))
      如果有個真值設定v讓v'((A→(B→C))→((A→B)→(A→C))) = 0,那麼v'(A→(B→C)) = 1而且v'((A→B)→(A→C)) = 0。讓v'((A→B)→(A→C)) = 0,那麼v'(A→B) = 1而且v'(A→C) = 0。讓v'(A→C) = 0,那麼v'(A) = 1而且v'(C) = 0。v'(A) = 1,所以要讓v'(A→B) = 1的話,v'(B) = 1。但是v'(A) = 1而且v'(C) = 0而且v'(B) = 1的話,v'(A→(B→C)) = 0,和之前v'(A→(B→C)) 設定的值(畫底線處)不同。因此找不到讓v'((A→(B→C))→((A→B)→(A→C))) = 0的真值設定。⊧(A→(B→C))→((A→B)→(A→C))成立。
      .
    3. 公理3:├(¬A→¬B)→(B→A)
      如果有個真值設定v讓v'((¬A→¬B)→(B→A)) = 0,那麼v'(¬A→¬B) = 1而且v'(B→A) = 0。讓v'(B→A) = 0,那麼v'(B) = 1而且v'(A) = 0。但是如此一來會讓v'(¬A→¬B) = 0,所以⊧(¬A→¬B)→(B→A)成立。
      .
  • A是前提:
    當前提裡的所有語句φ在某個真值設定v底下,v'(φ) = 1,那麼v'(A)當然也會是1。
I.H.假設,當Γ├A的證明長度小於n時,如果Γ├A則Γ ⊧A。

I.C.當Γ├A的證明長度等於n時,A要嘛是公理,要嘛是前提,要嘛是用MP規則推論出來的。
A是公理的話,在B.C.已經證明公理都是恆真句了,所以Γ⊧A(A是公理)。

A是前提的情況,證明方式和B.C.差不多。

A是用MP規則推論出來的,也就是說,A是如下推論出來的:
第1行:Γ├某個句子
第2行:Γ├某個句子

第 i 行:Γ├B→A

第 j 行:Γ├B

第 n 行:Γ├A(根據第i行、第j行及MP)

因為第 i 行和第 j 行的推論長度都小於第 n 行,所以它們都可以使用I.H.做推論。所以可以得到Γ⊧B→A和Γ⊧B。Γ⊧B→A的意思是,在任何真值設定v下,如果有v'讓Γ裡所有語句的值都是1,那麼那個v'也會讓B→A的值是1(v'(B) = 0 或v'(A) = 1)。Γ⊧B的意思是,在任何真值設定v下,如果有v'讓Γ裡所有語句的值都是1,那麼那個v'也會讓B的值是1

根據上一段畫了底線的那兩句話,可以知道,在Γ⊧B→A和Γ⊧B都成立的情況裡,
在任何真值設定v下,v'(A) = 1。因此,在Γ⊧B→A和Γ⊧B都成立的情況裡,Γ⊧A也成立。
得證PS這個證明系統的健全性。

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

2.13.2011

數學歸納法

數學歸納法(proof by induction)是集合論裡的定理(theorem)。這個定理用在語句邏輯上大概是這個樣子:
想證明某一類型的合法語句都具有某個性質P,就得先為該類型的語句們用自然數排序(例如句子裡面沒有連接詞的語句們的排序是0,有一個連接詞的語句們的排序是1之類的),然後就可以用數學歸納法了。

先證明排序中最小的語句們(例如,如果是用語句的連接詞數量來排序,那麼最小的排序是0;如果是用推論的長度來排序,那麼最小的排序是1)有性質P(base case),然後假設排序n的語句們有性質P(inductive hypothesis),再利用假設證明排序為n+1的語句們也有性質P(inductive case)。這樣就能得到我們想要的結論:任何排序的語句都有性質P。
有三種使用數學歸納法的方式,弱歸納法(weak induction)、強歸納法(strong induction)和良序歸納法(well-ordering induction)。但是我不清楚良序歸納法是什麼就不寫了。

弱歸納法
  • Base Case:證明最小的排序有性質P。
  • Inductive Hypothesis:假設排序為n的語句有性質P。
  • Inductive Case:用IH證明排序為n+1的語句有性質P。
    得證任何排序的語句都有性質P。
強歸納法
  • Base Case:證明最小的排序有性質P。
  • Inductive Hypothesis:假設排序小於n的語句都有性質P。
  • Inductive Case:用IH證明排序為n的語句有性質P。
    得證任何排序的語句都有性質P。(強歸納法的範例可以在這篇文章裡找到)

數學歸納法的部分我沒有讀得很清楚,所以這篇不是寫得很好。Kiki有在講義附上參考書目(Causey R. (2001), Logic, Sets, and Recursion.),有興趣的人可以找來看看。

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

2.12.2011

語句邏輯的證明系統

 (這裡用的A、B、C可以替換成其他合法的語句)

證明系統裡有公理(axiom)和推論規則(rule of inference)這兩個部分。

Kiki上課時用的證明系統(PS系統)裡只用了兩個連接詞,¬和→。不過我忘記要怎麼證明這兩個連接詞就夠用了。另外,Kiki有提到其實只要「|」這個連接詞*1就夠用。證明系統的公理越少,以後在證明健全性和完備性時會比較簡單,但是做推論時會比較麻煩,要寫好幾行才能推論出想要的東西。

PS系統裡會用到「├」這個符號,如果我沒記錯的話這個符號的名字是single term style。
證明(proof):├A
意思是A是公理,或A是由公理和推論規則產生的。A不需要任何前提就能堆論出來。

推導(deduction):Γ├A
意思是A是由Γ這組前提,以及公理和推論規則產生的語句。Γ是由語句們形成的集合。當Γ├A裡的Γ是空集合時,它就是├A。

一致(consistency):
Γ 是個一致的集合,若且唯若,對於某個語句A而言,不會有Γ├A而且Γ├¬A的情況發生。
PS系統的公理:
  1. ├A→(B→A)
  2. ├(A→(B→C))→((A→B)→(A→C))
  3. ├(¬A→¬B)→(B→A)
PS系統的推論規則:Modus Ponens(MP)
  • 由├A→B和├A可以得到├B,或者
  • A→B, A├B
有了公理和推論規則後,就可以推論出其它定理(theorem)(因為還沒證明語句邏輯的健全性完備性,所以不能用語句的真假值來證明這些定理):

推導├A→A。
  1. ├A→((A→A)→A)                                          公理1
  2. ├(A→((A→A)→A))→((A→(A→A))→(A→A))   公理2
  3. ├(A→(A→A))→(A→A)                                  1,2,MP
  4. ├A→(A→A)                                                  公理1
  5. ├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時推導的長度是五行)。
Base Case:
證明當Γ, A├B推導的長度是一行時,Γ, A├B則Γ├A→B會成立。

Γ, A├B推導的長度是一時,要嘛B和A是同一個語句,要嘛B是公理或Γ裡的某個語句。
  1. B和A是同一個語句:
    那麼根據├A→A這個定理,Γ├A→B會成立。
  2. B是公理:
    因此Γ├B。加上公理1Γ├B→(A→B),使用MP規則可以得到Γ├A→B。
  3. B是Γ裡的某個語句:
    因此Γ├B。加上公理1Γ├B→(A→B),使用MP規則可以得到Γ├A→B。
Inductive Hypothesis:
假設當Γ, A├B的推導長度小於n時,Γ, A├B則Γ├A→B會成立。

Inductive Case:
利用Inductive Hypothesis證明當Γ, A├B推導的長度是n行時,Γ, A├B則Γ├A→B會成立。

Γ, A├B推導的長度是n時,要嘛B和A是同一個語句,要嘛B是公理或Γ裡的某個語句,要嘛B是用MP規則推論出來的。
  1. B和A是同一個語句:證明方式和Base Case一樣。
  2. B是公理:同上。
  3. B是Γ裡的某個語句:同上。
  4. B是用MP規則推論出來的:
    也就是說,B是這樣推論出來的:
    第1行:Γ, A├某個句子
    第2行:Γ, A├某個句子

    第 i 行:Γ, A├C→B

    第 j 行:Γ, A├C

    第 n 行:Γ, A├B(根據第i行、第j行及MP)

    因為第 i 行和第 j 行的推論長度都小於第 n 行,所以它們都可以使用Inductive Hypothesis做推論。所以Γ, 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:
  1. 這個連接詞的真值表如下:
    A|B
    T F T
    T T F
    F T T
    F T F

2.02.2011

語句邏輯的語法和語意

(用φ、ψχ代表合法的語句,用Γ、Σ、Φ、Δ代表合法語句的集合 )
語法(syntax)

定義合法的邏輯符號:
  • ¬、∧、∨、→、↔ (邏輯連接詞)
  • A、A1、A2、…B、B1、B2、… (有可數無限大那麼多的語句符號)
  • (、) (括號)
定義合法的語句(well-formed formula,wff):
  1. A、A1、A2、…、B、B1、B2、…這些都是合法的語句。
  2. 如果φ和ψ都是合法的語句,那麼下列這些也是:
    ¬φ、¬ψ
    φ∧ψ
    φ∨ψ
    φ→ψ
    φ↔ψ
  3. 只有符合前兩點的才是合法的句子。
這樣的定義被稱為遞迴定義(recursive definition)。當你要確定某串符號是不是符合定義,就得一直往前追朔其他東西是不是符合定義。例如,要檢查(A∧C)→(↔B)是不是wff,就得檢查(A∧C)和↔B是不是wff(根據定義2)。要檢查A∧C是不是wff,就得看A和C是不是wff(根據定義2);A和C是wff(根據定義1),所以A∧C是wff。而↔B不符合定義1也不符合定義2,所以它不是wff(根據定義3)。因此,(A∧C)→(↔B)不是wff。

使用遞迴定義的好處是只要寫幾行字就夠了,而且以後可以用數學歸納法做推論。

語意(semantics)

語意談論的是語句的真假值。賦予語句真假值的是函數v(被稱為structure或interpretation)和函數v'(v的unique extension)。

函數v的定義域是語句符號(sentence letter,SL)的集合;對應域則是{0,1},1代表真,0代表假。換句話說,v會給每個原子語句(atomic sentence,原子語句是沒有用到任何邏輯連接詞的wff)設定真假值。(相關文章:Number of Structures in Sentential Logic - 哲學與思方)

v'的定義域是wff,對應域是{0,1}。詳情如下:
  • v'(φ)=1 iff v(φ)=1
    v'(φ)=0 iff v(φ)=0
    v'給φ的真值設定為真,若且唯若,v給φ的真值設定為真。
    v'給φ的真值設定為假,若且唯若,v給φ的真值設定為假。
  • v'(¬φ)=1 iff v'(φ)=0
    v'(¬φ)=0 iff v'(φ)=1
    v'給¬φ的真值設定為真,若且唯若,v'給φ的真值設定為假。
    v'給¬φ的真值設定為假,若且唯若,v'給φ的真值設定為真。
  • v'(φ∧ψ)=1 iff v'(φ)=1 and v'(ψ)=1
    v'(φ∧ψ)=0 iff v'(φ)=0 or v'(ψ)=0
    .
  • v'(φ∨ψ)=1 iff v'(φ)=1 or v'(ψ)=1
    v'(φ∨ψ)=0 iff v'(φ)=0 and v'(ψ)=0
    .
  • v'(φ→ψ)=1 iff v'(φ)=0 or v'(ψ)=1
    v'(φ→ψ)=0 iff v'(φ)=1 and v'(ψ)=0
    .
  • v'(φ↔ψ)=1 iff v'(φ)=v'(ψ)
    v'(φ↔ψ)=0 iff v'(φ)¹v'(ψ)
v只能為原子語句設定真假值,但是v的unique extension v'可以(根據v對原子語句的真值設定)為任何wff設定真假值。

定義完v和v'以後,就可以定義語句邏輯裡的恆真句(tautology)和蘊含(tautological consequence)了:
  • tautological consequence:
    Γ ⊧φ iff ∀v, if ∀x∈Γ , v'(x)=1, then v'(φ)=1
    某一組語句Γ 邏輯蘊含語句φ,若且唯若,對所有的v而言(不同的v會給原子語句們不同的真假值),如果有v的unique extension v'使的Γ 裡的語句全部為真時,該v'也會讓φ為真。
    換句話說,某一組語句Γ 邏輯蘊含語句φ,若且唯若,不管Γ 和φ裡包含的原子語句們的真值設定是什麼,當Γ 裡的語句都為真時,φ也會為真。
    再換句話說,某一組語句Γ 邏輯蘊含語句φ,若且唯若,找不到可以讓Γ 裡的語句都為真而且φ為假的真值設定。
    .
  • tautology:
    ∅⊧φ
    某個語句φ是恆真句,若且唯若,對所有的v而言,v的unique extension v'都會讓φ為真。
    換句話說,某個語句φ是恆真句,若且唯若,不管φ裡包含的原子語句們的真值設定是什麼,φ都會為真。
根據上述對⊧這個關於語句之間的關係(relation)的定義,我們可以發現它有幾個有趣的性質:
  • 自反性(reflexivity):φ⊧φ
  • 喀嚓*1(cut):if Γ, φψ and Σ, ψ⊧χ, then Γ, Σ, φ⊧χ
  • 單調性(monotonicity):if Γ⊧φ, then Γ,Σ⊧φ
  • conditionalization:⊧φ→ψ iff φ⊧ψ
    (有修過蔡行健老師的基礎邏輯一的同學,這個就是(⊧,→)規則)
  • clourse under MP:if Γ⊧φ→ψ and Γ⊧φ, then Γψ
不相信的人可以自己檢查看看。


在這篇文章裡,我們用中文、英文、希臘字母和集合論描述語句邏輯。因此,中文、英文、希臘字母和集合論是後設語言(metalanguage),語句邏輯是目標語言(object language)。⊧不是邏輯符號,v和v'也不是,因為語法在定義合法的邏輯符號時沒有說它們是邏輯符號。⊧、v和v'是後設語言,不是目標語言。

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

Note:
  1. 來自老胡的可愛翻譯。

2.01.2011

一百年中正哲學碩班甄試邏輯試題試答

小丸子昨天傳了這份試題給我看,寫完以後順便放上來討建議。

是非題
  1. [(A∧¬B)∨(B∧¬C)∨(C∧¬A)]→[(A∧B∧C∧D)→(E↔F)] is a tautology.

    T。
    要讓條件句為假,(A∧¬B)∨(B∧¬C)∨(C∧¬A)得為T,(A∧B∧C∧D)→(E↔F)得為F。要讓(A∧B∧C∧D)→(E↔F)是F,那麼A∧B∧C∧D要為T、E↔F為F。A∧B∧C∧D要為T的話,(A∧¬B)∨(B∧¬C)∨(C∧¬A)就會為F,所以找不到讓題幹的句子為假的真值設定。
    .
  2. ∃x(P(x)↔R(x)) is logically equivalent to ∃xP(x)↔∃xR(x).

    F。反例:Domain = {0,1} P = {0} R = {1},此時∃xP(x)↔∃xR(x)為T,∃x(P(x)↔R(x))為F。
    .
  3. Assume that only one of the following two sentences is true: (1) Pigs can fly unless Kant is not right; (2) Kant is not right only if pigs can fly. Based on this assumption, it is true that (3) if pigs can fly, then I will cry.

    T。
    P:Pigs can fly。K:Kant is right。I:I will cry。
    (1)P∨¬K (2)¬K→P (3)P→I
    因為(1)和(2)裡只有一句話為真,所以P要為假(P為真的話兩句話都會為真)。因此P→I為真。
    .
  4. If P and S are consistent and S and Q are inconsistent, then P cannot imply Q.

    T。
    在P和Q是一致的,而且S和Q是不一致的,而且P蘊含Q的情況下,當P為真時Q也會為真(P蘊含Q)、P和S可以同時為真(P和Q是一致的),所以會有個情況是P、Q和S同時為真。但是這結果和S和Q是不一致的預設矛盾,所以P不蘊含Q。
    .
  5. Suppose that most philosophers are truth-pursuers and that most truth-pursuers are smart. Then we can conclude that most philosophers are smart.

    F。反例:











給反例
  1.  ∃x(Px→∀yRy) /\∃xPx→∀yRy

    Model = (D, PM, RM), Domain = {0,1}, PM = {0}, RM = ∅
    .
  2.  ∀x¬R(x, x)∧∀x∃yR(x, y)∧∀x∀y∀z(R(x, y)→(R(y, z)→R(x, z))) /\∃x∀y(¬x=y→R(x, y))

    Model = (D, RM),Domain = 整數的集合,RM = 我們平常對小於符號「<」的解釋
符號化

Let “Lxy”stand for “x loves y”,
      “Hxy”stand for “x hates y”and
      “Px”stand for “x is a philosopher”.
Please symbolize the following sentence.

There is some philosopher who hates exactly two persons who are not philosophers and who love each other but no one else.

∃x(Px∧∃y∃z(Hxy∧Hxz∧∀w(Hxw→(w=y∨w=z))∧¬Py∧¬Pz∧Lyz∧Lzy∧∀w(Lyw→w=z)∧∀w(Lzw→w=y)))

證明

1. ∀x¬[(Px↔Rx)↔Qx]
2. ∃x∃y(¬Rx∨Sxy)                  /\∃x∃y[Qx→(¬Sxy→Px)]
3. ¬∃x∃y[Qx→(¬Sxy→Px)]          AIP
4. ∀x∀y¬[Qx→(¬Sxy→Px)]        3,QN
5. ¬Rx∨Sxy                                  2,EI
6. ¬[(Px↔Rx)↔Qx]                    1,UI
7. ¬[Qx→(¬Sxy→Px)]                  4,UI
8. Qx∧¬Sxy∧¬Px                         7,DN, Impl, DeM
9. ¬Sxy                                         8,Simp
10. ¬Rx                                         5,9,DS
11. (Px↔Rx)↔¬Qx                    6,¬(A↔B)≡A↔¬B
12. ((Px→Rx)∧(Rx→Px))→¬Qx  11,Equiv, Simp
13. (Px→Rx)→((Rx→Px)→¬Qx)  12,Exp
14. ¬Px∨Rx                                  8,Simp, Add
15. Px→Rx                                   14,Impl
16. Rx→Px                                   10,Add, Impl
17. ¬Qx                                        13,15,16,MP
18. Qx                                          8,Simp
19. ¬Qx∧Qx                                 17,18,Conj
20. ∃x∃y[Qx→(¬Sxy→Px)]          3-19,IP

相關文章:
九十九年中正哲學碩班甄試邏輯試答 - 啊啊哲學