數(shù)理邏輯史簡析

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

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

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

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

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

6、德國),對(duì)無窮集合來說, 如果把一一對(duì)應(yīng)作為是否相等的標(biāo)準(zhǔn), 則一個(gè)無窮集就會(huì)和它自己的真部分相等. 這是和有窮領(lǐng)域里人們的常識(shí)以及數(shù)學(xué)知識(shí) “ 全體大于部分 ” 相矛盾的.如果以“和真部分一一對(duì)應(yīng)”為悖論, 就必須否認(rèn)實(shí)無窮,數(shù)學(xué)背景: 第三次數(shù)學(xué)危機(jī),1900 年在巴黎召開的第二次國際數(shù)學(xué)會(huì)議上, 龐加萊宣稱: “數(shù)學(xué)的嚴(yán)格性到今天可以說已經(jīng)達(dá)到了”, 因?yàn)槔眉险摽梢远x自然數(shù)與實(shí)數(shù), 從而建立極限論, 為數(shù)學(xué)分析奠定了基礎(chǔ),R

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

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

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

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

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

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

13、樣, 就不是完全在邏輯上建立算術(shù)了,直覺主義: 數(shù)學(xué)概念是自主的智力活動(dòng),人具有先天的直覺能力, 能肯定這樣能一個(gè)一個(gè)地把自然數(shù)構(gòu)造出來. 因此, 數(shù)學(xué)對(duì)象是人靠智力活動(dòng)構(gòu)造出來的,Brouwer (1881 – 1966, 荷蘭),布勞維爾認(rèn)為不能考慮自然數(shù)總體. 因?yàn)橹庇X可以不能想象構(gòu)造出全體自然數(shù)的過程, 因?yàn)槟切枰獰o窮的時(shí)間,直覺主義認(rèn)為, 數(shù)學(xué)的對(duì)象, 必須能像自然數(shù)那樣明顯地用有限步驟構(gòu)造出來, 才可以認(rèn)為是存在的. 全體自

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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