連詞只包含「∼」和「↔」的合規式

我之前用「⊖」表示一個二位連詞,並嘗試證明只包含這連詞的合規式 (wff) ,無論如何建構,都與某個只包含「∼」和「↔」的合規式等值,例如:

p⊖q ⇔ ∼(p↔q)
(p⊖q)⊖r ⇔ ∼(∼(p↔q)↔r)
(p⊖q)⊖(r⊖s) ⇔ ∼(∼(p↔q)↔∼(r↔s))

然後我證明只包含 ⊖ 的合規式,在四行真值表裡最後一欄必定是四個T,四個F,或兩個T兩個F。然而,只包含 ∼ 和 ↔ 的合規式會否有其他組合方式,例如 ∼(p↔∼q) 或 ∼(p↔(∼p↔q)) ,使得四行真值表最後一欄不是「四個T,四個F,或兩個T兩個F」?不會。〈並非:p 若且唯若 q〉使用的方法同樣能證明:一個最多包含連詞 ∼ 和 ↔ 的合規式,無論如何建構,它的四行真值表最後一欄都是四個T,四個F,或兩個T兩個F。

我在 Geoffrey Hunter 的 Metalogic: An Introduction to the Metatheory of Standard First Order Logic 看到個挺簡潔的證明,雖然他用強數學歸納法 (strong mathematical induction) ,但原理和我之前寫的差不多。他證明的是:

對於所有合規式 x ,如果 x 的連詞最多只有 ∼ 和 ↔ ,並且真值表只有四行,則 x 的真值表最後一欄有四個T,或四個F,或兩個T兩個F。

他對連詞 (∼ 或 ↔) 出現的次數做強歸納法:第一,假如連詞出現次數是 1 ,證明 x 真值表有四個T或四個F或兩個T兩個F;第二,假設連詞出現次數少於 k 的合規式,四行真值表有四個T或四個F或兩個T兩個F,證明出現次數為 k 時, x 的真值表有四個T或四個F或兩個T兩個F。兩者加起來,代表:無論 x 裡面的 ∼ 和 ↔ 出現多少次,它的四行真值表都是有四個T,四個F,或兩個T兩個F。

第一部分 (Base Case)
假設 x 的連詞出現次數為 1 (只有一個連詞)。考慮真值表有四行的 x 。它有四行真值表,代表它裡面的連詞不是 ∼ ,並且不只有一個簡單述句。所以, x 是 y↔z ,而 y 和 z 分別是不同的簡單述句。在這情況, x 的真值表最後一欄是兩個T兩個F。

第二部分 (Inductive Step)
假設所有連詞 (∼ 或 ↔) 出現次數少於 k 的合規式,它的四行真值表都是四個T,四個F,或兩個T兩個F。現假定 x 的連詞出現次數是 k ,它只有兩種情況:

情況一, x 是 ∼y 。 y 的連詞數目等於 x 的連詞數目減一,少於 k 。因此,根據假設, y 的四行真值表有四個T,四個F,或兩個T兩個F。顯然, x 也是。 (因為 ∼ 不會影響T和F的數目。)

情況二, x 是 y↔z 。同樣的, y 和 z 的連詞數目都少於 k (因為 y 的連詞數目加 z 的連詞數目再加 1 才等於 x 的連詞數目),因此它們的四行真值表有四個T,四個F,或兩個T兩個F。 Hunter 在此列了九種情況,並說這九種情況裡 x 的四行真值表有四個T,四個F,或兩個T兩個F。這裡的做法與我之前的 Case 1-4 一樣。

沒有留言:

技術提供:Blogger.