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