2013年10月11日

在語句邏輯,判斷語句是否重言句 (tautology) 的慣常做法是畫真值表。每個語句的真值表行數取決於它所包含的簡單述句數目,例如,如果 $p$ 包含 2 個簡單述句,它的真值表就有 $2^2 (=4)$ 行,如果包含 3 個簡單述句,就有 $2^3 (=8)$ 行。換言之,包含了 $n$ 個簡單述句,真值表就要畫 $2^n$ 行。

Herbert Enderton 在 A Mathematical Introduction to Logic (2001, 2nd, p.26) 針對畫真值表所花的時間,談到件很有趣的事。兩個問題。一,如果有個語句包含 80 個簡單述句,真值表要寫多少行?二,假設你有部超級電腦,一微秒 (百萬分之一秒) 可以畫完一行,這部超級電腦要多久才能判斷那個語句是否重言句?

第一個問題很簡單,其實就是 $2^{80}$ 行。

第二個問題比較複雜。如果堅持用真值表法,一行一行畫,這部超級電腦大概要用 380 億年才畫完真值表。這個數字有多大?目前認為宇宙的年齡不過是 $150$ 億年。換句話說,把宇宙砍掉重練一次,那部電腦還在呱呱呱呱地畫真值表。如果不用最傳統的真值表法呢?說不定,有另一個方法,只需要 $10n^5$ 微秒就能判斷它是否重言句。如果有,只要 $9$ 小時左右就會有結果。快多了!

靠真值表法,簡單述句的數目一旦增加,要畫的行數就呈指數式增長 (grows exponentially) ,但另一個方法則是以多項式上升 (grows polynomially) ,得出來的數字也就差得多。

究竟有沒有這種更快捷的方法?這個問題在學界有個名稱,叫做 “P versus NP” 難題。 Enderton 說目前雖然尚未知道答案,不過學者普遍都抱持悲觀的立場。

0 comments:

張貼留言

 
Toggle Footer