§1.4　可判定謂詞及可判定問(wèn)題

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

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

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

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

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

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

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

定義1.4.1　M（x1，x2，…，xn）可判定，如果CM（x1，x2，…，xn）可計(jì)算；類(lèi)似的，M（x1，x2，…，xn）不可判定，如果CM（x1，x2，…，xn）不可計(jì)算.

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

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

其程序?yàn)镴（1，2，3）；J（1，1，4）；S（2）；T（2，1）.

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