人工智能逻辑PPT课件

1、人工智能逻辑人工智能逻辑中国科学院计算技术研究所中国科学院计算技术研究所智能信息处理重点实验室智能信息处理重点实验室主要内容主要内容逻辑简介逻辑程序设计非单调逻辑缺省逻辑限定逻辑真值维护系统情景演算1. 逻辑简介逻辑简介逻辑的历史逻辑系统命题逻辑谓词逻辑1.1 逻辑的历史Aristotle逻辑学Leibnitz数理逻辑Gottlob Frege (1848-1925)一阶谓词演算系统,符号论20世纪30年代，数理逻辑广泛发展1.2 逻辑系统一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：逻辑符号集合逻辑符号集合：在所有该逻辑的逻辑理论中均出

2、现的符号；非逻辑符号集合非逻辑符号集合：不同的逻辑理论中出现的不同的符号；语句规则语句规则：定义什么样的符号串是有意义的；证明证明：什么样的符号串是一个合理的证明；语义规则语义规则：定义符号串的语义。逻辑逻辑程序语言程序语言逻辑符号保留字或者符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的语句规则推理规则、公理和证明没有逻辑与程序语言的对比 一个证明证明是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。 在公理化逻辑中，逻辑给出一个逻辑公理逻辑公理和推理推理规则规则的集合。推理规则是可以从一个语句的集合得到另一语句的集合。

3、公理化逻辑中的证明就是一个语句序列，使得公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，其中的每个语句要么是逻辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。要么是由前面的语句通过推理规则得到的。证 明 在语法上，如果存在一个从假设到的证明，则记为 ，称由可推导出的，或可证明的可证明的。如果在没有任何假设下是可推导出的，则记为 ，称为可证明的。 称一个假设是不协调的不协调的，如果存在一个语句使得和的否定均可由推导得出。 称一个逻辑系统是一致的一致的，或相容的相容的(consistent)，如果不存在逻辑系统的公式A，使得A与A同时成立。证 明

4、(语法) 语言的解释解释是在某个论语(domain)中定义非逻辑符号。语句的语义是在解释下定义出语言L的真假值。如果I是L的一个解释，且在I中为真，则记为I ，称作I满足 ，或者I 是的一个模型模型。 类似地，给定一个语句和一个语句 ，如果对每个解释I ，有I 蕴含I ，换言之，如果I 是的一个模型则I也是的一个模型，则记为 ，我们称为的一个逻辑结果逻辑结果。解 释(语义)可靠性可靠性(reliable)一个逻辑是可靠的，如果它的证明保持真假值，即在任何解释I下，如果I是 的模型，且可由推导出，则I也是的一个模型。即，一个逻辑是可靠的，如果对任何语句集合和语句 ， 蕴涵 。可靠性和完备性完备性

5、完备性(complete)一个逻辑是完备的，如果任何永真语句是可证的。即，对任何语句集合和语句 ， 蕴涵 。如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。G Gdeldel完备性定理：完备性定理：一阶逻辑是完备的一阶逻辑是完备的可判定的可判定的一个逻辑称为是可判定的可判定的(decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定 A是否成立。否则，称为是不可判定的不可判定的(undecidable) 。如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的半可判定的。可判

6、定性一阶逻辑是不可判定的，但它是半可判定的。一阶逻辑是不可判定的，但它是半可判定的。1.3 命题逻辑命题是可以确定其真假的陈述句。Bolle提出了布尔代数。语言语言: ，；公式，原子公式公理模式公理模式: :(A (B A)(A (B C) (A B) (A C)(A)(B) (B A)推理规则推理规则: :分离规则(modus ponens，MP规则)BBAA,1.4 谓词逻辑(一阶逻辑)Frege谓词演算语言语言: ，(，)；常元，变元，函词，谓词；公式公理模式公理模式: :(A (B A)(A (B C) (A B) (A C)(A)(B) (B A)vA Atv (t对A中变元v可代入

7、)v(A B) (vA vB)A vA (v在A中无自由出现)推理规则推理规则: :分离规则BBAA,谓词逻辑与命题逻辑的区别谓词逻辑与命题逻辑的区别谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；它引入了“推广”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。2. 2. 逻辑程序设计逻辑程序设计消解原理(归结原理)Horn逻辑Prolog逻辑程序设计语言2.1 消解原理消解原理例： C1 = PQR C2 = PQ则C1与C2消解后的结果为：QR若子句集S能导出空子句 (有否证)，则称S是不可满足

8、的。反证法： S A iff S A QQPP,QQPP,2.2 Horn逻辑文字文字：原子公式(正文字)或原子公式的否定(负文字)。P, Q, R子句子句：若干文字的析取。PQRHorn子句子句：子句L1L2 Ln中如果至多只含一个正文字，那么该子句称为Horn子句。Horn子句P Q1 Q2 Qn通常表示为：P Q1, Q2, , QnHornHorn子句的类型：子句的类型： 过程：P Q1, Q2, , Qn 事实： P 目标： Q1, Q2, , Qn 空子句： 例例: : 过程：AT(dog, x) AT(Zhang, x) 事实：AT(Zhang, train) 目标： AT(do

9、g, train) 首先目标中过程调用AT(dog, train)与过程名AT(dog, x)匹配，合一为train/x，调用过程AT(Zhang, x)，从而产生新目标 AT(Zhang, train)，与事实匹配，产生目标 。因而调用成功，输出“是”。2.3 PrologProlog(Programming in logic)语言是以Horn子句逻辑为基础的高级程序设计语言。1972年，法国马赛大学的Alain. Colmerauer提出了Prolog的雏型。1975年，Prolog被用于问题求解系统。此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划

10、生成等领域。Prolog的构成的构成事实：关于对象性质和关系的事实语句；student(john)，married(tom,mary)规则：关于对象性质和关系的定义规则语句；它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。B: A“如果A则B”bird(x) : animal(x)，has(x, feather)问题：关于对象性质或关系的询问。? student(john)? married(mary，x)Prolog的执行方式的执行方式搜索：在程序中自上而下地搜索事实和规则；匹配：将目标中的项与事实和规则进行匹配；回溯：当目标中一项失败时，如果目标中

11、有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。Prolog语言的基本文法语言的基本文法Prolog语言的最基本语言成分是项(term)，一个项或者是常量，或者是变量，或者是一个结构。常量：是指对象和对象之间的特定关系的名；整数整数，如0，22，1586等；原子原子，如John，student，likes，sister-of变量：表示任意的对象，它与FOL中的变元相同；Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如X, Y, Answer, _value等。结构：是常量和变量的序列，它由一个函子(函词或谓词)和该函子的自变量所组

12、成。如：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)? li

13、kes(X, sports), likes(X, smith)(8)? likes(mary, smith) (mary / X)Y = mary，John与与Mary是朋友是朋友Prolog的基本特点的基本特点Horn子句逻辑是Prolog的基础。Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。Prolog完全依靠匹配、回溯来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。Prolog也使用元语言种的谓词，有很强的描述能力。Prolog采用统一的数据结

14、构项，它包含控制成分，且有专门进行数值计算和符号处理的模块。3. 非单调逻辑非单调逻辑单调逻辑非单调逻辑区别3.1 单调逻辑在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。A，AB B推理系统的定理集合随着推理过程的进行而单调地增大。单调性：单调性：(1) Th( )(2) 若 1 2 ，则Th(1) Th(2)(3) Th(Th( ) Th( ) (不动点)3.2 非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出地定理很可能会否定、改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。新规则：(4) P (不动点)4. . 缺省逻

15、辑缺省逻辑1980年，Reiter提出了缺省逻辑(Default Logic)。“一般情况下鸟是会飞的”“鸵鸟不会飞” “企鹅不会飞”)()(: )(xflyxMflyxBird会飞会飞”与系统不矛盾“是鸟xxx:4.1 缺省规则一个缺省规则是如下形式的规则：)()(,),(: )(1xxMxMxn(x):称为前提条件i(x):称为缺省条件，或检验条件 (x):称为结论为简便，通常情况下可以省略检验条件中的M。规则的使用：规则的使用：如果规则的前提条件满足，且现有的知识导不出检验条件的否定i(x)，则可以得出结论成立。4.2 缺省理论一个缺省理论由两个部分组成，即缺省规则集D和公式集W，一般用

16、二元组来表示 若D中的规则是闭规则时，则为闭缺省理论。定义：设 为一闭缺省理论， 为关于关于D的的一个算子一个算子，作用于任意的命题集合S，而其值为满足下列三个性质的最小命题集合(S)：(1) W (S)(2) Th(S) = (S)，其中Th(S) = A|(S) A(3) 如果D中有规则 ，且(S)，1, , m S ，那么(S)nMM,:14.3 缺省理论的扩充定义：对命题集合E，如果(E) = E，则E称为关于D的算子的不动点(fixpoint)。此时称E为缺省理论 的一个扩充(extension)。例1：设D ，W ，计算缺省理论 的扩充。FCCBBA:,:,: 有唯一的扩充E Th

17、(B, F)。例2：设D ，W B, CFA, AC E，计算缺省理论 的扩充。GAFAECEEAFCCBAA,:,:,:,: 有三个扩充E1 Th(WA, C)E2 Th(WA, E)E3 Th(WC, E, G)5. .限定推理限定推理1980年，McCarthy提出了一种非单调的推理限定推理限定推理(Circumscription)。基本思想基本思想：从某些事实A出发能够推出具有某一性质的P的对象就是满足性质P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。6. .真值维护系统真值维护系统TMSTMS1979年，Doyle提出了一种非单调推理系统真值维护系统真值维护系统(T

18、ruth Maintenance System)真值维护系统是大型推理系统的的一个子系统，实现知识库中信念(belief)的修改与维护。其基本问题有：必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。基本数据结构基本数据结构:结点结点：表示信念理由理由：表示信念的原因信念既包括已知的知识，也包括假设的知识。基本操作基本操作：新结点的形成新结点的形成将信念赋予该结点；新理由的加入新理由的加入把某个信念与该结点联接起来实现过程实现过程：默认假设的形成；相关性回溯过程。6.1 信念知识表示每一个命题或规则均称为

19、结点，它分为两类：IN-IN-结点结点：相信为真OUT-OUT-结点结点：不相信为真，或无理由相信为真， 或当前没有任何有效的理由。每个结点附有理由表，表示具体结点的有效性：支持表支持表SLSL：所在结点的信念的原因，理由；条件证明条件证明CPCP：出现矛盾的原因。(SL()()IN-结点表中的IN-结点表示知识库中的已知知识;OUT-结点表中的OUT-结点表示这些结点的否定。例例1 1:(1) 现在是夏天(SL( )( )(2) 天气很潮湿(SL(1)( )结点(1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提;结点(2)则依赖于当前结点(1)的信念.所以，与一阶逻辑不同

20、的是,TMS可以撤消前提,并可以对知识库作适当修改.（1）支持表SL例例2 2:(1) 现在是夏天(SL( )( )(2) 天气很潮湿(SL(1)(3)(3) 天气很干燥若结点(1)是IN,结点(3)是OUT,则结点(2)才为IN.若在某个时刻出现结点(3)的证据,则结点(2)就变为OUT,因为它不再有一个有效的证实.象结点(2)这样的结点称为假设,它与非空的OUT结点表的SL证实有关.OUT结点(3)是结点(2)的证实的一部分.但如果结点(3)不存在,就不能这样表示了.在TMS中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实.(CP (CP )如果结论结点为IN-结点,以及下

21、列条件成立:(1) IN假设中的每个结点都是IN-结点;(2) OUT-假设中的每个结点都是OUT-结点.那么条件证明CP是有效的.一般说来,OUT-假设总是空集.TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设.通常只要在IN-假设中的结点为IN,OUT-假设中的结点为OUT,则结论结点为IN.（2）条件证明CP6.2 默认假设令F1, F2, , Fn表示所有可能的侯选的默认假设结点集,G表示选择默认假设的原因的结点,即由G引起在F1, , Fn中进行缺省选择.这样我们结合结点Node(Fi)以如下理由:(SL(G)(F1, , Fi-1 , Fi+1, ,

22、Fn)而选取Fi为默认假设.如果不存在任何其它关于如何进行选择的信息，则可以认为除Fi之外其它任何时候选都不是可信的这样Fi为IN,其它Fj(i j)均为OUT.但如果接收到一个有效的理由支持某个其它的侯选Fj,则Fj就为IN,而导致Fi的假设失败而变为OUT.6.3 相关回溯当知识库中出现不一致时,TMS将寻找并删除已做的一个不正确的默认逻辑,恢复一致性.它包括三个步骤:(1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集,并从中去掉至少一个假设信念以消除矛盾.(2) 构造一个结点记录矛盾产生的原因.(3) 从S中选取假设A(即不合理假设),并证实列在其理由充足

23、的支持条件中的一个OUT-结点.(4) 矛盾(SL(1,3)( )(周三14:00没有空会议室)例例3 3:(1) 会议日期为星期三(SL( )(2)(2) 会议日期不应是星期三(3) 会议时间为14:00(SL(32,40,61)()(5) 不相容(CP4 (1,3)( )(2) 会议日期不应是星期三(SL(5)( )结点(2)与结点(5)为IN,就引起结点(1)为OUT,因为结点(1)的证实依赖于结点(2)是OUT.结点(4)现在也变成OUT.进而矛盾就消除了.7 情景演算 情景演算是一种一阶逻辑语言，主要是用来表示动态变化的世界的。世界的所有变化过程都是“动作”的结果。一个可能世界历史可

24、以简单表示为动作的序列，它是通过称之为情景的一阶项所表示的。 常量S0表示初始情景，即动作还没有发生时的情景。do(, s)表示在情景s中执行动作之后的后继情景。 do(put(A, B), s)表示当世界状态为s时，将A放到B上的结果这种情景。 do(putdown(A), do(walk(L), do(pickup(A)是一种表示世界历史由动作序列pickup(A), walk(L), putdown(A)所组成的，它们按照从右到左的方式组织。 定义定义1 定义Lsitcalc语言的动作理论D为如下形式：D = Dss Dap Duna DSo 其中： ：基础的、针对情景演算的独立于领域的公理。Dap：动作前提条件公理；Dss：后续状态公理