數(shù)理邏輯史簡析

1、數(shù)理邏輯史簡析,2010.12.16,——直覺主義邏輯,主要內(nèi)容,數(shù)學背景 - 萊布尼茨 - 第三次數(shù)學危機,三大學派 - 邏輯主義 - 直覺主義 - 形式主義,哲學背景 - 柏拉圖主義 - 康德的哲學,中國的哲學與數(shù)學 - 周公問數(shù) - 密率、徽率 - 算經(jīng)十書 - 太極,思考,數(shù)的本質是什么？思想有什么樣的作用？西方世界在第三次數(shù)學危機后如何產(chǎn)生了計算機理論？中國哲學有什么樣的作用？

2、直覺主義（構造主義）邏輯有什么樣的作用？,數(shù)學背景: 思想的啟蒙,數(shù)理邏輯: 一切用特制符號和數(shù)學方法來研究處理演繹方法的理論,也被稱為符號邏輯,Hobbes (1588-1679, 英國),Aristotle (前384-前322, 希臘),符號邏輯這個名詞是在數(shù)理邏輯發(fā)展的初期19 世紀80 年代提出的( 1881 年英國邏輯學家文恩J. Venn),形式邏輯自亞里士多德起到17 世紀后期已有2000 余年的歷史,英國的唯物主義哲

3、學家霍布士1655 年就曾提出過這樣的思想. 他說, 推理好像算術中的加法和減法一樣, 思維是可以計算的,數(shù)學背景: 數(shù)理邏輯的創(chuàng)立,德國唯理論哲學家和數(shù)學家萊布尼茨( 1646 - 1716 ) 被認為是數(shù)理邏輯的創(chuàng)始人,Leibniz (1588-1679, 德國),思維的演算: 遇到爭論, 雙方可以把筆拿在手中說: “讓我們來算一下”, 就可以把問題解決,表意的符號語言和思維的演算是萊氏提出的重要思想, 這二者也正是現(xiàn)代數(shù)理邏輯的

4、特征,數(shù)學背景: 數(shù)理邏輯的發(fā)展,第一階段: 用數(shù)學方法研究和處理形式邏輯從17 世紀70 年代的萊布尼茨到19 世紀末葉的布爾 , 德摩根, 施履德等共延續(xù)了約二百年,其成果是邏輯代數(shù)和關系邏輯,第二階段: 研究數(shù)學思想方法和數(shù)學基礎問題19 世紀中葉起, 康托爾, 希爾伯特, 弗雷格, 皮亞諾, 羅素, 布勞維爾等人奠定了它的理論基礎, 創(chuàng)建了特有的新方法, 成長為一門新學科. 其成果是集合論, 公理化方法, 邏輯演算, 證明

5、論,第三階段: 研究邏輯系統(tǒng)的完全性, 協(xié)調性, 計算機理論等1931 年哥德爾發(fā)表不完備性定理至今. 本階段數(shù)理邏輯的主要內(nèi)容大致可以分為五個方面: 邏輯演算, 證明論, 公理集合論, 遞歸論, 模型論,數(shù)學背景: 集合論(1870s),集合論是關于無窮集合和超窮數(shù)的數(shù)學理論. 數(shù)學里遇到的無窮有: 無窮過程, 無窮小和無窮大. 必須能作數(shù)學的處理, 能進行運算, 這樣的無窮才能算作數(shù)學的對象,Cantor (1845-1918,

6、德國),對無窮集合來說, 如果把一一對應作為是否相等的標準, 則一個無窮集就會和它自己的真部分相等. 這是和有窮領域里人們的常識以及數(shù)學知識 “ 全體大于部分 ” 相矛盾的.如果以“和真部分一一對應”為悖論, 就必須否認實無窮,數(shù)學背景: 第三次數(shù)學危機,1900 年在巴黎召開的第二次國際數(shù)學會議上, 龐加萊宣稱: “數(shù)學的嚴格性到今天可以說已經(jīng)達到了”, 因為利用集合論可以定義自然數(shù)與實數(shù), 從而建立極限論, 為數(shù)學分析奠定了基礎,R

7、ussell (1872-1970, 英國),羅素( 1872 - 1970 ), 英國著名的哲學家, 數(shù)學家和社會改革家在會上結識了皮亞諾并得到很大的啟發(fā). 兩年后, 羅素準備《數(shù)學原理》的書稿時, 發(fā)現(xiàn)一個悖論: 不以自己為元素的集合. 它是不是自己的元素？,數(shù)學背景: 第三次數(shù)學危機,1902 年6 月, 他給致力于把算術化歸于集合和邏輯的弗雷格寫了一封信, 敘述了他發(fā)現(xiàn)的悖論. 在集合論中存在著大漏洞. 把集合論作為算術的基礎,

8、 整個數(shù)學的基礎, 這一想法遭到嚴重的打擊弗雷格迅速給羅素回了信. 他說:“ 哎呀! 算術動搖了. ”弗雷格后來甚至于放棄了他的從邏輯導出數(shù)學的說法狄德金聞訊后, 把他的《什么是數(shù)》的再版推遲羅素則直到1908 年找到解決悖論的類型論后, 才出版他的《數(shù)學原理》,數(shù)學背景: 悖論,悖論是一種認識矛盾, 它既包括邏輯矛盾, 語義矛盾, 也包括思想方法上的矛盾. 數(shù)學悖論作為悖論的一種, 主要發(fā)生在數(shù)學研究中古希臘說謊者悖論,阿基里

9、斯追龜悖論戰(zhàn)國時期邏輯學家惠施（約370B.C. - 318B.C.）的“日方中方睨, 物方生方死”, “一尺之棰, 日取其半, 萬世不竭”,莫比烏斯帶,,哲學背景: 柏拉圖主義,柏拉圖( 公元前427 - 前347 年) 是有很大影響的古希臘唯心主義哲學家,Plato (前427－前347年, 希臘),數(shù)學結論的客觀性, 一個方程有多少根, 有哪幾個根, 是客觀的,柏拉圖主義: 數(shù)學研究的對象盡管是抽象的, 但是卻是客觀存在的. 而

10、且它們是不依賴于時間, 空間和人的思維而永恒存在的. 數(shù)學家提出的概念不是創(chuàng)造, 而是對這種客觀存在的描述,哲學背景: 康德 (德國古典哲學),數(shù)是思維創(chuàng)造的抽象實體,Kant (1724-1804, 德國),康德把人的先天認識能力分為感性, 知性和理性三種. 感性是掌握數(shù)學知識的能力, 知性是掌握物理學知識的能力, 理性企圖超越現(xiàn)象世界去認識 “ 什么自在之物 ”, 結果什么也得不到,康德認為人的先天感性直觀形式有兩種: 時間和空間.

11、 用先天的時間觀念整理關于事物的多與少的經(jīng)驗, 便創(chuàng)造了數(shù)的概念. 用先天的空間概念整理關于事物的形狀的經(jīng)驗, 便創(chuàng)造出了幾何公理,三大學派,在1900 年后幾年內(nèi), 數(shù)學基礎問題的討論和爭議已經(jīng)展開. 當時主要的問題為:(1) 如何解決已發(fā)現(xiàn)的悖論和如何進一步保證在公理系統(tǒng)中不出現(xiàn)任何形式的自相矛盾 ？(2) 如何理解 “ 數(shù)學的存在 ” ？(3) 有沒有實無窮和如何認識實無窮 ？(4) 數(shù)學的基礎是什么 ？,邏輯主義: 算術

12、是邏輯的一部分,邏輯主義的主要人物是羅素和弗雷格都是柏拉圖主義的支持者,Frege(1848-1925, 德國),自然數(shù)是客觀存在的. 在邏輯的基礎上建立算術, 進而建立整個數(shù)學, 以證明數(shù)學是邏輯學的一個分支,弗雷格的工作, 由于羅素悖論的出現(xiàn)而受到挫折. 羅素和懷海德從頭重新做起, 建立了龐大的結構, 總算實現(xiàn)了把算術還原為邏輯, 或者說, 還原為集合論. 但為了使自己的層次理論不太復雜, 羅素最后提出了一個“ 可化歸公理 ”. 這

13、樣, 就不是完全在邏輯上建立算術了,直覺主義: 數(shù)學概念是自主的智力活動,人具有先天的直覺能力, 能肯定這樣能一個一個地把自然數(shù)構造出來. 因此, 數(shù)學對象是人靠智力活動構造出來的,Brouwer (1881 – 1966, 荷蘭),布勞維爾認為不能考慮自然數(shù)總體. 因為直覺可以不能想象構造出全體自然數(shù)的過程, 因為那需要無窮的時間,直覺主義認為, 數(shù)學的對象, 必須能像自然數(shù)那樣明顯地用有限步驟構造出來, 才可以認為是存在的. 全體自

14、然數(shù), 全體實數(shù), 統(tǒng)統(tǒng)無法考慮, 因為構造不出來. 因此, 他們主張一種 “ 構造性數(shù)學 ”. 于是, 直覺主義也被叫做構造主義,直覺主義,這種否定實無窮的觀點, 最早可以追溯到亞里士多德. 在數(shù)學家當中, 康托爾的老師柯朗尼克也反對無窮集的觀點, 主張數(shù)學研究的對象一定要能夠在有限步驟之內(nèi)構造出來. 構造不出來的就不存在直覺主義邏輯否定了“ 排中律 ”, “反證法 ”布勞維爾在自己觀點的指導下開始了龐大的工程. 他建立了構造性的

15、數(shù)學: 構造性實數(shù), 構造性集合論, 構造性微積分在計算機出現(xiàn)后, 構造性數(shù)學有了大用場. 因為計算機只處理可構造出來的具體符號串. 直覺主義派不但沒使數(shù)學受到損害, 反而用構造性數(shù)學使這一領域大大豐富了我國著名數(shù)學家吳文俊教授指出, 中國古代數(shù)學是構造性數(shù)學. 在每個問題中都力求給出構造性的解答. 他還指出: 由于計算機技術的發(fā)展, 構造性數(shù)學將出現(xiàn)大發(fā)展, 甚至成為數(shù)學的主流,形式主義: 把數(shù)學化為關于有限符號排列的操作,形式主

16、義是一種唯心主義的形而上學觀點,Hilbert (1862 – 1943, 德國),形式主義是支持柏拉圖主義的. 目的是通過形式化為柏拉圖主義數(shù)學建立穩(wěn)固可靠的基礎. 形式主義者主張使用符號推演代替語言, 而符號的使用方法要靠約定的規(guī)則,希爾伯特建立了元數(shù)學- 形式系統(tǒng)的數(shù)學兩大目標: 形式數(shù)學系統(tǒng)的完全性, 協(xié)調性如果能推出所有的真命題, 就說這個系統(tǒng)是完全的如果推不出矛盾, 就說這個形式系統(tǒng)是協(xié)調的,哥德爾不完備定理,遺憾的是

17、, 在1931 年哥德爾不完備定理說明了希爾伯特的構想是不可能實現(xiàn)的,哥德爾和王浩 (左哥德爾),青年數(shù)學家哥德爾在1931 年發(fā)表了一條定理: 在包含了自然數(shù)的任一形式系統(tǒng)中, 一定有這樣的命題, 它是真的, 但不能被證明(系統(tǒng)協(xié)調),長期以來,數(shù)學家和哲學家總覺得, 數(shù)學的真理總是可以證明的. 哥德爾定理表明, “真”與“可證”是兩回事,爭論的結果: 計算機理論的產(chǎn)生,對數(shù)的本質的研究, 對數(shù)學對象本質的研究, 促進了數(shù)學基礎和數(shù)學

18、哲學的大發(fā)展. 但是對“什么是數(shù)？ ” “ 數(shù)學的真理意味著什么？ ”這樣的問題, 依然沒有一致的回答不同觀點的數(shù)學家, 沿著自己選定的道路前進, 發(fā)現(xiàn)大家不約而同地到達同一個地方: 數(shù)學研究的對象是一些關系與形式,這些關系與形式可以用有限符號來表達, 它又能包含著無限豐富的內(nèi)容數(shù)學的研究對象是抽象的形式與關系各派最后都導致對“算法”的研究, 在此研究基礎上出現(xiàn)了計算機理論,早期計算機雛形,左圖為二戰(zhàn)德軍使用的Enigma右圖為

19、2008年Bletchley Park博物館復制的 “圖靈炸彈”, 原機二戰(zhàn)后秘密銷毀,,中國的哲學與數(shù)學,公元前1046年, 武王伐商, 建立了周朝. 武王駕崩后, 兒子姬誦年幼, 便由叔叔姬旦( 史稱周公) 輔佐執(zhí)政竊聞乎大夫善數(shù)也, 請問古者包犧立周天歷度. 夫天不可階而生, 地不可得尺寸而度, 請問數(shù)安從出?(圓和方)……故折矩, 以為勾廣三, 股修四, 徑隅五禹治洪水, 決流江河. 望山川之形, 定高下之勢, 除滔天之災

20、, 釋昏墊之厄, 使東注于海而無浸逆. 乃勾股之所由生(趙爽《周髀算經(jīng)》注)古時認為數(shù)出自“兩儀”, 即陰陽之類, 表述事物的兩面性, 如正與反古希臘畢達哥拉斯在商高六百年后才發(fā)現(xiàn)勾股定理,周公問數(shù),大禹治水,中國的哲學與數(shù)學,《九章算術》成書約在東漢初期( 約公元1 世紀), 作為教材在民間流傳. 魏晉時期的劉徽在魏陳留王景元四年( 公元263 年) 完成了《九章算術》注在推求圓周率的過程中, 劉徽巧妙地導出一個普遍公式, 從正

21、六邊形一直推求至九十六邊形, 得到圓周率在3.14附近(徽率, 阿基米德數(shù))在弓形面積的計算中, 劉徽又一次運用了極限思想, 用 “ 割弧術 ” 進行面積逼近. “ 割之又割, 使至極細 ”,劉徽(生于公元250年左右),中國哲學與數(shù)學,《隋書》記述了祖沖之的圓周率值, 準確至小數(shù)點后七位;提出一個具有世界水平的密率值355/113. 這個準確至小數(shù)點后七位的數(shù)劉徽的割圓術, 就必須計算出圓內(nèi)接正24576 邊形的面積直到一千年后

22、, 才有阿拉伯數(shù)學家阿爾卡西打破祖沖之的記錄例如直徑10 公里, 用密率算出的圓周只比真值大不到3 毫米,祖沖之 公元429年─公元500年,中國哲學與數(shù)學,唐朝: 算經(jīng)十書, 王孝通的《緝古算經(jīng)》需要學三年(三次方程代數(shù)解法)宋朝: 沈括《夢溪筆談》, 秦九韶 “ 大衍求一術 ”元朝: 阿拉伯數(shù)字, 朱世杰“ 三次內(nèi)插公式 ”《四元玉鑒》1980年, 梁宗巨( 1942 - 1995年) 在《世界數(shù)學史簡編》中說: “自古以來

23、, 我國就是一個數(shù)學的先進國家, 但是朱世杰之后, 我國數(shù)學突然出現(xiàn)中斷的現(xiàn)象, 從朱世杰后的三個世紀, 沒有重要的創(chuàng)作.”,沈括,秦九韶,再談哥德爾不完備定理,根岑( 1936 ), 阿克曼( 1940 ), 諾維科夫( 1943 ), 洛倫岑( 1951), 許特( 1951 ), 卡羅多夫斯基( 1959 ), 史坦尼斯( 1952 ), 竹內(nèi)外史( 1953 ) 都得到一個結論: 算術系統(tǒng)自身的協(xié)調性不能在自身系統(tǒng)中證明括微積

24、分, 幾何的整個數(shù)學的協(xié)調性, 是逐步化歸到越來越小的系統(tǒng)的協(xié)調性的. 到了算術系統(tǒng), 小得不能再小了, 再想證明協(xié)調性, 就反而要把系統(tǒng)擴大了這是一種什么現(xiàn)象？,中西方計算工具,圖片依次為: 算籌, 漢代琉璃算籌, 古算盤, 皮納爾算籌(1617), 帕斯卡加法器(1641), 萊布尼茨乘法器(1701, 傳教士鮑威特, 二進制, 八卦的爻),布爾巴基學派,畢達哥拉斯做了第一次嘗試, 希望把數(shù)學統(tǒng)一于自然數(shù). 這次嘗試由于無理數(shù)的發(fā)

25、現(xiàn)而以失敗告終. 以后相當長時間里, 希望把數(shù)學統(tǒng)一于歐幾里得幾何. 最后發(fā)現(xiàn), 連幾何也是不統(tǒng)一的, 這種希望破滅了萊布尼茨, 弗雷格和羅素, 希望把數(shù)學統(tǒng)一于邏輯, 使龐大的, 復雜的數(shù)學歸結為非常通俗的, 直觀的, 易于洞察的邏輯. 其結果呢？導出了極不通俗, 極為復雜而令人難于洞察的層次理論與可化歸公理直覺主義派的布勞維爾和形式主義的希爾伯特, 又希望數(shù)學統(tǒng)一于算術. 結果, 哥德爾定理的推論說明連算術也不是統(tǒng)一的法國布爾

26、巴基學派最初的成員是巴黎師范學院的一群大學生. 在40 多年間, 他們計劃完成一部百科全書式的數(shù)學巨著《數(shù)學原理》, 對全部現(xiàn)代數(shù)學作徹底的探討與證明,數(shù)學的研究對象是抽象的形式與關系,中國哲學與數(shù)學,太極: 其大無外, 其小無內(nèi)有物混成, 先天地生. 寂兮寥兮, 獨立而不改, 周行而不殆, 可以為天下母. 吾不知其名, 字之曰道, 強為之名曰大,回答,數(shù)的本質是什么？思想有什么樣的作用？西方世界在第三次數(shù)學危機后如何產(chǎn)生了計算

27、機理論？中國哲學有什么樣的作用？直覺主義（構造主義）邏輯有什么樣的作用？,總結: 一沙一世界, 一花一天堂,想什么, 就會做什么事; 想什么, 就會產(chǎn)生什么樣的理論思想是一粒種子, 生根發(fā)芽, 不斷壯大. 我們所需要的就是那樣的一粒種子, 給予它營養(yǎng)不斷成長,《尚書》星星之火, 可以燎原巴爾扎克: 一個能思想的人, 才真是一個力量無邊的人一切只是源于一個想法,思考,為什么元朝以后我們國家的科學發(fā)展停滯了？為什么世界古文明只

28、有中華文明發(fā)展至今？不是古希臘的文明不發(fā)達, 不是古印度的思想不深刻,大作業(yè),關于計算機中的邏輯應用 (題目自擬) 要求:電子版發(fā)到 buaa.logic@gmail.com (doc格式)郵件題目: 學號-姓名-大作業(yè)題目, 題目為關鍵詞紙版送到G616, 存檔截止時間: 數(shù)理邏輯考試之前,參考題目,計算機語言背后的邏輯系統(tǒng) (Lisp,ML)硬件系統(tǒng)的邏輯描述網(wǎng)絡協(xié)議中的邏輯驗證邏輯理論機的原理 (Newell, S

29、haw, Simon, The Logic Theory Machine)羅素類型論 Gérard Huet簡單類型論王浩 Gentzen-style 系統(tǒng) Martinlöf 直覺主義類型論 (Nuprl)范疇抽象機CAM和CAML語言指針的邏輯描述 (參考中科大相關論文)自動定理證明器 Automated theorem proving (HOL, Isabella, PVS etc),謝謝!,20