2013年8月14日

古典邏輯總共有五個邏輯連詞(logical connectives),分別是「∽」、「∧」、「∨」、「→」和「↔」。這五個邏輯連詞可互相定義,例如可用只包含 ∽ 和 ∨ 的「∽p∨q」來定義「p→q」。 ∽ 和 ∨ 足以定義 → ,代表原本用 → 表達的 wff 都可改由只包含 ∽ 和 ∨ 的 wff 表達,也就是能把 → 刪去而不影響古典邏輯的表達力。由此引發一個問題:古典邏輯的連詞可減少到哪個程度(同時又不會削弱表達力)?

若只從原有的五個連詞裡,挑選其中一些來定義剩餘的連詞,最多可到減到只剩兩個。在此之前,先看看如何將連詞減到只有 ∽ 、 → 和 ∧ 三個。方法很簡單,只要證明餘下的 ∨ 和 ↔ 能透過剛才三個連詞定義便可。假定 p 和 q 是任意的 wff ,包含 ∨ 和 ↔ 的 wff 都可定義成:

(p∨q) ≡ (∽p→q)
(p↔q) ≡ ((p→q)∧(q→p))

舉例來說,「A→(B∨C)」可用「A→(∽B→C)」表達;而「~(A↔B)」則能改成「~((A→B)∧(B→A))」。由於 ∽ 、 ∧ 和 → 三者就擁有原本五個連詞的表達力,這情況可以稱做「{∽, ∧, →} is adequate」。(Theodore Sider 在 Logic for Philosophy 用 “adequate” ,Herbert Enderton 在 A Mathematical Introduction to Logic 用 “complete”)

原本五個連詞可減到只剩兩個,但會是哪兩個?答案不止一種,因為有幾個組合都足以定義剩餘的連詞,其中最常見的三個組合是 {∽, →} 、 {∽, ∧} 和 {∽, ∨}。證明 {∽, →} is adequate 可偷懶,利用前面的已用過的定義。由於最初已證明 ∽ 、 → 和 ∧ 可定義餘下兩個連詞,現在只要證明 ∧ 可進一步由 ∽ 和 → 定義,便證明了 ∽ 和 → 可定義其他三個連詞。用 ∽ 和 → 定義 ∧ 的方法很簡單:

(p∧q) ≡ (∽(p→∽q))

要看出這偷懶的方法為何可行,我將完整的定義列出來(把原先出現 ∧ 的地方都換成相應的 ∽ 和 →):

(p ∧ q) ≡ ((p→∽q))
(p∨q) ≡ (∽p→q)
(p↔q) ≡ (((p→q)→∽(q→p)))

同樣地,要證明 {∽, ∧} is adequate ,只需證明 ∽ 和 ∧ 足以定義 →。

(p→q) ≡ (∽(p∧∽q))

再來是 {∽, ∨} 。偷懶的方法是用這兩個連詞定義 ∧ 或 → ,因為已證明後者配合 ∽ 就有足夠的表達力,若證明 ∽ 和 ∨ 能定義(例如) → ,代表 {∽, ∨} 也足以表達 {∽, →} 能表達的。不過我好像一直都在偷懶,所以接下來乾脆將全部列出來:

(p∧q) ≡ (∽(∽p∨∽q))
(p→q) ≡ (∽p∨q)
(p↔q) ≡ (∽(p∨q)∨(∽(∽p∨∽q)))

最後的問題是:有沒有辦法只用一個連詞便有原本五個連詞的表達力(表達所有原本五個連詞能表達的語句)?有,不過那不是古典邏輯原有的連詞。總共有兩個這樣的二位連詞(binary connectives)。一個是著名的 Sheffer stroke 「|」,「 p|q 」的意思是「並非: p 和 q」;另一個是「↓」,「 p↓q 」的意思是「並非: p 或 q」。它們的真值表分別是:


這兩個二位連詞十分厲害,只消其中一個便足以定義古典邏輯五個連詞。換句話說,你可以只用 | 或只用 ↓ 來定義以下五種 wff :

∽p
p∧q
p∨q
p→q
p↔q

至於如何定義,我就不再多講了,有興趣可以思考思考。

0 comments:

張貼留言

 
Toggle Footer