∀x∃yRxy→∃y∀xRxy

有一條邏輯題目,幾乎學過述詞邏輯的人都遇過。我曾聽 C 老師說那題目已經「考爛了」,如果他要出研究所的考題,一定不會出那條。不過,那題雖然十分普遍,但仍不失為測試學生基本功的首選。題目大概是這樣:

Q. 請舉出一個反例證明 $∀x∃yRxy→∃y∀xRxy$ 不是邏輯真理。

此題最有趣的地方在於,它的前、後件只有「∀x」和「∃y」的位置互換。乍看之下沒有分別,但意思相差極大。關於前、後件,它們的讀法分別是:

1. $∀x∃yRxy$
1. 對於所有 $x$ ,存在一個 $y$ , $Rxy$
1. 所有 $x$ 都有一個 $y$ , $Rxy$

2. $∃y∀xRxy$
2. 存在一個 $y$ ,對於所有 $x$ , $Rxy$
2. 有一個 $y$ 對所有 $x$ 而言, $Rxy$

由於尚未規定「$Rxy$」的詮釋,目前兩句的差異仍不明顯。這條件句的反例甚多,為方便說明,我先舉一個不太嚴謹的反例,再用另一個較嚴謹的反例。

✖反例a
令論域包含所有人類,「$Rxy$」為「$y$ 是 $x$ 的母親」。據此模型:

1a. $∀x∃yRxy$
1a. 對於所有 $x$ ,存在一個 $y$ , $y$ 是 $x$ 的母親
1a. 所有 $x$ 都有一個 $y$ , $y$ 是 $x$ 的母親
1a. 所有人都有一個母親

2a. $∃y∀xRxy$
2a. 存在一個 $y$ ,對於所有 $x$ , $y$ 是 $x$ 的母親
2a. 有一個 $y$ 對所有 $x$ 而言, $y$ 是 $x$ 的母親
2a. 有一個人是所有人的母親

直覺上,雖然每個人都有母親,但就沒有人是所有人的母親。由此可見,「所有人都有一個母親」是真的,而「有一個人是所有人的母親」是假的,故那條件句前件真,後件假,整句為假。(此反例不夠嚴謹的原因是, (1a) 未必是真的。)

✖反例b
令論域包含所有自然數,「$Rxy$」為「$y$ 比 $x$ 大」。在這模型裡:

1b. $∀x∃yRxy$
1b. 對於所有 $x$ ,存在一個 $y$ , $y$ 比 $x$ 大
1b. 所有 $x$ 都有一個 $y$ , $y$ 比 $x$ 大
1b. 所有自然數都有一個自然數比它更大

2b. $∃y∀xRxy$
2b. 存在一個 $y$ ,對於所有 $x$ , $y$ 比 $x$ 大
2b. 有一個 $y$ 對所有 $x$ 而言, $y$ 比 $x$ 大
2b. 有一個自然數比所有自然數大

前件當然是真的,因為每個自然數都總會有下一個比它更大的數,例如 2 之後有 3 , 3 之後有 4 ,如此類推。後件當然是假的,因為自然數沒有上限;沒有最大的自然數。因此,在這個模型底下,「$∀x∃yRxy→∃y∀xRxy$」(如果所有自然數都有一個自然數比它更大,則有一個自然數比所有自然數大)為假。

沒有留言:

技術提供:Blogger.