中文XML论坛--计算机科学导论前言：逻辑的引擎[原创]

计算机科学与技术导论
庄朝晖

(厦门大学计算机科学系,361005，厦门）
计算机专业学什么？
... 计算机的实用层面：Windows使用，Office办公软件使用，Photoshop图像处理，收发Email，QQ聊天，上网，英汉翻译软件，语音识别…
... 计算机的应用层面：高级语言程序设计，数据结构，算法设计，操作系统，编译原理，汇编语言，计算机组成原理，嵌入式系统，数据库基础，计算机网络，计算机安全，图像处理，人工智能…
... 计算机的理论层面：计算理论，计算复杂性，形式语义学，体系结构，分布式算法，密码学，数理逻辑，图论与集合论…
课程简介
... 计算机，会计算的机器。又称电脑，这个名字更形象。什么叫计算？
... 计算机科学：也称计算科学。
... 艺术：还未形式化的东西，还未知计算方法的。
... 科学：计算科学中的理论层面，一般来说是形式化的，数字化的，还处于研究阶段的。
... 技术：计算科学中的技术层面，一般来说是已经成熟的，工艺化的。
计算科学的起源－从逻辑开始
... 中文的“逻辑”显然音译自英文的“logic”。logic又来自中古拉丁文的logica，logica又源自希腊文logos（λóγｏｓ）。logos一般翻译为“逻格斯”，接近于中文里的“道”。
... 中文的“道”和希腊文“logos”都有以下两层意思：
1 各种事物的定义或者各种活动的规则（西方各门学科的名字都以 -logy缀后的习惯）
2 言说，言谈
... 这两层意思也是相互关联的。言谈是为了揭示事物的道理，道理一般也通过言谈得以开显。
逻辑的发展
... 在言谈和辩论中，渐渐发展出逻辑学这一领域。从地域来分，古代逻辑学可以分为希腊逻辑学（亚里士多德），印度逻辑学（因明学）和中国逻辑学（墨子名学）。
... 亚里士多德三段论：
... 大前提：所有人都是有死的。
... 小前提：苏格拉底是人。
... 结论：苏格拉底是有死的。
逻辑四大基本定律
... 同一律：指概念在同一思维过程中必须保持同一。
... 矛盾律：亚里士多德在《形而上学》中说：“同一事物，不可能在同一时间内既存在又不存在，也不允许有以同样方式与自身相对立的东西。”
... 排中律：亚里士多德：“在对立的陈述之间不允许有任何居间者，而对于同一事物必须要么肯定要么否定其某一方面。”
... 充足理由律：首先由莱布尼兹提出。所谓充足理由律是指：“任何一件事如果是真实的或实在的，任何一个陈述如果是真实的，就必须有一个为什么这样而不那样的充足理由，虽然这些理由常常不能为我们所知道的。”
故事：为什么小子
... 在《聪明的一休》里，大家都躲着好奇小子，因为好奇小子老爱问“为什么”，常常会把大家问得无言以对。
... 公主：一休是我一个人的朋友！
... 为什么小子：为什么你一个人要霸占他？
... 公主大声叫：这件事用不着你管！
... 为什么小子：为什么不用我管呢？
... 公主：＠＃＠￥＃￥
... 为什么小子：“为什么你脸上的表情这么好笑呢？”
... 公主：……倒
逻辑与哲学的关系
... “哲学”一词出自古希腊文“philo-sophia”，意为“爱智慧”，原意为热爱智慧追求智慧
... 逻辑与哲学是密切相关的，一直伴随着哲学的发展，从亚里士多德的《工具论》到弗雷格的《算术基础》。当代西方哲学的一个重要方向分析哲学(语言哲学)的发展史就是逻辑学的发展史。
... 当代西方哲学的另一个重要方向现象学与逻辑也存在密切关系，现象学祖师胡塞尔就是从逻辑研究走向了现象学。
... 此外，逻辑学给哲学研究提供了一个思维基础，现在哲学的各个子学科基本上都要求有逻辑的基础。比如伦理学也有规范伦理学。

... 当然，逻辑也是科学的基石和立柱。你看，现代学科都要加上“-logy”的后缀。
... 科学学科都包含了归纳推理和演绎推理的方法。

... 在以往，逻辑学是哲学的一个分支。1800中期后，逻辑学也成为数学的一个分支。近代以来，逻辑学成为计算机科学的重要基础。根据应用的领域，逻辑可以分为哲学逻辑，数理逻辑和计算逻辑。
... 当代逻辑的发展，包含以下几位重要的人物：弗雷格、罗素、维特根斯坦、哥德尔、图灵
现代逻辑的发展
... “万一发生争执，正像两个会计员之间无须乎有辩论，两个哲学家也不需要辩论。因为他们只要拿起石笔，在石板前坐下来，彼此说一声（假如愿意，找个朋友作证）：我们来算算，也就行了。” －－莱布尼兹

... 德国思想家莱布尼兹是有史以来最伟大的思想家之一。他与牛顿分别独立发现了微积分，后世使用的微积分主要使用莱布尼兹的符号；
... 他提出了通用计算的思路，使用计算来代替思考。他的这种想法，对于后来数理逻辑、计算机科学和分析哲学有重大影响；他提出了可能世界思想。如果某世界与现有世界并不矛盾，那就是可能的世界。他的可能世界思想后来被克里普克发展为可能世界语义，广泛用于非经典逻辑的语义解释；他还系统提出了二进制，这是现代计算机使用的内部语言。

... 弗雷格对于我们也许是陌生的名字，然而弗雷格是上世纪最伟大的思想家之一。他的《概念语言》一书，系统提出了现代逻辑，用严格清晰的数学符号来研究逻辑学。因此，他开创的现代逻辑学又称为数理逻辑，或符号逻辑。为什么说他是上世纪最伟大的思想家之一，这一点没有夸张。

... 他开创的数理逻辑对上世纪的科学和哲学两大领域都有重大影响。一方面，顺着罗素，希尔伯特，哥德尔，计算机之父图灵机，人工智能之父麦卡锡这个方向，他开创的数理逻辑思想被广泛用到计算机科学，被广泛用到人工智能和程序证明。另一方面，顺着罗素，维特根斯坦，卡尔纳普，奎因，普特南这个方向，他开创的数理逻辑及概念分析法发展成分析哲学。而分析哲学，是当前西方哲学的主流方向之一。

... 罗素的头衔很多，哲学家，数学家，逻辑学家，社会活动家，文学家。他在逻辑学方面的成就，主要是与他的老师怀特海编写了《数学原理》，使得弗雷格开创的数理逻辑更加系统更加完善。

... 如果说弗雷格是数理逻辑的开山祖师，那么罗素就是数理逻辑的集大成者。罗素继续弗雷格的逻辑主义，想把数学归结到逻辑上。然后，他自己提出的罗素悖论使这一努力失败。

... 布劳维尔：荷兰数学，自立门户，提出了直觉主义思想，反对康托尔集合，认为罗素悖论是根源于非构造性的数学，强调构造性证明，反对基于无穷集的排中律。

... “我们必须知道，我们必将知道。”－－希尔伯特
... 数学基础出现了矛盾，以确定性追求为己任的数学家如何受得了。集合论的矛盾弥漫开来，有人也怀疑算术是否也有矛盾。为了捍卫古典数学的尊严，作为当时数学界的领袖，希尔伯特当仁不让，接过了这个挑战。

... 继1900在数学家大会上提出著名的希尔伯特23个问题后，1904年，希尔伯特在数学家大会上又提出一个证明算术无矛盾性的思路。
... 这个思路也称为形式主义纲领，它的核心思想是将算术表达为一种形式系统或称公理系统，然后用有穷步骤证明该系统的无矛盾性。希尔伯特的目的是试图对形式系统的无矛盾性给出让大家都可以接受的证明，以便克服悖论所引起的危机，一劳永逸地消除对数学基础以及数学推理方法可靠性的怀疑。对于这个纲领，希尔伯特信心十足，在哥尼斯堡演讲中说出了上面的话。

... 哥德尔研究了希尔伯特纲领，给出否定的答案，宣告希尔伯特纲领的失败。1930年提出的哥德尔第二不完备性说，任何包含一阶算术的形式系统，该形式系统的无矛盾性，在该形式系统内无法通过有穷的步骤得到证明。在定理的证明中，哥德尔还提出了很多有用的理论，比如如何把符号编码为自然数，还有使用递归函数来研究有穷证明的能力范围。

... 哥德尔的工作揭示了有些问题是不可通过有限的步骤得以证明的，那么什么问题是可以通过有限的步骤证明的？沿着这个问题，哥德尔的很多工作，被应用到了可计算性的研究。什么是可以有穷证明的，从可计算性的角度来说对应于，什么是可以计算的。

... 哥德尔不完备定理出世后，在剑桥大学的图灵设想：能否有这样一台机器，通过某种一般的机械步骤，能够解决所有可以解决的数学问题。以上机器就是他提出来的图灵机。图灵机可以计算的问题，就称为图灵机可计算。

... 它由一个控制器和一条两端可无限延长的工作带组成：工作带起着存储器的作用，它被划分为无穷多个可写可擦的方格。控制器则可以在带上左右移动，控制带有一个读写头，读写头可以读出当前方格内的符号，然后根据预先设计的状态转换指令，选择改写或抹去这一符号，然后选择往左移一格，往右移一格或者不移动，并进入下一个状态。当状态转换到停机状态，则停止运行。

... 图灵机的出现，奠定了计算机科学的理论基础，计算机的出现已经主要是技术实现的问题了。据说，图灵在二战期间主持设计了一台计算机。但资料比较多的，1946年，数学家冯...诺依曼主持设计了第一台计算机。但不管如何，图灵被广泛认为是“计算机之父”。现代计算机的计算能力，还是在图灵机的计算能力之内，当然速度是越来越快了。图灵开辟了一条大路，后来的科学家又开辟了一些中路小路，我们则行走在前人铺就的路上。
... 　　

... 1966年，美国计算机协会设立以图灵为名的“图灵奖”，用于表彰在计算机科学领域做出突出贡献的科学家。图灵奖的得主有： Ken Thompson ，Dennis M. Ritchie， Minsky，“人工智能之父”McCarthy，Dijkstra，Knuth，Backus，Floyd，Hoare，Codd，Cook，Thompson，Wirth，姚期智，RSA三人，“互联网之父”Cerf和Kahn……

逻辑与计算机科学的关系
... 在第三次数学危机中，随着罗素悖论等难题的出现，经典数学的方法受到了空前的置疑：反证法、实无穷。学者们思考这样一个问题：什么样的数学，是确定的？
... 在对经典数学的批判过程中，一些构造性的计算模型成长了起来：递归函数论、公理系统、图灵机和lambda演算等。在这些计算模型之上，学者们提出了何谓“计算”。
... 有趣的是，这些计算模型的计算能力是相同的。因此，目前人们对于“计算”的理解，就是基于这些计算模型之上的计算能力。量子计算的计算能力还是在这个范围之内。
... 其次，因为这些计算模型的等价性，图灵机的计算问题也可以化为在逻辑层面上的逻辑问题。比如P与NP是否相等的问题，也可以在逻辑层面上进行思考。
逻辑的局限
... 逻辑定理的有效性，依赖于公理和推理规则的有效性。
... 逻辑定理的有效性，已经包含在前提之中了。在这个意义上，维特根斯坦说定理都是废话。当然了，这些废话埋藏得如此之深，以致于人类不能一下子知道它是废话。这时候，机器可以帮助人类。人类给出前提，机器快速自动推出定理。
... 这就是当前计算机的价值和局限。未来，能不能发展出能听能看能认识外界能自己进行归纳的机器？
归纳
... 培根：“知识就是力量”
... 培根：“读史使人明智，读诗使人聪慧，演算使人精密，哲理使人深刻，论理学使人有修养，逻辑修辞使人善辩”
... 所谓归纳，是指从许多个别的事物中概括出一般性概念、原则或结论的思维方法。
... 比如张三有死，李四有死，…，故而归纳出“所有人都是有死的”。
... 又如鸽子会飞，大雁会飞，…，故而归纳出“所有鸟都是会飞的”。
休谟难题
... 以前每天太阳都会升起，那么明天的太阳是否必然也会升起？如果回答是必然，请问如何证明？
... 最早对归纳法提出置疑的是英国哲学家休谟，所以归纳法的合理性问题也称为“休谟问题”。
... 因为在科学研究中，特别是经验科学如物理学，经常进行实验再使用归纳法来得出知识。所以，休谟问题其实也是“知识如何保证”的问题。
... 因为休谟提出这个问题，有学者就认为休谟反对理性，这有点奇怪，难道要信仰“理性万能”才理性吗？难道能提出理性局限的人不是更理性吗？

... 休谟认为：“说到过去的经验那我们不能不承认，它所给我们的直接的确定的报告，只限于我们所认识的那些物象和认识发生时的那个时期。但是这个经验为什么可以扩展到将来，扩展到我们所见的仅在貌相上相似的别的物象；则正是我所欲坚持的一个问题。”他认为归纳推理的合理性不可证明，宣称这类推理只是一种心理“习惯”。
... 休谟虽然否认归纳法有逻辑的合理性，但是，休谟并不否认归纳法对于人们的指导作用。作为一名经验主义者，休谟在生活中很推崇归纳法。
... 几百年来，哲学家们尝试想攻克“休谟问题”，比如康德，始终以失败告终。当然，也有一些成果。比如使用概率来解释归纳。虽然有“休谟问题”，虽然不能证明知识是必然正确的，但与休谟一样，我们还是使用归纳法来获得科学知识，因为这些科学知识很实用。

归纳的局限
... 归纳出来的知识永远无法被证明是完全正确的。
... 归纳出来的知识是可错的，比如“所有的鸟都会飞”。
逻辑与归纳的结合
... 逻辑与归纳其实是分不开的。
... 逻辑的前提，往往来源于归纳。
... 根据前提，逻辑又可以推导出更多的定理和知识。
... 比如物理学，就是逻辑与归纳的完美结合。
何谓科学
... 什么是科学？什么不是科学？
... 关于科学的标准，比较直观的是“可证实性”标准。如果一个理论是可以证实的，那么该理论就是科学的。但是这个标准存在一些困难，对于一些全称语句比如“所有的鸟都会飞”或者“所有的人都是要死的”这样的理论，我们无法一一证实。
... 波普尔引入了“可证伪性”作为科学标准。如果一个理论是可以证伪的话，那么该理论就是科学理论。
... 后来，库恩提出了一种更全面的标准。他把科学看作一定的科学共同体按照一套共有的“范式”所进行的专业活动，并描绘了一种常规时期和科学革命时期相互交替的科学发展模式。
科学的一般方法
... 找到问题：寻找一个合适的问题，最好要有应用的前景。
... 分析问题：全面理解这个问题，前提是什么，有没有隐藏的前提，前提会不会太弱，结论是什么。如果此前没人研究过，如何把问题讲清楚？
... 前人对于这个问题做出了什么贡献？最新的进展是什么？有什么比较有前景的解决方法？
... 如何在前人的基础之上，做出自己的贡献？
... 如果是理科，要证明自己的观点。如果是理工科，还要做实验来验证自己的观点。


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	7,530.273ms