§1.4　可判定謂詞及可判定問題

在數(shù)學(xué)中，有一個共同的任務(wù)就是判斷一個數(shù)是否具有一些性質(zhì).這可以用謂詞來表述.例如，給定兩個數(shù)x，y，判斷x是y的倍數(shù).

數(shù)理邏輯最基本的形式系統(tǒng)又稱一階邏輯.一個可以回答真假的命題，不僅可以分析簡單命題，還可以分析研究的個體、量詞和謂詞.個體表示某一個物體或元素，量詞表示數(shù)量，謂詞表示個體的一種屬性.例如用P（x）表示x是一個人，則P（y）表示y是一個人，用Q（y）表示y是無所不能的.這里P、Q是一元謂詞，x，y是個體，公式“?x（P（x）→Q（x））”表示存在一個個體，如果他是人，則他都是無所不能的.公式“?x（P（x）∧?Q（x））”表示對于任何個體x，x是一個人而且x不是無所不能的.

什么是謂詞？在原子命題中，用以刻畫客體的性質(zhì)或客體之間的關(guān)系即是謂詞（predicate）.例如：“貓是動物”一句中的“是動物”就是一個謂詞，而“貓”是客體．“3大于2”中“大于”是一個謂詞.例如用P（3，2）就可以表示“3大于2”或“3小于2”等等.除了一元謂詞，也可以有二元、三元，甚至多元謂詞.事實上，數(shù)學(xué)中的關(guān)系、函數(shù)都可以看成謂詞.例如x≤y可以看成二元謂詞，x+y=z對應(yīng)三元謂詞.例如若用Q（x）表示x是有理數(shù)，則公式?x?y（Q（x）∧Q（y）∧x＜y→?z（Q（z）∧x＜z＜y））表示任意兩個不相等的有理數(shù)之間一定存在另一個有理數(shù)，這是有理數(shù)的稠密性.

數(shù)理邏輯中的一個重要問題，它表現(xiàn)為尋求一個程序或者算法，能夠?qū)δ愁悊栴}中的任何一個個體在有窮步驟內(nèi)確定是否具有某一特定的性質(zhì).如果對某類問題已經(jīng)獲得算法，就說明這類問題是可判定的、可解的；否則，就是不可判定.從語義方面考慮，判定問題是要確定一公式是否常真，亦即是否普遍有效，或者可否滿足；在語法方面，它是要確定某一公式是可證的，還是可否證的.

在數(shù)學(xué)系統(tǒng)里，C.H.朗格弗德于1927年證明了自然數(shù)的線性序理論的判定問題是可解的.1929年，M．普利斯貝格證明了自然數(shù)的加法理論的判定問題是可解的.50年代初，A.塔爾斯基解決了初等幾何理論的判定問題.1970年，蘇聯(lián)學(xué)者Ю.В．馬季亞謝維奇證明了D.希爾伯特所提出的23個著名數(shù)學(xué)問題中的第10個問題是不可解的.希爾伯特第10個問題是指尋找一個算法，用它能確定一任給的整系數(shù)多項式方程p（x1，…，xn）=0是否有整數(shù)解.結(jié)果證明，這樣的算法是不存在的.

從計算復(fù)雜性方面對可解的判定問題的研究證明，一些理論雖然原則上是可判定的，但它的判定程序（算法）所需的計算步數(shù)太大，以致在實踐上是不可行的.例如，就可判定的自然數(shù)的加法理論來說，已經(jīng)證明，對于該理論的每一判定算法，都有長度為n的語句，使得依據(jù)該算法判定此語句是否可證需要計算2cn步（c為＞0的常數(shù)）.假如取n=10，那么即使使用每秒運算一億次的高速計算機作判定，也需要很多億個世紀.一個重要的問題是：是否存在某些可判定的理論，而且其判定方法是快速的，在實踐上是可行的.對于這個問題迄今未能做出肯定的或否定的回答.

設(shè)M（x1，x2，…，xn）是一個n元謂詞．其特征函數(shù)CM（x1，x2，…，xn）為

定義1.4.1　M（x1，x2，…，xn）可判定，如果CM（x1，x2，…，xn）可計算；類似的，M（x1，x2，…，xn）不可判定，如果CM（x1，x2，…，xn）不可計算.

例1.4.1?。?）“x≠y”可判定，其特征函數(shù)

（2）“x=0”可判定，其特征函數(shù)

其程序為J（1，2，3）；J（1，1，4）；S（2）；T（2，1）.

（3）“x是y的倍數(shù)”可判定.