Fuleige 弗雷格
(F.L.)G. Friedrich Ludwig Gottlob Frege (1848~1925)
德国数学家、逻辑学家。1848年11月8日生于德国维斯马,1925年7月26日卒于巴德克莱茵。1873年毕业于格丁根大学,获博士学位。1874年起即在耶拿大学任讲师,1879年任教授,1918年退休。在耶拿大学执教的四十余年间,致力于数学基础、数学哲学和逻辑理论的研究。
弗雷格于 1879年出版了《概念语言》一书,所谓“概念语言”是一种表意语言,用它进行推理最易于察觉隐含的前提和有漏洞的步骤。由于弗雷格认为算术定理可由纯逻辑规律出发证得,为了保证推理过程的绝对严格性,他特地建立了这一符号语言。他成功地引入了数学中的函数概念,建立了量词理论。这样就构作了一种基本自足的逻辑演算即一阶谓词演算。从而给出了历史上第一个严格的关于逻辑规律的公理系统。嗣后,他又出版了《算术基础》(1884)和《算术的基本规律》 (卷I,1893;卷Ⅱ,1903)。在这些著作中他首创从逻辑出发来定义数和自然数,并从逻辑规律出发推导出一系列算术定理。尽管弗雷格明确地提出了数学可以化归为逻辑的思想,但没有全面地进行从逻辑推导数学的研究,因而他未能象B.A.W.罗素和A.N.怀特海在《数学原 理》中那样精详论证、充分展开逻辑主义的纲领(见数 学基础),但弗雷格仍不失为逻辑主义的创始人之一。 逻辑主义的主要代表人物罗素,甚为称颂弗雷格的工作。 弗雷格晚年从事数学哲学和逻辑理论的研究。
(徐云从)
弗雷格
大连理工大学 杜瑞芝
弗雷格,F.L.G.(Frege,Friedrich Ludwig Go-ttlob)1848年11月8日生于德国维斯马(Wismar);1925年7月26日卒于巴德克莱茵(Bad Kleinen).数学、逻辑学、哲学.
弗雷格出生的年代正值德国民主革命开始.维斯马是一个远离德国政治中心的小商业城镇,革命风潮对这里影响很小.弗雷格出生在一个信奉路德教的中产阶级家庭,在血统上是混杂的(部分是德国的,部分是波兰的).其父亚历山大•弗雷格(AlexanderFrege)开办了一所女子学校.他去世后这所学校就由他妻子来管理.1869年,母亲奥古斯特•弗雷格(Auguste Frege)送弗雷格到耶拿大学就读.当时弗雷格就把数学作为自己的主要兴趣,但也选修了化学、物理和哲学.他的老师——数学家、物理学家E.阿贝(Abbe)及时发现了他的才能,成为他毕生信念的支持者.在阿贝的帮助下,他离开耶拿,来到格丁根大学继续深造.1873年,在数学家E.谢林(Schering)的指导下,弗雷格以论文“论平面上虚影的几何图形”(Ueber eine geometrische Darstellung derim ginaren Gebilde in der Ebene)获得哲学博士学位.该论文通过对平面上虚影图形性质的讨论,阐明了几何学基于直觉的观点.他在格丁根还参加了著名哲学家R.H.洛采(Lotze)的讲座.洛采的逻辑观念,特别是他对纯逻辑的看法,对弗雷格逻辑思想的形成有着重要的影响.
弗雷格在格丁根大学获得博士学位之后,又回到耶拿大学.在阿贝的帮助下,他于1874年以论文“基于量值概念外延的演算方法”(Rechungsmethoden,die sich auf eine Erweitung desGr ssenbegriffes gr nden)获得了无薪大学讲师的资格①.在这篇论文中,弗雷格提出了用于运算的量值概念,并断言算术真理产生于量值概念.1879年,弗雷格的《概念语言》问世之后,他又一次在阿贝的推荐下成为耶拿大学的编外教授.1896年成为荣誉教授.弗雷格在耶拿大学执教40余年,讲授过数学的各分支学科及有关的逻辑系统,举办过“概念符号”讲座,他一直致力于数学基础、数学哲学和逻辑理论的研究.1918年退休.
弗雷格首先是作为一位数学家和逻辑学家而闻名于世的.他在数学上的主要成就,是使自C.F.高斯(Gauss)以来所建立的数学体系更精确和完善,确立了算术演算的基本规则.他第一个建立了初步自足的命词演算系统和量词理论,首次提供了现代意义下的数理逻辑的一个体系,因而成为数理逻辑的奠基人.他提出数学可以化归为逻辑的思想,成为逻辑主义的创始人.弗雷格还是一位杰出的哲学家.他的绝大部分著作都具有明显的哲学特征.他认为:“一个好的数学家,至少是半个哲学家;一个好的哲学家,至少是半个数学家.”他直接把传统哲学对思维内容和认识能力的探讨,转向对语言表达形式和语言内部框架的考虑.他认为对语言意义的分析,是哲学研究的主要任务.弗雷格对哲学任务的重新规定,标志着当代西方分析哲学的开端.因此他被誉为当代分析哲学的真正奠基者.
弗雷格的主要著作有:《概念语言》、《算术的基础》、《函项与概念》(Function und Begriff,1891)、《论意义和所指》( ber Sinn und Bedeutung,1892)、《论概念和对象》( berBegriff und Gegenstand,1892)、《算术的基本规律》1—2卷(以下简称《基本规律》).
弗雷格的科学生涯大致可以分为五个时.
在第一个时期,弗雷格主要从事纯逻辑的研究.其研究成果总结在1879年出版的《概念语言》中.用数学方法研究逻辑问题,一般认为是由G.W.莱布尼茨(Leibniz)提出的文字学设想开始.他提出过有关思维演算的思想.莱布尼茨的这种先驱性想法没有及时得到应有的发展.在淹没了一个世纪之后,19世纪英国的两位数学家A.德摩根(De Morgen)和G.布尔(Boole)用代数的方法建立了逻辑代数.但这种逻辑代数与亚里士多德(Ar-istotle)的形式逻辑本质上是相似的.在1874—1879年间,弗雷格攻读了布尔学派和一些哲学逻辑学家的著作.除上文提到的洛采外,18世纪德国哲学家A.特伦德伦堡(Trendelenburg)的著作对弗雷格也有较大的影响.通过特伦德伦堡的工作使弗雷格了解到莱布尼茨关于逻辑语言的观点.弗雷格还追随特伦德伦堡,把他的逻辑符号系统称作“概念语言”.弗雷格用心研究莱布尼茨和I.康德(Kant)的逻辑学和数学哲学方面的著作,有选择地接受了两位哲学家的思想.在弗雷格晚年,他是这样描述自己的研究动机的:“我开始是搞数学.在我看来,这门科学急需更好的基础:……语言逻辑的不完善对这种研究是一种障碍.我在《概念语言》中寻求弥补.所以,我就从数学转向了逻辑.”
经过5年的沉思,弗雷格完成了一部划时代的著作——《概念语言》.在这本书里,弗雷格把从洛采和特伦德伦堡,以及从莱布尼茨和康德那里得到的观点,变成一种全新的逻辑.这本不足80页的小书是弗雷格的不朽之作.弗雷格在此建立的逻辑有效地终结了亚里士多德逻辑两千多年来一直占据的统治地位,完成了始于几百年前G.伽利略(Galilei)破除亚里士多德物理学的进程.在《概念语言》中,弗雷格创造了一种表意的语言,即“纯粹思想的语言”.正如他在这本书的副标题中所说——它可以使我们完全精确地表达判断的概念内涵.弗雷格认为,真理分为两种,一种真理的证明必须以经验事实为根据,例如物理学中的定理.另一种真理的证明似乎可以纯粹从逻辑规律出发.他认为算术命题就是属于后一种的.在探讨如何根据思维的逻辑规律经过推理以得到算术命题时,必须绝对严格,要防止未被查觉的直观因素渗入,因此必须使推理过程没有漏洞.他觉得日常语言是表达严密思想的障碍.当所表达的关系越复杂时,日常语言就越不能满足要求.因此他创造了这种概念语言.他说,用这种语言进行推理,最有利于觉察隐含的前提和有漏洞的步骤.这种语言和日常语言相比,就好像机械手和人手相比,或者像显微镜和肉眼相比一样.利用这种语言,弗雷格成功地构造了一个严格的逻辑演算体系.下面简要介绍一下弗雷格逻辑演算的内容.
1.弗雷格严格区别了命题的表达和断定.他认为,我们只有能够表达一个思想,理解一个思想,才能对它加以断定.他引进断定符号“├”.“├┌”表示“┌是被断定的”.其中垂直短线“|”称为判断短线,水平短线“—”称为内容短线.“—┌”是一个整体,它只表达可断定的内容,即命题的表达.而“├┌”才表示命题的断定.如“├┌”表示“不同的磁极相互吸引”这一断言,而“—┌”只是表达了不同磁极相互吸引这一思想,而对这一思想的正确性没有任何判断.
2.弗雷格明确提出真值蕴涵的思想并指出它与日常语言的区别.他采用否定和蕴涵作为基本的逻辑联结词.他用小竖线“ ”放在内容短线下面表示否定.“┬┌”表示“非┌”.符号 表示“△蕴涵┌”.他列举了┌和△的四种可能的真值组合:(1)┌肯定,△肯定;(2)┌肯定,△否定;(3)┌否定,△肯定;(4)┌否定,△否定.用符号“ ”表示以上第三种可能不实现而其余三个可能性中的每一个都可实现.弗雷格说,当┌为真时,△蕴含┌常可被断定,在此情形下,△可以是任一命题,其具体内容完全无所谓.┌和△不必有因果关系,与日常语言中的“如果……则”不同.
3.弗雷格引进一个内容同一的符号.设┌和△为任意名称,即不一定是命题记号,他规定,“├(┌≡△)”的意思是“名称┌和名称△有相同的概念内容,使得┌总是能由△替换,反之亦然”.他还指出,由他的新符号所联结的名称不仅代表它们的内容而且代表名称自身.后来,他改用符号“=”,“=”不被看成两个名字之间的关系,而是看成名字的指称之间的关系.“=”用于专门的指称,相当于等词;用于命题的指称(真值),则相当于现在的等值符号.
4.弗雷格把数学中的函数概念引入逻辑演算,从而建立了量词的理论.他采用变目和函项两个术语,┌表示变目,记号Φ(┌)表达变目┌的一个不确定的函项.记号Ψ(┌,△)表达按顺序所取的两个变目┌和△的一个函项.假定如下一种函项:当它由变目填满时,它表达可能的判断内容.于是,“├Φ(┌)”读作“┌有性质Φ”,“├Ψ(┌,△)”读作“┌与△有关系Ψ”.弗雷格使用这种符号的主要优点是,它能够比普通语言所提供的方式更令人满意地表达一般性.在此基础上,弗雷格引进了全称量词和存在量词
表示“不管怎样取函项的变目,函项总是一个事实”.即“凡a都是Φ.在这里,全称量词是基本概念,存在量词则通过全称量词而表达为
它表达“至少有一个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)代入规则,弗雷格使用了但没有严格地陈述.
假定a并不在表达式Г中出现,而且a仅处于Φ(a)的变目空位中.
a不在┌和△中出现,Φ(a)中的a只处于变目空位中.事实上,这条规则是第三条规则的推广.
弗雷格在上述公理和规则的基础上,进行了大量的推演,成功地构造了一种基本自足的逻辑演算,从而给出了历史上第一个严格的关于逻辑规律的公理系统——现代的逻辑系统.它实质上包含了作为现代数理逻辑基础的两个演算系统——命题演算系统和一阶谓词演算系统.
不幸的是,弗雷格这本划时代的小册子被数学家和哲学家们忽视了.他在《概念语言》中建立的新逻辑没有马上被人理解.其中使用复杂而陌生的符号来表达新奇的概念,确使读者望而生畏.德国数学家E.施罗德(Schrder)发表长篇文章,对该书进行全面批评.事实上,直到B.A.W.罗素(Russell)1901年开始发现弗雷格著作的价值之前,《概念语言》几乎没有读者.
《概念语言》出版之后,弗雷格的创造生涯进入第二时期.在这一时期,弗雷格开始形成逻辑主义的观点.在最初几年,他由于自己的著作没有受到重视而大受挫折,没有发表任何作品.但他仍然在重新思考和深刻挖掘自己的哲学和数学观点,并逐渐形成了他的数学哲学的三个主要原则:第一,他反对在数学基础问题上的经验主义,否认数学来源的经验基础,强调数学真理的先天性;第二,他认为数学真理是客观的,这种客观性基于数学的非经验的基础.在他看来,客观性是思想的必要条件;第三,他主张一切数学最终都可化归为逻辑,数学概念可以定义为逻辑普遍要求的概念,数学公理可以从逻辑原则中得到证明.这第三条原则后来被罗素作为逻辑主义的基本主张而广为传播,弗雷格因此成为逻辑主义的创始人之一.
弗雷格在《算术的基础》中力图作为逻辑的延展去建立数学.为此,首先要从逻辑推出算术.为使大家能够理解他的著作,他对自己的观点及关于数和算术所流行的各种哲学观点作了非形式的说明.然后他指出,要从逻辑推出算术,首先必须给出数和自然数的定义.
弗雷格接受他的前辈的观点:所有大于1的自然数可由指出它们的前趋即用“2=1+1”,“3=2+1”一类等式来定义.但他认为,这些定义是不完全的,因为使用了“数1”和“加1”这两个未定义的概念.他考察了从欧几里得(Euclid)到G.康托尔(Cantor)以来的许多数学家的著作,发现关于数的定义是相当混乱的.他指出在此之前所见到的一切关于数的定义都含有基本的逻辑错误.他说:“数是什么?这是一个最根本的问题.如果我们对这个问题都不能做清楚的回答,岂不是一个笑话?”又说:“数学的本质就在于,一切能证明的都要证明,而不是通过归纳法来验证.因此,我们也应考虑如何来证明关于正整数的命题.”
弗雷格发展了《概念语言》中关于数学序列的理论.在那里他用“遗传性”定义了“y属于从x开始的f-序列”和“y是x的f-后裔”,为自然数的定义和说明数学归纳法作了理论和技术上的准备.弗雷格给出的自然数的定义的核心在于使用了“一一对应”的概念:属于两个概念F和G的对象借助于关系Φ一一对应,如果(1)每一个属于概念F的对象对于属于概念G的一个对象,有关系Φ;(2)对于属于概念G的每一个对象,存在一个属于概念F并与前者有关系Φ的对象;(3)对所有x,y和z而言,如果x对y和z有关系Φ,那么y和z就是同样的;(4)对所有x,y和z而言,如果x和y对z有关系Φ,那么x和y就是同样的.
弗雷格在此基础上构造了以下三个定义:
(1)“概念F与概念G是等数的”与“存在一个关系Φ,使得属于概念F的对象与属于概念G的对象一一对应”其意义是相同的.
(2)属于概念F的数是“与概念F等数”这一概念的外延.
(3)“n是一个数”与“存在一个概念使得n是属于它的数”其意义是相同的.
接着他又定义了“n在自然数序列中是m的直接后继”:“存在一个概念F和一个归于它的对象x,使得属于概念F的数是n,属于概念‘归于F但不同于x’的数是m”.这实质上是后继函数的定义.
在这些工作的基础上,弗雷格取0作为数列的起点,提出如下定义:
0是属于概念“不同于自身”的数,
1是属于概念“同于0”的数,
2是属于概念“同于0或同于1”的数,
3是属于概念“同于0或同于1或同于2”的数,
……
可见,1在自然数序列中是0的直接后继,2在自然数序列中是1的直接后继,等等.
事实上,弗雷格所用到的“一一对应”概念与康托尔所谓的集合的“等价”意义是一样的,弗雷格指出,他的数与康托尔理论中集合的“势”或“基数”是相同的.两个概念同数,就是两个集合等价.概念“与概念F等数”的外延,就是与集合F等价的一切集合构成的集合.所以弗雷格实际上是把数定义为集合的集合,或类的类.利用康托尔的语言,概括弗雷格关于数的定义:
(1)一个集合的基数是所有等价于它的集合的集合.
(2)0=df•{^}(空集合的单元集)
1=df•{0}
2=df•{0,1}
3=df•{0,1,2}
弗雷格的后续函数的定义实际上是说:后续函数把等价集合的集合m映射到一个新的集合的集合Φ(m)(即n),Φ(m)中的每一个集合是由在m中的某一个集合加上一个新分子而得到.
由此可见,自然序列中的每一个数,有一个直接后继的数.这样,自然数就由0和后继函数而确定下来.
有逻辑学家评论,弗雷格的这个定义系统是哲学技巧中极其卓越的成就.人们也很容易理解,为什么弗雷格认为他至少使得算术化归为逻辑是可能的.
在《算术的基础》的最后几页,弗雷格指出,其他类型的数,也可以用类似的方式加以定义.实数和复数同样可以刻画为概念的外延.在《基本规律》的第二卷中,他阐明了这个方案是如何实施于实数的.
康托尔在1884年也给出数的定义,但弗雷格的定义比康托尔的更为精确.
弗雷格从逻辑出发定义了数和自然数,他对自然数的归纳定义也是对数学归纳法的最好说明.他认为,借助于上述定义,自然数的概念就被化归成了逻辑的概念;自然数的理论则可以借助于上述定义和逻辑得到建立,这样,算术理论就被“逻辑化”了.
弗雷格在他的第三时期集中精力写作《基本规律》.原计划写三卷,实际上只完成两卷(1893,1903).弗雷格准备在这部专著中,从逻辑出发去展开除了几何学以外的全部数学.他认为,逻辑的原则是完全可靠的,一旦完成了上述工作,数学“就被固定在一个永恒的基础上了.”
1893年,出版了《基本规律》第一卷,它是《算术的基础》的理论的严谨发展,书中改进了《概念语言》符号系统,提出了不同的公理,阐述了高阶谓词演算.从《概念语言》到《基本规律》,弗雷格的逻辑发生了三个主要变化:(1)他在自己的系统中加上了函项的值域这一概念;(2)区分了意义的两个方面,即“所指”和“意义”;(3)更为严格地规定了与对象相对的函项的性质,明确提出了“第一层函项”和“第二层函项”的区别.第一层函项就是以前所定义的函项,其变目是对象,第二层函项就是函项的函项,其变目是函项,例如在Mβ(F(β))中,Mβ就是第二层函项,其变目是F.弗雷格还把概念分为第一层概念和第二层概念.这些逻辑上的变化在《基本规律》第一卷之前的5篇文章①中就已经提出并作了解释.
弗雷格在《基本规律》第一卷中建立了另一个逻辑系统——二阶谓词演算,提出了新的公理.他用‘xF(x)代表F(x)的值域,例如,若F(x)表达“x是人”,则它的值域‘xF(x)就表达“人类”.他还引进代表定冠词的函项符号\x.如\’xF(x)读为“那个具有性质F的x”.用现在的符号表示弗雷格的新公理如下:
在这个新系统中,除分离规则和代入规则之外,弗雷格还把原来系统的一些公理和定理作为新的推理规则.在这一系统中处理了命题演算,谓词演算,类理论和关系理论,更重要的是进行了推导算术的工作.
《基本规律》第一卷出版后,再次受到冷遇.只有G.皮亚诺(Peano)在1895年作了评述,但他对这本书的内容没有足够的理解.这再一次使弗雷格深感痛苦.然而,弗雷格并没有放弃自己的目标,他继续撰写《基本规律》第二卷,其中主要论述实数的理论,并用较多的篇幅批评当时流行的观点.
但是,弗雷格并没有完成他的计划.因为要理解数学科学的性质,除了算术以外,还必须考虑无穷集合的理论——集合论.弗雷格没有深入研究集合论,没有接触到关于无穷集合的各种问题,特别是悖论问题.1902年,正当弗雷格等待《基本规律》第二卷付印的时候,他收到了罗素6月16日写给他的信.信中首先称颂他的工作:“就我所知,您的工作是我们时代中最好的.”“在许多具体问题上,我发现您的著作都进行了讨论、区分和定义,这使其他逻辑学家的工作黯然失色.”具有讽刺意味的是,罗素的来信既标志着弗雷格的工作开始得到承认,也宣告了他的独创性工作的终结.因为罗素在他的信中接着写道:
“只有在一点上我遇到了困难①,……由于下述矛盾:令W为不能论断自身的谓词的谓词,W可以论断自身吗?每种回答都隐含着它的否定①,因而人们必须得出,W不是一个谓词.同理,没有不包含自身的作为整体的类的类.由此我得到,在某种条件下,一个可定义的集合没有构成一个整体.”
罗素当时并没有完全认识到他的发现是怎样严重地威协着弗雷格的逻辑主义纲领.但是,弗雷格本人毫无疑问地认识到这个矛盾的潜在致命力.他对罗素来信的反映迅速而强烈,他马上复信[15]:
“您发现的矛盾引起了我极大的震惊,我几乎可以说是惊愕不已,因为它动摇了我建立算术基础的企图,……我的《基本规则》第二卷看来是有缺陷的.我无疑要补充一个附录,对您的发现作出论述.”
在1903年,弗雷格出版了带有一个后记(写于1902年10月)的《基本规则》的第二卷.他在后记中不无悲哀地写道:
“对于一个科学工作者来说,最不幸的事情莫过于:当他完成他的工作时,发现他的知识大厦的一块基石突然动摇了.正当本书的印刷接近完成之际,伯伦特•罗素先生给我的一封信使我陷入这种境地.这封信是关于我的公理V的问题.我本人从来没有掩盖这条公理缺乏其他公理所具有的并必为逻辑规律所正当要求的自明性.
……
成为问题的恰恰不是我建立算术的特殊方式,而是算术是否完全可能有一个逻辑基础.”
弗雷格的第四时期是在极度消沉中度过的.这一时期长达十几年.最初,他相信能有补救的办法使他的系统避免矛盾.他首先提出一种设想:可能有一些概念没有相应的类.然后他用修改第Ⅴ公理的办法来阻止罗素悖论的衍生.但是,后来逻辑学家的工作证明,他所做的努力并不足以使他的系统避免不一致.他还打算论述集合论的逻辑悖论(1906).经过几年的努力之后,弗雷格似乎不那么相信能够找到解决矛盾的办法.虽然他没有公开放弃自己的主张,但也不再做进一步的努力.至到1918年,弗雷格才彻底放弃把算术化归为逻辑的一切希望,放弃了《基本规律》第三卷的写作计划.从此以后,他又进入了新的研究时期.他的研究兴趣仍在数学基础上,并很自然地转向几何学,提出了几何学是整个数学的基础的主张.弗雷格在1903年以后发表的论著很少.
虽然弗雷格的逻辑主义纲领没有实现,但是他的独创性工作对数学和哲学的发展都产生了重要影响.他的成就在有生之年没有得到广泛的承认,只是通过少数几位有洞察力的人的努力,他的思想才逐渐得到理解,并通过他们的工作得到发展.
首先认识到弗雷格工作重要性的是罗素.罗素在他的《数学原理》(Principles of mathematics,1903)的附录中,对弗雷格的逻辑进行了深入细致的研究,对弗雷格的从《概念语言》到《基本规律》第一卷等论著作了广泛详尽的评论.罗素发展了弗雷格的思想,他和A.N.怀特海(Whitehead)在《数学原理》(Principia mathematica,1910)中精详论证,充分展开了逻辑主义纲领.书中可以看出弗雷格的明显影响,甚至罗素与弗雷格不同的观点也是受到弗雷格著作中难点的启示而提出的.罗素表示:“在逻辑分析问题上,我们主要是从弗雷格获得教益.”稍后,罗素的学生和朋友L.维特根斯坦(Wittgenstein)成为弗雷格的崇拜者.这位20世纪的著名思想家明确指出,他的哲学工作的两个来源是“弗雷格的巨著和我的朋友罗索的著作”.30年代末期,由弗雷格本人的学生L.卡尔纳普(Carnap)以及美国逻辑学家A.丘奇(Church)的倡导,弗雷格的逻辑理论,特别是关于意义和所指的学说重新引起人们的研究兴趣[27].1950年,《算术的基础》英译本出版,在使用英语的数学家中产生很大影响.
1918年以前,弗雷格一直安静地生活在耶拿这座小小的大学城内.他身材矮小,性格胆怯羞涩.弗雷格的工作长期得不到理解和承认.一般认为,他的著作对于大多数数学家来说是过于哲学化了,而对大多数哲学家来说又过于数学化了.弗雷格的著作长期受到冷遇,在相当长一段时间内,哲学杂志和数学杂志都拒绝发表他的论文.由于得不到专业上的承认,他在耶拿大学当了好多年的编外教授.弗雷格还经受了长远计划失败的体验.所有这一切使他变得比较内向.他长期远离自己的数学和哲学同事.但是,弗雷格全心全意追求真理,从不追求个人名声;他屡受拙折而不放弃自己的奋斗目标;他勇于承认自己的失败并另辟蹊径提出新的主张.弗雷格这种追求真理的执著精神和科学态度值得后人学习.
苹果树下的散步
欧洲有个古老的传说:一辆著名的战车,被一根山茱萸树皮编制的绳索牢牢地捆住了。你要想取得统治世界的王位吗?那就必须解开这个绳结。无数聪明、强悍的勇士满怀希望而来,垂头丧气而去,因为绳结盘旋缠绕,绳头隐藏难寻。一天,亚历山大也慕名来到这里,他略略思索一下,便果断地抽出宝剑,一剑把绳截成两段。难解的绳结就这样轻而易举地被“解开”了。亚历山大因此享有对整个世界的统治权。
1888年9月6日,人们惊喜地获悉:十多年来许多数学家为之奋斗的著名难题——果尔丹问题,终于被一位当时尚名不见经传的青年人攻克了。他运用的方法和途径是那样的出人意料、令人折服,就像亚历山大解开绳结一样;也正如这位显赫的君主在辽阔的欧亚大陆上留下旷世战功,这位年轻人穷尽毕生心血和才华,在广阔的数学领域里纵横捭阖,遍及现代数学几乎所有的前沿阵地,在整个数学的版图上,到处都刻下他那光辉的名字。他就是数学世界的亚历山大——大卫•希尔伯特!
哥尼斯堡是德国一座古老而美丽的城市,康德、哥德巴赫是这座城堡的荣誉和骄傲,著名的七桥问题更使之名扬欧洲。1862年1月23日,希尔伯特就诞生在这座富有学术传统的城市里。受家庭的熏陶,早在中学时代,希尔伯特对数学就表现出浓厚的兴趣,并立志把数学作为自己奋斗的专业。
1880年秋,希尔伯特进入哥尼斯堡大学。这里的学术空气浓厚而且自由,非常适宜希尔伯特的生活习性和学习要求。这段时间内,他同两位年轻的数学家的交往使他受益终生。一位是比他大3岁的胡尔维茨,在希尔伯特还是学生时,这位见多识广的青年就已是副教授;另一位是闵可夫斯基,虽比希尔伯特小两岁,但已荣获巴黎科学院大奖而名扬国际。他们三位一体,情投意合。他们每天下午“准5点”相会于校园旁边的苹果树下,互相交流彼此的学习心得、制订计划、探索未知领域。对于每一个重大问题,他们总是分头准备、认真思考,并各抒己见,有时也会争得面红耳赤。据说,曾有一位前来哥尼斯堡大学访问的外地学者,这天偶然经过苹果园,忽然听到里面传出几个人互不相让的争吵声,他驻足而观,发现三位年轻人比比划划,旁若无人。这位好心的人觉得有必要去劝解一下,但马上就知道自己的担心是多余的。那正是希尔伯特三人在讨论问题。
苹果树下的小路清晰地向远方延伸。他们通过日复一日的无数次散步,漫游了数学世界的每一个角落。这种数学家们特有的学习方式给他们其中的每一位带来了希望、成功和友谊。
苹果树下的散步使希尔伯特利用有趣而又容易接受的学习方式像海绵吸水那样接受数学知识,并以最简洁、快速的方法到达数学研究的前沿阵地。胡尔维茨渊博、系统的知识,闵可夫斯基快捷、灵敏的思维,无不令希尔伯特如醉如痴,也激励着他更加如饥似渴地学习、思考。这段时光为希尔伯特打下了牢固而全面的基础,他也因之能在以后的岁月里频频出击,并获得数学麦加——哥廷根大学的教授席位。
英国现代计算机的起步的是从纳粹德国的“谜”开始的。“谜”(Enigma)是一种密码电报机,由德国人在一战和二战之间研制成功。“谜”能把日常语言变为代码,通过无线电或电话线路秘密传送。它是一个木箱子,配有一台打字机,箱上有26个闪烁不停的小灯泡,与打字机键盘的26个字母相对应。“谜”的设计无懈可击,有一套极精密的解码设置,非一般的电报密码所能比拟。在内行人看来,平白如话,但在旁人,又是无从索解的天书。因此,这台看似平常的机器,有了“谜”的称号。这样,德国的“谜”引起了英国情报部门高度的兴趣。常规的解码方式奈何不了“谜”,怎么办?
这时,天才的数学家图灵出现了。1931年图灵进入剑桥大学国王学院,开始了他的数学天涯。一到那里,图灵开始崭露头角,毕业后去美国普林斯顿大学攻读博士学位,在那里就发明过一个解码器(Encipher),二战爆发后回到剑桥。
在剑桥,图灵是一个妇孺皆知的怪才,常有出人意表的举动。他每天骑自行车到离公寓3公里的一个叫布雷奇莱公园(Bletchley Park)的地方上班,因常患过敏性鼻炎,一遇花粉,鼻涕不止,图灵就常戴防毒面具骑车上班,招摇过市,成为剑桥的一大奇观。
他的自行车链条经常在半道上掉落,要是换了别人,早就去车铺修理了。而图灵偏不,他在琢磨,发现这链条总是踏到一定的圈数时下滑,图灵在骑车时就特别留心计算,于是能做到在链条下滑前一刹那戛然停车!让旁人叹服不已,以为是在玩杂耍。后来他居然在踏脚旁装了一个小巧的机械计数器,到圈数时就停,好换换脑筋想些别的问题。图灵的脑袋转得比自行车飞轮还快。
用图灵的脑袋来破译德国的“谜”看来不是什么难事。二战爆发后,图灵成为英国外交部通信部门战时公务员,主要负责解码。他果然不负众望,成功破译了“谜”。而德国人还蒙在鼓里,还以为他们的“谜”能一直迷下去,照用不误,泄露了大量的核心机密,在战事上屡屡遭挫,战后,图灵被授予帝国勋章。至于图灵如何破译“谜”的,由于英国政府严格的保密法令,一直没有公之于世。所以图灵破译“谜”也成为一个“谜”。
早在30年代初,图灵就发表了一篇著名的论文《论数字计算在决断难题中的应用》,他提出了一种十分简单但运算能力极强的理想计算装置,用它来计算所有能想象得到的可计算函数。它由一个控制器和一根假设两端无界的工作带组成,工作带起着存储器的作用,它被划分为大小相同的方格,每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动,控制带有一个读写头,读写头可以读出控制器访问的格子上的符号,也能改写和抹去这一符号。
这一装置只是一种理想的计算模型,或者说是一种理想中的计算机。正如飞机的真正成功得力于空气动力学一样,图灵的这一思想奠定了整个现代计算机的理论基础。这就是电脑史上与“冯·诺依曼机器”齐名的“图灵机”。
图灵机被公认为现代计算机的原型,这台机器可以读入一系列的零和一,这些数字代表了解决某一问题所需要的步骤,按这个步骤走下去,就可以解决某一特定的问题。这种观念在当时是具有革命性意义的,因为即使在50年代的时候,大部分的计算机还只能解决某一特定问题,不是通用的,而图灵机从理论上却是通用机。在图灵看来,这台机器只用保留一些最简单的指令,一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了,在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题,而困难的部分则是如何确定最简单的指令集,怎么样的指令集才是最少的,而且又能顶用,还有一个难点是如何将复杂问题分解为这些指令的问题。
此后图灵在国家物理学实验室(NPL)工作,并继续为数字式计算机努力,在那里人发明了自动计算机(Automatic Computing Engine,ACE),在这一时期他开始探索计算机与自然的关系。他写了一篇名为《智能机》的文章于1969发表,这时便开始有了人工智能的雏形。
图灵相信机器可以模拟人的智力,他也深知让人们接受这一想法的困难,今天仍然有许多人认为人的大脑是不可能用机器模仿的。而在图灵认为,这样的机器一定是存在的。图灵经常和其它科学家发生争论,争论的问题就是机器实现人类智能的问题,在今天我们看来这没有什么,但是在当时这可不太容易被人接受。他经常问他的同事,你们能不能找到一个计算机不能回答的问题,当时计算机处理多选问题已经可以了,可是对于文章的处理还根本不可能,但今天的发展证明了图灵的远见,今天的计算机已经可以读写一些简单的文章了。
图灵相信如果模拟人类大脑的思维就可以做出一台可以思考的机器,它于1950写文章提出了著名的“图灵测试”,测试是让人类考官通过键盘向一个人和一个机器发问,这个考官不知道他现在问的是人还是机器。如果在经过一定时间的提问以后,这位人类考官不能确定谁是人谁是机器,那这个机器就有智力了。这个测试在我们想起来十分简单,可是伟大的思想就源于这种简单的事物之中。
现在已经有软件可以通过图灵测试的子测试,软件这个人类智慧的机器反映应该可以解决一些人类智力的问题。在完成ACE之前,图灵离开了NPL,它在曼彻斯特大学开发曼彻斯特自动计算机(Manchester Automatic Digital Machine,MADAM)。他相信在2000年前一定可以制造出可以模拟人类智力的机器,图灵开始创立算法,并使用MADAM继续他的工作。
查尔斯·霍尔
---从QUICKSORT、CASE到程序设计语言程序设计语言的公理化
学过“数据结构”或“算法设计与分析”的人都知道著名的快速排序算法QUICKSORT;编过程序的人大概也都用过实现条件转移的最方便的语句CASE语句。但是你知道这个算法和这个语句是谁发明的吗?它们的发明者就是1990年IEEE计算机先驱奖和1980年图灵奖的获得者英国牛津大学计算机科学家查尔斯·霍尔(Charles AntonyRichard Hoare)。当然霍尔之所以获得这两项大奖决不仅仅是因为他发明了QUICKSORT和CASE,而是因为他在计算机科学技术的发展中,尤其是在程序设计语言的定义和设计、数据结构和算法、操作系统等许多方面都起了重要的作用,有一系列发明创造,QUICKSORT和CASE只是其中的一小部分而已。
霍尔于1934年1月11日诞生于英国南部。在坎特伯雷(Canter·bury)的国王学校(King’s Sch001)度过中学阶段以后,进入牛津的莫顿学院(Merton College)学习数学,1960年取得硕士学位。之后他进入伦敦一家不大的计算机生产厂家Elliott Brothers公司,为该公司的Elliott 803计算机编写库子程序,从此开始他的计算机生涯。QUICK,SORT就是他在那个时候用原有的SHELLSORT(以算法的发明人D.L.Shell命名的通过调换并移动数据项实现排序的一种算法,发明于1959年)编程时分析了它的缺点而发明出来的。QUICKSORT具有“快刀斩乱麻”的特点,能迅速地对乱序作大幅度调整,特别适合于因多次追加、删除而变得杂乱无章的数据集合。QUICKSORT是利用“分治法”(divide and conquer)进行算法设计的一个成功范例,它的发明是霍尔在计算机方面的天才的第一次显露,受到老板的赞赏和重视。第二年,霍尔接受了一个新的任务,为公司的新机型Elliott 503设计一个新的高级语言。但就在其时,他弄到了一份Algol 60报告的复印件,还参加了一个由狄克斯特拉(E.W.D耻stra,首届计算机先驱奖获得者)等人在布赖顿举办的Algol 60培训班,感到与其自己没有把握地去设计一个新的语言,还不如将比较成熟的Algol 60在Elliott 503上加以实现。霍尔和他的同事们的这个想法获得公司同意以后,由霍尔主持设计与实现了Algol 60的一个子集的版本。霍尔在开发初首先制定了明确的目标,即系统要安全可靠,生成的目标码要简洁,工作区数据要紧凑,过程和函数的人口和出口要清晰、严密等,还明确了整个编译过程采用一次扫描等原则。这样,ElliottAl-gol的开发十分顺利与成功,它在1963年中推出以后大受欢迎,成为世界各国所开发的Algol 60的各种版本中在效率、可靠性和方便性等方面的性能指标都首屈一指的一个版本,霍尔本人也从此受到国际学术界的重视。国际信息处理联盟IFIP后来任命霍尔为2.1工作组(WorkingGroup 2.1)的负责人,这个工作组的任务是维护和发展Algol。霍尔果然不负众望,主持设计了Algol X以继承与发展Algol60。正是在AlgolX的设计中,霍尔发明了CASE语句。CASE语句具有如下形式的语法结构:
CASE E of
C1:S1;
C2:S2;
.
.
.
Cn-1:Sn-1;
Otherwise:Sn
End
其中E是一个表达式,称为“选择子”(Selector),每个Ci的值为常数,称为“分情形标号”,Si则为可执行语句。CASE语句的含义是:若E的值等于某个Ci的值,则执行其后的Si(i=1,2,3,…,n—1),否则执行Sn。某个Si或S。执行完之后,整个CASE语句也就执行完毕。由于CASE语句构成多路分支,程序结构清晰、直观,所以CASE语句后来几乎成为程序设计语言的标准,被各种语言广泛采用。在C语言中,没有独立的CASE语句,但它的SWITCH语句(开关语句)实际上是在CASE语句的基础上形成的:
switch E
{case C1:S1;
case C2:S2;
.
.
.
case Cn-1:Sn-1;
[default:Sn]
不同之处有二:一是C;可以是表达式,但计算结果必须仍是常数;二是E的结果若不等于某个Ci(i=1,2,3,…,n—1)的值,则视有无default子句,若有,执行Sn;若无,则什么也不执行,控制转向SWITCH后的语句。显然,这些都是对CASE语句的进一步改进。
霍尔于1968年离开Elliott,离开产业界,原因是作为学者他对程序设计浯言的形式化定义这类更偏重于学术性和理论性的课题更感兴趣。离开Elliott以后,他任职过一年英国国家计算中心主任,发现自己也不适于从事行政管理,因此又转入爱尔兰的昆土大学(Queen’s University),从事教学和研究,1977年转入牛津大学。离开Elliott以后,霍尔在计算机科学理论的研究中发挥其特长,作出了许多创造性的重大贡献。首先是1969年10月,霍尔在Communications of ACM上发表了他那篇有里程碑意义的论文“计算机程序设计的公理基础”(An Axiomatic Basis for Computer Programming)。在这篇论文中,霍尔提出了程序设计语言的公理化定义方法,即公理语义学(axiomatic semantics),也就是用一组公理和一组规则描写语言应有的性质,从而使语言与具体实现的机器无关,而且也易于证明程序的正确性。这是继麦卡锡(J.McCarthy,1985年计算机先驱奖获得者)在1963年提出用递归函数定义程序、弗洛伊德(R.W.Floyd,1991年计算机先驱奖获得者)在1967年提出基于程序流程图的归纳断言法以后,在程序逻辑研究中所取得的又一个重大技术进展。霍尔提出的方法在逻辑上与弗洛伊德提出的方法类似,但不是用流程图而是用代数法,即控制流用以下一些结构表示:
begin al;a2;a3;…;an end
if p then a1 else a2
while p do a
后面为了方便,我们用到第一个结构时省略首尾的begin和end。
相应于弗洛伊德的验证条件,霍尔引入下列符号:
p{a}q
其意义是:如果在执行。之前P(叫做precondition)成立,则当α执行完了后q(叫做postcondition)成立。
霍尔给出了以下一组证明规则(proof rule)或叫推导规则:
p’ pp{a}qq→q’
1.
p’{a}q’
这个规则中的p’→和q’→q是普通数理逻辑中的断言命题,表示若p’(或q’)成立,则p(或q)成立。这个规则表示,若横线以上的p’→p、p{a}q、q→q’成立,则横线以下的p’{a}q1成立。
2.
P(e){x:=e}p(x)
这个规则表示,如果在将e赋给x之前p(e)成立,则其后p(x)成立。
3. P{a}qq{b}r
p{a;b}r
这个规则表示的是“传递律”(transitive law),即如果执行α之前p成立,α执行完了以后q成立;而如果执行b之前q成立,b执行完了以后r成立,则若在动作序列。和^执行之前P成立,则a和b执行完了以后r成立。
4. p∧r{a}qp∧~r(b)q
p{if r then a else b}q
这个规则中的∧和~是一般数理逻辑中的合取(conjunction)和否定(negation)连接词。这个规则定义了if-then-else的执行取决于precondition r的值。
5. p∧q{a}p
p{while q do a}p∧~q
这个规则定义了while循环:p是循环不变量(loop invariant),而q是终止循环的条件。
下面我们举一个例子说明如何用霍尔建立的系统验证程序的正确性。设有计算n的阶乘n!的如下程序:
A: x:1;B
B: while y>0 do C
C: x:y×x;y:=y-1
则通过下列霍尔断言可以证明上述程序是正确的,因为这些断言都是真的,而且在霍尔的系统中是可以被证明的,而最后一个断言正是我们所要寻求的结论,因此它们形成对上述阶乘程序正确性的说明。
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!
[类似(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!。
为了给出证明,应该从程序的最后一行开始逐步后推。在这个例子中,(iii)步是最关键的,其中y≥0∧x×y! =n!就是循环不变量或归纳假设(induction hypothesis)。
利用霍尔提出的这种方法,已经成功地描述了PASCAL等语言,说明了这个方法的巨大威力。但应该指出的是,霍尔的这个方法是不完备的,因为霍尔在开发和建立这个系统时并没有追求系统的完备性,而更多地追求系统的实用性。
在数据类型、数据结构和操作系统设计等方面,霍尔也做了许多开创性的工作。目前广泛流行与应用着的许多概念都源于霍尔的工作。例如,关于抽象数据类型的规格说明(Specification,也叫规约)与其实现是否一致,就是由霍尔于1972年公式化了的。霍尔通过前后断言方法用已经定义了的(抽象)数据类型给出所要定义的新类型的抽象模型,这成为抽象数据类型规格说明的两种主要方法之一,即模型方法(另一方法为基于异调代数理论的代数方法)。对于操作系统的设计与实现十分关键的monitor(监控程序)的概念也是霍尔首先提出,并界定了它的作用与功能,即作为操作系统的核心,在把操作系统看做虚拟机扩充时,monitor是硬件的第一次扩充,它完成中断处理、进程控制与进程通信、存储区动态分配,建立软时钟,驱动设备通道,进行处理机调度。monitor为外面各层的设计提供良好的环境,并提高系统的安全性。
20世纪70年代后期,霍尔又深入研究了运行在不同的机器上的若干个程序之间如何互相通信、互相交换数据的问题,实现了面向分布式系统的程序设计语言CSP。在该语言中,一个并发系统由若干并行运行的顺序进程组成,每个进程不能对其他进程的变量赋值。进程之间只能通过一对通信原语实现协作:Q?x表示从进程Q输入一个值到变量x中;P!e表示把表达式e的值发送给进程户。当户进程执行Q?x,同时口进程执行户!‘时,发生通信,e的值从Q进程传送给户进程的变量x。CSP语言后来成为著名的并行处理语言OCCAM(由INMOS公司为Transputer开发)的基础。20世纪80年代中期,霍尔又和布鲁克斯(S.Brooks)等人合作,提出了“CSP理论”TCSP(Theory Of Communicating Sequential Processes),它与上述CSP不同,但又有联系,这是一个代数演算系统,其基本成分是事件(或动作)。进程由事件和一组算子构造而成。TCSP采用“广播式通信”,而不像程序设计语言CSP中那样采用握手式通信,即只有当并行运行的各进程都执行同一动作时,才发生通信。此外,TCSP采用失败等价作为确定进程等价的准则,这就是著名的“失败语义”。利用失败可以构造TCSP的指称模型。霍尔为失败等价建立了一些公理系统,可以对语义上的等价关系进行形式推导。霍尔在这方面的工作开创了用代数方法研究通信并发系统的先河,形成了所谓“进程代数”(process algebra)这一新的研究领域,产生了很重要的影响。
霍尔的论著极多,而且都很有份量,有很高的学术水平。有评论说,霍尔每发表一篇论文,几乎就要改变一次人们对程序设计的认识。这虽然是一种夸张的说法,但也说明霍尔的论著确实非常重要。ACM在1983年评选出最近四分之一个世纪中发表在Communications of ACM上的有里程碑式意义的25篇经典论文,只有两名学者各有2篇论文人选,霍尔就是其中之一(另一名是首届计算机先驱奖获得者狄克斯特拉)。霍尔人选的两篇论文分别是1969年10月的“计算机程序设计的公理基础”(An Axiomatic Basis for Computer Programming,这篇论文的要点我们前面已经介绍过了),另一篇是1978年8月的“通信顺序进程”(Communicating Sequential Processes),该论文奠定了前述CSP语言的基础。CSP现在已推广为“混合通信/顷序进程”(Hybrid Communicating Sequential Processes)。在这个语言中,有一种特殊的语句称为“连续构件”,可表示一个具体给定初值的微分方程;而原有的通信语句可用来表达事件的起源和发生;语言中的顺序算子、条件算子等则用来刻画连续构件和通信间的耦合关系。
值得指出的是,霍尔还和我国软件学者、中国科学院软件所的周巢尘研究员等合作,在20世纪80年代末由于Esprit的ProCos项目的需要而对基于时态逻辑的逻辑型混合计算模型进行了研究,在这个模型中引入了时段和切变的概念,建立了时段演算,已引起该领域同行的广泛重视。时段用以刻画系统在一个时间区间上的连续变化,而切变则表示事件的发生(离散变量的变化)。在单个时段上,借助连续数学(微分方程理论)推导系统的行为;而在相邻时段间,则用时态逻辑中切变算子的规则,推导系统行为的转化。这种混合计算模型对于设计要求绝对安全的软件系统具有十分重大的意义。时段演算已在煤气燃烧器、铁路岔口控制、水位控制、自动导航、OCCAM语言的实时语义、描述调度程序的实时行为和电路设计等方面获得成功应用。
此外,由法国学者阿勃利尔(J.R.Abrial)提出的以状态机为模型的著名的形式规约语言Z语言,也是由霍尔所领导的研究小组加以发展并实现的。
霍尔出版的专著主要有以下几种:
《操作系统技术》(Operating Systems Techniques,Academic Pr.,1972)
《数理逻辑和程序设计语言》(Mathematical Logic and Programming language,Prentice—Hall,1985)
《并发和通信的发展》(Development in Concurrency and Communication,Addison-Wesley,1990)
《机器推理和硬件设计》(Mechanized Reasoning and Hardware Design,Prentice·Hall,1992)
除了获得计算机先驱奖和图灵奖以外,霍尔还在1981年获得AFIPS的Harry Goode奖;1985年获得英国IEE的法拉第奖章。霍尔曾应邀到过世界的许多国家讲学,中国科学院研究生院也曾于1983年邀请霍尔到北京讲学,并主办讨论班。1989年霍尔当选为欧洲科学院院士。1992年新加坡政府授予霍尔“李光耀优秀访问学者”称号。在2000年北京WCC大会上,霍尔应邀作了主题报告。
联系客服