故事的另一半.docVIP

故事的另一半 作者:张恒溧 5050309367 2005ACM班 摘要:计算机在很多人心目中仅仅是工程的产物,然而,它不仅是物理的体现,更是逻辑的表达.本文讲述的是现代计算机背后的那些基本概念和 发展出这些概念的人. 关键词:逻辑 计算机 引言:计算机从最初的庞然大物,逐渐演变成今天的轻巧而强大的机器,在这整个过程中,其背后的逻辑始终保持一致.那么,这些逻辑概念是如何一步步发展起来,并最终导致计算机的产生呢? 从莱布尼茨之梦说起。 在于我们的理解,莱布尼茨最重要的贡献莫过于他为微积分运算而发明的一套符号,这使得人们不用过多思考便可进行复杂的运算.实际工作的似乎就是那些符号.不仅在微积分,算术和代数中所使用的特殊符号,化学和天文所使用的符号,无不说明一个真正合适的符号系统是多么重要.那么一个自然的想法就是,对于整个人类的思想领域,是否也能找到这样一种符号系统呢?这就是被莱布尼茨称为的”普遍文字”(universal characteristic).他梦想对一种普遍的人工数学语言和演算规则进行一种百科全书式的汇编,知识的任何一个方面都可以用这种数学语言表达出来,而演算规则将揭示这些命题之间所有的逻辑关系.最后,制造出完成这些演算的机器,从而使心灵从创造性的思考中解脱出来.莱布尼茨认为他的宏伟计划由三个主要部分组成.首先,在合适的符号被选择出来以前,有必要创造一套涵盖人类知识全部范围内的纲要或百科全书.然后,对其背后的观念进行选择,并为其中的每一个提供合适的符号.最后,演绎规则可以归结为对这些符号的操作,今天或可称其为一种符号逻辑. 布尔把逻辑变为代数 亚里士多德的古典逻辑一直有着很深远的影响,它包括这样一些句子: 1,所有的植物都是有生命的 2,没有河马是聪明的 3,有些人说英语 布尔逐渐认识到,在逻辑推理中,像”有生命的”,”河马”,或”人”这样一些词重要之处在于它所描述的所有个体的类或群体:有生命事物的类,河马的类,人的类.不仅如此,他还认识到这种类型的推理可以用一种关于这些类的代数来表达.布尔用字母表示类.如:X和Y表示两种特定的类,那么说,XY表示既在X中,又在Y中的事物的类.在某种意义上,布尔认为这种类的运算类似与数的乘法运算.然而,如果X表示绵羊的类,那么XX表示什么呢?.......还是绵羊的类,所以,XX=X.那么,若X表示数呢?对于XX=X为真,有X=0,或X=1.于是布尔认为,如果只限于0和1两个值,那么逻辑代数就成了普通代数.于是,0就是我们现在所说的空集,1则是全集.对应普通代数,类的加减表示什么呢?X+Y表示或者在X中,或者在Y中的类;X-Y表示在X中,但不在Y中的类.那么,对于XX=X,我们有,X(X-1)=0!也就是说,没有任何东西可以既属于又不属于一个给定的类.而这,正是亚里士多德的矛盾律!原来,它不过是这种新观念的一种特殊应用.同时,这种逻辑代数还能正确地处理亚里士多德所研究的称为三段论的受限推理(在此不累述),并且,还能表达人们日常生活中所涉及的2级命题.举个简单的例子(这是一段对话): 乔找不到他的支票簿了，苏三正在帮他。 苏：你是不是在买东西的时候把它忘在超市了？ 乔：没，我给他们打过电话，他们没有找到。如果我把它忘在那了，他们肯定就能找到。 苏：等一等！你昨天晚上在饭馆开过一张支票，我看见你把支票簿放在口袋里了，如果你从那时起就没有再用过它，那么它肯定还在那里。 乔：你说对了。我没有用过它，它就在我口袋里。 让我们看看布尔的代数如何被用来分析这样的推理。 在他们的推理中，乔和苏三处理的是如下命题： L=乔把支票簿忘超市了。 F=乔的支票簿在超市找到了。 W=乔昨晚在饭馆开了一张支票。 P=昨晚开了支票后，乔把支票簿放在了他的口袋里。 H=乔从昨晚起就再没用过支票簿。 S=乔的支票簿仍然在他的口袋里。 他们用到的是这样的推理形式： 前提： 如果L，那么F； 非F； W且P； 如果W且P且H，那么S； H． 结论： 非L。 S． 换算成方程： L（1-F）=0， F=0， WP=1， WPH（1-S）=0， H=1。 很容易地，我们解得，L=0，S=1。 当然,我们不需要这种代数,但在人类的日常交流背后,正在不知不觉地发生的那种推理,却可以为布尔的代数所掌握.于是,更为复杂的推理也是有可能被把握的.很自然的,我们可以认为数学系统概括了极为复杂的逻辑推理,所以要想对一种以完备性为目标的逻辑理论进行最终的检验,那么就要看它是否包含了一切数学推理. 我们说,布尔的伟大成就是一劳永逸地证明了逻辑演绎可以成为数学的一个分支.然而,布尔的逻辑代数是不完备的.考虑这样一个句子:所有失败的学生或是糊涂的或是懒惰的.这正是布尔代数无法表达的.