2013年9月29日

之前提過「 | 」 (not-and) 和「 ↓ 」 (not-or) 都能獨自一個定義全部五個古典連詞「|」稱作 Sheffer stroke ,也可寫作「↑」。,但有沒有其他二位連詞同樣神通廣大,同樣能以一替五?答案是「沒有」。二位連詞之中就只有這兩個特別威猛,能夠一個幹五人份的工作。要嚴謹地證明其他所有二位連詞都無法定義五個古典連詞,要用數學歸納法,但要明白其中的理路,大可不必如此麻煩。

首先做個熱身,解釋一位連詞 (unary connective) 為何無法定義五個古典連詞。一位連詞總共只有四種:


第三種就是古典連詞「∼」。第一種和第四種無法定義 ∼ ,因為它們只有單一一種真假值,而 ∼ 卻有兩個。第二種同樣無法定義 ∼ ,因為這連詞無論出現多少次,直假值都不會變。暫以「∸」當作第二種連詞, p 和 ∸p 和 ∸∸p 和 ∸∸∸p 和 ∸∸∸∸p 等等,皆有一樣真假值,但 p 和 ∼p 就會有相反的真假值。因此,一位連詞之中,除了 ∼ ,其他都肯定不能以一替五,因為它們連 ∼ 也定義不了。然而, ∼ 也無法定義「∧」、「∨」或者「→」,因為連詞只包含 ∼ 的合規式 (wff) ,真值表 (最後一欄) 必定有一半是真值,一半是假值,但 ∧ 、 ∨ 和 → 這三個連詞的真值表都可以有超過一半的真值/假值,例如 P∧Q 就有一行真,三行假。

接著是二位連詞 (binary connective) 。二位連詞總共有十六種,當中四種是古典連詞 (深黃色) ,兩種是 | 和 ↓ (藍色) 。為方便稱呼,除了已有名稱的連詞,我直接用每欄底下的編號指相關連詞。


現在的問題是:除了 9 和 15 ,這排連詞當中有沒有一個能以一替五。

首先出局的是 1-8 ,因為這八個連詞如果只輸入T (第一行) ,輸出也會是T,所以無法定義 ∼ 。 ∼ 要在輸入T時輸出F,並且在輸入F時輸出T,例如 P 為真時 ∼P 要為假,而 P 為假時 ∼P 要為真。同樣道理, 2, 4, 6, 8, 10, 12, 14, 16 也出局,因為它們的輸入和輸出一樣都是F (第四行) ,一樣無法定義 ∼ 。剩下的四種二位連詞是 9, 11, 13, 15 。由於 9 和 15 分別是 not-and 和 not-or ,不列入考慮。

最後, 11 和 13 都不能獨自定義五個古典連詞。為了方便,我用 ⑪ 代表 11 那欄的連詞,並用 ⑬ 代表 13 那欄的連詞。仔細觀察它們的真值表,你會發現兩件事: p⑪q 和 ∼q 等值,而 p⑬q 和 ∼p 等值。然而,在熱身部分已說過, ∼ 無法定義五個古典連詞,因為連詞只包含 ∼ 的真值表必定有一半真值和一半假值。連詞只有 11 或 13 的合規式,真值表與只有 ∼ 的一樣一半是真值一半是假值,所以 11 和 13 也不能以一替五。

0 comments:

張貼留言

 
Toggle Footer