【台灣大學】《邏輯學》（全100講）傅皓政 P34 - 34. Ⅴ：5.5.可決定性

這樣的方法有什麼好處呢 各位在 5.5 的部份可以看到 我們有一個很重要的性質 稱之為可決定性 我們叫 decidability 可決定性是一個非常好的性質 就在這個邏輯系統裡面 它的意思是這樣 我們整個真值表法 可以提供一個有限而有效的程序 這個程序是可以用來證明 這個命題邏輯裡面的論證 是不是一個有效論證的方法 也就是說 你只要根據剛剛我們所 在 5.2 開始所列出來的步驟 你只要一步一步一步的做 你一定可以決定 任何一個命題邏輯的論證 是一個有效論證 或者是一個無效論證 那這樣的一個特性 我們把它稱之為可決定性 那這個可決定性其實是非常重要的 我舉個例子給大家聽 各位應該中學都做過數學證明題 當你在做數學證明題的時候 我相信有些同學跟我一樣 有時候自己不太會做 然後有一句問會做的同學說 這個你怎麼做出來的 你可不可以一步一步告訴我 你怎麼想到這一步的 通常你會得到什麼樣的答案呢 我記得我在中學的時候得到最多的答案 就說 就這樣啊 他也沒有辦法回答你更多的答案 他就告訴你 就這樣啊 你問他 你怎麼知道要做這一步呢 不知道啊 我就會做啊 所以 會做這個證明題 它好像沒有一個標準的程序 或者一個標準的方式 沒有一個 SOP 告訴你說 你只要根據我這個 SOP 照表操課 照著這個步驟做 你就可以一步一步的把它做出來 似乎沒有這樣的 我們在中學做數學證明題 似乎沒有這樣的步驟 也沒有這樣的 SOP 可是呢 在我們的命題邏輯系統裡面 我們真值表法提供了這樣的一個程序 也就是說 你一定可以依照這樣的程序 最後把我們的答案做出來 這個我們就稱之為 Decidability 叫做可決定性 所以它是命題邏輯裡面 在真值表法裡面一個很好的性質 那我們在稍後要介紹的 這個公理法或者自然演繹法 都沒有這個性質 也就是說 它都沒有具有 可決定性這個性質 稍後我們在公理法或自然演繹法的時候 遇到的時候 各位就會發現 其實這個真值表法的重要性就在於 它提供了這樣的一個 可以來證明 這個論證是一個有效與否的程序 那這個對我們來講是非常重要的 那我稍微說明一下 為什麼它是這個可決定的呢 因為很簡單 各位可以看得出來 每一個論證的命題符號一定是有限的 我們假設有 N 個好了 只要它的命題符號是有限的 那麼它的可能情況 是 2 的 N 次方 它也會是一個有限的 所以呢 既然它是有限的表示 你可以在有限的步驟裡面完成這個證明 簡單來講 我們只要根據這樣一個簡單的想法 我們就知道說為什麼它是 具有 Decidability 就是可決定性這樣一個 很好的性質 因為一個邏輯系統具有這樣的性質的話 我們就可以有一個 SOP 去做出來說 它到底是不是一個有效論證 對我們來講是非常有幫助的一個系統 但是呢 我們的問題來了 雖然這個真值表法具有可決定性 可是各位都知道 我們是根據命題符號的數目 來決定我們要處理的可能情況 那各位只要仔細想想 我們剛剛舉的例子都是隻有兩個命題符號 對不對 了不起三個命題符號 那如果是兩個命題符號的話呢 我們只要處理這種情況 沒有錯 我們只要處理四種情況 那如果三個命題符號呢 對 我們要處理八種情況 那各位想想看 假設我給你八個命題符號呢 如果我給各位八個命題符號的話 那各位要畫出幾種可能情況呢 對 你要畫出 256 種情況 對吧 那更不要說 如果我給你 15 個命題符號 給你 20 個命題符號的話 那你這個畫出來的數量 其實是非常非常的龐大 所以呢 真值表法有一個缺點 就在於說 萬一我們的命題符號的數量太多的話 那我們這個整個真值表會顯得很大 你很難去處理完畢 對不對 因此呢 邏輯學家就想方設法說 如果是這樣的話 我們雖然它是一個很好的方法 它也有很好的 SOP 對吧 可是呢 如果我要把它做完的話呢 其實對我來講會有點負擔太大 那這個負擔會使得我很難把它完整的做完 因為你如果給我十幾個命題符號的話呢 我光畫這個真值表就畫不完 因此呢 我們邏輯學家想到說 我們應該要去尋求一個比較簡單的方法 來克服我們剛剛這個困難