啊啊哲學

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）放著備用。

如果Γ是最大化一致集合，那麼對任何合法的語句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∈Γ。
.
如果Γ是最大化一致集合，那麼對任何合法的語句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開始編號。每個編號都不一樣。把Γ擴充成最大化一致集合Γ^*的程序如下：

Γ₀ = Γ（Γ₀就是Γ）。

Γ_n+1 = Γ_n∪φ_n+1，如果Γ_n∪φ_n+1是一致的
（如果Γ_n∪φ_n+1是一致的，那麼Γ_n+1 = Γ_n∪φ_n+1）。
Γ₁ = Γ_n，如果Γ_n∪φ_n+1是不一致的
（如果Γ_n∪φ_n+1是不一致的，那麼Γ_n+1 = Γ_n）。

Γ^* = ∪_n∈ωΓ_n（Γ^* = Γ₀∪Γ₁∪Γ₂∪...Γ_n∪...，ω是指自然數的集合。根據定義不能聯集一串無限大的集合，所以Γ^* = Γ₀∪Γ₁∪Γ₂∪...Γ_n∪...的寫法是不合法的）。

證明對任何屬於ω的n來說，Γ_n是一致的（弱數學歸納法）：

B.C.：Γ₀根據預設是一致的。

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會被標上某個編號，例如A_m，因為Γ^*∪{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的時候，要嘛φ = ¬ψ，要嘛φ = ψ→χ。

φ = ¬ψ
ψ的連接詞數量是n-1，根據I.H.，ψ∈Γ^*若且唯若v'(ψ) = 1。v'(φ) = 1若且唯若v'(ψ) = 0，v'(ψ) = 0若且唯若ψ∉Γ^*。因為Γ^*是最大化一致集合，根據之前證的「如果Γ是最大化一致集合，那麼對任何合法的語句A而言，要嘛A∈Γ，要嘛¬A∈Γ」，ψ∉Γ^*所以¬ψ∈Γ^*。因此φ∈Γ^*。
.
φ = ψ→χ
ψ和χ的連接詞數量都小於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是前提的情況，證明方式和B.C.差不多。

A是用MP規則推論出來的，也就是說，Ａ是如下推論出來的：
第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系統的公理：

├A→(B→A)
├(A→(B→C))→((A→B)→(A→C))
├(¬A→¬B)→(B→A)

PS系統的推論規則：Modus Ponens（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時推導的長度是五行）。

Base Case：
證明當Γ, 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。

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規則推論出來的。

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

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 行，所以它們都可以使用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：

這個連接詞的真值表如下：
A｜B
T F T
T T F
F T T
F T F

2.02.2011

語句邏輯的語法和語意

（用φ、ψ、χ代表合法的語句，用Γ、Σ、Φ、Δ代表合法語句的集合）

語法（syntax）

定義合法的邏輯符號：

¬、∧、∨、→、↔　（邏輯連接詞）
A、A₁、A₂、…B、B₁、B₂、…　（有可數無限大那麼多的語句符號）
(、)　（括號）

定義合法的語句（well-formed formula，wff）：

A、A₁、A₂、…、B、B₁、B₂、…這些都是合法的語句。
如果φ和ψ都是合法的語句，那麼下列這些也是：
¬φ、¬ψ
φ∧ψ
φ∨ψ
φ→ψ
φ↔ψ
只有符合前兩點的才是合法的句子。

這樣的定義被稱為遞迴定義（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'是後設語言，不是目標語言。