现代逻辑学发展史.ppt

数理逻辑发展史数理逻辑发展史研究生课程研究生课程苏苏 畅畅11 五月五月 2024从莱布尼茨到哥德尔.逻辑学是一门古老而又年轻的科学逻辑学是一门古老而又年轻的科学古老 形式逻辑已有两千多年的悠久历史。早在公元前5世纪前后，古代中国、古印度和古希腊就产生了各具特色的逻辑学说。中国的名辩、印度的因明和西方的逻辑。2Aristotle逻辑学Leibnitz数理逻辑GottlobFrege(1848-1925)一阶谓词演算系统,符号论20世纪30年代，数理逻辑广泛发展3逻辑是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。4利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。莱布尼茨就曾经设想过能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。51847年，英国数学家布尔发表了逻辑的数学分析，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。6十九世纪末二十世纪初，数理逻辑有了比较大的发展，1884年，德国数学家弗雷格出版了数论的基础一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。7库尔特库尔特哥德尔哥德尔（KurtGödel）（1906年4月28日1978年1月14日）是位数学家、逻辑学家和哲学家。其最杰出的贡献是哥德尔不完全性定理和连续统假设的相对协调性证明。8哥德尔发展了冯诺伊曼和伯奈斯等人的工作，其主要贡献在逻辑学和数学基础方面。在20世纪初，他证明了形式数论（即算术逻辑）系统的不完全性定理：即使把初等数论形式化之后，在这个形式的演绎系统中也总可以找出一个合理的命题来，在该系统中既无法证明它为真，也无法证明它为假。这一著名结果发表在1931年的论文中。他还致力于连续统假设的研究，在1930年采用一种不同的方法得到了选择公理的相容性证明。3年以后又证明了（广义）连续统假设的相容性定理，并于1940年发表。他的工作对公理集合论有重要影响，而且直接导致了集合和序数上的递归论的产生。9哥德尔思想的博大精深，“恰是远在天边的一处幽秘风景，虽令人心弛神往却难以身临其境”；所以，要领略那一处风景，“实在得有一种能够顾盼几个世纪的历史眼光才行”。10人们对于爱因斯坦并不陌生，但对于被他视为知己的普林斯顿高等研究院的同事哥德尔却不甚了解。哥德尔无疑是一位智慧巨人，美国时代杂志评选出对20世纪思想产生重大影响的100人中，哥德尔列为第四。11他的不完全性定理不仅使数学发生革命性的变化，而且改变了整个科学世界和建筑于此定理之上的哲学，还波及语言学、计算机科学、宇宙学，甚至包括法律上的“无罪推定”。对于人类来说，不了解哥德尔就不了解人类已达到的智力水平与人类智力奋斗的历程，也就无法了解我们这个世界在思想观念上已经发生或正在发生的深刻变化。12哥德尔被认为是自亚里士多德以来最伟大的逻辑学家。哥德尔定理粉碎了逻辑最终将使我们理解整个世界的梦想，同时也引发了许多富有挑战性的问题：什么是理性思维的界限？我们能够完全理解我们自己造的机器吗？我们能够搞清楚我们心智的内在工作过程吗？13自古以来，人类一直在给知识的确定性寻找一个坚实的基础。从亚里士多德使逻辑学成为一个专门的学科开始，甚至哲学上无休止的争论也是源于对我们的知识是否有确定性以及这种确定性的来源的争论。但逻辑学家、数学家与哲学家不同，他们不满足于仅仅给知识的确定性一个形而上学的解释，他们希望用逻辑与数学为人类的知识建立一个严格的、自满自足的、与形而上学无关的基础。科学家们一直坚信，总有一个完备的公理化系统，任何命题在其中或被证明为真、或被证明为伪。有了这样一个一劳永逸的系统，任何知识都可以被证明、被推导或者被确认。141930年初，信心满满的希尔伯特在自己的出生地哥尼斯堡接受“荣誉市民”的演说时还乐观地说：“我们必须知道，我们必将知道。”但同样在1930年秋于哥尼斯堡举行的科学哲学讨论会上，年方25岁的哥德尔在会议即将结束时宣布了那个革命性的发现不完全性定理。简单说就是在一个稍微复杂（例如包含算术中的加法和乘法）的形式系统中，存在一些命题，我们既不能证明它是真的，也不能证明它是假的。换言之，一个定理的真假和它的可证性不是一回事。15这与我们对数学的传统观念大不相同。过去对于数学中的一个问题，我们怎样确定说它被解决了呢？要么你给出一个证明，要么你给出一个反例说明这个定理不成立。这两种情形不论哪种都可以使问题得到解决。但这个不完全性定理却大大颠覆了人们对传统数学的观念，打碎了无数人的美梦，数学的“灾难”因此降临了。对此，数学家外尔哀叹道：“上帝是存在的，因为数学无疑是相容的；魔鬼也是存在的，因为我们不能证明这种相容性”。16对于爱因斯坦来说，在普林斯顿高等研究院的日子，最重要的并不是科学研究，而是陪哥德尔散步回家，他们谈论哲学、物理学和政治，“彼此知心得不得了，彼此赏识得不得了”；爱因斯坦赞扬哥德尔是“自亚里士多德以来比任何人都有力地动摇了逻辑基础”的人。著名经济学家摩根施特恩说“他确实是自莱布尼茨以来，或者说是自亚里士多德以来最伟大的逻辑学家”。王浩称哥德尔定理的奠基性贡献“好比弗洛依德的心理学、爱因斯坦的相对论、玻尔的互补性原理、海森堡的测不准原理、凯恩斯的经济学和DNA的双螺旋”。1718爱因斯坦晚年曾说，他之所以每天还去普林斯顿高等研究所的办公室，就是为了能与哥德尔一起在上下班的路上散步交谈。物理学家戴森(FreemanDyson)也说，哥德尔是同事中间惟一能够与爱因斯坦平等交谈的人。19比较一下爱因斯坦和哥德尔，会发现他们存在许多的相同点。都是在很年轻的时候就做出最重要的成果，1905年，爱因斯坦26岁，这一年是他的奇迹年。1930年，哥德尔24岁，作出了他的第一个伟大贡献-哥德尔第一不完备性定理；他们都是说同样的母语，并且这些成果都是在中欧的德语区做出的；两人在年轻的时候都曾想进入对方的领域；然后也都因为在欧洲待不去了才逃亡到了美国。20冯.诺依曼慧眼识明珠1930年10月当哥德尔在柯尼斯堡的讨论会上首次发表他的第一不完备性定理时，当时只有一个人领会了这位年轻的逻辑学家的报告，就是冯.诺依曼。虽然在当时，他的观点与希尔伯特一致，同时也是形式主义的典型代表，与哥德尔强烈的实证主义观点不同。并且在会上，冯.诺依曼根据哥德尔的报告还得出一个推论-哥德尔第二不完备性定理。然后通过冯.诺依曼在高等研究院的大肆宣传，哥德尔的定理开始首先受到关注。21深刻影响了图灵图灵19361937在高等研究院作学术访问，也正是在这里，他通过冯.诺依曼接触到了哥德尔的不完备性定理。在回到剑桥后，他继续沿着哥德尔的推理路线前时，最终取得了极大成功。他的关于可判定性和可计算性的证明工作也让哥德尔甚感欣慰，他说图灵的工作巩固了他的两个不完备性定理。不过可惜的是，两个天才却从未谋面。222002年8月17日，英国著名科学家霍金在北京国际弦理论会议上发表了题为哥德尔与M理论的报告，他说，建立一个单一的描述宇宙的大统一理论是不太可能的。这一推测正是基于数学领域的哥德尔不完全性定理。其实，这只是哥德尔思想的巨大冰山的一角，要更深入地认识、理解它，还需要更多的时间与更高的智识。23哥德尔在第一不完全性定理的证明中，构造了一个公式G，使得这个G是真的但在这个系统内却是不可证的。这个G可以理解为以下的汉语描述：“这个数论语句在系统中是不可证的。”这个G是不可证的，也就是“这个数论语句在系统中是不可证的”在系统中是不可证的。在这里，我们看到了“自引用”（或称“自指”，“怪圈”）。24这种怪圈并不是在数学上独有的。侯世达先生（DouglasR.Hofstadter）的哥德尔、艾舍尔、巴赫集异壁之大成是人工智能界的一本奇书。在这本书里，作者考察了各种形式的“自引用”。为了对这种“自引用”有个直观的了解，大家不妨看一下艾舍尔的木雕画，看看那些“瀑布”、“拿着反光球的手”、“变形”、“左手画右手，右手画左手”等怪画。同样，在巴赫的卡农与赋格里，也存在类似的怪圈。数理逻辑学家哥德尔更是神奇般地把这种怪圈引进了以精确著称的数学领域。令人叫绝的是，侯世达先生甚至在本书的创造中也使用了很多怪圈。25这种怪圈在音乐界，在美术界，在文学界，在数学界，道德界、语言界乃至日常生活中都有其客观的存在，那能否说怪圈是人类的一种现象呢？是不是因为某种更本质的怪圈（比如意识里的怪圈），才导致了这种怪圈现象在音乐、在美术、在文学、在数学上的投影呢？26数理逻辑论的体系数理逻辑论的体系数理逻辑的主要分支包括：逻辑演算(包括命题演算和谓词演算)、模型论、证明论、递归论和公理化集合论。数理逻辑和计算机科学有许多重合之处，这是因为许多计算机科学的先驱者既是数学家、又是逻辑学家，如阿兰图灵、邱奇等。27程序语言学、语义学的研究从模型论衍生而来，而程序验证则从模型论的模型检测衍生而来。柯里霍华德同构给出了“证明”和“程序”的等价性，这一结果与证明论有关，直觉逻辑和线性逻辑在此起了很大作用。演算和组合子逻辑这样的演算现在属于理想程序语言。计算机科学在自动验证和自动寻找证明等技巧方面的成果对逻辑研究做出了贡献，比如说自动定理证明和逻辑编程。28与计算机科学的联系与计算机科学的联系 布尔电路：香龙Shanon是第一人。计算理论：可计算性，TuringTuring机，形式语言，自动机，计算复杂性。程序语义与验证技术.Intel bug:5亿美元。程序的自动生成与转换。SQL:SQL:本质上等价于一阶逻辑。PrologProlog语言以逻辑演算为基础 LISPLISP语言以演算为基础 人工智能：非单调推理，缺省推理。信息安全等 29与知识表示和推理的关系与知识表示和推理的关系30关于知识的表示与推理 智能行为的基础是知识，尤其是所谓的常识性知识。人类的智能行为对于知识的依赖主要表现在对于知识的利用，即利用已经具有的知识进行分析、猜测、判断、预测等等。人类利用知识可以预测未来，由已知的情况推测未知的情况、由发生的事件预测还未发生的事件等等。31关于知识的表示与推理但是，当人们希望计算机具有智能行为时，除了告诉计算机如何像人一样地利用知识以外（对于知识进行推理），一个更为基础和先行的工作是如何使计算机具有知识（对于知识进行表示），即在计算机上如何表达人类的知识。32关于知识的表示与推理 多数的基于逻辑的智能系统使用一阶逻辑或者它的一些扩张形式。一阶逻辑的优点是它具有相当强的表达能力。有的人工智能专家坚信所有的人工智能中的知识表示问题完全可以在一阶逻辑的框架中得以实现。一阶逻辑在表达不确定性知识时其表达能力也是很强的。例如，x P(x)表达在所考虑的论域中存在一个具有性质P的对象，而具体的是哪一个对象具有此性质则是待确定的；33关于知识的表示与推理再如，PQ表示P和Q这两个性质之间有一个是成立的，至于到底是哪一个成立则是根据具体的情况而定的。34关于知识的表示与推理 有人坚信从本质上看,一阶逻辑对于知识表示 是足够的,但从实际应用的角度看,为方便、清楚和简洁起见,知识表示不一定非得从一阶逻辑出发。事实上，人们从实际应用出发已经发明和建立了许多适用于不同目的的逻辑系统。35(1)为了表示关于认知的有关概念，如相信、知道、愿望、意图、目标、承诺等等，人们引进了刻划各种认知概念的模态逻辑；(2)为了刻划智能系统中的时间因素，人们在逻辑系统中引进时间的概念，提出了各种时序逻辑；36关于知识的表示与推理 (3)为了描述各种不确定的和不精确的概念，人们引进了所谓模糊逻辑；模糊逻辑是直接建立在自然语言上的逻辑系统，与其它逻辑系统相比较，它考虑了更多的自然语言的成分。按照其创始人Zadeh的说法就是词语上的计算，表示为一个公式,即，fuzzy logiccomputing with words；37关于知识的表示与推理(4)人类的知识与人类的活动是息息相关的，人类正是在各种活动和行为中获得知识的。因此，行为或者动作的概念在智能系统中是一个关键的概念。动作的概念与一般逻辑中的静态的概念很不相同，它是一个动态的概念，动作的发生影响着智能系统的性质。对于动作的考虑，给人工智能界带来了许多难题，如框架问题、量词问题等等。为了刻划动作的概念，人们引进了一些新的逻辑体系来刻划它。38关于知识的表示与推理 (5)计算机对于人类进行决策时进行若干方面的支持已经成为计算机应用的一个重要方面。人类在决策时，对于各种方案和目标有一定的偏好和选择。这时“偏爱”就成为了一个基本的概念。为了表述和模拟人类在决策时的选择的规律和行为，对于“偏爱”这个词的研究就是不可避免的。于是，基于管理科学的所谓的偏爱逻辑被提出并加以研究。39关于知识的表示与推理(6)时间是智能系统中最重要的几个概念之一。人类使用各类副词来对时间概念加以描述。例如，“一会儿”“相当长”“断断续续地”“偶尔”等等,这一类词在我们的日常生活中比比皆是。含有这些词的句子显然是很难用经典的时序逻辑来刻划的,于是有人引进了一种逻辑系统专门刻划这类句子。其基本思想是利用数学中积分的思想，通过对时间的某种像积分那样的表示和运算来形式化这些句子。40逻辑系统逻辑系统一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：逻辑符号集合逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号；非逻辑符号集合非逻辑符号集合：不同的逻辑理论中出现的不同的符号；语句规则语句规则：定义什么样的符号串是有意义的；证明证明：什么样的符号串是一个合理的证明；语义规则语义规则：定义符号串的语义。41逻辑逻辑程序语言程序语言逻辑符号保留字或者符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的语句规则推理规则、公理和证明没有逻辑与程序语言的对比42哲学逻辑手册哲学逻辑手册1983-89年间出版了4卷本 哲学逻辑手册(Handbook of Philosophical Logic)2001年开始出版第 2版，约为1818卷卷，迄今已经出版12卷。该书由英国伦敦皇家学院计算机系的多夫加贝加贝（Dov M.Gabbay）教授和德国路德维希-麦克米兰大学信息与语言处理中心的冈瑟冈瑟（F.Guenthner）教授共同主编。43已经出版的前已经出版的前1212卷内容卷内容 高阶逻辑 冲突 多值逻辑多值逻辑 模糊逻辑 概率论 条件句 模态逻辑模态逻辑 动态逻辑 容错逻辑 优先逻辑 图形逻辑图形逻辑 偏逻辑 直觉主义逻辑直觉主义逻辑 非单调推理非单调推理 信念逻辑 自由逻辑 时序逻辑时序逻辑 相干逻辑 量子逻辑 蕴涵逻辑 时态逻辑 问题逻辑 道义逻辑 弗协调逻辑 目标导向演绎 认知逻辑 加标演绎系统加标演绎系统（逻辑新框架理论）等44现代逻辑学与计算机科学、计算语言学和人工智能的关系表现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻逻 辑辑 自然语自然语 程序程序 人工人工 逻辑逻辑 指令与直指令与直 数据库数据库 复杂性复杂性 智能体智能体 未未 来来 展展 望望 言处理言处理 控制控制 智能智能 编程编程 陈式语言陈式语言 理论理论 理论理论 理论理论时序逻辑时序逻辑 广泛应用广泛应用模态逻辑模态逻辑 非常活跃非常活跃算法证明算法证明 非单调推理非单调推理 意义重大意义重大概率和模糊概率和模糊 目前主流目前主流直觉主义逻辑直觉主义逻辑 主要替代者主要替代者高阶逻辑，高阶逻辑，-演算演算 更具中心作用更具中心作用经典逻辑片断经典逻辑片断 前景诱人前景诱人资源和子结构逻辑资源和子结构逻辑 纤维化和组合逻辑纤维化和组合逻辑 可自我指称可自我指称谬误理论谬误理论 在适当语境在适当语境逻辑动力学逻辑动力学 动态逻辑观动态逻辑观论辩理论游戏论辩理论游戏 前景光明前景光明对象层次对象层次/元层次元层次 总起中心作用总起中心作用机制机制:溯因溯因 缺省缺省 相干相干 逻辑的一部分逻辑的一部分与神经网络的联系与神经网络的联系 极重要，刚开始极重要，刚开始时间时间-行动行动-修正模型修正模型 一类新模型一类新模型加标演绎系统加标演绎系统 逻辑学的统一框架逻辑学的统一框架45参考文献参考文献史忠植，高级人工智能，科学出版社，1998。陆钟万，面向计算机科学的数理逻辑，科学出版社，2000。王元元，计算机科学中的逻辑学，科学出版社，1989。46THANKSTHANKS47