西交《离散数学》第五章拓展资源

网院作业

西交《离散数学》第五章 格与布尔代数 拓展资源
在众多为计算机事业做出杰出贡献的科学家中,有位科学家终身没有接触过计算机,但他的研究成果却为现代计算机设计提供了重要的理论根据.
他就是英国数学家布尔.他所创立的布尔代数或称逻辑代数理论现在是,以后也仍将是计算机专业的必修课程.布尔(1815～1864)出身于一个手工业者的家庭,家境不十分宽裕.他原是一位中学教师,后来通过刻苦钻研,自学成才当上了大学教授.他对研究人类思维规律的逻辑学有着浓厚的兴趣.逻辑学当时在西方很受器重.古希腊著名哲学家和思想家亚里士多德在两千多年前就对逻辑学有过深刻研究,发展了演绎法,为形式逻辑奠定了基础.但是两千多年来,逻辑学在理论上的进展却很缓慢.著名数学家莱布尼兹在逻辑学上也做出过贡献,他提出了形式逻辑中重要的"充足理由律".他还试图建立一种普遍方法,把一切正确的逻辑推理归结为数学演算,可惜没有最后获得成功.1854年,布尔发表了著作《思维规律研究》,成功地将形式逻辑归结为一种代数运算,这就是布尔代数.布尔代数产生于19世纪中叶,当时被认为"既无明显的实际背景,也不可能考虑到它的实际应用",可是一个世纪后它却在计算机的理论和实践领域放射出耀眼的光彩.布尔代数在后来的机电计算机及电子式计算机的各类逻辑部件和程序的设计中都是不可缺少的数学工具.布尔代数与普通的代数不一样,布尔代数中的量只有两个值:1和0."1"表示命题为真,"0"表示命题为假.这个结果很自然地与"接通"和"断开"两种状态联系起来,因此,布尔代数特别适合于电路系统的分析与综合.1910年荷兰学者埃伦菲斯特利用布尔代数建立了分析与设计继电器和电子电路的系统方法.这是后来机电式计算机和电子计算机研制成功必不可少的先决条件.
机电计量机的发明.我们今天早已步入电的世界,电灯、电话、电视……在人们日常生活中已经司空见惯了.我们每天都要和电打交道.没有电就没有现代文明,也就谈不上今天的电子计算机.正像蒸汽机发明以后,出现了第一次工业革命那样,各种电机(发电机和电动机)的发明以及电力的广泛应用,标志着第二次工业革命的出现.这也使人们的视野比过去开阔多了.对于研究计算机的人来说,很自然的一件事就是:不能把目光仅仅停留在老式机械式计算机上,应该考虑可否利用电器来改进原有的机械式计算机的装置.1822年,法国的盖.吕萨克和阿拉戈利用电流的磁效应,把通电导线绕在软铁上,使一块普通的软铁变成了磁铁.几年后,美国的亨利在此基础上发明了磁性强大的电磁铁,利用电磁铁的原理,人们制成了继电器.继电器是在机电式计算机上第一个派上用场的电器部件.同学们中一定有人玩过遥控玩具,或者使用过遥控电视机的遥控装置吧!大多数遥控装置都离不开继电器.继电器是一种开关,不过它的开启与闭合不是靠人手去拨弄,而是靠微弱的电流.这种弱电流通过一个电磁铁的线圈,使电磁铁磁化并将一个衔铁吸下.衔铁连着一个开关,就可使得另一个大电流接通或断开.有了继电器,一个微弱的电流就可以控制一个大电流的开断.而微弱电流本身的开断不一定需要我们用手去拨动,它可以通过其他各种手段达到.比如无线电信号、导电的水、能导电的人体等,因此,继电器在各种控制电路中有着广泛的应用.计算机的研制者们欣喜地发现,继电器的应用还有潜力可挖,它可以用来计数.它有开和关两种状态,就可以用来表示二进制中"0"和"1"两个数.用多个继电器就可以记录多位的二进制数.正是因为继电器具备这样的特性,所以,后来在机电式计算机中发挥了关键作用.
随着电与人类关系的逐步密切,许多人开始考虑将电学成果应用于计算技术.其中首先取得实质性进展的是霍利瑞斯制表机.提到它的设计人霍利瑞斯,人们或许会感到意外,因为他既不是工程师,也不是科学家,而是一名普普通通的统计人员.霍利瑞斯是德国移民的后裔,毕业于哥伦比亚大学附属专科学校,他曾在美国人口调查局工作过,对统计工作的特点和艰巨性非常了解.当时的美国每隔几年就要作一次人口调查,调查的项目十分详细,光是按年龄的划分就有10类:5岁以下、6～10岁、11～20岁、21～30岁、……直到80岁以上年龄段.大家知道,美国人口主要是由移民组成的.18世纪末、19世纪初,美国的人口还不多,广大的西部还都是人烟稀少的森林、草原和沼泽地,这个时期作人口统计当然没有太大的困难.随着人口的迅速繁衍和大规模移民潮的涌入,美国人口剧增,这就使得人口调查和统计工作的难度一次次增加.大量的人口资料堆积如山,使统计工作者望而生畏,以致1880年的人口调查统计任务一直拖到1887年也没有结果.霍利瑞斯制表机就是在这种背景下应运而生的.一天,霍利瑞斯和一位在人口调查局工作的官员比灵斯聊天,几句话就扯到了令人厌烦而又无法回避的人口调查问题上.比灵斯叹了一阵苦经之后,忽然提到一个他已考虑了多日的设想,那就是使用穿孔卡片帮助统计.让每个接受调查的人都使用相同规格的硬纸卡片,按照不同的个人情况在不同的位置上穿孔,然后使用一种特殊的机器把这些信息读出并加以统计,至于机器如何设计他就不得而知了.
比灵斯的设想给霍利瑞斯以极大的启发,激起了霍利瑞斯的创造灵感,使他仿佛看到了解决问题的曙光.他过去听说过提花编织机上穿孔卡的故事,那件事发生在1728年,一位法国工程师发明了一种自动提花织布机,其中设计了一连串长长的穿了孔的卡片,让卡片转动,使得那些与卡片上的洞眼正好对着的织针顺利通过,而不相对的织针通不过.这样,纱线就织出了规定好的花纹.当时已是19世纪末,时代不同了,要求也不一样.霍利瑞斯懂得,仅用机械的方法显然会黔驴技穷,只有配上最新的电工技术才会使问题得到解决.那时候、电工技术在美同是一样很时髦的于艺,霍利瑞斯虽然没有专门学过电学,但对电工技术还是很内行的,因为他常在业余时间摆弄各种电器.在同事、家人、邻居的心目中,他可是个能干而热心的人.最后,他将弱电流技术和过去的穿扎卡片技术融为一体,设计制造了可用于人口调查的制表机.霍利瑞斯制表机主要由5个部分构成:1.接受压力机;2.继电器;3.计数器;4.分类盒;5.电池.制表机上阅读穿孔卡片的设计别具匠心,现在我们就以一个孔的位置为例介绍一下.先将卡片平放在相应位置上,孔的位置上方是一根带弹簧的金属棒,下方是一个水银杯.工作时,金属棒被轻轻地压下来,如果该位置上没有孔,金属棒被卡片纸挡住不下来,不能出现后续动作.反之,由于该位置事先已穿好了孔,金属棒就"长驱直入"地插入下方水银杯中.水银和金属棒都是导体,它们接触以后,就好比接通了开关,形成了回路,产生电流.又由于所加的电压低,形成的电流很弱,不会产生损坏制表机的电火花,也不会对人体造成伤害.另一方面,电流虽弱,但可以使继电器吸合,产生大电流.大电流使相应的计数器加1,这样就完成了此项目的一个人的统计.这种设计实在太巧妙了!金属棒有很多根,它的数目由统计项目和分类的多少来决定.
其实在今天,我们仍然有不少表格需要填写,像中学生升学填表,大学生毕业填表,甚至有时在考试中也有用填表作为答案的.不过,今天不用再穿孔,而只要你在相应位置上用笔涂黑就行.读表的装置也比那时高明得多了,用的是光电阅读器,它可算是穿孔卡片方法的"直系后裔"了.美国的人口统计机关当时曾征集过能加快统计速度的发明,除霍利瑞斯.
以外,还有两名应征者.他们采用了颜色卡片,但分类和计算仍依靠手工,与霍利瑞斯的发明相比真是相形见拙,霍利瑞斯成了竞争中的唯一胜利者.有了制表机的武装,人口调查的难题自然迎刃而解.1890年,共作了6300万人的调查登记,资料汇总到首都华盛顿以后,一个月就完成了统计制表工作.而1880年,仅作了5000万人的调查登记,统计制表工作化了7年半的时间,还多化了几百万美元.人们对制表机的成功,大加赞赏,许多大企业的会计业务、产品统计,都竞相仿效,后来还风行于世界各地,奥地利、加拿大、挪威、俄国等都改用制表机进行人口调查.霍利瑞斯制表机,尤其是它的读写卡片装置的巧妙设计,对以后的机电式计算机和电子计算机的研制都有极大的影响.霍利瑞斯研制成功制表机以后,穿孔式计数技术得到了发展;继电器得到了更广泛的应用.人们还发现,19世纪的英国数学家布尔创立的一套被称为"布尔代数"的数学理论,特别适合用于逻辑电路的设计,因此,逻辑电路设计也取得了很大的成绩.就这样,在本世纪三四十年代,一批与当年巴贝奇方案相似的新型计算机——机电式计算机方案出现了.
中国有句成语,叫做"英雄所见略同".在德国和美国,几乎同时有人在研制机电式计算机,原理、结构、性能都十分相似.德国的朱斯从1934年开始,投身于机电式计算机的研制,当时他24岁,正在学习土木工程.但是,他的主要精力没有放在土木工程这门"主课"上,反而对计算机研制工作于得津津有味,难免有人认为他"不务正业",他的"爱好"受到别人奚落.他读过巴贝奇的传记,虽然巴贝奇的结局是悲剧性的,不过他觉得巴贝奇很有道理.如果巴贝奇活到现在,就有成功的可能.有人不理解他,觉得他为古人担忧有些好笑,可是朱斯却认真得很,决心依靠自己个人的财力开展研究.由于资金短缺,有时候动手拆除家中一些器具充当计算机部件.他试制的第一台计算机Z—1是纯机械结构的计算机,费用不算太大,花了九牛二虎之力,总算在1938年完成.接下去他要大干一番,打算采用继电器技术制造计算机Z—2,其实,这就是一台机电式计算机.刚动手干不久,战争贩子希特勒就开始了进攻波兰的闪电战,第二次世界大战爆发了.纳粹德国开始大征兵,年轻的朱斯"榜上有名",计算机Z—2的研制完全"泡汤"了.事有凑巧,一个偶然出现的机会挽救了他.1939年,他的朋友,也是后来的合作者许莱尔向纳粹政府提交了一个备忘录,竭力鼓吹朱斯关于新式计算机研制工作的重大意义.由于计算机将来在军事上会很有用,敏感的当局不仅豁免了朱斯的军役,而且还慷慨地拨出了专款支持朱斯的研究,这偶然的巧事,使得朱斯"因祸得福"经过两年的艰苦努力,他终于在1941年研制成功全继电器的,机电式的通用自动计算机Z—3.这台计算机可以说是当时世界上最先进的新型计算机了.它能够执行8种指令,字长22位二进制,计算加法为0.3秒、乘法为4～5秒.整机用了2600个继电器,这是世界上第一台通用程序控制计算机.1945年初,朱斯对Z—3计算机作了改进,制成了可靠性很高的机电式计算机Z—4.
就在这一年,前苏联的红军和西方盟国的部队已经攻到了德国本土,逼近了柏林,希特勒点燃起的战火烧到了他自己家门口,全世界爱好和平的人民都为之振奋.燃烧的战火对于发明家朱斯,真是太不幸了,他的实验室,他的Z—3计算机都遭到了盟军的轰炸,在霹雳声中灰飞烟灭.唯一值得庆幸的是,Z—4计算机被藏在一座农舍的地窖里,才免遭此劫.德国战败以后,朱斯流亡到中立国瑞士的一个偏僻的乡村,即使在那里他也无心欣赏美丽的田园风光,计算机研究仍然是他的第二生命.虽然没有了实验室,没有了计算机,可是还有大脑,他还能研究计算机软件,他在那里提出了"程序演算"理论,即今天所说的计算机程序设计.这对软件的发展影响很大.可惜的是,朱斯在第二次世界大战期间完成的发明很少被德国以外的人所了解,仅有一台幸存的Z—4计算机成了他的伟业的见证.这台计算机的牢固性和可靠性令人赞叹,1950年到1954年用于瑞士技术学院,1955年到1958年用于法国国防部,直到1959年才被送进历史博物馆.
与朱斯同时,美国的艾肯(1900～1973)也在研制机电式计算机.艾肯1900年生于新泽西州的霍博肯,青少年时代学习勤奋刻苦,1923年他以优异成绩毕业于威斯康星大学,1939年在哈佛大学获得博士学位.在攻读博士学位期间,经常遇到大量的冗长乏味的计算.他设想造一台计算机,帮助解那些比较复杂的代数方程.1937年,艾肯正式提出一份题为《自动计算机建议》的备忘录,在原理、结构、性能方面,与巴贝奇、朱斯的设计不谋而合.当时美德两国正处于敌对状态,所以艾肯与朱斯互不了解对方的工作.艾肯读过巴贝奇的自传,并为巴贝奇的创造精神鼓舞,但他没有读过艾达.拜伦对于巴贝奇分析机的说明,因此在机电式计算机的设计中,他表现了高度的独创精神.事有凑巧,当时国际商业机器公司(即著名的IBM公司)总经理汤姆斯.沃森财大气粗,并且很有远见,看到艾肯的"建议"以后,决定给予支持.从1939年开始,艾肯得到了IBM公司的资助,哈佛大学也趁机成立了计算研究所.看来艾肯的境遇比他同时代的朱斯好多了.艾肯工作起来极其认真.他往往是天蒙蒙亮到研究所,晚上八九点钟才离开.他讲起话来,发音极为清晰,表达思想十分精确.艾肯认为造出新型计算机对科学和社会是一种奉献,这种理想一直鼓舞着他奋不顾身地工作.经过4年的艰苦努力,艾肯和他的同事们共同制成了这台机电式计算机.起先他们将它叫做自动程序控制计算机,后来大家给它起了个绰号,叫做"马克—1".它是个庞然大物,约有15.5米长、2.5米高,几乎塞满了计算机研究所的一间大屋子.它用了3000多个继电器,运行时声音很响,人们很难在它身旁说话.1944年8月,马克—1计算机正式完成,接着交给了订户哈佛大学,一直使用了15年之久.由于它诞生在远离战场的美国,所以其影响要比朱斯的Z—3计算机大得多.马克—1计算机主要用于科学计算.1945～1947年间,艾肯又负责研制成功了经过改进的马克—2计算机.在计算机的发展史上,这两台机电式计算机有着重要的地位.1956年,艾肯还负责制成过马克—4计算机,那是一台在美国空军支持下研制成功的电子计算机.艾肯是个意志非常坚强最会珍惜时间的人,他每天总要晚上八九点钟才离开研究所,有时第二天凌晨4点就又回所了.1973年3月14日,艾肯在美国的圣路易斯病逝.机电式计算机是计算机发展史上短暂的一页.它是计算机发展道路上的一次必要的科学尝试.由于它工作中仍有机械动作,因此它的运算速度很难本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986