[科普中國(guó)]-判定問(wèn)題

判定問(wèn)題是數(shù)理邏輯中的一個(gè)重要問(wèn)題。它表現(xiàn)為尋求一種能行的方法、一種機(jī)械的程序或者算法，從而能夠?qū)δ愁悊?wèn)題中的任何一個(gè)在有窮步驟內(nèi)確定是否具有某一特定的性質(zhì)。

概念定義就命題邏輯的任一公式是不是常真這個(gè)問(wèn)題， 就可以在有窮步內(nèi)按照一定的程序用真值表判定。如果對(duì)某類問(wèn)題已經(jīng)獲得這種能行的方法，就說(shuō)明這類問(wèn)題是可判定的，或者說(shuō)其判定問(wèn)題是可解的；如能夠證明某類問(wèn)題不可能存在這樣的方法，就說(shuō)這類問(wèn)題不是能行可判定的。判定問(wèn)題有不同的陳述。從語(yǔ)義方面考慮，判定問(wèn)題是要確定一公式是否常真，亦即是否普遍有效，或者可否滿足；在語(yǔ)法方面，它是要確定某一公式是可證，還是可否證。1

研究發(fā)展邏輯系統(tǒng)的判定問(wèn)題命題邏輯的任一公式是否常真以及是否可證都是能行可判定的。20世紀(jì)30年代美國(guó)數(shù)學(xué)家A.丘奇和英國(guó)的A.M.圖靈分別證明了謂詞邏輯的判定問(wèn)題是不可解的。對(duì)謂詞邏輯公式可以用前束范式分類，前束范式是一公式，其中一切量詞都未被否定地處于公式的最前方，謂詞邏輯的每一公式都和一前束范式等值或者可以互推。有些前束范式類是可判定的，例如只含有全稱量詞的前束范式。1962年A.S.柯?tīng)?、E.F.摩爾和美籍華人學(xué)者王浩證明了不可判定的謂詞邏輯公式都可以歸約為凬ヨ凬式。這種不可判定的公式類型被稱為歸納類。

在數(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é)果證明，這樣的算法是不存在的。

解決方法證明一個(gè)理論的判定問(wèn)題可解，只需給出一個(gè)算法，并證明這算法就是所要求的，問(wèn)題就解決了。要證明一個(gè)理論的判定問(wèn)題是不可解的，首先需要把算法（機(jī)械程序）概念精確化，并給出算法概念的嚴(yán)格的數(shù)學(xué)定義，使一切算法的類成為明確的數(shù)學(xué)對(duì)象，從而能用嚴(yán)格的數(shù)學(xué)方法證明對(duì)某個(gè)理論來(lái)說(shuō)不存在解決它的判定問(wèn)題的算法。判定問(wèn)題的研究推動(dòng)了對(duì)算法理論或稱可計(jì)算性理論的研究，促進(jìn)了遞歸函數(shù)論（見(jiàn)遞歸論）和圖林機(jī)器理論的建立。2

能行性和可行性從計(jì)算復(fù)雜性方面對(duì)可解的判定問(wèn)題的研究證明，一些理論雖然原則上是可判定的，但它的判定程序（算法）所需的計(jì)算步數(shù)太大，以致在實(shí)踐上是不可行的。例如，就可判定的自然數(shù)的加法理論來(lái)說(shuō)，已經(jīng)證明，對(duì)于該理論的每一判定算法，都有長(zhǎng)度（即符號(hào)數(shù)目）為 n的語(yǔ)句（公式），使得依據(jù)該算法判定此語(yǔ)句是否可證需要計(jì)算 2步（c為>0的常數(shù)）。假如取n=10，那末即使使用每秒運(yùn)算一億次的高速計(jì)算機(jī)作判定,也需要很多億個(gè)世紀(jì)。一個(gè)重要的問(wèn)題是:是否存在某些可判定的理論。而且其判定方法是快速的,在實(shí)踐上是可行的。對(duì)于這個(gè)問(wèn)題迄今未能作出肯定的或否定的回答。70年代以來(lái)，通過(guò)研究命題邏輯的判定方法的復(fù)雜性，發(fā)現(xiàn)了許多已知的組合型的判定問(wèn)題都可化歸為命題邏輯的判定問(wèn)題，如果能找到判定命題邏輯中的公式是否為重言式的快速算法，則可隨之而獲得一大批判定問(wèn)題的快速算法。但迄今這仍是懸案，既未能找到命題邏輯的快速判定算法，也未能證明不存在它的快速判定算法。3

數(shù)理邏輯邏輯學(xué)是一門研究推理與論證、自然語(yǔ)言(人們?nèi)粘Ｉ钏褂玫恼Z(yǔ)言)、自然科學(xué)與社會(huì)科學(xué)中的邏輯問(wèn)題以及思維、科學(xué)方法論中有關(guān)問(wèn)題的學(xué)科。與數(shù)學(xué)一樣，都是以反映事物的“思想事物”為對(duì)象。數(shù)理邏輯正是這兩門科學(xué)發(fā)展的共同產(chǎn)物，它是用數(shù)學(xué)方法研究數(shù)學(xué)概念與推理、數(shù)學(xué)證明與計(jì)算中的邏輯問(wèn)題的一個(gè)數(shù)學(xué)分支。它包括邏輯演算(命題演算與謂詞演算)、公理化集合論、證明論、遞歸函數(shù)論、模型論和算法理論等。它是離散數(shù)學(xué)的一個(gè)重要組成部分。

數(shù)理邏輯從稱為公理的命題(相當(dāng)于判斷)出發(fā)，利用所規(guī)定的一組特定的符號(hào)，使得所討論的復(fù)雜邏輯關(guān)系，可以用公式很清晰地表示出來(lái)。

按照一些特定的演繹規(guī)則，可以推導(dǎo)出一系列稱為定理的命題，從而構(gòu)成一個(gè)公理系統(tǒng)。在數(shù)理邏輯中，討論演繹推理的結(jié)構(gòu)，和公理系統(tǒng)(特別是數(shù)學(xué)的公理系統(tǒng))的性質(zhì)。

萊布尼茲最早具有數(shù)理邏輯的概念，他在1666年提出，可以利用符號(hào)來(lái)進(jìn)行數(shù)學(xué)推理。在1682年，他就為數(shù)理邏輯奠定了基礎(chǔ)。但是，直到1847年布爾發(fā)表《邏輯的數(shù)學(xué)分析》以后，特別是由于研究數(shù)學(xué)基礎(chǔ)問(wèn)題的推動(dòng)，人們?yōu)榱藵M足尋求無(wú)矛盾性證明等方面的需要，數(shù)理邏輯才得到很快的發(fā)展。在其中，希爾伯特等人起了重要的作用。20世紀(jì)30年代，哥德?tīng)栕C明了謂詞演算的完全性，和算術(shù)系統(tǒng)的不完全性等重要結(jié)論，使數(shù)理邏輯成為一門獨(dú)立的學(xué)科。它對(duì)于公理化方法、數(shù)學(xué)基礎(chǔ)及某些數(shù)學(xué)分支的研究，都具有重要的作用，它還是控制論與計(jì)算機(jī)科學(xué)的基礎(chǔ)理論之一。在計(jì)算機(jī)技術(shù)、人工智能、語(yǔ)言學(xué)、自動(dòng)化系統(tǒng)及開(kāi)關(guān)線路中得到廣泛的應(yīng)用，同時(shí)它本身也隨之得到了迅速的發(fā)展。數(shù)理邏輯對(duì)哲學(xué)也有重要意義，它使哲學(xué)精確化，并使人易于理解。

邏輯學(xué)關(guān)于思維形式及其規(guī)律的科學(xué)。包括形式邏輯、辯證邏輯、數(shù)理邏輯等分支。一般指的是形式邏輯。

邏輯學(xué)是一門古老的學(xué)科。在古希臘時(shí)期，著名學(xué)者亞里士多德(公元前384年—公元前322年)曾對(duì)邏輯學(xué)作了比較系統(tǒng)的闡述。亞氏的主要邏輯著作有：《范疇篇》、《解釋篇》、《前分析篇》、《后分析篇》、《論辯篇》、《辯謬篇》，后人把這些著作收集在一起，合稱為《工具論》。其中《范疇篇》主要研究概念和范疇問(wèn)題;《解釋篇》主要研究判斷及其有關(guān)問(wèn)題;《前分析篇》和《后分析篇》主要研究推理和證明問(wèn)題;《論辯篇》和《辯謬篇》主要研究辯論的方法以及如何駁斥詭辯的問(wèn)題。此外，亞氏還在其《形而上學(xué)》一書中集中論述了同一律、矛盾律、排中律。這樣，以演繹法為主的形式邏輯體系在亞氏那里就初步形成了。正因?yàn)槿绱?，后人稱亞氏為“邏輯之父”，認(rèn)為他是邏輯學(xué)的奠基人。

古代中國(guó)也是邏輯學(xué)的發(fā)祥地之一。春秋戰(zhàn)國(guó)時(shí)期，許多思想家曾研究過(guò)邏輯學(xué)方面的問(wèn)題，如惠施、公孫龍、墨翟、荀況、韓非等人，都有關(guān)于邏輯學(xué)的論述。其中后期墨家所建立的中國(guó)古代“名辯之學(xué)”對(duì)中國(guó)古代邏輯學(xué)的發(fā)展影響很大。《墨經(jīng)》中的《經(jīng)上》、《經(jīng)下》、《經(jīng)說(shuō)上》、《經(jīng)說(shuō)下》、《大取》、《小取》六篇以及《荀子·正名》對(duì)中國(guó)古代邏輯學(xué)的貢獻(xiàn)最為卓著。

古代印度也產(chǎn)生了邏輯學(xué)說(shuō)，即“因明”。所謂“因”，是指推理的依據(jù);所謂“明”，是指我們通常所講的“學(xué)說(shuō)”。因此，“因明”的含義就是關(guān)于推理依據(jù)的學(xué)說(shuō)。在公元二、三世紀(jì)，古印度思想家足目(又稱喬答摩，梵文Aksapada的意譯)創(chuàng)立了“五支作法”的推理形式。公元五至六世紀(jì)，陳那的《因明正理門論》以及商羯羅主的《因明入正理論》使因明理論趨于系統(tǒng)和嚴(yán)密，從而形成了印度特有的邏輯理論和體系。

公元17世紀(jì)，隨著實(shí)驗(yàn)自然科學(xué)的興起和發(fā)展，英國(guó)哲學(xué)家弗蘭西斯·培根著重研究了歸納法，他的主要著作《新工具》奠定了歸納邏輯的基礎(chǔ)，對(duì)傳統(tǒng)形式邏輯作出了巨大的貢獻(xiàn)。到了19世紀(jì)，英國(guó)哲學(xué)家穆勒繼續(xù)發(fā)展了培根的歸納學(xué)說(shuō)，他在《邏輯體系》(中國(guó)的嚴(yán)復(fù)將該書譯為《穆勒名學(xué)》)一書中，明確而系統(tǒng)地闡述了科學(xué)歸納的五種邏輯方法，即：契合法(求同法)、差異法(求異法)、契合差異并用法(求同求異并用法)、共變法和剩余法。至此，由亞氏創(chuàng)立的演繹邏輯和由培根創(chuàng)立、穆勒發(fā)展的歸納邏輯一起，構(gòu)成了傳統(tǒng)形式邏輯的基本內(nèi)容。

辯證邏輯是從18世紀(jì)開(kāi)始產(chǎn)生、發(fā)展起來(lái)的邏輯學(xué)的一個(gè)分支，它是研究辯證思維的形式及其規(guī)律的科學(xué)。18世紀(jì)德國(guó)哲學(xué)家康德在它所創(chuàng)立的先驗(yàn)邏輯中初步探討了辯證邏輯的某些基本問(wèn)題，并以先驗(yàn)邏輯的形式，提出了一個(gè)辯證邏輯的模糊的輪廓。到了19世紀(jì)，德國(guó)哲學(xué)家黑格爾批判了舊邏輯中形式與內(nèi)容相割裂的觀點(diǎn)，區(qū)分了知性思維和理性思維，從而建立了一個(gè)比較全面而系統(tǒng)的龐大的辯證邏輯體系。但是，無(wú)論是康德還是黑格爾，他們對(duì)辯證邏輯的闡述都是建立在唯心主義理論基礎(chǔ)之上的。從19世紀(jì)中葉到20世紀(jì)，馬克思主義經(jīng)典作家批判地吸收了黑格爾辯證邏輯中的合理因素，用唯物辯證法的觀點(diǎn)研究、闡述辯證思維的形式及其規(guī)律，從而為科學(xué)的辯證邏輯奠定了堅(jiān)實(shí)的基礎(chǔ)。

本詞條內(nèi)容貢獻(xiàn)者為:

胡建平 - 副教授 - 西北工業(yè)大學(xué)