Fuleige 弗雷格
（F.L.）G. Friedrich Ludwig Gottlob Frege (1848～1925)
德國數學(xué)家、邏輯學(xué)家。1848年11月8日生于德國維斯馬,1925年7月26日卒于巴德克萊茵。1873年畢業(yè)于格丁根大學(xué)，獲博士學(xué)位。1874年起即在耶拿大學(xué)任講師，1879年任教授，1918年退休。在耶拿大學(xué)執教的四十余年間，致力于數學(xué)基礎、數學(xué)哲學(xué)和邏輯理論的研究。
弗雷格于 1879年出版了《概念語(yǔ)言》一書(shū)，所謂“概念語(yǔ)言”是一種表意語(yǔ)言，用它進(jìn)行推理最易于察覺(jué)隱含的前提和有漏洞的步驟。由于弗雷格認為算術(shù)定理可由純邏輯規律出發(fā)證得，為了保證推理過(guò)程的絕對嚴格性，他特地建立了這一符號語(yǔ)言。他成功地引入了數學(xué)中的函數概念，建立了量詞理論。這樣就構作了一種基本自足的邏輯演算即一階謂詞演算。從而給出了歷史上第一個(gè)嚴格的關(guān)于邏輯規律的公理系統。嗣后，他又出版了《算術(shù)基礎》（1884）和《算術(shù)的基本規律》 （卷I,1893；卷Ⅱ，1903）。在這些著(zhù)作中他首創(chuàng )從邏輯出發(fā)來(lái)定義數和自然數，并從邏輯規律出發(fā)推導出一系列算術(shù)定理。盡管弗雷格明確地提出了數學(xué)可以化歸為邏輯的思想，但沒(méi)有全面地進(jìn)行從邏輯推導數學(xué)的研究，因而他未能象B.A.W.羅素和A.N.懷特海在《數學(xué)原 理》中那樣精詳論證、充分展開(kāi)邏輯主義的綱領(lǐng)（見(jiàn)數 學(xué)基礎），但弗雷格仍不失為邏輯主義的創(chuàng )始人之一。 邏輯主義的主要代表人物羅素，甚為稱(chēng)頌弗雷格的工作。 弗雷格晚年從事數學(xué)哲學(xué)和邏輯理論的研究。
?。ㄐ煸茝模?nbsp;
弗雷格
大連理工大學(xué) 杜瑞芝
弗雷格，F．L．G．(Frege，Friedrich Ludwig Go-ttlob)1848年11月8日生于德國維斯馬(Wismar)；1925年7月26日卒于巴德克萊茵(Bad Kleinen)．數學(xué)、邏輯學(xué)、哲學(xué)．
弗雷格出生的年代正值德國民主革命開(kāi)始．維斯馬是一個(gè)遠離德國政治中心的小商業(yè)城鎮，革命風(fēng)潮對這里影響很?。ダ赘癯錾谝粋€(gè)信奉路德教的中產(chǎn)階級家庭，在血統上是混雜的(部分是德國的，部分是波蘭的)．其父亞歷山大?弗雷格(AlexanderFrege)開(kāi)辦了一所女子學(xué)校．他去世后這所學(xué)校就由他妻子來(lái)管理．1869年，母親奧古斯特?弗雷格(Auguste Frege)送弗雷格到耶拿大學(xué)就讀．當時(shí)弗雷格就把數學(xué)作為自己的主要興趣，但也選修了化學(xué)、物理和哲學(xué)．他的老師——數學(xué)家、物理學(xué)家E．阿貝(Abbe)及時(shí)發(fā)現了他的才能，成為他畢生信念的支持者．在阿貝的幫助下，他離開(kāi)耶拿，來(lái)到格丁根大學(xué)繼續深造．1873年，在數學(xué)家E．謝林(Schering)的指導下，弗雷格以論文“論平面上虛影的幾何圖形”(Ueber eine geometrische Darstellung derim ginaren Gebilde in der Ebene)獲得哲學(xué)博士學(xué)位．該論文通過(guò)對平面上虛影圖形性質(zhì)的討論，闡明了幾何學(xué)基于直覺(jué)的觀(guān)點(diǎn)．他在格丁根還參加了著(zhù)名哲學(xué)家R．H．洛采(Lotze)的講座．洛采的邏輯觀(guān)念，特別是他對純邏輯的看法，對弗雷格邏輯思想的形成有著(zhù)重要的影響．
弗雷格在格丁根大學(xué)獲得博士學(xué)位之后，又回到耶拿大學(xué)．在阿貝的幫助下，他于1874年以論文“基于量值概念外延的演算方法”(Rechungsmethoden，die sich auf eine Erweitung desGr ssenbegriffes gr nden)獲得了無(wú)薪大學(xué)講師的資格①．在這篇論文中，弗雷格提出了用于運算的量值概念，并斷言算術(shù)真理產(chǎn)生于量值概念．1879年，弗雷格的《概念語(yǔ)言》問(wèn)世之后，他又一次在阿貝的推薦下成為耶拿大學(xué)的編外教授．1896年成為榮譽(yù)教授．弗雷格在耶拿大學(xué)執教40余年，講授過(guò)數學(xué)的各分支學(xué)科及有關(guān)的邏輯系統，舉辦過(guò)“概念符號”講座，他一直致力于數學(xué)基礎、數學(xué)哲學(xué)和邏輯理論的研究．1918年退休．
弗雷格首先是作為一位數學(xué)家和邏輯學(xué)家而聞名于世的．他在數學(xué)上的主要成就，是使自C．F．高斯(Gauss)以來(lái)所建立的數學(xué)體系更精確和完善，確立了算術(shù)演算的基本規則．他第一個(gè)建立了初步自足的命詞演算系統和量詞理論，首次提供了現代意義下的數理邏輯的一個(gè)體系，因而成為數理邏輯的奠基人．他提出數學(xué)可以化歸為邏輯的思想，成為邏輯主義的創(chuàng )始人．弗雷格還是一位杰出的哲學(xué)家．他的絕大部分著(zhù)作都具有明顯的哲學(xué)特征．他認為：“一個(gè)好的數學(xué)家，至少是半個(gè)哲學(xué)家；一個(gè)好的哲學(xué)家，至少是半個(gè)數學(xué)家．”他直接把傳統哲學(xué)對思維內容和認識能力的探討，轉向對語(yǔ)言表達形式和語(yǔ)言?xún)炔靠蚣艿目紤]．他認為對語(yǔ)言意義的分析，是哲學(xué)研究的主要任務(wù)．弗雷格對哲學(xué)任務(wù)的重新規定，標志著(zhù)當代西方分析哲學(xué)的開(kāi)端．因此他被譽(yù)為當代分析哲學(xué)的真正奠基者．
弗雷格的主要著(zhù)作有：《概念語(yǔ)言》、《算術(shù)的基礎》、《函項與概念》(Function und Begriff，1891)、《論意義和所指》( ber Sinn und Bedeutung，1892)、《論概念和對象》( berBegriff und Gegenstand，1892)、《算術(shù)的基本規律》1—2卷(以下簡(jiǎn)稱(chēng)《基本規律》)．
弗雷格的科學(xué)生涯大致可以分為五個(gè)時(shí)．
在第一個(gè)時(shí)期，弗雷格主要從事純邏輯的研究．其研究成果總結在1879年出版的《概念語(yǔ)言》中．用數學(xué)方法研究邏輯問(wèn)題，一般認為是由G．W．萊布尼茨(Leibniz)提出的文字學(xué)設想開(kāi)始．他提出過(guò)有關(guān)思維演算的思想．萊布尼茨的這種先驅性想法沒(méi)有及時(shí)得到應有的發(fā)展．在淹沒(méi)了一個(gè)世紀之后，19世紀英國的兩位數學(xué)家A．德摩根(De Morgen)和G．布爾(Boole)用代數的方法建立了邏輯代數．但這種邏輯代數與亞里士多德(Ar-istotle)的形式邏輯本質(zhì)上是相似的．在1874—1879年間，弗雷格攻讀了布爾學(xué)派和一些哲學(xué)邏輯學(xué)家的著(zhù)作．除上文提到的洛采外，18世紀德國哲學(xué)家A．特倫德倫堡(Trendelenburg)的著(zhù)作對弗雷格也有較大的影響．通過(guò)特倫德倫堡的工作使弗雷格了解到萊布尼茨關(guān)于邏輯語(yǔ)言的觀(guān)點(diǎn)．弗雷格還追隨特倫德倫堡，把他的邏輯符號系統稱(chēng)作“概念語(yǔ)言”．弗雷格用心研究萊布尼茨和I．康德(Kant)的邏輯學(xué)和數學(xué)哲學(xué)方面的著(zhù)作，有選擇地接受了兩位哲學(xué)家的思想．在弗雷格晚年，他是這樣描述自己的研究動(dòng)機的：“我開(kāi)始是搞數學(xué)．在我看來(lái)，這門(mén)科學(xué)急需更好的基礎：……語(yǔ)言邏輯的不完善對這種研究是一種障礙．我在《概念語(yǔ)言》中尋求彌補．所以，我就從數學(xué)轉向了邏輯．”
經(jīng)過(guò)5年的沉思，弗雷格完成了一部劃時(shí)代的著(zhù)作——《概念語(yǔ)言》．在這本書(shū)里，弗雷格把從洛采和特倫德倫堡，以及從萊布尼茨和康德那里得到的觀(guān)點(diǎn)，變成一種全新的邏輯．這本不足80頁(yè)的小書(shū)是弗雷格的不朽之作．弗雷格在此建立的邏輯有效地終結了亞里士多德邏輯兩千多年來(lái)一直占據的統治地位，完成了始于幾百年前G．伽利略(Galilei)破除亞里士多德物理學(xué)的進(jìn)程．在《概念語(yǔ)言》中，弗雷格創(chuàng )造了一種表意的語(yǔ)言，即“純粹思想的語(yǔ)言”．正如他在這本書(shū)的副標題中所說(shuō)——它可以使我們完全精確地表達判斷的概念內涵．弗雷格認為，真理分為兩種，一種真理的證明必須以經(jīng)驗事實(shí)為根據，例如物理學(xué)中的定理．另一種真理的證明似乎可以純粹從邏輯規律出發(fā)．他認為算術(shù)命題就是屬于后一種的．在探討如何根據思維的邏輯規律經(jīng)過(guò)推理以得到算術(shù)命題時(shí)，必須絕對嚴格，要防止未被查覺(jué)的直觀(guān)因素滲入，因此必須使推理過(guò)程沒(méi)有漏洞．他覺(jué)得日常語(yǔ)言是表達嚴密思想的障礙．當所表達的關(guān)系越復雜時(shí)，日常語(yǔ)言就越不能滿(mǎn)足要求．因此他創(chuàng )造了這種概念語(yǔ)言．他說(shuō)，用這種語(yǔ)言進(jìn)行推理，最有利于覺(jué)察隱含的前提和有漏洞的步驟．這種語(yǔ)言和日常語(yǔ)言相比，就好像機械手和人手相比，或者像顯微鏡和肉眼相比一樣．利用這種語(yǔ)言，弗雷格成功地構造了一個(gè)嚴格的邏輯演算體系．下面簡(jiǎn)要介紹一下弗雷格邏輯演算的內容．
1．弗雷格嚴格區別了命題的表達和斷定．他認為，我們只有能夠表達一個(gè)思想，理解一個(gè)思想，才能對它加以斷定．他引進(jìn)斷定符號“├”．“├┌”表示“┌是被斷定的”．其中垂直短線(xiàn)“｜”稱(chēng)為判斷短線(xiàn)，水平短線(xiàn)“—”稱(chēng)為內容短線(xiàn)．“—┌”是一個(gè)整體，它只表達可斷定的內容，即命題的表達．而“├┌”才表示命題的斷定．如“├┌”表示“不同的磁極相互吸引”這一斷言，而“—┌”只是表達了不同磁極相互吸引這一思想，而對這一思想的正確性沒(méi)有任何判斷．
2．弗雷格明確提出真值蘊涵的思想并指出它與日常語(yǔ)言的區別．他采用否定和蘊涵作為基本的邏輯聯(lián)結詞．他用小豎線(xiàn)“ ”放在內容短線(xiàn)下面表示否定．“┬┌”表示“非┌”．符號 表示“△蘊涵┌”．他列舉了┌和△的四種可能的真值組合：(1)┌肯定，△肯定；(2)┌肯定，△否定；(3)┌否定，△肯定；(4)┌否定，△否定．用符號“ ”表示以上第三種可能不實(shí)現而其余三個(gè)可能性中的每一個(gè)都可實(shí)現．弗雷格說(shuō)，當┌為真時(shí)，△蘊含┌?？杀粩喽?，在此情形下，△可以是任一命題，其具體內容完全無(wú)所謂．┌和△不必有因果關(guān)系，與日常語(yǔ)言中的“如果……則”不同．
3．弗雷格引進(jìn)一個(gè)內容同一的符號．設┌和△為任意名稱(chēng)，即不一定是命題記號，他規定，“├(┌≡△)”的意思是“名稱(chēng)┌和名稱(chēng)△有相同的概念內容，使得┌總是能由△替換，反之亦然”．他還指出，由他的新符號所聯(lián)結的名稱(chēng)不僅代表它們的內容而且代表名稱(chēng)自身．后來(lái)，他改用符號“=”，“=”不被看成兩個(gè)名字之間的關(guān)系，而是看成名字的指稱(chēng)之間的關(guān)系．“=”用于專(zhuān)門(mén)的指稱(chēng)，相當于等詞；用于命題的指稱(chēng)(真值)，則相當于現在的等值符號．
4．弗雷格把數學(xué)中的函數概念引入邏輯演算，從而建立了量詞的理論．他采用變目和函項兩個(gè)術(shù)語(yǔ)，┌表示變目，記號Φ(┌)表達變目┌的一個(gè)不確定的函項．記號Ψ(┌，△)表達按順序所取的兩個(gè)變目┌和△的一個(gè)函項．假定如下一種函項：當它由變目填滿(mǎn)時(shí)，它表達可能的判斷內容．于是，“├Φ(┌)”讀作“┌有性質(zhì)Φ”，“├Ψ(┌，△)”讀作“┌與△有關(guān)系Ψ”．弗雷格使用這種符號的主要優(yōu)點(diǎn)是，它能夠比普通語(yǔ)言所提供的方式更令人滿(mǎn)意地表達一般性．在此基礎上，弗雷格引進(jìn)了全稱(chēng)量詞和存在量詞
表示“不管怎樣取函項的變目，函項總是一個(gè)事實(shí)”．即“凡a都是Φ．在這里，全稱(chēng)量詞是基本概念，存在量詞則通過(guò)全稱(chēng)量詞而表達為
它表達“至少有一個(gè)a是Φ”．
5．弗雷格建立了9條公理，用現代的符號表示為：
(1)├a→(b→a)，
(2)├(c→(b→a))→((c→b)→(c→a))，
(3)├(d→(b→a))→(b→(d→a))，
(4)├(b→a)→(┐a→ ┐b)，
(5)├ ┐┐a→a，
(6)├a→ ┐┐a，
(7)├(c=d)→(f(c)→f(d))，
(8)├c=c，
公理以外有四條變形規則：
(2)代入規則，弗雷格使用了但沒(méi)有嚴格地陳述．
假定a并不在表達式Г中出現，而且a僅處于Φ(a)的變目空位中．
a不在┌和△中出現，Φ(a)中的a只處于變目空位中．事實(shí)上，這條規則是第三條規則的推廣．
弗雷格在上述公理和規則的基礎上，進(jìn)行了大量的推演，成功地構造了一種基本自足的邏輯演算，從而給出了歷史上第一個(gè)嚴格的關(guān)于邏輯規律的公理系統——現代的邏輯系統．它實(shí)質(zhì)上包含了作為現代數理邏輯基礎的兩個(gè)演算系統——命題演算系統和一階謂詞演算系統．
不幸的是，弗雷格這本劃時(shí)代的小冊子被數學(xué)家和哲學(xué)家們忽視了．他在《概念語(yǔ)言》中建立的新邏輯沒(méi)有馬上被人理解．其中使用復雜而陌生的符號來(lái)表達新奇的概念，確使讀者望而生畏．德國數學(xué)家E．施羅德(Schrder)發(fā)表長(cháng)篇文章，對該書(shū)進(jìn)行全面批評．事實(shí)上，直到B．A．W．羅素(Russell)1901年開(kāi)始發(fā)現弗雷格著(zhù)作的價(jià)值之前，《概念語(yǔ)言》幾乎沒(méi)有讀者．
《概念語(yǔ)言》出版之后，弗雷格的創(chuàng )造生涯進(jìn)入第二時(shí)期．在這一時(shí)期，弗雷格開(kāi)始形成邏輯主義的觀(guān)點(diǎn)．在最初幾年，他由于自己的著(zhù)作沒(méi)有受到重視而大受挫折，沒(méi)有發(fā)表任何作品．但他仍然在重新思考和深刻挖掘自己的哲學(xué)和數學(xué)觀(guān)點(diǎn)，并逐漸形成了他的數學(xué)哲學(xué)的三個(gè)主要原則：第一，他反對在數學(xué)基礎問(wèn)題上的經(jīng)驗主義，否認數學(xué)來(lái)源的經(jīng)驗基礎，強調數學(xué)真理的先天性；第二，他認為數學(xué)真理是客觀(guān)的，這種客觀(guān)性基于數學(xué)的非經(jīng)驗的基礎．在他看來(lái)，客觀(guān)性是思想的必要條件；第三，他主張一切數學(xué)最終都可化歸為邏輯，數學(xué)概念可以定義為邏輯普遍要求的概念，數學(xué)公理可以從邏輯原則中得到證明．這第三條原則后來(lái)被羅素作為邏輯主義的基本主張而廣為傳播，弗雷格因此成為邏輯主義的創(chuàng )始人之一．
弗雷格在《算術(shù)的基礎》中力圖作為邏輯的延展去建立數學(xué)．為此，首先要從邏輯推出算術(shù)．為使大家能夠理解他的著(zhù)作，他對自己的觀(guān)點(diǎn)及關(guān)于數和算術(shù)所流行的各種哲學(xué)觀(guān)點(diǎn)作了非形式的說(shuō)明．然后他指出，要從邏輯推出算術(shù)，首先必須給出數和自然數的定義．
弗雷格接受他的前輩的觀(guān)點(diǎn)：所有大于1的自然數可由指出它們的前趨即用“2=1+1”，“3=2+1”一類(lèi)等式來(lái)定義．但他認為，這些定義是不完全的，因為使用了“數1”和“加1”這兩個(gè)未定義的概念．他考察了從歐幾里得(Euclid)到G．康托爾(Cantor)以來(lái)的許多數學(xué)家的著(zhù)作，發(fā)現關(guān)于數的定義是相當混亂的．他指出在此之前所見(jiàn)到的一切關(guān)于數的定義都含有基本的邏輯錯誤．他說(shuō)：“數是什么？這是一個(gè)最根本的問(wèn)題．如果我們對這個(gè)問(wèn)題都不能做清楚的回答，豈不是一個(gè)笑話(huà)？”又說(shuō)：“數學(xué)的本質(zhì)就在于，一切能證明的都要證明，而不是通過(guò)歸納法來(lái)驗證．因此，我們也應考慮如何來(lái)證明關(guān)于正整數的命題．”
弗雷格發(fā)展了《概念語(yǔ)言》中關(guān)于數學(xué)序列的理論．在那里他用“遺傳性”定義了“y屬于從x開(kāi)始的f-序列”和“y是x的f-后裔”，為自然數的定義和說(shuō)明數學(xué)歸納法作了理論和技術(shù)上的準備．弗雷格給出的自然數的定義的核心在于使用了“一一對應”的概念：屬于兩個(gè)概念F和G的對象借助于關(guān)系Φ一一對應，如果(1)每一個(gè)屬于概念F的對象對于屬于概念G的一個(gè)對象，有關(guān)系Φ；(2)對于屬于概念G的每一個(gè)對象，存在一個(gè)屬于概念F并與前者有關(guān)系Φ的對象；(3)對所有x，y和z而言，如果x對y和z有關(guān)系Φ，那么y和z就是同樣的；(4)對所有x，y和z而言，如果x和y對z有關(guān)系Φ，那么x和y就是同樣的．
弗雷格在此基礎上構造了以下三個(gè)定義：
(1)“概念F與概念G是等數的”與“存在一個(gè)關(guān)系Φ，使得屬于概念F的對象與屬于概念G的對象一一對應”其意義是相同的．
(2)屬于概念F的數是“與概念F等數”這一概念的外延．
(3)“n是一個(gè)數”與“存在一個(gè)概念使得n是屬于它的數”其意義是相同的．
接著(zhù)他又定義了“n在自然數序列中是m的直接后繼”：“存在一個(gè)概念F和一個(gè)歸于它的對象x，使得屬于概念F的數是n，屬于概念‘歸于F但不同于x’的數是m”．這實(shí)質(zhì)上是后繼函數的定義．
在這些工作的基礎上，弗雷格取0作為數列的起點(diǎn)，提出如下定義：
0是屬于概念“不同于自身”的數，
1是屬于概念“同于0”的數，
2是屬于概念“同于0或同于1”的數，
3是屬于概念“同于0或同于1或同于2”的數，
……
可見(jiàn)，1在自然數序列中是0的直接后繼，2在自然數序列中是1的直接后繼，等等．
事實(shí)上，弗雷格所用到的“一一對應”概念與康托爾所謂的集合的“等價(jià)”意義是一樣的，弗雷格指出，他的數與康托爾理論中集合的“勢”或“基數”是相同的．兩個(gè)概念同數，就是兩個(gè)集合等價(jià)．概念“與概念F等數”的外延，就是與集合F等價(jià)的一切集合構成的集合．所以弗雷格實(shí)際上是把數定義為集合的集合，或類(lèi)的類(lèi)．利用康托爾的語(yǔ)言，概括弗雷格關(guān)于數的定義：
(1)一個(gè)集合的基數是所有等價(jià)于它的集合的集合．
(2)0=df?｛^｝(空集合的單元集)
1=df?｛0｝
2=df?｛0，1｝
3=df?｛0，1，2｝
弗雷格的后續函數的定義實(shí)際上是說(shuō)：后續函數把等價(jià)集合的集合m映射到一個(gè)新的集合的集合Φ(m)(即n)，Φ(m)中的每一個(gè)集合是由在m中的某一個(gè)集合加上一個(gè)新分子而得到．
由此可見(jiàn)，自然序列中的每一個(gè)數，有一個(gè)直接后繼的數．這樣，自然數就由0和后繼函數而確定下來(lái)．
有邏輯學(xué)家評論，弗雷格的這個(gè)定義系統是哲學(xué)技巧中極其卓越的成就．人們也很容易理解，為什么弗雷格認為他至少使得算術(shù)化歸為邏輯是可能的．
在《算術(shù)的基礎》的最后幾頁(yè)，弗雷格指出，其他類(lèi)型的數，也可以用類(lèi)似的方式加以定義．實(shí)數和復數同樣可以刻畫(huà)為概念的外延．在《基本規律》的第二卷中，他闡明了這個(gè)方案是如何實(shí)施于實(shí)數的．
康托爾在1884年也給出數的定義，但弗雷格的定義比康托爾的更為精確．
弗雷格從邏輯出發(fā)定義了數和自然數，他對自然數的歸納定義也是對數學(xué)歸納法的最好說(shuō)明．他認為，借助于上述定義，自然數的概念就被化歸成了邏輯的概念；自然數的理論則可以借助于上述定義和邏輯得到建立，這樣，算術(shù)理論就被“邏輯化”了．
弗雷格在他的第三時(shí)期集中精力寫(xiě)作《基本規律》．原計劃寫(xiě)三卷，實(shí)際上只完成兩卷(1893，1903)．弗雷格準備在這部專(zhuān)著(zhù)中，從邏輯出發(fā)去展開(kāi)除了幾何學(xué)以外的全部數學(xué)．他認為，邏輯的原則是完全可靠的，一旦完成了上述工作，數學(xué)“就被固定在一個(gè)永恒的基礎上了．”
1893年，出版了《基本規律》第一卷，它是《算術(shù)的基礎》的理論的嚴謹發(fā)展，書(shū)中改進(jìn)了《概念語(yǔ)言》符號系統，提出了不同的公理，闡述了高階謂詞演算．從《概念語(yǔ)言》到《基本規律》，弗雷格的邏輯發(fā)生了三個(gè)主要變化：(1)他在自己的系統中加上了函項的值域這一概念；(2)區分了意義的兩個(gè)方面，即“所指”和“意義”；(3)更為嚴格地規定了與對象相對的函項的性質(zhì)，明確提出了“第一層函項”和“第二層函項”的區別．第一層函項就是以前所定義的函項，其變目是對象，第二層函項就是函項的函項，其變目是函項，例如在Mβ(F(β))中，Mβ就是第二層函項，其變目是F．弗雷格還把概念分為第一層概念和第二層概念．這些邏輯上的變化在《基本規律》第一卷之前的5篇文章①中就已經(jīng)提出并作了解釋?zhuān)?br> 弗雷格在《基本規律》第一卷中建立了另一個(gè)邏輯系統——二階謂詞演算，提出了新的公理．他用‘xF(x)代表F(x)的值域，例如，若F(x)表達“x是人”，則它的值域‘xF(x)就表達“人類(lèi)”．他還引進(jìn)代表定冠詞的函項符號＼x．如＼’xF(x)讀為“那個(gè)具有性質(zhì)F的x”．用現在的符號表示弗雷格的新公理如下：
在這個(gè)新系統中，除分離規則和代入規則之外，弗雷格還把原來(lái)系統的一些公理和定理作為新的推理規則．在這一系統中處理了命題演算，謂詞演算，類(lèi)理論和關(guān)系理論，更重要的是進(jìn)行了推導算術(shù)的工作．
《基本規律》第一卷出版后，再次受到冷遇．只有G．皮亞諾(Peano)在1895年作了評述，但他對這本書(shū)的內容沒(méi)有足夠的理解．這再一次使弗雷格深感痛苦．然而，弗雷格并沒(méi)有放棄自己的目標，他繼續撰寫(xiě)《基本規律》第二卷，其中主要論述實(shí)數的理論，并用較多的篇幅批評當時(shí)流行的觀(guān)點(diǎn)．
但是，弗雷格并沒(méi)有完成他的計劃．因為要理解數學(xué)科學(xué)的性質(zhì)，除了算術(shù)以外，還必須考慮無(wú)窮集合的理論——集合論．弗雷格沒(méi)有深入研究集合論，沒(méi)有接觸到關(guān)于無(wú)窮集合的各種問(wèn)題，特別是悖論問(wèn)題．1902年，正當弗雷格等待《基本規律》第二卷付印的時(shí)候，他收到了羅素6月16日寫(xiě)給他的信．信中首先稱(chēng)頌他的工作：“就我所知，您的工作是我們時(shí)代中最好的．”“在許多具體問(wèn)題上，我發(fā)現您的著(zhù)作都進(jìn)行了討論、區分和定義，這使其他邏輯學(xué)家的工作黯然失色．”具有諷刺意味的是，羅素的來(lái)信既標志著(zhù)弗雷格的工作開(kāi)始得到承認，也宣告了他的獨創(chuàng )性工作的終結．因為羅素在他的信中接著(zhù)寫(xiě)道：
“只有在一點(diǎn)上我遇到了困難①，……由于下述矛盾：令W為不能論斷自身的謂詞的謂詞，W可以論斷自身嗎？每種回答都隱含著(zhù)它的否定①，因而人們必須得出，W不是一個(gè)謂詞．同理，沒(méi)有不包含自身的作為整體的類(lèi)的類(lèi)．由此我得到，在某種條件下，一個(gè)可定義的集合沒(méi)有構成一個(gè)整體．”
羅素當時(shí)并沒(méi)有完全認識到他的發(fā)現是怎樣嚴重地威協(xié)著(zhù)弗雷格的邏輯主義綱領(lǐng)．但是，弗雷格本人毫無(wú)疑問(wèn)地認識到這個(gè)矛盾的潛在致命力．他對羅素來(lái)信的反映迅速而強烈，他馬上復信[15]：
“您發(fā)現的矛盾引起了我極大的震驚，我幾乎可以說(shuō)是驚愕不已，因為它動(dòng)搖了我建立算術(shù)基礎的企圖，……我的《基本規則》第二卷看來(lái)是有缺陷的．我無(wú)疑要補充一個(gè)附錄，對您的發(fā)現作出論述．”
在1903年，弗雷格出版了帶有一個(gè)后記(寫(xiě)于1902年10月)的《基本規則》的第二卷．他在后記中不無(wú)悲哀地寫(xiě)道：
“對于一個(gè)科學(xué)工作者來(lái)說(shuō)，最不幸的事情莫過(guò)于：當他完成他的工作時(shí)，發(fā)現他的知識大廈的一塊基石突然動(dòng)搖了．正當本書(shū)的印刷接近完成之際，伯倫特?羅素先生給我的一封信使我陷入這種境地．這封信是關(guān)于我的公理V的問(wèn)題．我本人從來(lái)沒(méi)有掩蓋這條公理缺乏其他公理所具有的并必為邏輯規律所正當要求的自明性．
……
成為問(wèn)題的恰恰不是我建立算術(shù)的特殊方式，而是算術(shù)是否完全可能有一個(gè)邏輯基礎．”
弗雷格的第四時(shí)期是在極度消沉中度過(guò)的．這一時(shí)期長(cháng)達十幾年．最初，他相信能有補救的辦法使他的系統避免矛盾．他首先提出一種設想：可能有一些概念沒(méi)有相應的類(lèi)．然后他用修改第Ⅴ公理的辦法來(lái)阻止羅素悖論的衍生．但是，后來(lái)邏輯學(xué)家的工作證明，他所做的努力并不足以使他的系統避免不一致．他還打算論述集合論的邏輯悖論(1906)．經(jīng)過(guò)幾年的努力之后，弗雷格似乎不那么相信能夠找到解決矛盾的辦法．雖然他沒(méi)有公開(kāi)放棄自己的主張，但也不再做進(jìn)一步的努力．至到1918年，弗雷格才徹底放棄把算術(shù)化歸為邏輯的一切希望，放棄了《基本規律》第三卷的寫(xiě)作計劃．從此以后，他又進(jìn)入了新的研究時(shí)期．他的研究興趣仍在數學(xué)基礎上，并很自然地轉向幾何學(xué)，提出了幾何學(xué)是整個(gè)數學(xué)的基礎的主張．弗雷格在1903年以后發(fā)表的論著(zhù)很少．
雖然弗雷格的邏輯主義綱領(lǐng)沒(méi)有實(shí)現，但是他的獨創(chuàng )性工作對數學(xué)和哲學(xué)的發(fā)展都產(chǎn)生了重要影響．他的成就在有生之年沒(méi)有得到廣泛的承認，只是通過(guò)少數幾位有洞察力的人的努力，他的思想才逐漸得到理解，并通過(guò)他們的工作得到發(fā)展．
首先認識到弗雷格工作重要性的是羅素．羅素在他的《數學(xué)原理》(Principles of mathematics，1903)的附錄中，對弗雷格的邏輯進(jìn)行了深入細致的研究，對弗雷格的從《概念語(yǔ)言》到《基本規律》第一卷等論著(zhù)作了廣泛詳盡的評論．羅素發(fā)展了弗雷格的思想，他和A．N．懷特海(Whitehead)在《數學(xué)原理》(Principia mathematica，1910)中精詳論證，充分展開(kāi)了邏輯主義綱領(lǐng)．書(shū)中可以看出弗雷格的明顯影響，甚至羅素與弗雷格不同的觀(guān)點(diǎn)也是受到弗雷格著(zhù)作中難點(diǎn)的啟示而提出的．羅素表示：“在邏輯分析問(wèn)題上，我們主要是從弗雷格獲得教益．”稍后，羅素的學(xué)生和朋友L．維特根斯坦(Wittgenstein)成為弗雷格的崇拜者．這位20世紀的著(zhù)名思想家明確指出，他的哲學(xué)工作的兩個(gè)來(lái)源是“弗雷格的巨著(zhù)和我的朋友羅索的著(zhù)作”．30年代末期，由弗雷格本人的學(xué)生L．卡爾納普(Carnap)以及美國邏輯學(xué)家A．丘奇(Church)的倡導，弗雷格的邏輯理論，特別是關(guān)于意義和所指的學(xué)說(shuō)重新引起人們的研究興趣[27]．1950年，《算術(shù)的基礎》英譯本出版，在使用英語(yǔ)的數學(xué)家中產(chǎn)生很大影響．
1918年以前，弗雷格一直安靜地生活在耶拿這座小小的大學(xué)城內．他身材矮小，性格膽怯羞澀．弗雷格的工作長(cháng)期得不到理解和承認．一般認為，他的著(zhù)作對于大多數數學(xué)家來(lái)說(shuō)是過(guò)于哲學(xué)化了，而對大多數哲學(xué)家來(lái)說(shuō)又過(guò)于數學(xué)化了．弗雷格的著(zhù)作長(cháng)期受到冷遇，在相當長(cháng)一段時(shí)間內，哲學(xué)雜志和數學(xué)雜志都拒絕發(fā)表他的論文．由于得不到專(zhuān)業(yè)上的承認，他在耶拿大學(xué)當了好多年的編外教授．弗雷格還經(jīng)受了長(cháng)遠計劃失敗的體驗．所有這一切使他變得比較內向．他長(cháng)期遠離自己的數學(xué)和哲學(xué)同事．但是，弗雷格全心全意追求真理，從不追求個(gè)人名聲；他屢受拙折而不放棄自己的奮斗目標；他勇于承認自己的失敗并另辟蹊徑提出新的主張．弗雷格這種追求真理的執著(zhù)精神和科學(xué)態(tài)度值得后人學(xué)習．
蘋(píng)果樹(shù)下的散步
歐洲有個(gè)古老的傳說(shuō)：一輛著(zhù)名的戰車(chē)，被一根山茱萸樹(shù)皮編制的繩索牢牢地捆住了。你要想取得統治世界的王位嗎？那就必須解開(kāi)這個(gè)繩結。無(wú)數聰明、強悍的勇士滿(mǎn)懷希望而來(lái)，垂頭喪氣而去，因為繩結盤(pán)旋纏繞，繩頭隱藏難尋。一天，亞歷山大也慕名來(lái)到這里，他略略思索一下，便果斷地抽出寶劍，一劍把繩截成兩段。難解的繩結就這樣輕而易舉地被“解開(kāi)”了。亞歷山大因此享有對整個(gè)世界的統治權。
1888年9月6日，人們驚喜地獲悉：十多年來(lái)許多數學(xué)家為之奮斗的著(zhù)名難題——果爾丹問(wèn)題，終于被一位當時(shí)尚名不見(jiàn)經(jīng)傳的青年人攻克了。他運用的方法和途徑是那樣的出人意料、令人折服，就像亞歷山大解開(kāi)繩結一樣；也正如這位顯赫的君主在遼闊的歐亞大陸上留下曠世戰功，這位年輕人窮盡畢生心血和才華，在廣闊的數學(xué)領(lǐng)域里縱橫捭闔，遍及現代數學(xué)幾乎所有的前沿陣地，在整個(gè)數學(xué)的版圖上，到處都刻下他那光輝的名字。他就是數學(xué)世界的亞歷山大——大衛?希爾伯特！
哥尼斯堡是德國一座古老而美麗的城市，康德、哥德巴赫是這座城堡的榮譽(yù)和驕傲，著(zhù)名的七橋問(wèn)題更使之名揚歐洲。1862年1月23日，希爾伯特就誕生在這座富有學(xué)術(shù)傳統的城市里。受家庭的熏陶，早在中學(xué)時(shí)代，希爾伯特對數學(xué)就表現出濃厚的興趣，并立志把數學(xué)作為自己奮斗的專(zhuān)業(yè)。
1880年秋，希爾伯特進(jìn)入哥尼斯堡大學(xué)。這里的學(xué)術(shù)空氣濃厚而且自由，非常適宜希爾伯特的生活習性和學(xué)習要求。這段時(shí)間內，他同兩位年輕的數學(xué)家的交往使他受益終生。一位是比他大3歲的胡爾維茨，在希爾伯特還是學(xué)生時(shí)，這位見(jiàn)多識廣的青年就已是副教授；另一位是閔可夫斯基，雖比希爾伯特小兩歲，但已榮獲巴黎科學(xué)院大獎而名揚國際。他們三位一體，情投意合。他們每天下午“準5點(diǎn)”相會(huì )于校園旁邊的蘋(píng)果樹(shù)下，互相交流彼此的學(xué)習心得、制訂計劃、探索未知領(lǐng)域。對于每一個(gè)重大問(wèn)題，他們總是分頭準備、認真思考，并各抒己見(jiàn)，有時(shí)也會(huì )爭得面紅耳赤。據說(shuō)，曾有一位前來(lái)哥尼斯堡大學(xué)訪(fǎng)問(wèn)的外地學(xué)者，這天偶然經(jīng)過(guò)蘋(píng)果園，忽然聽(tīng)到里面傳出幾個(gè)人互不相讓的爭吵聲，他駐足而觀(guān)，發(fā)現三位年輕人比比劃劃，旁若無(wú)人。這位好心的人覺(jué)得有必要去勸解一下，但馬上就知道自己的擔心是多余的。那正是希爾伯特三人在討論問(wèn)題。
蘋(píng)果樹(shù)下的小路清晰地向遠方延伸。他們通過(guò)日復一日的無(wú)數次散步，漫游了數學(xué)世界的每一個(gè)角落。這種數學(xué)家們特有的學(xué)習方式給他們其中的每一位帶來(lái)了希望、成功和友誼。
蘋(píng)果樹(shù)下的散步使希爾伯特利用有趣而又容易接受的學(xué)習方式像海綿吸水那樣接受數學(xué)知識，并以最簡(jiǎn)潔、快速的方法到達數學(xué)研究的前沿陣地。胡爾維茨淵博、系統的知識，閔可夫斯基快捷、靈敏的思維，無(wú)不令希爾伯特如醉如癡，也激勵著(zhù)他更加如饑似渴地學(xué)習、思考。這段時(shí)光為希爾伯特打下了牢固而全面的基礎，他也因之能在以后的歲月里頻頻出擊，并獲得數學(xué)麥加——哥廷根大學(xué)的教授席位。
英國現代計算機的起步的是從納粹德國的“謎”開(kāi)始的?！爸i”（Enigma）是一種密碼電報機，由德國人在一戰和二戰之間研制成功?！爸i”能把日常語(yǔ)言變?yōu)榇a，通過(guò)無(wú)線(xiàn)電或電話(huà)線(xiàn)路秘密傳送。它是一個(gè)木箱子，配有一臺打字機，箱上有26個(gè)閃爍不停的小燈泡，與打字機鍵盤(pán)的26個(gè)字母相對應?！爸i”的設計無(wú)懈可擊，有一套極精密的解碼設置，非一般的電報密碼所能比擬。在內行人看來(lái)，平白如話(huà)，但在旁人，又是無(wú)從索解的天書(shū)。因此，這臺看似平常的機器，有了“謎”的稱(chēng)號。這樣，德國的“謎”引起了英國情報部門(mén)高度的興趣。常規的解碼方式奈何不了“謎”，怎么辦？
這時(shí)，天才的數學(xué)家圖靈出現了。1931年圖靈進(jìn)入劍橋大學(xué)國王學(xué)院，開(kāi)始了他的數學(xué)天涯。一到那里，圖靈開(kāi)始嶄露頭角，畢業(yè)后去美國普林斯頓大學(xué)攻讀博士學(xué)位，在那里就發(fā)明過(guò)一個(gè)解碼器（Encipher），二戰爆發(fā)后回到劍橋。
在劍橋，圖靈是一個(gè)婦孺皆知的怪才，常有出人意表的舉動(dòng)。他每天騎自行車(chē)到離公寓3公里的一個(gè)叫布雷奇萊公園（Bletchley Park）的地方上班，因?；歼^(guò)敏性鼻炎，一遇花粉，鼻涕不止，圖靈就常戴防毒面具騎車(chē)上班，招搖過(guò)市，成為劍橋的一大奇觀(guān)。
他的自行車(chē)鏈條經(jīng)常在半道上掉落，要是換了別人，早就去車(chē)鋪修理了。而圖靈偏不，他在琢磨，發(fā)現這鏈條總是踏到一定的圈數時(shí)下滑，圖靈在騎車(chē)時(shí)就特別留心計算，于是能做到在鏈條下滑前一剎那戛然停車(chē)！讓旁人嘆服不已，以為是在玩雜耍。后來(lái)他居然在踏腳旁裝了一個(gè)小巧的機械計數器，到圈數時(shí)就停，好換換腦筋想些別的問(wèn)題。圖靈的腦袋轉得比自行車(chē)飛輪還快。
用圖靈的腦袋來(lái)破譯德國的“謎”看來(lái)不是什么難事。二戰爆發(fā)后，圖靈成為英國外交部通信部門(mén)戰時(shí)公務(wù)員，主要負責解碼。他果然不負眾望，成功破譯了“謎”。而德國人還蒙在鼓里，還以為他們的“謎”能一直迷下去，照用不誤，泄露了大量的核心機密，在戰事上屢屢遭挫，戰后，圖靈被授予帝國勛章。至于圖靈如何破譯“謎”的，由于英國政府嚴格的保密法令，一直沒(méi)有公之于世。所以圖靈破譯“謎”也成為一個(gè)“謎”。
早在30年代初，圖靈就發(fā)表了一篇著(zhù)名的論文《論數字計算在決斷難題中的應用》，他提出了一種十分簡(jiǎn)單但運算能力極強的理想計算裝置，用它來(lái)計算所有能想象得到的可計算函數。它由一個(gè)控制器和一根假設兩端無(wú)界的工作帶組成，工作帶起著(zhù)存儲器的作用，它被劃分為大小相同的方格，每一格上可書(shū)寫(xiě)一個(gè)給定字母表上的符號?？刂破骺梢栽趲献笥乙苿?dòng)，控制帶有一個(gè)讀寫(xiě)頭，讀寫(xiě)頭可以讀出控制器訪(fǎng)問(wèn)的格子上的符號，也能改寫(xiě)和抹去這一符號。
這一裝置只是一種理想的計算模型，或者說(shuō)是一種理想中的計算機。正如飛機的真正成功得力于空氣動(dòng)力學(xué)一樣，圖靈的這一思想奠定了整個(gè)現代計算機的理論基礎。這就是電腦史上與“馮·諾依曼機器”齊名的“圖靈機”。
圖靈機被公認為現代計算機的原型，這臺機器可以讀入一系列的零和一，這些數字代表了解決某一問(wèn)題所需要的步驟，按這個(gè)步驟走下去，就可以解決某一特定的問(wèn)題。這種觀(guān)念在當時(shí)是具有革命性意義的，因為即使在50年代的時(shí)候，大部分的計算機還只能解決某一特定問(wèn)題，不是通用的，而圖靈機從理論上卻是通用機。在圖靈看來(lái)，這臺機器只用保留一些最簡(jiǎn)單的指令，一個(gè)復雜的工作只用把它分解為這幾個(gè)最簡(jiǎn)單的操作就可以實(shí)現了，在當時(shí)他能夠具有這樣的思想確實(shí)是很了不起的。他相信有一個(gè)算法可以解決大部分問(wèn)題，而困難的部分則是如何確定最簡(jiǎn)單的指令集，怎么樣的指令集才是最少的，而且又能頂用，還有一個(gè)難點(diǎn)是如何將復雜問(wèn)題分解為這些指令的問(wèn)題。
此后圖靈在國家物理學(xué)實(shí)驗室（NPL）工作，并繼續為數字式計算機努力，在那里人發(fā)明了自動(dòng)計算機（Automatic Computing Engine，ACE），在這一時(shí)期他開(kāi)始探索計算機與自然的關(guān)系。他寫(xiě)了一篇名為《智能機》的文章于1969發(fā)表，這時(shí)便開(kāi)始有了人工智能的雛形。
圖靈相信機器可以模擬人的智力，他也深知讓人們接受這一想法的困難，今天仍然有許多人認為人的大腦是不可能用機器模仿的。而在圖靈認為，這樣的機器一定是存在的。圖靈經(jīng)常和其它科學(xué)家發(fā)生爭論，爭論的問(wèn)題就是機器實(shí)現人類(lèi)智能的問(wèn)題，在今天我們看來(lái)這沒(méi)有什么，但是在當時(shí)這可不太容易被人接受。他經(jīng)常問(wèn)他的同事，你們能不能找到一個(gè)計算機不能回答的問(wèn)題，當時(shí)計算機處理多選問(wèn)題已經(jīng)可以了，可是對于文章的處理還根本不可能，但今天的發(fā)展證明了圖靈的遠見(jiàn)，今天的計算機已經(jīng)可以讀寫(xiě)一些簡(jiǎn)單的文章了。
圖靈相信如果模擬人類(lèi)大腦的思維就可以做出一臺可以思考的機器，它于1950寫(xiě)文章提出了著(zhù)名的“圖靈測試”，測試是讓人類(lèi)考官通過(guò)鍵盤(pán)向一個(gè)人和一個(gè)機器發(fā)問(wèn)，這個(gè)考官不知道他現在問(wèn)的是人還是機器。如果在經(jīng)過(guò)一定時(shí)間的提問(wèn)以后，這位人類(lèi)考官不能確定誰(shuí)是人誰(shuí)是機器，那這個(gè)機器就有智力了。這個(gè)測試在我們想起來(lái)十分簡(jiǎn)單，可是偉大的思想就源于這種簡(jiǎn)單的事物之中。
現在已經(jīng)有軟件可以通過(guò)圖靈測試的子測試，軟件這個(gè)人類(lèi)智慧的機器反映應該可以解決一些人類(lèi)智力的問(wèn)題。在完成ACE之前，圖靈離開(kāi)了NPL，它在曼徹斯特大學(xué)開(kāi)發(fā)曼徹斯特自動(dòng)計算機（Manchester Automatic Digital Machine，MADAM）。他相信在2000年前一定可以制造出可以模擬人類(lèi)智力的機器，圖靈開(kāi)始創(chuàng )立算法，并使用MADAM繼續他的工作。
查爾斯·霍爾
---從QUICKSORT、CASE到程序設計語(yǔ)言程序設計語(yǔ)言的公理化
學(xué)過(guò)“數據結構”或“算法設計與分析”的人都知道著(zhù)名的快速排序算法QUICKSORT；編過(guò)程序的人大概也都用過(guò)實(shí)現條件轉移的最方便的語(yǔ)句CASE語(yǔ)句。但是你知道這個(gè)算法和這個(gè)語(yǔ)句是誰(shuí)發(fā)明的嗎?它們的發(fā)明者就是1990年IEEE計算機先驅獎和1980年圖靈獎的獲得者英國牛津大學(xué)計算機科學(xué)家查爾斯·霍爾(Charles AntonyRichard Hoare)。當然霍爾之所以獲得這兩項大獎決不僅僅是因為他發(fā)明了QUICKSORT和CASE，而是因為他在計算機科學(xué)技術(shù)的發(fā)展中，尤其是在程序設計語(yǔ)言的定義和設計、數據結構和算法、操作系統等許多方面都起了重要的作用，有一系列發(fā)明創(chuàng )造，QUICKSORT和CASE只是其中的一小部分而已。
霍爾于1934年1月11日誕生于英國南部。在坎特伯雷(Canter·bury)的國王學(xué)校(King’s Sch001)度過(guò)中學(xué)階段以后，進(jìn)入牛津的莫頓學(xué)院(Merton College)學(xué)習數學(xué)，1960年取得碩士學(xué)位。之后他進(jìn)入倫敦一家不大的計算機生產(chǎn)廠(chǎng)家Elliott Brothers公司，為該公司的Elliott 803計算機編寫(xiě)庫子程序，從此開(kāi)始他的計算機生涯。QUICK，SORT就是他在那個(gè)時(shí)候用原有的SHELLSORT(以算法的發(fā)明人D．L．Shell命名的通過(guò)調換并移動(dòng)數據項實(shí)現排序的一種算法，發(fā)明于1959年)編程時(shí)分析了它的缺點(diǎn)而發(fā)明出來(lái)的。QUICKSORT具有“快刀斬亂麻”的特點(diǎn)，能迅速地對亂序作大幅度調整，特別適合于因多次追加、刪除而變得雜亂無(wú)章的數據集合。QUICKSORT是利用“分治法”(divide and conquer)進(jìn)行算法設計的一個(gè)成功范例，它的發(fā)明是霍爾在計算機方面的天才的第一次顯露，受到老板的贊賞和重視。第二年，霍爾接受了一個(gè)新的任務(wù)，為公司的新機型Elliott 503設計一個(gè)新的高級語(yǔ)言。但就在其時(shí)，他弄到了一份Algol 60報告的復印件，還參加了一個(gè)由狄克斯特拉(E．W．D恥stra，首屆計算機先驅獎獲得者)等人在布賴(lài)頓舉辦的Algol 60培訓班，感到與其自己沒(méi)有把握地去設計一個(gè)新的語(yǔ)言，還不如將比較成熟的Algol 60在Elliott 503上加以實(shí)現?；魻柡退耐聜兊倪@個(gè)想法獲得公司同意以后，由霍爾主持設計與實(shí)現了Algol 60的一個(gè)子集的版本?；魻栐陂_(kāi)發(fā)初首先制定了明確的目標，即系統要安全可靠，生成的目標碼要簡(jiǎn)潔，工作區數據要緊湊，過(guò)程和函數的人口和出口要清晰、嚴密等，還明確了整個(gè)編譯過(guò)程采用一次掃描等原則。這樣，ElliottAl-gol的開(kāi)發(fā)十分順利與成功，它在1963年中推出以后大受歡迎，成為世界各國所開(kāi)發(fā)的Algol 60的各種版本中在效率、可靠性和方便性等方面的性能指標都首屈一指的一個(gè)版本，霍爾本人也從此受到國際學(xué)術(shù)界的重視。國際信息處理聯(lián)盟IFIP后來(lái)任命霍爾為2．1工作組(WorkingGroup 2．1)的負責人，這個(gè)工作組的任務(wù)是維護和發(fā)展Algol?；魻柟徊回摫娡?，主持設計了Algol X以繼承與發(fā)展Algol60。正是在A(yíng)lgolX的設計中，霍爾發(fā)明了CASE語(yǔ)句。CASE語(yǔ)句具有如下形式的語(yǔ)法結構：
CASE E of
C1:S1；
C2:S2；
.
.
.
Cn-1:Sn-1;
Otherwise:Sn
End
其中E是一個(gè)表達式，稱(chēng)為“選擇子”(Selector)，每個(gè)Ci的值為常數，稱(chēng)為“分情形標號”，Si則為可執行語(yǔ)句。CASE語(yǔ)句的含義是：若E的值等于某個(gè)Ci的值，則執行其后的Si(i=1，2，3，…，n—1)，否則執行Sn。某個(gè)Si或S。執行完之后，整個(gè)CASE語(yǔ)句也就執行完畢。由于CASE語(yǔ)句構成多路分支，程序結構清晰、直觀(guān)，所以CASE語(yǔ)句后來(lái)幾乎成為程序設計語(yǔ)言的標準，被各種語(yǔ)言廣泛采用。在C語(yǔ)言中，沒(méi)有獨立的CASE語(yǔ)句，但它的SWITCH語(yǔ)句(開(kāi)關(guān)語(yǔ)句)實(shí)際上是在CASE語(yǔ)句的基礎上形成的：
switch E
{case C1:S1；
case C2:S2；
.
.
.
case Cn-1:Sn-1;
[default:Sn]
不同之處有二：一是C；可以是表達式，但計算結果必須仍是常數；二是E的結果若不等于某個(gè)Ci(i=1，2，3，…，n—1)的值，則視有無(wú)default子句，若有，執行Sn；若無(wú)，則什么也不執行，控制轉向SWITCH后的語(yǔ)句。顯然，這些都是對CASE語(yǔ)句的進(jìn)一步改進(jìn)。
霍爾于1968年離開(kāi)Elliott，離開(kāi)產(chǎn)業(yè)界，原因是作為學(xué)者他對程序設計浯言的形式化定義這類(lèi)更偏重于學(xué)術(shù)性和理論性的課題更感興趣。離開(kāi)Elliott以后，他任職過(guò)一年英國國家計算中心主任，發(fā)現自己也不適于從事行政管理，因此又轉入愛(ài)爾蘭的昆土大學(xué)(Queen’s University)，從事教學(xué)和研究，1977年轉入牛津大學(xué)。離開(kāi)Elliott以后，霍爾在計算機科學(xué)理論的研究中發(fā)揮其特長(cháng)，作出了許多創(chuàng )造性的重大貢獻。首先是1969年10月，霍爾在Communications of ACM上發(fā)表了他那篇有里程碑意義的論文“計算機程序設計的公理基礎”(An Axiomatic Basis for Computer Programming)。在這篇論文中，霍爾提出了程序設計語(yǔ)言的公理化定義方法，即公理語(yǔ)義學(xué)(axiomatic semantics)，也就是用一組公理和一組規則描寫(xiě)語(yǔ)言應有的性質(zhì)，從而使語(yǔ)言與具體實(shí)現的機器無(wú)關(guān)，而且也易于證明程序的正確性。這是繼麥卡錫(J．McCarthy，1985年計算機先驅獎獲得者)在1963年提出用遞歸函數定義程序、弗洛伊德(R．W．Floyd，1991年計算機先驅獎獲得者)在1967年提出基于程序流程圖的歸納斷言法以后，在程序邏輯研究中所取得的又一個(gè)重大技術(shù)進(jìn)展?；魻柼岢龅姆椒ㄔ谶壿嬌吓c弗洛伊德提出的方法類(lèi)似，但不是用流程圖而是用代數法，即控制流用以下一些結構表示：
begin al；a2；a3；…；an end
if p then a1 else a2
while p do a
后面為了方便，我們用到第一個(gè)結構時(shí)省略首尾的begin和end。
相應于弗洛伊德的驗證條件，霍爾引入下列符號：
p{a}q
其意義是：如果在執行。之前P(叫做precondition)成立，則當α執行完了后q(叫做postcondition)成立。
霍爾給出了以下一組證明規則(proof rule)或叫推導規則：
p’ pp{a}qq→q’
1.
p’{a}q’
這個(gè)規則中的p’→和q’→q是普通數理邏輯中的斷言命題，表示若p’(或q’)成立，則p(或q)成立。這個(gè)規則表示，若橫線(xiàn)以上的p’→p、p{a}q、q→q’成立，則橫線(xiàn)以下的p’{a}q1成立。
2．
P(e){x:=e}p(x)
這個(gè)規則表示，如果在將e賦給x之前p(e)成立，則其后p(x)成立。
3． P{a}qqr
p{a;b}r
這個(gè)規則表示的是“傳遞律”(transitive law)，即如果執行α之前p成立，α執行完了以后q成立；而如果執行b之前q成立，b執行完了以后r成立，則若在動(dòng)作序列。和^執行之前P成立，則a和b執行完了以后r成立。
4. p∧r{a}qp∧～r(b)q
p{if r then a else b}q
這個(gè)規則中的∧和～是一般數理邏輯中的合取(conjunction)和否定(negation)連接詞。這個(gè)規則定義了if-then-else的執行取決于precondition r的值。
5. p∧q{a}p
p{while q do a}p∧～q
這個(gè)規則定義了while循環(huán)：p是循環(huán)不變量（loop invariant），而q是終止循環(huán)的條件。
下面我們舉一個(gè)例子說(shuō)明如何用霍爾建立的系統驗證程序的正確性。設有計算n的階乘n！的如下程序：
A: x:1;B
B: while y>0 do C
C: x:y×x;y:=y-1
則通過(guò)下列霍爾斷言可以證明上述程序是正確的，因為這些斷言都是真的，而且在霍爾的系統中是可以被證明的，而最后一個(gè)斷言正是我們所要尋求的結論，因此它們形成對上述階乘程序正確性的說(shuō)明。
i. y>0∧x×y! =n! {x:=y×x}y>0∧x×(y-1)! =n!
[首先y>0∧x×y! =n!→y>0∧(y×x)×(y-1)! =n!]
然后用規則（2），用x代替y×x]
ii. y>0∧x×(y-1)! =n!{y:=y-1}y≥0∧x×y! =n!
[類(lèi)似（i），利用規則（2）]
iii．y>0∧x×y! =n! {C}y≤0∧x×y! =n!
[對(i)和(ii)用規則(3)]
iv．Y≥0∧y=n∧x=1{B}x=n!
[因為] y=n∧x=1→x×y! =n!
又因為0！ =1，所以Y≥0∧x×y! =n! ∧y≤0→y=0∧x=n! →x×y! =n!
根據（iii），利用規則（5），令（5）中p=y≤0∧x×y! =n!，q=y>0，孥可得(iv)]
v. y≥0∧y=n{x:=1}y≥0∧y!=n∧x=1
[因為p{x:=1}p∧x=1]
vi. y≥0∧y=n{A}x=n!
[對（V）和(Vi)利用規則(3)]
因為(vi)中的precondition正好是n的初始條件，而postcondition給出了所需結果，這樣就證明了程序可算出n!。
為了給出證明，應該從程序的最后一行開(kāi)始逐步后推。在這個(gè)例子中，(iii)步是最關(guān)鍵的，其中y≥0∧x×y! =n!就是循環(huán)不變量或歸納假設(induction hypothesis)。
利用霍爾提出的這種方法，已經(jīng)成功地描述了PASCAL等語(yǔ)言，說(shuō)明了這個(gè)方法的巨大威力。但應該指出的是，霍爾的這個(gè)方法是不完備的，因為霍爾在開(kāi)發(fā)和建立這個(gè)系統時(shí)并沒(méi)有追求系統的完備性，而更多地追求系統的實(shí)用性。
在數據類(lèi)型、數據結構和操作系統設計等方面，霍爾也做了許多開(kāi)創(chuàng )性的工作。目前廣泛流行與應用著(zhù)的許多概念都源于霍爾的工作。例如，關(guān)于抽象數據類(lèi)型的規格說(shuō)明(Specification，也叫規約)與其實(shí)現是否一致，就是由霍爾于1972年公式化了的?；魻柾ㄟ^(guò)前后斷言方法用已經(jīng)定義了的(抽象)數據類(lèi)型給出所要定義的新類(lèi)型的抽象模型，這成為抽象數據類(lèi)型規格說(shuō)明的兩種主要方法之一，即模型方法(另一方法為基于異調代數理論的代數方法)。對于操作系統的設計與實(shí)現十分關(guān)鍵的monitor(監控程序)的概念也是霍爾首先提出，并界定了它的作用與功能，即作為操作系統的核心，在把操作系統看做虛擬機擴充時(shí)，monitor是硬件的第一次擴充，它完成中斷處理、進(jìn)程控制與進(jìn)程通信、存儲區動(dòng)態(tài)分配，建立軟時(shí)鐘，驅動(dòng)設備通道，進(jìn)行處理機調度。monitor為外面各層的設計提供良好的環(huán)境，并提高系統的安全性。
20世紀70年代后期，霍爾又深入研究了運行在不同的機器上的若干個(gè)程序之間如何互相通信、互相交換數據的問(wèn)題，實(shí)現了面向分布式系統的程序設計語(yǔ)言CSP。在該語(yǔ)言中，一個(gè)并發(fā)系統由若干并行運行的順序進(jìn)程組成，每個(gè)進(jìn)程不能對其他進(jìn)程的變量賦值。進(jìn)程之間只能通過(guò)一對通信原語(yǔ)實(shí)現協(xié)作：Q?x表示從進(jìn)程Q輸入一個(gè)值到變量x中；P!e表示把表達式e的值發(fā)送給進(jìn)程戶(hù)。當戶(hù)進(jìn)程執行Q?x，同時(shí)口進(jìn)程執行戶(hù)!‘時(shí)，發(fā)生通信，e的值從Q進(jìn)程傳送給戶(hù)進(jìn)程的變量x。CSP語(yǔ)言后來(lái)成為著(zhù)名的并行處理語(yǔ)言OCCAM(由INMOS公司為T(mén)ransputer開(kāi)發(fā))的基礎。20世紀80年代中期，霍爾又和布魯克斯(S．Brooks)等人合作，提出了“CSP理論”TCSP(Theory Of Communicating Sequential Processes)，它與上述CSP不同，但又有聯(lián)系，這是一個(gè)代數演算系統，其基本成分是事件(或動(dòng)作)。進(jìn)程由事件和一組算子構造而成。TCSP采用“廣播式通信”，而不像程序設計語(yǔ)言CSP中那樣采用握手式通信，即只有當并行運行的各進(jìn)程都執行同一動(dòng)作時(shí)，才發(fā)生通信。此外，TCSP采用失敗等價(jià)作為確定進(jìn)程等價(jià)的準則，這就是著(zhù)名的“失敗語(yǔ)義”。利用失敗可以構造TCSP的指稱(chēng)模型?；魻枮槭〉葍r(jià)建立了一些公理系統，可以對語(yǔ)義上的等價(jià)關(guān)系進(jìn)行形式推導?；魻栐谶@方面的工作開(kāi)創(chuàng )了用代數方法研究通信并發(fā)系統的先河，形成了所謂“進(jìn)程代數”(process algebra)這一新的研究領(lǐng)域，產(chǎn)生了很重要的影響。
霍爾的論著(zhù)極多，而且都很有份量，有很高的學(xué)術(shù)水平。有評論說(shuō)，霍爾每發(fā)表一篇論文，幾乎就要改變一次人們對程序設計的認識。這雖然是一種夸張的說(shuō)法，但也說(shuō)明霍爾的論著(zhù)確實(shí)非常重要。ACM在1983年評選出最近四分之一個(gè)世紀中發(fā)表在Communications of ACM上的有里程碑式意義的25篇經(jīng)典論文，只有兩名學(xué)者各有2篇論文人選，霍爾就是其中之一(另一名是首屆計算機先驅獎獲得者狄克斯特拉)?；魻柸诉x的兩篇論文分別是1969年10月的“計算機程序設計的公理基礎”(An Axiomatic Basis for Computer Programming，這篇論文的要點(diǎn)我們前面已經(jīng)介紹過(guò)了)，另一篇是1978年8月的“通信順序進(jìn)程”(Communicating Sequential Processes)，該論文奠定了前述CSP語(yǔ)言的基礎。CSP現在已推廣為“混合通信／頃序進(jìn)程”(Hybrid Communicating Sequential Processes)。在這個(gè)語(yǔ)言中，有一種特殊的語(yǔ)句稱(chēng)為“連續構件”，可表示一個(gè)具體給定初值的微分方程；而原有的通信語(yǔ)句可用來(lái)表達事件的起源和發(fā)生；語(yǔ)言中的順序算子、條件算子等則用來(lái)刻畫(huà)連續構件和通信間的耦合關(guān)系。
值得指出的是，霍爾還和我國軟件學(xué)者、中國科學(xué)院軟件所的周巢塵研究員等合作，在20世紀80年代末由于Esprit的ProCos項目的需要而對基于時(shí)態(tài)邏輯的邏輯型混合計算模型進(jìn)行了研究，在這個(gè)模型中引入了時(shí)段和切變的概念，建立了時(shí)段演算，已引起該領(lǐng)域同行的廣泛重視。時(shí)段用以刻畫(huà)系統在一個(gè)時(shí)間區間上的連續變化，而切變則表示事件的發(fā)生(離散變量的變化)。在單個(gè)時(shí)段上，借助連續數學(xué)(微分方程理論)推導系統的行為；而在相鄰時(shí)段間，則用時(shí)態(tài)邏輯中切變算子的規則，推導系統行為的轉化。這種混合計算模型對于設計要求絕對安全的軟件系統具有十分重大的意義。時(shí)段演算已在煤氣燃燒器、鐵路岔口控制、水位控制、自動(dòng)導航、OCCAM語(yǔ)言的實(shí)時(shí)語(yǔ)義、描述調度程序的實(shí)時(shí)行為和電路設計等方面獲得成功應用。
此外，由法國學(xué)者阿勃利爾(J．R．Abrial)提出的以狀態(tài)機為模型的著(zhù)名的形式規約語(yǔ)言Z語(yǔ)言，也是由霍爾所領(lǐng)導的研究小組加以發(fā)展并實(shí)現的。
霍爾出版的專(zhuān)著(zhù)主要有以下幾種：
《操作系統技術(shù)》(Operating Systems Techniques，Academic Pr.,1972)
《數理邏輯和程序設計語(yǔ)言》(Mathematical Logic and Programming language，Prentice—Hall，1985)
《并發(fā)和通信的發(fā)展》(Development in Concurrency and Communication，Addison-Wesley，1990)
《機器推理和硬件設計》(Mechanized Reasoning and Hardware Design，Prentice·Hall，1992)
除了獲得計算機先驅獎和圖靈獎以外，霍爾還在1981年獲得AFIPS的Harry Goode獎；1985年獲得英國IEE的法拉第獎?wù)??；魻栐鴳竭^(guò)世界的許多國家講學(xué)，中國科學(xué)院研究生院也曾于1983年邀請霍爾到北京講學(xué)，并主辦討論班。1989年霍爾當選為歐洲科學(xué)院院士。1992年新加坡政府授予霍爾“李光耀優(yōu)秀訪(fǎng)問(wèn)學(xué)者”稱(chēng)號。在2000年北京WCC大會(huì )上，霍爾應邀作了主題報告。
聯(lián)系客服
