逻辑

Logic

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

来源:机器之心
简介

逻辑本身是指是推论和证明的思想过程,而逻辑学是研究“有效推论和证明的原则与标准”的一门学科。作为一个形式科学,逻辑透过对推论的形式系统与自然语言中的论证等来研究并分类命题与论证的结构。

[描述来源: https://zh.wikipedia.org/wiki/逻辑]

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

一阶逻辑,也叫一阶谓词演算,允许量化陈述的公式,是使用于数学、哲学、语言学及计算机科学中的一种形式系统。一阶逻辑是区别于高阶逻辑的数理逻辑,它不允许量化性质。性质是一个物体的特性;所以一个红色物体被表述为有红色的特性。逻辑程序的语言是一阶谓词演算的子集,因为它对许多任务有用。一阶谓词演算可以看作是一种对逻辑程序的语言,它可以增加 disjunction 析取和显式量化。一阶逻辑是一阶的,因为它允许对域内的个体进行量化。一阶逻辑既不允许谓词为变量,也不允许对谓词进行量化。

不像命题逻辑只处理简单的陈述命题,一阶逻辑还额外包含了断言和量化。断言像是一个会传回真或伪的函数。考虑下列句子:“苏格拉底是哲学家”、“柏拉图是哲学家”。在命题逻辑里,上述两句被视为两个不相关的命题,简单标记为pq。然而,在一阶逻辑里,上述两句可以使用断言以更相似的方法来表示。其断言为Phil(a),表示a是哲学家。因此,若a代表苏格拉底,则Phil(a)为第一个命题-p;若a代表柏拉图,则Phil(a)为第二个命题-q

其他的谓词逻辑有二阶逻辑,多类逻辑或无穷逻辑等等。其他的常用逻辑则有关系逻辑(Relational Logic),埃尔布朗(Herbrand Logic)逻辑等。

[描述来源:Russell, S. J., & Norvig, P. (2010). Artificial Intelligence (A Modern Approach). ]

发展历史

逻辑本身起源于古希腊哲学和数学。 第一个已知的系统逻辑学研究是由亚里士多德完成的,他的作品是他的学生在公元前322年去世后整理出来的。 公元前3世纪,古希腊哲学家克利西波斯基于之前的哲学家的观点,将命题逻辑发展成了逻辑学的一个正式分支。到12世纪,Peter Abelard 使用符号逻辑重新发明了命题逻辑。

将逻辑推理简化为适用于正式语言的纯粹抽象的过程的想法是由Wilhelm Leibniz提出的,尽管他在实现这些想法方面成功有限。 George Boole在他的书“The Mathematical Analysis of Logic”一书中介绍了第一个全面而可行的形式逻辑系统。George Boole的逻辑严密地模拟了实数的普通代数,并用逻辑等价表达式的替代作为其主要推理方法。 虽然George Boole的系统仍然缺乏完整的命题逻辑,但它已足够接近了。

第一个可以进行逻辑推理的机械装置是由third Earl of Stanhope建造的。William Stanley Jevons——是改进和扩展George Boole工作的人之一——在1869年构建了他的“逻辑钢琴”,以使用布尔逻辑进行推理。第一个发表的逻辑推理计算机程序是理论家Newell,Shaw和Simon在1957年提出的,该计划旨在模拟人类思维过程。

Emil Post(1921)和Ludwig Wittgenstein(1922)分别独立介绍了真值表作为测试命题逻辑有效或不满足的方法。在20世纪30年代,关于一阶逻辑的推理方法取得了很大进展。特别是Godel在1930年的文章表明,使用Herbrand定理,通过命题逻辑的减少可以获得完整的一阶逻辑推理过程。1943年,McCulloch和Pitts在他们的论文开创性的提出了在神经网络领域建立具有命题逻辑的代理人的想法。Davis-Putnam算法——由Davis和Putnam在1960年提出——是第一个有效的命题解析算法。1965年,在J.A.Robinson的论文中,他展示了如何在不使用命题技术的情况下进行一阶推理。

由于逻辑状态估计需要逻辑表示行为的影响 - 这是自20世纪50年代末以来人工智能中的一个关键问题。1963年,McCarthy提出了情境演算形式主义,主要应用在一阶逻辑中。1992年,Kautz和Selman提出了SATPLAN算法,这是一种更一般的方法。

1972年,Alain Colmerauer与Phillipe Roussel 开发了第一个逻辑编程系统(Prolog)。1987年,Poole, D.基于逻辑推理建立诊断系统。

逻辑不仅已经对人类心智产生了根本性的影响,也极大地影响了对机器的设计,所以逻辑的发展阶段被确定为社会影响阶段。当在谷歌趋势上搜索「logic」时,我们可以看到和「人工智能」相比,人们对逻辑的兴趣一直很高;而从谷歌学术上收集的数据也反映出了类似的结果。当然,这并不奇怪,因为在人工智能出现很久之前,逻辑就已经是一大学科了。人类会使用逻辑来解决日常生活中的很多问题(包括程序设计),而机器也要使用逻辑来理解和执行命令。因此,逻辑被运用在许多逐渐受到欢迎的学习技术领域中。如,2007年,Mihalkova等学者开发了用于马尔可夫逻辑网络(Markov Logic Networks),这是用于转移学习的算法;2012年,Fitting, M.将一阶逻辑应用于自动定理的证明。

[描述来源:Russell, S. J., & Norvig, P. (2010). Artificial Intelligence (A Modern Approach). ]

主要事件

年份事件相关论文/Reference
1921-1922Emil Post(1921)和Ludwig Wittgenstein(1922)分别独立介绍了真值表作为测试命题逻辑有效或不满足的方法Post, E. L. (1921). Introduction to a general theory of elementary propositions. American Journalof Mathematics, 43, 163–185. //Wittgenstein, L. (1922). Tractatus Logico- Philosophicus (second edition). Routledge and Kegan Paul.
1930Godel的文章表明,使用Herbrand定理,通过命题逻辑的减少可以获得完整的一阶逻辑推理过程Godel, K. (1930). Uber die Vollstandigkeit des Logikkalkuls. Ph.D. thesis, University of Vienna.
1943McCulloch和Pitts在他们的论文开创性的提出了在神经网络领域建立具有命题逻辑的代理人的想法McCulloch, W. S. and Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5, 115–137.
1957Newell,Shaw和Simon提出逻辑推理计算机程序Newell, A., Shaw, J. C., and Simon, H. A. (1957). Empirical explorations with the logic theory machine.Proc. Western Joint Computer Conference, 15, 218–239.
1960Davis和Putnam提出Davis-Putnam算法Davis,M. and Putnam, H. (1960). A computing procedure for quantification theory. JACM, 7(3), 201–215.
1963McCarthy提出了情境演算形式主义,主要应用在一阶逻辑中McCarthy, J. (1963). Situations, actions, and causal laws. Memo 2, Stanford University Artificial IntelligenceProject.
1965J.A.Robinson展示了如何在不使用命题技术的情况下进行一阶推理Robinson, J. A. (1965). A machine-oriented logic based on the resolution principle. JACM, 12, 23–41.
1972Alain Colmerauer与Phillipe Roussel 开发了第一个逻辑编程系统(Prolog)Colmerauer, A.; Roussel, P. (1993). The birth of Prolog. ACM SIGPLAN Notices. 28 (3): 37.
1992Kautz和Selman提出了SATPLAN算法Kautz, H. and Selman, B. (1992). Planning as satisfiability. In ECAI-92, pp. 359–363.
2007Mihalkova等学者开发了用于马尔可夫逻辑网络(Markov Logic Networks)的转移学习算法Mihalkova L.; Huynh T.; Mooney R. J. (2007),Mapping and Revising Markov Logic Networks for Transfer.Learning Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-2007).pp. 608–614,
2012Fitting, M.将一阶逻辑应用于自动定理的证明Fitting, M. (2012). First-order logic and automated theorem proving. Springer Science & Business Media.

发展分析

瓶颈

  • 逻辑所面临的瓶颈不是其在人工智能领域的应用,而是其内在的局限性,比如为逻辑推理设定的假设是否正确。

未来发展方向

  • 克服逻辑本身固有的局限性可不容易,但逻辑在人工智能领域的应用还会得到扩展。比如说,逻辑学与机器人的整合可以给我们带来一个「家用的亚里士多德」,为我们答疑解惑,成为我们的朋友和导师。

Contributor:Yuanyuan LI, Mos Zhang

相关机构
  • Computational Logic and Argumentation, Imperial College London
  • Artificial Intelligence (AI) Group, UWaterloo
  • Stanford Logic Group
相关人物
马丁·戴维斯
马丁·戴维斯
美国数学家,1950年在普林斯顿大学获得博士学位。他是Davis–Putnam算法和DPLL算法的共同发明者。他还以他的Post–Turing机器模型和他在希尔伯特第十个问题上的工作而闻名。
路德维希·维特根斯坦
路德维希·维特根斯坦
奥地利哲学家,生于奥地利,后入英国籍。维特根斯坦是20世纪最有影响力的哲学家之一,其研究领域主要在语言哲学、心灵哲学和数学哲学等方面。1939年至1947年,任教于剑桥大学三一学院。他在生前出版的著作不多,主要为1921年的《逻辑哲学论》和一本奥地利小学生的字典。
沃伦·麦卡洛克
沃伦·麦卡洛克
美国神经科学家和控制论学者,以其在大脑理论基础上的工作和对控制论的贡献而闻名。他与Walter Pitts一起基于阈值逻辑算法创建了计算模型。
乔治·布尔
乔治·布尔
1815-1864,英格兰数学家和哲学家,数理逻辑学先驱。布尔最著名的著作是《The Laws of Thought》,他在这本书中介绍了现在以他的名字命名的布尔代数。布尔撰写了微分方程和差分方程的课本,这些课本在英国一直使用到19世纪末。
亨利·考茨
亨利·考茨
计算机科学家,美国国家科学基金会信息和智能系统部门主任,罗切斯特大学教授、数据科学研究所创始主任,AAAI、AAAS会士。研究兴趣:知识表示、人工智能、数据科学和普适计算。
William Stanley Jevons
William Stanley Jevons
John A. Robinson
John A. Robinson
Alain Colmerauer
Alain Colmerauer
埃米尔·莱昂·波斯特
埃米尔·莱昂·波斯特
(1897~1954),哥伦比亚大学博士,美国数学家和逻辑学家,以在可计算性理论方面的工作而著称。
简介
相关机构
相关人物