高级人工智能-第二章-人工智能逻辑

2020/4/1史忠植高级人工智能1高级人工智能第二章人工智能逻辑史忠植中国科学院计算技术研究所2020/4/1史忠植高级人工智能2第二章人工智能逻辑2.1重要的形式工具-----逻辑2.2非单调逻辑2.3默认逻辑2.4限定逻辑2.5自认知逻辑2.6真值维护系统2.7情景演算的逻辑基础2.8动态描述逻辑2020/4/1史忠植高级人工智能3逻辑的历史•Aristotle——逻辑学•Leibnitz——数理逻辑•GottlobFrege(1848-1925)——一阶谓词演算系统,《符号论》•20世纪30年代，数理逻辑广泛发展2020/4/1史忠植高级人工智能4重要的形式工具──逻辑在本世纪30年代以后，数学方法广泛渗透与运用于数理逻辑，使得数理逻辑成为数学领域中与代数、几何等并列的学科之一。现代数理逻辑可以分为逻辑运算、证明论、公理集合论、递归论和模型论。2020/4/1史忠植高级人工智能5关于知识的表示与推理智能行为的基础是知识，尤其是所谓的常识性知识。人类的智能行为对于知识的依赖主要表现在对于知识的利用，即利用已经具有的知识进行分析、猜测、判断、预测等等。人类利用知识可以预测未来，由已知的情况推测未知的情况、由发生的事件预测还未发生的事件等等。但是，当人们希望计算机具有智能行为时，除了告诉计算机如何像人一样地利用知识以外（对于知识进行推理），一个更为基础和先行的工作是如何使计算机具有知识（对于知识进行表示），即在计算机上如何表达人类的知识。2020/4/1史忠植高级人工智能6关于知识的表示与推理多数的基于逻辑的智能系统使用一阶逻辑或者它的一些扩张形式。一阶逻辑的优点是它具有相当强的表达能力。有的人工智能专家坚信所有的人工智能中的知识表示问题完全可以在一阶逻辑的框架中得以实现。一阶逻辑在表达不确定性知识时其表达能力也是很强的。例如，xP(x)表达在所考虑的论域中存在一个具有性质P的对象，而具体的是哪一个对象具有此性质则是待确定的；再如，PQ表示P和Q这两个性质之间有一个是成立的，至于到底是哪一个成立则是根据具体的情况而定的。2020/4/1史忠植高级人工智能7关于知识的表示与推理有人坚信从本质上看,一阶逻辑对于知识表示是足够的,但从实际应用的角度看,为方便、清楚和简洁起见,知识表示不一定非得从一阶逻辑出发。事实上，人们从实际应用出发已经发明和建立了许多适用于不同目的的逻辑系统。(1)为了表示关于认知的有关概念，如相信、知道、愿望、意图、目标、承诺等等，人们引进了刻划各种认知概念的模态逻辑；(2)为了刻划智能系统中的时间因素，人们在逻辑系统中引进时间的概念，提出了各种时序逻辑；2020/4/1史忠植高级人工智能8关于知识的表示与推理(3)为了描述各种不确定的和不精确的概念，人们引进了所谓模糊逻辑；模糊逻辑是直接建立在自然语言上的逻辑系统，与其它逻辑系统相比较，它考虑了更多的自然语言的成分。按照其创始人Zadeh的说法就是词语上的计算，表示为一个公式,即，fuzzylogic＝computingwithwords；(4)人类的知识与人类的活动是息息相关的，人类正是在各种活动和行为中获得知识的。因此，行为或者动作的概念在智能系统中是一个关键的概念。动作的概念与一般逻辑中的静态的概念很不相同，它是一个动态的概念，动作的发生影响着智能系统的性质。对于动作的考虑，给人工智能界带来了许多难题，如框架问题、量词问题等等。为了刻划动作的概念，人们引进了一些新的逻辑体系来刻划它。2020/4/1史忠植高级人工智能9关于知识的表示与推理(5)计算机对于人类进行决策时进行若干方面的支持已经成为计算机应用的一个重要方面。人类在决策时，对于各种方案和目标有一定的偏好和选择。这时“偏爱”就成为了一个基本的概念。为了表述和模拟人类在决策时的选择的规律和行为，对于“偏爱”这个词的研究就是不可避免的。于是，基于管理科学的所谓的偏爱逻辑被提出并加以研究。(6)时间是智能系统中最重要的几个概念之一。人类使用各类副词来对时间概念加以描述。例如，“一会儿”“相当长”“断断续续地”“偶尔”等等,这一类词在我们的日常生活中比比皆是。含有这些词的句子显然是很难用经典的时序逻辑来刻划的,于是有人引进了一种逻辑系统专门刻划这类句子。其基本思想是利用数学中积分的思想，通过对时间的某种像积分那样的表示和运算来形式化这些句子。2020/4/1史忠植高级人工智能10逻辑系统一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：•逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号；•非逻辑符号集合：不同的逻辑理论中出现的不同的符号；•语句规则：定义什么样的符号串是有意义的；•证明：什么样的符号串是一个合理的证明；•语义规则：定义符号串的语义。2020/4/1史忠植高级人工智能11逻辑程序语言逻辑符号保留字或者符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的语句规则推理规则、公理和证明没有逻辑与程序语言的对比2020/4/1史忠植高级人工智能12在语法上，如果存在一个从假设到的证明，则记为⊢，称由可推导出的，或可证明的。是可推导出的，则记为⊢，称为可证明的。是不协调的，如果存在一个语句使得和的否定均可由推导得出。一致的，或相容的(consistent)，如果不存在逻辑系统的公式A，使得⊢A与⊢¬A同时成立。证明(语法)2020/4/1史忠植高级人工智能13一个证明是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。逻辑公理和推理规则的集合。推理规则是可以从一个语句的集合得到另一语句的集合。公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。2020/4/1史忠植高级人工智能14语言的解释是在某个论语(domain)中定义非逻辑符号。语句的语义是在解释下定义出语言L的真假值。I是L的一个解释，且在I中为真，则记为I⊨，称作I满足，或者I是的一个模型。和一个语句，如果对每个解释I，有I⊨蕴含I⊨，换言之，如果I是的一个模型则I也是的一个模型，则记为⊨，我们称为的一个逻辑结果。解释(语义)2020/4/1史忠植高级人工智能15可靠性(reliable)一个逻辑是可靠的，如果它的证明保持真假值，即在任何解释I下，如果I是的模型，且可由推导出，则I也是的一个模型。即，一个逻辑是可靠的，如果对任何语句集合和语句，⊢蕴涵⊨。可靠性和完备性完备性(complete)一个逻辑是完备的，如果任何永真语句是可证的。即，对任何语句集合和语句，⊨蕴涵⊢。如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。Gődel完备性定理：一阶逻辑是完备的2020/4/1史忠植高级人工智能16可判定的可判定的(decidable)，如果存在一个算法对逻辑中的任一公式A，可确定⊢A是否成立。否则，称为是不可判定的(undecidable)。对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。可判定性一阶逻辑是不可判定的，但它是半可判定的。哲学逻辑手册1983-89年间出版了4卷本哲学逻辑手册(HandbookofPhilosophicalLogic)2001年开始出版第2版，约为18卷，迄今已经出版12卷。该书由英国伦敦皇家学院计算机系的多夫·加贝（DovM.Gabbay）教授和德国路德维希-麦克米兰大学信息与语言处理中心的冈瑟（F.Guenthner）教授共同主编。已经出版的前12卷内容高阶逻辑冲突多值逻辑模糊逻辑概率论条件句模态逻辑动态逻辑容错逻辑优先逻辑图形逻辑偏逻辑直觉主义逻辑非单调推理信念逻辑自由逻辑时序逻辑相干逻辑量子逻辑蕴涵逻辑时态逻辑问题逻辑道义逻辑弗协调逻辑目标导向演绎认知逻辑加标演绎系统（逻辑新框架理论）等现代逻辑学与计算机科学、计算语言学和人工智能的关系表逻辑自然语程序人工逻辑指令与直数据库复杂性智能体未来展望言处理控制智能编程陈式语言理论理论理论时序逻辑√√√√√√√√广泛应用模态逻辑√√√√√√√√非常活跃算法证明√√√√√√√√非单调推理√√√√√√√意义重大概率和模糊√√√√√√√目前主流直觉主义逻辑√√√√√√√√主要替代者高阶逻辑，λ-演算√√√√√√更具中心作用经典逻辑片断√√√√√√前景诱人资源和子结构逻辑√√√√纤维化和组合逻辑√√√√√√可自我指称谬误理论在适当语境逻辑动力学√√动态逻辑观论辩理论游戏√前景光明对象层次/元层次√√总起中心作用机制:溯因缺省相干√√逻辑的一部分与神经网络的联系极重要，刚开始时间-行动-修正模型√√一类新模型加标演绎系统√√√√√逻辑学的统一框架2020/4/1史忠植高级人工智能20命题逻辑•命题是可以确定其真假的陈述句。•Bolle提出了布尔代数。语言:¬，；公式，原子公式公理模式:◆(A(BA))◆((A(BC))((AB)(AC)))◆(((¬A))(¬B)(BA))推理规则:分离规则(modusponens，MP规则)BBAA,2020/4/1史忠植高级人工智能21谓词逻辑(一阶逻辑)•Frege谓词演算语言:¬，，，，(，)；常元，变元，函词，谓词；公式公理模式:◆(A(BA))◆((A(BC))((AB)(AC)))◆(((¬A)(¬B))(BA))◆vAAtv(t对A中变元v可代入)◆v(AB)(vAvB)◆AvA(v在A中无自由出现)推理规则:分离规则BBAA,2020/4/1史忠植高级人工智能22谓词逻辑与命题逻辑的区别谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；它引入了“推广”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。2020/4/1史忠植高级人工智能23逻辑程序设计•消解原理(归结原理)•Horn逻辑•Prolog逻辑程序设计语言2020/4/1史忠植高级人工智能24归结原理例：C1=¬P∨Q∨RC2=P∨Q则C1与C2消解后的结果为：Q∨R若子句集S能导出空子句⊓(有否证)，则称S是不可满足的。S⊢AiffS¬A⊢⊓QQPP,QQPP,2020/4/1史忠植高级人工智能25Horn逻辑•文字：原子公式(正文字)或原子公式的否定(负文字)。P,Q,¬R•子句：若干文字的析取。¬P∨Q∨R•Horn子句：L1∨L2∨…∨Ln中如果至多只含一个正文字，那么该子句称为Horn子句。Horn子句P∨¬Q1∨¬Q2∨…∨¬Qn通常表示为：PQ1,Q2,…,Qn2020/4/1史忠植高级人工智能26Horn子句的类型：◆过程：PQ1,Q2,…,Qn◆事实：P◆目标：Q1,Q2,…,Qn◆空子句：⊓例:◆过程：AT(dog,x)AT(Zhang,x)◆事实：AT(Zhang,train)◆目标：AT(dog,train)首先目标中过程调用AT(dog,train)与过程名AT(dog,x)匹配，合一为{train/x}，调用过程AT(Zhang,x)，从而产生新目标AT(Zhang,train)，与事实匹配，产生目标⊓。因而调用成功，输出“是”。2020/4/1史忠植高级人工智能27Prolog•Prolog(Programminginlogic)语言是以Horn子句逻辑为基础的高级程序设计语言。•1972年，法国马赛大学的Alain.Colmerauer提出了Prolog的雏型。•1975年，Prolog被用于问题求解系统。•此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。2020/4/1史忠植高级人工智能28Prolog的构成•事实：