人工智能第七章2014.ppt_第1页
人工智能第七章2014.ppt_第2页
人工智能第七章2014.ppt_第3页
人工智能第七章2014.ppt_第4页
人工智能第七章2014.ppt_第5页
已阅读5页,还剩19页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、8/6/2020,1,第七章 基于规则的演绎系统,主讲:欧阳丹彤,8/6/2020,2,归结方法 优点:实现简单(仅使用一条推理规则) 完备 缺点:低效(不使用领域知识) 转换成子句形式过程中失去了控制信息 基于规则的演绎系统 优点:易于理解(推理过程与人的推理过程相近) 高效(尽量使用与领域有关的知识) 缺点:不完备,8/6/2020,3,基于规则的演绎系统,描述领域知识的逻辑语句分为两类: 描述该领域的一般性规律-转换成产生式规则 描述该领域的具体情况或状态-转换成产生式系统的状态描述 工作过程 选可用的产生式规则用于状态描述、产生新的状态描述,当产生的状态描述满足终止条件时,推导任务完成

2、。 工作方式 正向系统:以事实作为初始状态描述,以结论为终止条件的演绎系统 反向系统:以结论作为初始状态描述,以事实为终止条件的演绎系统,8/6/2020,4,7.1 正向演绎系统,一、初始状态描述 先把描述事实的逻辑公式转换成不含蕴涵符号的AND/OR形式,再用AND/OR图表示。 事实表达式的AND/OR形转换 与化Skolem范式过程类似 不同:不要求母式是合取范式 要求:不同的主合取项里变量使用不同的名字。,8/6/2020,5,例,表示事实的逻辑公式 G=u v (Q (v,u) (R(v)P(v) S(u,v) = u v (Q (v,u)( (R(v) P(v) S(u,v) 用

3、常量符号A代替u得 v(Q(v,A)(R(v)P(v)S(A,v) 对变量改名,使得不同的主合取项里变量使用不同的名字: wQ(w,A) v(R(v)P(v)S(A,v) Q(w,A) (R(v)P(v)S(A,v),8/6/2020,6,事实表达式的AND/OR图表示,节点:表示事实AND/OR形式的子表达式 如果子表达式E1,Ek的父亲节点是(E1Ek),则用k-连接符把这些子节点与父节点连接起来; 如果子表达式E1,Ek的父亲节点是(E1Ek),则用1-连接符分别把这些子节点与父节点连接起来。,8/6/2020,7,表示逻辑公式的AND/OR图的性质: 该公式对应的所有子句可以从终止在叶

4、节点的解图集合中 读出- AND/OR图是子句形式的一种紧凑表示方式 例.Q(w,A) (R(v)P(v)S(A,v)对应的所有子句 Q(w,A) S(A,v)R(v) S(A,v)P(v) 都可从解图读出来。 Note:其一般性要比子句形式稍差一点。 原因: 在子句形式中,不同子句之间变量允许任意改名; 在AND/OR图表示中,改名有时会受到限制-仅允许最外层合取项间经改名无公共变量。,8/6/2020,8,二、正向演绎系统的规则,F规则的形式:LW 是正常Skolem化后恢复成蕴涵式,且要求: L是单文字; W是AND/OR形公式; 出现在蕴涵式中的所有变量假定是对整个蕴涵式全称定量的;

5、不同规则使用的变量名互不相同; 规则与事实AND/OR图中的变量名也不相同。 Note:正向演绎系统的规则的前提必须是单文字,看起来似乎限制很强。但是,很多逻辑公式可以转换成满足这种限制的规则. 例如,形式为(L1L2)W的蕴涵式等价于两条规则 L1W和L2W。,8/6/2020,9,例,对于公式 x(y zP(x,y,z) uQ(x,u) 可以通过如下步骤实现其转换: (1)暂时删除蕴涵符号: x(y zP(x,y,z) uQ(x,u) (2)把否定符移到原子前: x(y zP(x,y,z) uQ(x,u) (3)化前束范式:xy z u(P(x,y,z) Q(x,u) (4)Skolem化

6、:用f(x,y)代z,得 P(x,y,f(x,y) Q(x,u) (5)恢复成蕴涵形式: P(x,y,f(x,y)Q(x,u),8/6/2020,10,F规则的使用 规则LW中的L同AND/OR图叶节点n匹配(合一下)成功时,称为使用该规则的一次推理。 应用规则的结果:把表示W的AND/OR图通过L连到AND/OR图的节点n上,n和它的后继节点L以1-连接符(称为匹配弧,用 标记)连接。,8/6/2020,11,例. 已知:事实:(PQ)R)(S(TU) 带有文字S的子句是:PQS和RS 规则:S(XY)Z 子句形式是:SXZ和SYZ,8/6/2020,12,图7.3 应用一条规则后所得到的A

7、ND/OR图XZPQ,YZPQ,RYZ,RXZ都包含在解图所表示的子句中,8/6/2020,13,结论:对AND/OR图应用一条规则的过程,以十分简便高效的方式达到了使用归结方法经过多次归结才能达到的目的。 当对一个节点应用规则后,这个节点已经不再是叶节点了,但它仍然用单文字标记。 把单文字标记的节点叫文字节点,并且规定对文字节点可以继续使用规则。 这样应用规则后的AND/OR图既能表示原来的事实公式又能表示推理结果。 终止于文字节点的解图对应于AND/OR图所表示的子句。,8/6/2020,14,包含变量的正向演绎系统例事实:P(x,y)(Q(x,A)R(B,y) 子句: P(x,y)Q(x

8、,A) P(x,y)R(B,y)规则:P(A,B)(S(A)X(B),8/6/2020,15,新增加的叶节点与原图的叶节点构成两个新的解图,与这两个解图对应的子句是:S(A)X(B)Q(A,A)和S(A)X(B)R(B,B),8/6/2020,16,三、正向演绎系统的目标,目标公式形式:文字的析取形式。 当目标公式包含存在定量和全称定量的变量时,是经对偶Skolem化后的文字的析取形式; 对公式中的变量进行改名,使得不同的析取项中没有相同的变量。 Note:对偶Skolem化:全称量词用存在量词的Skolem函数所代替,然后把存在量词删去,出现的变量假定都是存在定量的。 改名依据:x(W1(x

9、) W2(x)=xW1(x) yW2(y),8/6/2020,17,目标节点 基情形:当目标公式中的一个文字与AND/OR图中的一个文字n相匹配时,我们把匹配的目标文字作为节点n的后继加到AND/OR图上,这个节点称作目标节点。 含变量情形:当目标公式中的一个文字与AND/OR图中的一个文字n可合一时,我们把匹配的目标文字作为节点n的后继加到AND/OR图上,其间以匹配弧相接,用最一般合一标记,这个节点称作目标节点。 产生式系统成功终止条件 基情形:当AND/OR图包含一个终止在目标节点的解图时,产生式系统成功地终止。 含变量情形:对AND/OR图不断地应用规则,当AND/OR图包含一个终止于

10、目标节点的相容解图时,系统成功地终止。把合一复合用于相容解图,就得到从事实到目标的证明。,8/6/2020,18,例 事实:AB 规则:ACD BEG 目标: CG,8/6/2020,19,Note:对于AB,因为不知道A是真的还是B是真的,必须分情况加以证明,先假定A是真的去证明目标,再假定B是真的去证明目标。只有当这两个证明都成功时,才能算做是证明了目标。因此在图7.4中,节点(AB)的两个后继用2-连接符号(AB)连接,这就是为什么在AND/OR图中要使用k-连接符连接析取节点与其后继的理由。,8/6/2020,20,四、 正向演绎系统的相容解图,定义(替换的相容性集合、合一复合替换)

11、设有替换集合1 ,2 ,n,每一i 具有如下形式: i = ti1/vi1 ,tim(i)/vim(i) 其中ti1,tim(i) 是项,vi1,vim(i)是变量; 我们用这些替换构造两个表达式U1和U2如下: U1 =v11,v1m(1),vn1,vnm(n) U2 =t11,t1m(1),tn1,tnm(n)) 如果U1 和U2是可合一的,则替换集合1 ,2 ,n称作是相容 的,否则称作是不相容的, U1 和U2的最一般合一替换也叫做1 ,2 ,n的合一复合替换。,8/6/2020,21,例:问如下1,2是否相容? 若相容,给出合一复合替换。设(1)1,2=A/x,B/x (2)1,2=x/y,y/z (3) 1,2=f(z)/x,f(A)/x (4) 1,2=g(y)/x,f(x)/y,8/6/2020,22,Note:只有对具有相容匹配替换的解图才考虑它对应的子句集是合理的.,例.事实:P(x)Q(x) 规则:P(A)R(A) Q(B)R(B) (R(A)R(B)不是该AND/OR图的一个子句表示。,8/6/2020,23,例. 事实DOG(FIDO)(BARKS(FIDO)BITES(FIDO) 规则:R1: DOG(x)TERRIER(x) R2: BARKS(y)NOISY(y)目标: TER

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论