判定問題是數理邏輯中的一個重要問題。它表現為尋求一種能行的方法、一種機械的程式或者算法，從而能夠對某類問題中的任何一個在有窮步驟內確定是否具有某一特定的性質。
基本介紹
- 中文名：判定問題
- 外文名：Decision problem
- 解釋：數理邏輯中的一個重要問題
- 學科：數學
- 學科：數理邏輯
概念定義,研究發展,解決方法,數理邏輯,邏輯學,
概念定義
就命題邏輯的任一公式是不是常真這個問題， 就可以在有窮步內按照一定的程式用真值表判定。如果對某類問題已經獲得這種能行的方法，就說明這類問題是可判定的，或者說其判定問題是可解的；如能夠證明某類問題不可能存在這樣的方法，就說這類問題不是能行可判定的。判定問題有不同的陳述。從語義方面考慮，判定問題是要確定一公式是否常真，亦即是否普遍有效，或者可否滿足；在語法方面，它是要確定某一公式是可證，還是可否證。
研究發展
邏輯系統的判定問題命題邏輯的任一公式是否常真以及是否可證都是能行可判定的。20世紀30年代美國數學家A.丘奇和英國的A.M.圖靈分別證明了謂詞邏輯的判定問題是不可解的。對謂詞邏輯公式可以用前束範式分類，前束範式是一公式，其中一切量詞都未被否定地處於公式的最前方，謂詞邏輯的每一公式都和一前束範式等值或者可以互推。有些前束範式類是可判定的，例如只含有全稱量詞的前束範式。1962年A.S.柯爾、E.F.摩爾和美籍華人學者王浩證明了不可判定的謂詞邏輯公式都可以歸約為凬ヨ凬式。這種不可判定的公式類型被稱為歸納類。
在數學系統里，C.H.朗格弗德於1927年證明了自然數的線性序理論的判定問題是可解的。1929年，M.普利斯貝格證明了自然數的加法理論的判定問題是可解的。50年代初，A.塔爾斯基解決了初等幾何理論的判定問題。1970年，蘇聯學者Ю.В.馬季亞謝維奇證明了 D.希爾伯特所提出的23個著名數學問題中的第10個問題是不可解的。希爾伯特第10個問題是指尋找一個算法，用它能確定一任給的整係數多項式方程：p(x1，...，xn)=0是否有整數解。結果證明，這樣的算法是不存在的。
解決方法
證明一個理論的判定問題可解，只需給出一個算法，並證明這算法就是所要求的，問題就解決了。要證明一個理論的判定問題是不可解的，首先需要把算法（機械程式）概念精確化，並給出算法概念的嚴格的數學定義，使一切算法的類成為明確的數學對象，從而能用嚴格的數學方法證明對某個理論來說不存在解決它的判定問題的算法。判定問題的研究推動了對算法理論或稱可計算性理論的研究，促進了遞歸函式論（見遞歸論）和圖林機器理論的建立。
能行性和可行性從計算複雜性方面對可解的判定問題的研究證明，一些理論雖然原則上是可判定的，但它的判定程式（算法）所需的計算步數太大，以致在實踐上是不可行的。例如，就可判定的自然數的加法理論來說，已經證明，對於該理論的每一判定算法，都有長度（即符號數目）為 n的語句（公式），使得依據該算法判定此語句是否可證需要計算 2步（c為>0的常數）。假如取n=10，那末即使使用每秒運算一億次的高速計算機作判定,也需要很多億個世紀。一個重要的問題是:是否存在某些可判定的理論。而且其判定方法是快速的,在實踐上是可行的。對於這個問題迄今未能作出肯定的或否定的回答。70年代以來，通過研究命題邏輯的判定方法的複雜性，發現了許多已知的組合型的判定問題都可化歸為命題邏輯的判定問題，如果能找到判定命題邏輯中的公式是否為重言式的快速算法，則可隨之而獲得一大批判定問題的快速算法。但迄今這仍是懸案，既未能找到命題邏輯的快速判定算法，也未能證明不存在它的快速判定算法。
數理邏輯
邏輯學是一門研究推理與論證、自然語言(人們日常生活所使用的語言)、自然科學與社會科學中的邏輯問題以及思維、科學方法論中有關問題的學科。與數學一樣，都是以反映事物的“思想事物”為對象。數理邏輯正是這兩門科學發展的共同產物，它是用數學方法研究數學概念與推理、數學證明與計算中的邏輯問題的一個數學分支。它包括邏輯演算(命題演算與謂詞演算)、公理化集合論、證明論、遞歸函式論、模型論和算法理論等。它是離散數學的一個重要組成部分。
數理邏輯從稱為公理的命題(相當於判斷)出發，利用所規定的一組特定的符號，使得所討論的複雜邏輯關係，可以用公式很清晰地表示出來。
按照一些特定的演繹規則，可以推導出一系列稱為定理的命題，從而構成一個公理系統。在數理邏輯中，討論演繹推理的結構，和公理系統(特別是數學的公理系統)的性質。
萊布尼茲最早具有數理邏輯的概念，他在1666年提出，可以利用符號來進行數學推理。在1682年，他就為數理邏輯奠定了基礎。但是，直到1847年布爾發表《邏輯的數學分析》以後，特別是由於研究數學基礎問題的推動，人們為了滿足尋求無矛盾性證明等方面的需要，數理邏輯才得到很快的發展。在其中，希爾伯特等人起了重要的作用。20世紀30年代，哥德爾證明了謂詞演算的完全性，和算術系統的不完全性等重要結論，使數理邏輯成為一門獨立的學科。它對於公理化方法、數學基礎及某些數學分支的研究，都具有重要的作用，它還是控制論與計算機科學的基礎理論之一。在計算機技術、人工智慧、語言學、自動化系統及開關線路中得到廣泛的套用，同時它本身也隨之得到了迅速的發展。數理邏輯對哲學也有重要意義，它使哲學精確化，並使人易於理解。
邏輯學
關於思維形式及其規律的科學。包括形式邏輯、辯證邏輯、數理邏輯等分支。一般指的是形式邏輯。
邏輯學是一門古老的學科。在古希臘時期，著名學者亞里士多德(公元前384年—公元前322年)曾對邏輯學作了比較系統的闡述。亞氏的主要邏輯著作有：《範疇篇》、《解釋篇》、《前分析篇》、《後分析篇》、《論辯篇》、《辯謬篇》，後人把這些著作收集在一起，合稱為《工具論》。其中《範疇篇》主要研究概念和範疇問題;《解釋篇》主要研究判斷及其有關問題;《前分析篇》和《後分析篇》主要研究推理和證明問題;《論辯篇》和《辯謬篇》主要研究辯論的方法以及如何駁斥詭辯的問題。此外，亞氏還在其《形上學》一書中集中論述了同一律、矛盾律、排中律。這樣，以演繹法為主的形式邏輯體系在亞氏那裡就初步形成了。正因為如此，後人稱亞氏為“邏輯之父”，認為他是邏輯學的奠基人。
古代中國也是邏輯學的發祥地之一。春秋戰國時期，許多思想家曾研究過邏輯學方面的問題，如惠施、公孫龍、墨翟、荀況、韓非等人，都有關於邏輯學的論述。其中後期墨家所建立的中國古代“名辯之學”對中國古代邏輯學的發展影響很大。《墨經》中的《經上》、《經下》、《經說上》、《經說下》、《大取》、《小取》六篇以及《荀子·正名》對中國古代邏輯學的貢獻最為卓著。
古代印度也產生了邏輯學說，即“因明”。所謂“因”，是指推理的依據;所謂“明”，是指我們通常所講的“學說”。因此，“因明”的含義就是關於推理依據的學說。在公元二、三世紀，古印度思想家足目(又稱喬答摩，梵文Aksapada的意譯)創立了“五支作法”的推理形式。公元五至六世紀，陳那的《因明正理門論》以及商羯羅主的《因明入正理論》使因明理論趨於系統和嚴密，從而形成了印度特有的邏輯理論和體系。
公元17世紀，隨著實驗自然科學的興起和發展，英國哲學家弗蘭西斯·培根著重研究了歸納法，他的主要著作《新工具》奠定了歸納邏輯的基礎，對傳統形式邏輯作出了巨大的貢獻。到了19世紀，英國哲學家穆勒繼續發展了培根的歸納學說，他在《邏輯體系》(中國的嚴復將該書譯為《穆勒名學》)一書中，明確而系統地闡述了科學歸納的五種邏輯方法，即：契合法(求同法)、差異法(求異法)、契合差異並用法(求同求異並用法)、共變法和剩餘法。至此，由亞氏創立的演繹邏輯和由培根創立、穆勒發展的歸納邏輯一起，構成了傳統形式邏輯的基本內容。
辯證邏輯是從18世紀開始產生、發展起來的邏輯學的一個分支，它是研究辯證思維的形式及其規律的科學。18世紀德國哲學家康德在它所創立的先驗邏輯中初步探討了辯證邏輯的某些基本問題，並以先驗邏輯的形式，提出了一個辯證邏輯的模糊的輪廓。到了19世紀，德國哲學家黑格爾批判了舊邏輯中形式與內容相割裂的觀點，區分了知性思維和理性思維，從而建立了一個比較全面而系統的龐大的辯證邏輯體系。但是，無論是康德還是黑格爾，他們對辯證邏輯的闡述都是建立在唯心主義理論基礎之上的。從19世紀中葉到20世紀，馬克思主義經典作家批判地吸收了黑格爾辯證邏輯中的合理因素，用唯物辯證法的觀點研究、闡述辯證思維的形式及其規律，從而為科學的辯證邏輯奠定了堅實的基礎。
