《人工智能》第三章知识演绎.ppt
《《人工智能》第三章知识演绎.ppt》由会员分享,可在线阅读,更多相关《《人工智能》第三章知识演绎.ppt(54页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、人工智能人工智能第三章第三章 知识演绎知识演绎 主讲:夏幼明主讲:夏幼明人工智能人工智能第三章第三章 知识演绎知识演绎 2规则演绎系统规则演绎系统谓词演绎的归结方法谓词演绎的归结方法归结反驳搜索策略归结反驳搜索策略Hone子句的归结子句的归结“知识演绎知识演绎”核心内容核心内容人工智能人工智能第三章第三章 知识演绎知识演绎 3规则演绎系统规则演绎系统在基于规则系统中,每个在基于规则系统中,每个if可能与某断言可能与某断言(assertion)集集中的一个或多个断言匹配;中的一个或多个断言匹配;then部分用于规定放部分用于规定放入工作内存的新断言。入工作内存的新断言。这种系统叫做基于规则的演绎
2、系统这种系统叫做基于规则的演绎系统(rulebaseddeductionsystem)。在这种系统中,通常称规则的在这种系统中,通常称规则的if部分为前项部分为前项(antecedent),称规则的,称规则的then部分为后项部分为后项(consequent)。人工智能人工智能第三章第三章 知识演绎知识演绎 4规则演绎系统规则演绎系统基于规则的求解系统由基于规则的求解系统由if-then形式的规则形式的规则建立的。建立的。例如:例如:if(antecedent)then(consequent)基于规则的系统称为规则演绎系统,若后件用于规定基于规则的系统称为规则演绎系统,若后件用于规定动作,则称
3、为产生式系统。规则演绎系统可以分动作,则称为产生式系统。规则演绎系统可以分为如下的为如下的3种:种:规则正向演绎系统、规则逆向演绎规则正向演绎系统、规则逆向演绎系统、规则双向演绎系统。系统、规则双向演绎系统。前件前件 后件后件人工智能人工智能第三章第三章 知识演绎知识演绎 5 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统从从if部分向部分向then部分推理的过程称为正向推理,即从事部分推理的过程称为正向推理,即从事实或状态向目标或行动进行操作。实或状态向目标或行动进行操作。规则正向演绎系统的步骤:规则正向演绎系统的步骤:F事实表达命题式的与或形变换事实表达命题式的与或形
4、变换a)利用利用(W1W2)和和(W1W2)的等价关系,消去符号的等价关系,消去符号(如果存在如果存在该符号的话该符号的话)。实际上,在事实中间很少有符号。实际上,在事实中间很少有符号出现,因为可把出现,因为可把蕴涵式表示为规则。蕴涵式表示为规则。b)用狄用狄摩根摩根(DeMorgan)定律把否定符号移进括号内,直到每个否定律把否定符号移进括号内,直到每个否定符号的辖域最多只含有一个谓词为止。定符号的辖域最多只含有一个谓词为止。人工智能人工智能第三章第三章 知识演绎知识演绎 6 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统从从if部分向部分向then部分推理的过程称为正
5、向推理,即从事部分推理的过程称为正向推理,即从事实或状态向目标或行动进行操作。实或状态向目标或行动进行操作。规则正向演绎系统的步骤:规则正向演绎系统的步骤:x yP(x,y)F事实表达命题式的与或形变换事实表达命题式的与或形变换 xP(x,f(x)y xP(x,y)xP(x,a)xP(x)x P(x)c)对所得到的表达式进行对所得到的表达式进行Skolem化和前束化。化和前束化。d)对全称量词辖域内的变量进行改名和变量标准化,而存在量词量对全称量词辖域内的变量进行改名和变量标准化,而存在量词量化变量用化变量用Skolem函数代替。函数代替。e)删去全称量词,而任何余下的变量都被认为具有全称量化
6、作用。删去全称量词,而任何余下的变量都被认为具有全称量化作用。人工智能人工智能第三章第三章 知识演绎知识演绎 7 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统从从if部分向部分向then部分推理的过程称为正向推理,即从事部分推理的过程称为正向推理,即从事实或状态向目标或行动进行操作。实或状态向目标或行动进行操作。规则正向演绎系统的步骤:规则正向演绎系统的步骤:例例1:我们有事实表达式:我们有事实表达式(u)(v)Q(v,u)(R(v)P(v)S(u,v)把它化为把它化为:Q(v,A)R(v)P(v)S(A,v)对变量更名标准化,使得同一变量不出现在事实表达式的不同主要合
7、对变量更名标准化,使得同一变量不出现在事实表达式的不同主要合取式中。更名后得表达式:取式中。更名后得表达式:Q(w,A)R(v)P(v)S(A,v)必须注意到必须注意到Q(v,A)中的变量中的变量v可用新变量可用新变量w代替,而合取代替,而合取式式 R(v)P(v)中的变量中的变量v却不可更名,因为后者也出现在析却不可更名,因为后者也出现在析取式取式 S(A,v)中。中。人工智能人工智能第三章第三章 知识演绎知识演绎 8 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统从从if部分向部分向then部分推理的过程称为正向推理,即从事部分推理的过程称为正向推理,即从事实或状态向
8、目标或行动进行操作。实或状态向目标或行动进行操作。规则正向演绎系统的步骤:规则正向演绎系统的步骤:例例2:我们有事实表达式:我们有事实表达式(v)(u)Q(v,u)(R(v)P(v)S(u,v)注意,这时变量注意,这时变量u成为了变量成为了变量v的函数的函数f(v),利用,利用Skolem函数把函数把这个表达式化为这个表达式化为:Q(v,f(v)R(v)P(v)S(f(v),v)人工智能人工智能第三章第三章 知识演绎知识演绎 9 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统规则正向演绎系统的步骤:规则正向演绎系统的步骤:F事实表达命题式的与或形变换事实表达命题式的与或形
9、变换 R(V)P(V)R(V)P(V)S(A,V)R(V)P(V)S(A,V)Q(W,A)Q(W,A)R(V)P(V)S(A,V)每个节点表示该事实表达式的一个子每个节点表示该事实表达式的一个子表达式。某个事实表达式表达式。某个事实表达式(E1En)的每个合取子表达式的每个合取子表达式E1,En是用是用后继节点表示的,并由一个后继节点表示的,并由一个k线连接符线连接符把它们连接到父辈节点上。某个事实把它们连接到父辈节点上。某个事实表达式表达式(E1Ek)的析取关系子表达的析取关系子表达式式E1,Ek是由单一的后继节点表是由单一的后继节点表示的,并由一个单线连接符接到父辈示的,并由一个单线连接符
10、接到父辈结点。结点。人工智能人工智能第三章第三章 知识演绎知识演绎 10 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统与或图的正向推理:与或图的正向推理:限制规则的公式类型为:限制规则的公式类型为:LW其中:其中:L为单文字;为单文字;W为与为与或形的唯一公式。或形的唯一公式。例如:考虑规则例如:考虑规则S(xy)z应用应用到右面的事实表达式中。到右面的事实表达式中。TS(TU)S(TU)(PQ)RS(TU)(PQ)RPQU(PQ)R表示某个事实表达式的与或图的叶节点均由表示某个事实表达式的与或图的叶节点均由表达式中的文字来标记。表达式中的文字来标记。图中标记有整个事实
11、表达式的节点,称为根图中标记有整个事实表达式的节点,称为根节点,它在图中没有祖先。节点,它在图中没有祖先。XYSX YZ当目标公式按正向规则应用当目标公式按正向规则应用到事实表达式与或图,产生到事实表达式与或图,产生的与或图包含有终止在目标的与或图包含有终止在目标节点的一个解图时,证明目节点的一个解图时,证明目标公式成立。标公式成立。人工智能人工智能第三章第三章 知识演绎知识演绎 11 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统与或图的正向推理:与或图的正向推理:公式的与或图表示有个有趣的性质,即由变换该公式得到的子句集可公式的与或图表示有个有趣的性质,即由变换该公式
12、得到的子句集可作为此与或图的解图的集合作为此与或图的解图的集合(终止于叶节点终止于叶节点)读出;也就是说,所读出;也就是说,所得到的每个子句是作为解图的各个叶节点上文字的析取。这样,得到的每个子句是作为解图的各个叶节点上文字的析取。这样,由表达式由表达式Q(w,A)R(v)P(v)S(A,v)得到的子句为:得到的子句为:Q(w,A),S(A,v)R(v),S(A,v)P(v)我们一般把事实表达式的与或图表示倒过来画,即把根节点画在最下我们一般把事实表达式的与或图表示倒过来画,即把根节点画在最下面,而把其后继节点往上画。我们将要讨论到目标公式的与或图面,而把其后继节点往上画。我们将要讨论到目标公
13、式的与或图表示,它是按通常方式画出的,即目标在上面。表示,它是按通常方式画出的,即目标在上面。人工智能人工智能第三章第三章 知识演绎知识演绎 12 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统推理规则:消解推理规则:消解(归结归结)F把原子公式和原子公式的否定称为文字。任何文字的析取式称为把原子公式和原子公式的否定称为文字。任何文字的析取式称为子句。析取式子句。析取式P Q R可用子句表示为:可用子句表示为:P,Q,R。不包。不包含任何文字的子句称为空子句(含任何文字的子句称为空子句(NIL)。空子句是永假的。由子句)。空子句是永假的。由子句构成的集合称为子句集。构成的
14、集合称为子句集。F归结定义为:从归结定义为:从 1和和 2(1和和 2是文字集合,是文字集合,是一是一个文字个文字),可以归结为,可以归结为 1 2,它被称为两个子句的归结式。,它被称为两个子句的归结式。是是被归结的文字。这个过程称为归结。被归结的文字。这个过程称为归结。人工智能人工智能第三章第三章 知识演绎知识演绎 13 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统推理规则:消解推理规则:消解(归结归结)F归结定义为:从归结定义为:从 1和和 2(1和和 2是文字集合,是文字集合,是一是一个文字个文字),可以归结为,可以归结为 1 2,它被称为两个子句的归结式。,它被
15、称为两个子句的归结式。是是被归结的文字。这个过程称为归结。例:被归结的文字。这个过程称为归结。例:1、P R和和Q R归结归结R为为P Q。注意到。注意到P R与与Q R的等价写法的等价写法为为PR、RQ,利用蕴涵,利用蕴涵“”的传递性,则有的传递性,则有PQ,而它的等价表示为而它的等价表示为P Q。于是,可以看出,通过链式的推理规则。于是,可以看出,通过链式的推理规则产生的结果与归结是一致的。产生的结果与归结是一致的。2、R和和Q R归结归结R为为Q。而。而Q R等价于等价于RQ,这样,此归结与,这样,此归结与假言推理是一致的。假言推理是一致的。人工智能人工智能第三章第三章 知识演绎知识演绎
16、 14 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统推理规则:消解推理规则:消解(归结归结)F归结是合理的。归结是合理的。证明:所谓合理的,就是说,如果证明:所谓合理的,就是说,如果 1和和 2均是真的,那均是真的,那么么 1 2是真的。对是真的。对 的真假值讨论就可以了。的真假值讨论就可以了。情形一:情形一:是真的,那么,是真的,那么,是假的,因此,是假的,因此,2为真,必须为真,必须 2为真,故为真,故 1 2是真的。是真的。情形二:情形二:是假的,那么,是假的,那么,1为真,必须为真,必须 1为真,故为真,故 1 2是是真的。真的。综合情形一和二,可知,综合情形一
17、和二,可知,1、2至少有一个必须为真,即至少有一个必须为真,即 1 2是真是真的。的。人工智能人工智能第三章第三章 知识演绎知识演绎 15 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统与或图的正向推理:与或图的正向推理:应用消解原理的结果应用消解原理的结果:规则规则S(XY)Z化为子句:化为子句:SXZ;SYZ;事实表达式事实表达式(PQ)RS(TU)化为化为子句:子句:PQS;RS;PQTU;RTU归结结果:归结结果:XZPQ;YZPQ;RXZ;RYZ人工智能人工智能第三章第三章 知识演绎知识演绎 16 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎
18、系统与或图的正向推理:与或图的正向推理:应用一条规则得到的与或图继续表示事实表达式和推得的表达式,应用一条规则得到的与或图继续表示事实表达式和推得的表达式,这可利用匹配弧两侧有相同标记的节点来实现。对一个节点这可利用匹配弧两侧有相同标记的节点来实现。对一个节点应用一条规则之后,此节点就不再是该图的叶节点。应用一条规则之后,此节点就不再是该图的叶节点。不过,它仍然由单一文字标记而且可以继续具有一些应用于它的不过,它仍然由单一文字标记而且可以继续具有一些应用于它的规则。规则。我们把图中标有单文字的任一节点都称为文字节点,由一个与或我们把图中标有单文字的任一节点都称为文字节点,由一个与或图表示的子句
19、集就是对应于该图中以文字节点终止的解图集。图表示的子句集就是对应于该图中以文字节点终止的解图集。人工智能人工智能第三章第三章 知识演绎知识演绎 17 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统作为终止条件的目标公式作为终止条件的目标公式 应用规则推理的目的在于从某个事实公式和某个规则集出应用规则推理的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。发来证明某个目标公式。在正向推理系统中,这种目标表达式只限于可证明的表达式,尤其是可在正向推理系统中,这种目标表达式只限于可证明的表达式,尤其是可证明的文字析取形的目标公式表达式。我们用文字集表示此目标公证明的文字
20、析取形的目标公式表达式。我们用文字集表示此目标公式,并设该集各元都为析取形式。式,并设该集各元都为析取形式。目标文字和规则可用来对与或图添加后继节点,当一个目标文字与该图目标文字和规则可用来对与或图添加后继节点,当一个目标文字与该图中文字节点中文字节点n上的一个文字相匹配时,我们就对该图添加这个节点上的一个文字相匹配时,我们就对该图添加这个节点n的新后裔,并标记为匹配的目标文字。这个后裔叫做目标节点,的新后裔,并标记为匹配的目标文字。这个后裔叫做目标节点,目标节点都用匹配弧分别接到它们的父辈节点上。目标节点都用匹配弧分别接到它们的父辈节点上。人工智能人工智能第三章第三章 知识演绎知识演绎 18
21、 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统作为终止条件的目标公式作为终止条件的目标公式例例3:事实:事实PQ;规则规则PC,QG;目标;目标CG。把规则化为子句形,得子句集:把规则化为子句形,得子句集:PC,QG目标的否定为目标的否定为:(CG);其子句形为;其子句形为:C,G PCPQQC CQ QG G QNIL人工智能人工智能第三章第三章 知识演绎知识演绎 19 规则规则演绎系统演绎系统(1)(1)规则正向演绎系统规则正向演绎系统作为终止条件的目标公式作为终止条件的目标公式例例3:事实:事实PQ;规则规则PC,QG;目标;目标CG。PQPR(P Q)(PO)R
22、S(TU)(PQ)R(TU)STUQ(TU)SCDEGCG当目标公式按正向规则应用当目标公式按正向规则应用到事实表达式与或图,产生到事实表达式与或图,产生的与或图包含有终止在目标的与或图包含有终止在目标节点的一个解图时,证明目节点的一个解图时,证明目标公式成立。标公式成立。人工智能人工智能第三章第三章 知识演绎知识演绎 20 规则规则演绎系统演绎系统(2)(2)规则规则逆向演绎系统逆向演绎系统基于规则的逆向演绎系统,其操作过程与正向演绎系统相反,即为从目基于规则的逆向演绎系统,其操作过程与正向演绎系统相反,即为从目标到事实的操作过程,从标到事实的操作过程,从then到到if的推理过程。的推理过
23、程。目标表达式的与或形式目标表达式的与或形式 采用与变换事实表达式同样的过程,把目标公式化成与或形,即消去蕴采用与变换事实表达式同样的过程,把目标公式化成与或形,即消去蕴涵符号,把否定符号移进括号内,对全称量词涵符号,把否定符号移进括号内,对全称量词Skolem化并删去存化并删去存在量词。留在目标表达式与或形中的变量假定都已存在量词量化。在量词。留在目标表达式与或形中的变量假定都已存在量词量化。例例1:目标表达式:目标表达式:(y)(x)P(x)(x,y)P(x)S(y)被化成与或形:被化成与或形:P(f(y)Q(f(y),y)P(f(y)S(y)式中,式中,x=f(y)为一为一Skolem函
24、数。函数。人工智能人工智能第三章第三章 知识演绎知识演绎 21 规则规则演绎系统演绎系统(2)(2)规则规则逆向演绎系统逆向演绎系统目标表达式的与或形式目标表达式的与或形式 与或形的目标公式也可以表示为与或图。不与或形的目标公式也可以表示为与或图。不过,与事实表达式的与或图不同的是,对过,与事实表达式的与或图不同的是,对于目标表达式,与或图中的于目标表达式,与或图中的k线连接符用线连接符用来分开合取关系的子表达式。在目标公式来分开合取关系的子表达式。在目标公式的与或图中,我们把根节点的任一后裔叫的与或图中,我们把根节点的任一后裔叫做子目标节点,而标在这些后裔节点中的做子目标节点,而标在这些后裔
25、节点中的表达式叫做子目标。表达式叫做子目标。例例1:目标表达式:目标表达式:P(f(y)Q(f(y),y)P(f(y)S(y)P(f(y)Q(f(y),y)P(f(y)S(y)Q(f(y),y)P(f(y)S(y)P(f(y)Q(f(y),y)S(y)P(f(y)P(f(y)S(y)人工智能人工智能第三章第三章 知识演绎知识演绎 22 规则规则演绎系统演绎系统(2)(2)规则规则逆向演绎系统逆向演绎系统与或图的逆向推理规则变换与或图的逆向推理规则变换我们应用逆向推理规则来变换逆向演绎系统的与或图结构,逆向推理规我们应用逆向推理规则来变换逆向演绎系统的与或图结构,逆向推理规则是建立在确定的蕴涵式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 第三 知识 演绎
限制150内