並非:p 若且唯若 q

我在〈兩個以一替五的二位連詞〉提到,有兩個二位連詞各自足以定義五個古典邏輯連詞。由於這兩個連詞的意思分別是 not-and (p nand q) 和 not-or (p nor q) ,於是引起一個疑問:是否由 not 配合二位連詞而產生的二位連詞,都能獨自定義全部五個古典連詞。答案是否定的,比如「not-iff」就無法獨自定義五個古典連詞。

暫用「⊖」表示「not-iff」,它的真值表是:


要證明它無法定義全部古典連詞,就要證明:至少有個用古典連詞表達的合規式 (wff) ,如果用只包含 ⊖ 的合規式,無論如何都不能產生相應的真值表。舉例來說,連詞只包含 ⊖ 的合規式便無法定義 P→Q (P,Q 都是簡單述句) ,因為連詞只有 ⊖ 的合規式都有個特徵:如果它的真值表有四行,最後一欄必定是四個T,或四個F,或者兩個T兩個F。然而, P→Q 的真值表卻有三個T一個F。

比較麻煩的地方,是針對 P→Q 證明

(最多)只包含 ⊖, P, Q 的合規式,如果真值表有四行,最後一欄必定是四個T,或四個F,或兩個T兩個F

它是全稱命題,意思等於

對於所有合規式 x ,如果 x 只包含 ⊖, P, Q 並且真值表只有四行,則 x 真值表的最後一欄必定是四個T,或四個F,或兩個T兩個F

目前所有合規式只有兩種:一、簡單述句,二、由兩個合規式配合 ⊖ 產生的合規式。第二項是遞迴的那全稱命題其實是說所有合規式 x 都有以下這個性質:

如果 x 只包含 ⊖, P, Q 並且真值表只有四行,則 x 真值表的最後一欄必定是四個T,或四個F,或兩個T兩個F

為方便引述,暫稱這性質做「偶數真值」。要證明所有合規式都有此性質,需用到數學歸納法。我用弱歸納法,證明分兩部分。第一,如果 x 是 (不由合規式組成的) 簡單述句,則它是偶數真值。第二,如果組成 x 的合規式 y 和 z 是偶數真值(即是, x = y⊖z) ,則 x 也是偶數真值。只要證明這兩點,代表所有合規式都是偶數真值;即是,最多只包含 ⊖, P, Q 的真值表最後一欄都必定有四個T,或四個F,或兩個T兩個F,因而無法定義有三個T一個F的 P→Q 。

第一部分 (Base Case)

假設 x 是簡單述句。再假設它最多只包含 ⊖, P, Q ,真值表也只有四行。欲證明它真值表最後一欄是四個T,或四個F,或兩個T兩個F。

由於 x 是簡單述句,它只會是 P 或者是 Q 。一般會約定 P 或 Q 的真值表只有兩行,但我們可加個約定,將兩行的真值表都「擴充」成四行,方法是多放一個 x 沒有包含的簡單述句,如果 x 是 P ,便多放個 Q :

PQP
TTT
TFT
FTF
FFF

最後(右)一欄的 P 便有兩個T兩個F,是偶數真值。如果 x 是 Q ,情況一樣。因此,如果 x 是簡單述句,它便是偶數真值。

第二部分 (Inductive Step)

假設 x 是由其他合規式組成的 y⊖z,而 y 和 z 都是偶數真值。再假設 y⊖z 只包含 ⊖, P, Q ,真值表也只有四行。欲證明 y⊖z 真值表最後一欄是四個T,或四個F,或兩個T兩個F。

現在真值表的情況是:

PQyzy⊖z
TT???
TF???
FT???
FF???

雖然 y 和 z 都有可能是簡單述句,但根據第一部分的約定它們依然可以順利擴充成四行,並與目前的真值表畫法相吻合。假如無此約定,第一部分依然成立,因為簡單述句的真值表只有兩行,所以「如果它的真值表有四行並只包含 ⊖, P, Q ,則...」前件為假,整句為真,屬 vacuously true 情況,會是偶數真值。在第二部分,如果 y 和 z 是同一個簡單述句,例如,如果它們都是 P , y⊖z 即是 P⊖P ,真值表同樣只有兩行,「如果 y⊖z 的真值表有四行並只包含 ⊖, P, Q ,則...」一樣 vacuously true ,所以 y⊖z 也是偶數真值。最後,就算 x 和 y 有一個是簡單述句,只要 y⊖z 總共包含 P 和 Q 兩個簡單述句,真值表就是四行,而在四行真值表中,根據一般畫真值表的約定,簡單述句都如同第一部分的約定般有四個T,或四個F,或兩個T兩個F。接著就只要考慮正文第二部分,證明當 y⊖z 的真值表有四行並只包含 ⊖, P, Q,它也是有四個T,或四個F,或兩個T兩個F。目前 y 和 z 那兩欄各有三個可能性:四個T、四個F、兩個T兩個F。先分四種情形:

Case 1: y 是四個T。假如 z 也是四個T, y⊖z 會有四個F。假如 z 是四個F, y⊖z 會有四個T。假如 z 是兩個T兩個F, y⊖z 會有兩個T兩個F。每個情況裡, y⊖z 都是四個T,或四個F,或兩個T兩個F。

Case 2: y 是四個F。假如 z 也是四個F, y⊖z 會有四個F。假如 z 是四個T, y⊖z 會有四個T。假如 z 是兩個T兩個F, y⊖z 會有兩個T兩個F。每個情況裡, y⊖z 都是四個T,或四個F,或兩個T兩個F。

Case 3: z 是四個T或者四個F。情況同上,只需把 case 1 和 case 2 的 y 和 z 互換。

Case 4: y 和 z 都是兩個T兩個F。如果兩邊的T都在同一行, y⊖z 會是四個F (例如下表左邊)。如果都錯開,y⊖z 會是四個T (例如下表中間)。如果只有一個T在同一行, y⊖z 會是兩個T兩個F (例如下表右邊)。每個情況裡, y⊖z 都是四個T,或四個F,或兩個T兩個F。

yzy⊖zyzy⊖zyzy⊖z
TTFTFTTFT
TTFTFTTTF
FFFFTTFFF
FFFFTTFTT

因此,如果 y 和 z 都是偶數真值, y⊖z (即 x) 也會是偶數真值。

結論

由第一和第二部分得證,所有只包含 ⊖, P, Q 的合規式的四行真值表最後一欄,都必定是四個T,或四個F,或兩個T兩個F。

沒有留言:

技術提供:Blogger.