Let Fib(n) denote the predicate “n is a Fibonacci number” and Prime(n) denote the predicate “n is a prime”. Please translate the following statement into a formula in predicate logic:
“There is a Fibonacci number that is a prime.”
請問助教這題答案是"倒E(存在)n , Fin(n)→Prim(n) "嗎? 是交大考題，所以總覺得哪裡怪怪的!?
另外請問一個敘述句There exists a program to determine whether or not any arbitrary program can stop, and this program has to execute with exponential time complexity.
是錯的嗎? 因為我覺得一個不會stop的程式，用另一個程式去測試它，測試者也不知何時停。
這樣想法有問題嗎?
3 則留言:
1. 這裡比較沒有若p則q的意涵在, 比較妥當的寫法應該是 "∃n, Fib(n)^Prime(n)", 因為那句話翻成中文會比較像是: 存在一個費式數為質數", 也就是說存在一個數既為費式數亦為質數; 如果寫 "∃n, Fib(n)→Prime(n)", 會變成是只要我們可以找到一個不是費式數的數, 那這句話就成立了, 這樣你可以感覺到兩者之間的差異嗎?
2. 這個問題就是在計算理論領域裡很有名的 halting problem, 它被證明是一個 undecidable 的 problem, 意思就是說不可能存在著有一個程式可以判定任意一個給定的程式在某個input之下會不會停, 利用矛盾證法, 證明就可以寫得短短的, 但非常有技巧, 概念上有點像是老師說的那個理髮師的故事, 有自我指涉的味道在, 如果你真的很想知道要怎麼證我再寫給你看
謝謝助教詳細的解答，您提到的第一題的第五行，是要說：那這句話就"不"成立了嗎? 第二題以上網看答案，謝謝!!
1. 我想說的是成立, 不是不成立, 因為假使命題是"若 p 則 q", 則 ~p 也會是 true, 也就是說即使今天所有的 Fibonacci number 都不是質數, 只要存在有一個數它不是 Fibonacci number, 那 "∃n, Fib(n)→Prime(n)" 這句話也還是會成立, 但這和我們要的 "存在有一個 Fibonacci number 為質數" 這個敘述的意義就不一樣了, 那麼在這個情況下 "∃n, Fib(n)^Prime(n)" 並不成立, 這就是這兩句話之間的差別
如果你對此還是感覺不太熟悉, 你可以再練習做一下書上 p10-108 的範例 6 (98長庚資工), 那一題考的剛好就是我在這裡想說明的觀念
張貼留言