1、高级人工智能,第二章 人工智能逻辑,2.1 重要的形式工具-逻辑2.2 非单调逻辑 2.3 默认逻辑 2.4 限定逻辑 2.5 自认知逻辑 2.6 真值维护系统2.7 情景演算的逻辑基础 2.8 动态描述逻辑,逻辑的历史,Aristotle逻辑学Leibnitz数理逻辑Gottlob Frege(1848-1925)一阶谓词演算系统,符号论20世纪30年代，数理逻辑广泛发展,重要的形式工具逻辑,在本世纪30年代以后，数学方法广泛渗透与运用于数理逻辑，使得数理逻辑成为数学领域中与代数、几何等并列的学科之一。现代数理逻辑可以分为逻辑运算、证明论、公理集合论、递归论和模型论。,关于知识的表示与推理,
2、智能行为的基础是知识，尤其是所谓的常识性知识。人类的智能行为对于知识的依赖主要表现在对于知识的利用，即利用已经具有的知识进行分析、猜测、判断、预测等等。人类利用知识可以预测未来，由已知的情况推测未知的情况、由发生的事件预测还未发生的事件等等。但是，当人们希望计算机具有智能行为时，除了告诉计算机如何像人一样地利用知识以外（对于知识进行推理），一个更为基础和先行的工作是如何使计算机具有知识（对于知识进行表示），即在计算机上如何表达人类的知识。,关于知识的表示与推理,多数的基于逻辑的智能系统使用一阶逻辑或者它的一些扩张形式。一阶逻辑的优点是它具有相当强的表达能力。有的人工智能专家坚信所有的人工智能中
3、的知识表示问题完全可以在一阶逻辑的框架中得以实现。一阶逻辑在表达不确定性知识时其表达能力也是很强的。例如，x P(x)表达在所考虑的论域中存在一个具有性质P的对象，而具体的是哪一个对象具有此性质则是待确定的；再如，P Q表示P和Q这两个性质之间有一个是成立的，至于到底是哪一个成立则是根据具体的情况而定的。,关于知识的表示与推理,有人坚信从本质上看,一阶逻辑对于知识表示 是足够的,但从实际应用的角度看,为方便、清楚和简洁起见,知识表示不一定非得从一阶逻辑出发。事实上，人们从实际应用出发已经发明和建立了许多适用于不同目的的逻辑系统。(1)为了表示关于认知的有关概念，如相信、知道、愿望、意图、目标、
4、承诺等等，人们引进了刻划各种认知概念的模态逻辑；(2)为了刻划智能系统中的时间因素，人们在逻辑系统中引进时间的概念，提出了各种时序逻辑；,关于知识的表示与推理,(3)为了描述各种不确定的和不精确的概念，人们引进了所谓模糊逻辑；模糊逻辑是直接建立在自然语言上的逻辑系统，与其它逻辑系统相比较，它考虑了更多的自然语言的成分。按照其创始人Zadeh的说法就是词语上的计算，表示为一个公式,即，fuzzy logiccomputing with words；(4)人类的知识与人类的活动是息息相关的，人类正是在各种活动和行为中获得知识的。因此，行为或者动作的概念在智能系统中是一个关键的概念。动作的概念与一般
5、逻辑中的静态的概念很不相同，它是一个动态的概念，动作的发生影响着智能系统的性质。对于动作的考虑，给人工智能界带来了许多难题，如框架问题、量词问题等等。为了刻划动作的概念，人们引进了一些新的逻辑体系来刻划它。,关于知识的表示与推理,(5)计算机对于人类进行决策时进行若干方面的支持已经成为计算机应用的一个重要方面。人类在决策时，对于各种方案和目标有一定的偏好和选择。这时“偏爱”就成为了一个基本的概念。为了表述和模拟人类在决策时的选择的规律和行为，对于“偏爱”这个词的研究就是不可避免的。于是，基于管理科学的所谓的偏爱逻辑被提出并加以研究。(6)时间是智能系统中最重要的几个概念之一。人类使用各类副词来
6、对时间概念加以描述。例如，“一会儿”“相当长”“断断续续地”“偶尔”等等,这一类词在我们的日常生活中比比皆是。含有这些词的句子显然是很难用经典的时序逻辑来刻划的,于是有人引进了一种逻辑系统专门刻划这类句子。其基本思想是利用数学中积分的思想，通过对时间的某种像积分那样的表示和运算来形式化这些句子。,逻辑系统,一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号；非逻辑符号集合：不同的逻辑理论中出现的不同的符号；语句规则：定义什么样的符号串是有意义的；证明：什么样的符号串是一个合理的证明；语义规则：
7、定义符号串的语义。,逻辑与程序语言的对比,在语法上，如果存在一个从假设到的证明，则记为，称由可推导出的，或可证明的。如果在没有任何假设下是可推导出的，则记为，称为可证明的。称一个假设是不协调的，如果存在一个语句使得和的否定均可由推导得出。称一个逻辑系统是一致的，或相容的(consistent)，如果不存在逻辑系统的公式A，使得A与A同时成立。,证 明(语法),一个证明是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。在公理化逻辑中，逻辑给出一个逻辑公理和推理规则的集合。推理规则是可以从一个语句的集合得到另一语句的集合。公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻
8、辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。,证明,语言的解释是在某个论语(domain)中定义非逻辑符号。语句的语义是在解释下定义出语言L的真假值。如果I是L的一个解释，且在I中为真，则记为I，称作I满足，或者I 是的一个模型。类似地，给定一个语句和一个语句，如果对每个解释I，有I 蕴含I，换言之，如果I 是的一个模型则I也是的一个模型，则记为，我们称为的一个逻辑结果。,解 释(语义),可靠性(reliable)一个逻辑是可靠的，如果它的证明保持真假值，即在任何解释I下，如果I是 的模型，且可由推导出，则I也是的一个模型。即，一个逻辑是可靠的，如果对任何语句集合和语句，蕴涵
9、。,可靠性和完备性,完备性(complete)一个逻辑是完备的，如果任何永真语句是可证的。即，对任何语句集合和语句，蕴涵。如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。Gdel完备性定理：一阶逻辑是完备的,可判定的一个逻辑称为是可判定的(decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定 A是否成立。否则，称为是不可判定的(undecidable)。如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。,可判定性,一阶逻辑是不可判定的，但它是半可判定的。,哲学逻辑手
10、册1983-89年间出版了4卷本 哲学逻辑手册(Handbook of Philosophical Logic)2001年开始出版第 2版，约为18卷，迄今已经出版12卷。该书由英国伦敦皇家学院计算机系的多夫加贝（Dov M.Gabbay）教授和德国路德维希-麦克米兰大学信息与语言处理中心的冈瑟（F.Guenthner）教授共同主编。,已经出版的前12卷内容 高阶逻辑 冲突 多值逻辑 模糊逻辑 概率论 条件句 模态逻辑 动态逻辑 容错逻辑 优先逻辑 图形逻辑 偏逻辑 直觉主义逻辑 非单调推理 信念逻辑 自由逻辑 时序逻辑 相干逻辑 量子逻辑 蕴涵逻辑 时态逻辑 问题逻辑 道义逻辑 弗协调逻辑
11、目标导向演绎 认知逻辑 加标演绎系统（逻辑新框架理论）等,现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻 辑 自然语 程序 人工 逻辑 指令与直 数据库 复杂性 智能体 未 来 展 望 言处理 控制 智能 编程 陈式语言 理论 理论 理论时序逻辑 广泛应用模态逻辑 非常活跃算法证明 非单调推理 意义重大概率和模糊 目前主流直觉主义逻辑 主要替代者高阶逻辑，-演算 更具中心作用经典逻辑片断 前景诱人资源和子结构逻辑 纤维化和组合逻辑 可自我指称谬误理论 在适当语境逻辑动力学 动态逻辑观论辩理论游戏 前景光明对象层次/元层次 总起中心作用机制:溯因 缺省 相干 逻辑的一部分与神经网络的联
12、系 极重要，刚开始时间-行动-修正模型 一类新模型加标演绎系统 逻辑学的统一框架,命题逻辑,命题是可以确定其真假的陈述句。Bolle提出了布尔代数。语言:，；公式，原子公式公理模式:(A(B A)(A(B C)(A B)(A C)(A)(B)(B A)推理规则:分离规则(modus ponens，MP规则),谓词逻辑(一阶逻辑),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中无自由出现)推理规则:分离规则,谓词逻辑与命题
13、逻辑的区别谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；它引入了“推广”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。,逻辑程序设计,消解原理(归结原理)Horn逻辑Prolog逻辑程序设计语言,归结原理,例：C1=PQR C2=PQ则C1与C2消解后的结果为：QR若子句集S能导出空子句(有否证)，则称S是不可满足的。反证法：S A iff S A,Horn逻辑,文字：原子公式(正文字)或原子公式的否定(负文字)。P,Q,R子句：若干文字的析取。PQRHorn子句：子句L1L2 Ln中如果至多只
14、含一个正文字，那么该子句称为Horn子句。Horn子句P Q1 Q2 Qn通常表示为：P Q1,Q2,Qn,Horn子句的类型：过程：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)，与事实匹配，产生目标。因而调用成功，输出“是”。,Prolog,Prolog(Programming i
15、n logic)语言是以Horn子句逻辑为基础的高级程序设计语言。1972年，法国马赛大学的Alain.Colmerauer提出了Prolog的雏型。1975年，Prolog被用于问题求解系统。此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。,Prolog的构成,事实：关于对象性质和关系的事实语句；student(john)，married(tom,mary)规则：关于对象性质和关系的定义规则语句；它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。B:A“如果A则B”bird(x):animal(x)，
16、has(x,feather)问题：关于对象性质或关系的询问。?student(john)?married(mary，x),Prolog语言的基本文法,Prolog语言的最基本语言成分是项(term)，一个项或者是常量，或者是变量，或者是一个结构。常量：是指对象和对象之间的特定关系的名；整数，如0，22，1586等；原子，如John，student，likes，sister-of变量：表示任意的对象，它与FOL中的变元相同；Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如X,Y,Answer,_value等。结构：是常量和变量的序列，它由一个函子(函词或谓词)和该函子的自变量
17、所组成。如：likes(john,X)married(mary,jack),例：(1)likes(bell,sports)(2)likes(mary,smith)(3)likes(mary,sports)(4)likes(jones,smith)(5)friend(john,X):likes(X,sports),likes(X,smith)(规则)(6)?friends(john,Y)(问题),(事实),(7)?likes(X,sports),likes(X,smith),(8)?likes(bell,smith)(bell/X),(7)?likes(X,sports),likes(X,smi
18、th),(8)?likes(mary,smith)(mary/X),Y=mary，John与Mary是朋友,Prolog的执行方式,搜索：在程序中自上而下地搜索事实和规则；匹配：将目标中的项与事实和规则进行匹配；回溯：当目标中一项失败时，如果目标中有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。,Prolog的基本特点,Horn子句逻辑是Prolog的基础。Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。Prolog完全
19、依靠匹配、回溯来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。Prolog也使用元语言种的谓词，有很强的描述能力。Prolog采用统一的数据结构项，它包含控制成分，且有专门进行数值计算和符号处理的模块。,逻辑程序设计,PROLOG B A1,An B?A1,An,单调逻辑,在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。A，AB B推理系统的定理集合随着推理过程的进行而单调地增大。单调性：(1)Th()(2)若 1 2，则Th(1)Th(2)(3)Th(Th()Th()(不动点),非单调逻辑,推理系统的定理集合并不随着推理过程的进行而单调地增大，新推
20、出地定理很可能会否定、改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。新规则：(4)P(不动点),非单调逻辑,推理系统的定理集合并不随推理过程的进行而单调地增大,新推出的定理很可能会否定、改变原来的一些定理,使得原来能够解释的某些现象变得不能解释了。,非单调逻辑,推理系统的定理集合并不随推理过程的进行而单调地增大,新推出的定理很可能会否定、改变原来的一些定理,使得原来能够解释的某些现象变得不能解释了。t1t2 F(t1)F(t2),非单调逻辑,鸟会飞 鸵鸟是鸟 所以,鸵鸟会飞,非单调推理,1 John在时刻t1是活着的2 Dell在时刻t2t1把子弹装进枪膛3 Dell在时刻t3
21、t2举枪对John射击4 问题：John在时刻t4t3还是活着吗？,非单调逻辑,设表示推理规则集,则单调逻辑语言Th()=A|A(1)Th()(2)if 1 2,then Th(1)Th(2)(3)Th(Th()=Th()(不动点)(4)if P,then MP 其中M模态词,默认逻辑,1980年，Reiter提出了默认缺省逻辑(Default Logic)。“一般情况下鸟是会飞的”“鸵鸟不会飞”“企鹅不会飞”,默认规则,一个默认规则是如下形式的规则：,(x):称为前提条件i(x):称为缺省条件，或检验条件(x):称为结论为简便，通常情况下可以省略检验条件中的M。规则的使用：如果规则的前提条件
22、满足，且现有的知识导不出检验条件的否定i(x)，则可以得出结论成立。,默认理论,一个默认理论由两个部分组成，即默认规则集D和公式集W，一般用二元组来表示 若D中的规则是闭规则时，则为闭缺省理论。,定义：设 为一闭缺省理论，为关于D的一个算子，作用于任意的命题集合S，而其值为满足下列三个性质的最小命题集合(S)：(1)W(S)(2)Th(S)=(S)，其中Th(S)=A|(S)A(3)如果D中有规则，且(S)，1,m S，那么(S),默认理论的扩充,定义：对命题集合E，如果(E)=E，则E称为关于D的算子的不动点(fixpoint)。此时称E为默认理论 的一个扩充(extension)。,例1：
23、设D，W，计算默认理论 的扩充。,有唯一的扩充E Th(B,F)。,例2：设D，W B,CFA,AC E，计算默认理论 的扩充。,有三个扩充E1 Th(WA,C)E2 Th(WA,E)E3 Th(WC,E,G),封闭默认理论的扩展,设封闭默认理论=,为关于D的一个算符，作用于任意的命题集合S，其值为满足下列三个性质的最小命题集合(S):(1)W(S);(2)Th(S)=(S);这里，Th(S)为命题集A|(S)A;(3)如果有默认规则,封闭默认理论的扩展,命题集合E称为关于D的算符的固定点，如果(E)=E,此时又称E为=$的一个扩充。有了扩充的概念，便可定义非单调的“推出”概念。如果命题A包含
24、在默认理论 的一个扩充中，那么称A在 中可推出，记为|。扩充 E必须 含有所有的已知事实;在关系|下是封闭的;其前提被 E满足,默认条件与 E相容的任意默认的结论必须也在E中。,封闭默认理论的扩展,具有扩展的存在条件将显得十分重要。下面我们讨论三种情况。(1)不含任何默认的理论:这种理论退化到一阶逻辑理论,在这里它虽有唯一的一个扩展Th(W),但对默认推理毫无意义和作用。(2)一个默认理论 称为规范默认理论，如果D中默认规则均有如下形式:,封闭默认理论的扩展,如果一个理论中的所有默认都是规范的,则该理论称为规范理论。由于每个规范默认的结论与其合理条件相同,因而这种缺省不会导致不一致性,不会证伪
25、其它已用过的默认的合理条件。因此我们说规范默认理论是行为良好(well-behaved)的理论,并且可以证明:任何规范默认理论必定至少有一个扩充。,封闭默认理论的扩展,(3)半规范默认理论(Seminormal Default Theory):虽然规范默认理论至少有一个扩充,从而保证了系统知识库 W的一致性。然而现实世界中许多事物、现象是无法用规范默认表示的,而用如下形式的默认则可有效地进行处理:,封闭默认理论的扩展,为了保证半规范默认理论具有一个扩充,必须对它的默认加以限制,Reiter给出了一个半规范默认理论至少具有一个扩充的充分条件,这个条件要求封闭的半规范默认理论是有序的.。有序性建立
26、在一个偏序关系上,这个偏序要求:如果在推导的过程中用到了,则。Etheringthon在这种基础上给出了求算偏序关系及其扩充的算法,并讨论了算法的收敛性问题。,限定推理,1980年，McCarthy提出了一种非单调的推理限定推理(Circumscription)。基本思想：从某些事实A出发能够推出具有某一性质的P的对象就是满足性质P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。,限定逻辑,限定逻辑CIRC是一种极小化逻辑。下面，从一个基于极小模型定义的命题限定出发，给出限定的基本定义,进而给出一阶限定的基本结果，并将它推广。定义 2.1 设L0是一个命题语言，p1,p2是在命题
27、语言L0 中的两个赋值。称p1小于p2，记为p1 p2,当且仅当对任一命题变元x,如果p1(x)=l,则p2(x)=l。,限定逻辑,定义 2.2 设A 是一个公式，称A的一个赋值p是极小的，当且仅当不存在A的其它赋值p使得 p p。显然,是一个偏序关系。p1 p2表示p1包含的真命题比p2 少。极小赋值包含的真命题极小。定义 2.3 极小后承M。设A,B是两个公式，A M B 当且仅当B在所有A 的极小模型中都为真。极小模型是非单调的，它以命题的极小化作为优先模型的准则。,限定逻辑,定义 2.4 设A是一个包含命题集 P=p1,p2,.,pn 的公式，一个A的赋值p称为 Z-极小赋值，当且仅当
28、不存在A的其它赋值p使得p p,定义如下：设p1,p2 是两个赋值，p1 Z-p2 当且仅当对任一z Z,若p1(Z)=l,则 p2(Z)=l。,限定逻辑,定义 2.5 命题限定P 或 CIRC(A,P)。设A是一个包含命题集的公式，是一个公式，A P 当且仅当 在所有A的 p-极小赋值中都为真。定理 2.1 A p 当且仅当A P,限定逻辑,定义 2.6 令L是一个一阶语言，T是一个L的公式，它包含谓词元组集。设MT和 M*T是公式T的两个模型。定义M*T优先于MT,记为M*T MT，当且仅当(1)M和M*有相同的对象域，(2)除外，公式T中所有的其它关系和函数常数在M和M*都有相同的解释，
29、(3)在M*中的外延是在M中的子集。,限定逻辑,一个理论T的模型M称为优先的，当且仅当不存在T的其它模型M使得M M。定义 2.7 Mm是的最小模型，当且仅当 M Mm,M=Mm,限定逻辑,例如 设论域 D=1,2 T=xy(P(y)Q(x,y)=(P(1)Q(1,1)(P(2)Q(1,2)(P(1)Q(2,1)(P(2)Q(2,2)M:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)T T F T F TM*:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)F T F T F T,自认知逻辑,Moore 考虑自认知理论 T 对于一组初始前提A 是可靠的，当且仅
30、当T 中的每一个自认知解释器是一个T 中的自认知模型，其中全部A 的公式为真。一个理想的理性主体的信念必须满足下列条件：(1)设 P1,.,Pn T,and P1,.,Pn Q,则 Q T。(2)设 P T,则 BP T。(3)设 P T,则 BP T。,自认知逻辑,在这种情况下，主体不能再得到更进一步的结论，因此，Moore称上述理论为稳定自认知理论。当然，下列条件也成立：(4)如果 BP T,则 P T。(5)如果 BP T,则 P T。,真值维护系统TMS,1979年，Doyle提出了一种非单调推理系统真值维护系统(Truth Maintenance System)真值维护系统是大型推理
31、系统的的一个子系统，实现知识库中信念(belief)的修改与维护。其基本问题有：必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。,基本数据结构:结点：表示信念理由：表示信念的原因信念既包括已知的知识，也包括假设的知识。,基本操作：新结点的形成将信念赋予该结点；新理由的加入把某个信念与该结点联接起来,实现过程：默认假设的形成；相关性回溯过程。,信念知识表示,每一个命题或规则均称为结点，它分为两类：IN-结点：相信为真OUT-结点：不相信为真，或无理由相信为真，或当前没有任何有效的理由。,每个结点附有理由表
32、，表示具体结点的有效性：支持表SL：所在结点的信念的原因，理由；条件证明CP：出现矛盾的原因。,(SL()()IN-结点表中的IN-结点表示知识库中的已知知识;OUT-结点表中的OUT-结点表示这些结点的否定。例1:(1)现在是夏天(SL()()(2)天气很潮湿(SL(1)()结点(1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提;结点(2)则依赖于当前结点(1)的信念.所以，与一阶逻辑不同的是,TMS可以撤消前提,并可以对知识库作适当修改.,（1）支持表SL,例2:(1)现在是夏天(SL()()(2)天气很潮湿(SL(1)(3)(3)天气很干燥若结点(1)是IN,结点(3
33、)是OUT,则结点(2)才为IN.若在某个时刻出现结点(3)的证据,则结点(2)就变为OUT,因为它不再有一个有效的证实.象结点(2)这样的结点称为假设,它与非空的OUT结点表的SL证实有关.OUT结点(3)是结点(2)的证实的一部分.但如果结点(3)不存在,就不能这样表示了.在TMS中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实.,(CP)如果结论结点为IN-结点,以及下列条件成立:(1)IN假设中的每个结点都是IN-结点;(2)OUT-假设中的每个结点都是OUT-结点.那么条件证明CP是有效的.一般说来,OUT-假设总是空集.TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设.通常只要在IN-假设中的结点为IN,OUT-假设中的结点为OUT,则结论结点为IN.,（2）条件证明CP,默认假设,令F1,F2,Fn表示所有可能的侯选的默认假设结点
