《人工智能导论》04推理0...

1、人工智能导论方若宇方若宇2009年秋季汕头大学计算机系本科课程年秋季汕头大学计算机系本科课程推理推理正向与反向推理正向与反向推理归结推理归结推理不确定性推理概述不确定性推理概述贝叶斯网络贝叶斯网络正向与反向推理方式正向与反向推理方式- -以产生式系统为例以产生式系统为例1.1.正向推理正向推理 正向推理又称为正向链接推理，其推理基础是逻辑演绎的推理链，它从一组表示事实的谓词或正向推理又称为正向链接推理，其推理基础是逻辑演绎的推理链，它从一组表示事实的谓词或命题出发，使用一组推理规则，来证明目标谓词公式或命题是否成立。命题出发，使用一组推理规则，来证明目标谓词公式或命题是否成立。 实现正向推理的

2、一般策略是：先提供一批数据实现正向推理的一般策略是：先提供一批数据( (事实事实) )到总数据库中，系统利用这些事实与规则到总数据库中，系统利用这些事实与规则的前提匹配，触发匹配成功的规则的前提匹配，触发匹配成功的规则( (即启用规则即启用规则) )，把其结论作为新的事实添加到总数据库中。继，把其结论作为新的事实添加到总数据库中。继续上述过程，用更新过的总数据库中的所有事实再与规则库中另一条规则匹配，用其结论再修改续上述过程，用更新过的总数据库中的所有事实再与规则库中另一条规则匹配，用其结论再修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库为止。总数据库的内容，直到没有可

3、匹配的新规则，不再有新的事实加到总数据库为止。例如，有规则集如下例如，有规则集如下: :规则规则1: IF P1 THEN P2 1: IF P1 THEN P2 规则规则2: IF P2 THEN P3 2: IF P2 THEN P3 规则规则3: IF P3 THEN q3 3: IF P3 THEN q3 规则中的规则中的P1P1、P2P2、P3P3、q3q3可以是谓词公式或命题。设总数据库（工作存储器）中已有事实可以是谓词公式或命题。设总数据库（工作存储器）中已有事实P1P1，则，则应用这三条规则进行正向推理，即从应用这三条规则进行正向推理，即从P1P1出发推导出出发推导出q3q3的

4、过程如图的过程如图4.164.16所示。所示。 前面已经指出，前件和后件可以用命题或谓词来表示，当它们是谓词时，全局前提与总数据库前面已经指出，前件和后件可以用命题或谓词来表示，当它们是谓词时，全局前提与总数据库中的事实匹配成功是指：对前件谓词中出现的变量进行某种统一的置换，使置换后的前件谓词成中的事实匹配成功是指：对前件谓词中出现的变量进行某种统一的置换，使置换后的前件谓词成为总数据库中某个谓词的实例，即实例化后前件谓词与总数据库中某个事实相同。执行后件是指：为总数据库中某个谓词的实例，即实例化后前件谓词与总数据库中某个事实相同。执行后件是指：当前件匹配成功时，用前件匹配时使用的相同变量，按

5、同一方式对后件谓词进行置换，并把置换当前件匹配成功时，用前件匹配时使用的相同变量，按同一方式对后件谓词进行置换，并把置换结果（后件谓词实例）加进总数据库。结果（后件谓词实例）加进总数据库。正向推理链接过程示意图正向推理链接过程示意图 2.2.反向推理反向推理 反向推理又称为后向链接推理，其基本原理是从表示目标的谓词或命题出发，使用一组规反向推理又称为后向链接推理，其基本原理是从表示目标的谓词或命题出发，使用一组规则证明事实谓词或命题成立，即提出一批假设则证明事实谓词或命题成立，即提出一批假设( (目标目标) )，然后逐一验证这些假设。，然后逐一验证这些假设。 举例如下：仍用上述的三条规则为例，

6、应用反向推理方法，从举例如下：仍用上述的三条规则为例，应用反向推理方法，从P1P1出发推导出出发推导出q3q3的过程如图的过程如图4.184.18所示：所示： 首先假定目标首先假定目标q3q3成立，由规则成立，由规则3 3（P3q3P3q3），为证明），为证明q3q3成立，须先验证成立，须先验证P3P3是否成立；但总数是否成立；但总数据库没有事实据库没有事实P3P3，所以假定子目标，所以假定子目标P3P3成立；由规则成立；由规则2(P2P3)2(P2P3)，应验证，应验证P2P2；同样，由于数据库；同样，由于数据库中没有事实中没有事实P2P2，假定子目标，假定子目标P2P2成立；由规则成立；由

7、规则1(P1P2)1(P1P2)，为验证，为验证P2P2成立，须先验证成立，须先验证P1P1。因为数。因为数据库中有事实据库中有事实P1P1，所以假定的目标，所以假定的目标P2P2成立，因而成立，因而P3P3成立，最终导出结论成立，最终导出结论q3q3确实成立。确实成立。 总之，反向推理的具体实现策略是：先假定一个可能的目标，系统试图证明它，看此假设总之，反向推理的具体实现策略是：先假定一个可能的目标，系统试图证明它，看此假设目标是否在总数据库中，若在，则假设成立。否则，看这些假设是否证据目标是否在总数据库中，若在，则假设成立。否则，看这些假设是否证据( (叶子叶子) )结点，若是，结点，若是

8、，向用户询问，若不是，则再假定另一个目标，即找出结论部分中包含此假设的那些规则，把它向用户询问，若不是，则再假定另一个目标，即找出结论部分中包含此假设的那些规则，把它们的前提作为新的假设，试图证明它。这样周而复始，直到所有目标被证明，或所有路径被测们的前提作为新的假设，试图证明它。这样周而复始，直到所有目标被证明，或所有路径被测试。试。 反向推理链接过程示意图反向推理链接过程示意图3.3.双向推理双向推理还有归结推理方法归结推理方法概述概述 归结原理由归结原理由J.A.RobinsonJ.A.Robinson由由19651965年提出。年提出。 与演绎法与演绎法(deductive infer

9、ence)(deductive inference)完全不同，是一种新的逻辑演完全不同，是一种新的逻辑演算算(inductive inference)(inductive inference)算法。至今为止一阶逻辑中最有效的半可算法。至今为止一阶逻辑中最有效的半可判定的算法。一阶逻辑中任意恒真公式，使用归结原理，总可以在判定的算法。一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。有限步内给以判定。 语义网络、框架表示、产生式规则等等以推理方法为前提的。即，语义网络、框架表示、产生式规则等等以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。有了规则已知条件，顺藤摸瓜找到

10、结果。 归结方法没有这样一个循归结方法没有这样一个循序渐进的过程，而是在一个规则指导下，进行自动推导（序渐进的过程，而是在一个规则指导下，进行自动推导（“数学定数学定理机器证明理机器证明”）。）。 本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶 谓词逻辑问题。谓词逻辑问题。 命题逻辑的归结法命题逻辑的归结法命题逻辑基础：命题逻辑基础： 定义：定义：合取式：合取式：p p与与q q，记做，记做p p q q析取式：析取式：p p或或q q，记做，记做p p q q蕴含式：如果蕴含式：如果p p则则q q，记做，记做p p q q等

11、价式：等价式：p p当且仅当当且仅当q q，记做，记做p p q q析取范式：仅由有限个简单合取式组成的析取式。析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。合取范式：仅由有限个简单析取式组成的合取式。.基本等值式基本等值式2424个个(1)(1)交换率：交换率：p pq q q q p p ； p p q q q q p p 结合率：结合率： ( (p pq q) ) r r p p(q q r);r); ( (p p q) q) r r p p (q q r) r)分配率：分配率： p p(q q r) (r) (p pq q)()(p p r)

12、r) ； p p (q q r) (r) (p p q q) () (p p r) r) 摩根率摩根率: : ( (p pq q) ) p p q q ； ( (p p q q) ) p p q q 吸收率吸收率: : p p(p pq q ) ) p p ； p p (p pq q ) ) p p 同一律同一律: : p p0 0 p p ； p p1 1 p p 蕴含等值式蕴含等值式: :p p q q p pq q 假言易位式假言易位式: : p p q q p p q q命题逻辑的归结法命题逻辑的归结法 归结法的基本单元是简单命题（陈述句）归结法的基本单元是简单命题（陈述句）命题：命题

13、： A A1 1、A A2 2、A A3 3 和和 B B求证：求证： A A1 1AA2 2AA3 3成立，则成立，则B B成立，成立，即求证：即求证：A A1 1AA2 2AA3 3 B B归结法使用反证法：归结法使用反证法： 证明证明A A1 1AA2 2AA3 3B B 是矛盾式（即永假式）是矛盾式（即永假式） 首先需要建立子句集首先需要建立子句集 1.1.写出合取范式：写出合取范式：PP（ PQPQ）（PQPQ）（即（命题）、（命题和）的与）（即（命题）、（命题和）的与）2.2.从合取范式得到子句集从合取范式得到子句集S S：合取范式形式下的子命题（元素）的集合合取范式形式下的子命题

14、（元素）的集合例：将命题公式写成合取范式的形式：例：将命题公式写成合取范式的形式：PP（ PQPQ）（ PQPQ） 得到子句集得到子句集 S S：S = P, PQ, S = P, PQ, PQPQ 其次进行归结其次进行归结 归结式归结式 设设C1C1和和C2C2是子句集中的任意两个子句是子句集中的任意两个子句, ,如果如果C1C1中的文字中的文字L1L1与与C2C2中的文字中的文字L2L2互补互补, ,那么可以从那么可以从C1C1和和C2C2中分别消去中分别消去L1L1和和L2,L2,并将并将C1C1和和C2C2中余下的部分按析取关系构成一个新子句中余下的部分按析取关系构成一个新子句C12,

15、C12,则称这个过程为归则称这个过程为归结结, ,称称C12C12为为C1C1和和C2C2的归结式的归结式 归结法的核心是在子句集之上求两个子句间的归结式归结法的核心是在子句集之上求两个子句间的归结式. . 归结过程归结过程 ： 1.1.将命题写成合取范式将命题写成合取范式 2.2.求出子句集求出子句集 3.3.对子句集使用归结推理规则对子句集使用归结推理规则 4.4.归结式作为新子句参加归结归结式作为新子句参加归结 5.5.归结式为空子句，归结式为空子句，S S是不可满足的（矛盾），原命题成立。是不可满足的（矛盾），原命题成立。（证明完毕）（证明完毕）命题逻辑归结例题命题逻辑归结例题例题，证

16、明公式：例题，证明公式：(P Q) (P Q) (Q Q P)P)证明：证明： 1. 1. 根据归结原理，将待证明公式转化成待归结命题公式：根据归结原理，将待证明公式转化成待归结命题公式：(P Q) (P Q) ( (Q Q P)P)2. 2. 将公式前项化为合取范式：将公式前项化为合取范式：P Q P Q P QP Q结论求后的后项化为合取范式：结论求后的后项化为合取范式：( (Q Q P)P) (Q(QP) P) Q PQ P两项合并后化为合取范式：两项合并后化为合取范式： （P QP Q）Q PQ P 3. 3. 则子句集为：则子句集为： PQPQ，Q Q，PP假定结论不成立假定结论不成

17、立子句集为：子句集为： PQPQ，Q Q，PP4.4.对子句集中的子句进行归结可得：对子句集中的子句进行归结可得：1.1. PQPQ2.2. Q Q3.3. P P4.4. Q Q （1 1，3 3归结）归结）5.5. NilNil （2 2，4 4归结）归结）由上可知假设矛盾，即原公式成立。由上可知假设矛盾，即原公式成立。谓词归结原理基础谓词归结原理基础一阶逻辑一阶逻辑基本概念基本概念 个体词个体词 ：表示主语的词：表示主语的词 谓词谓词 ：刻画个体性质或个体之间关系的词：刻画个体性质或个体之间关系的词 量词量词 ：表示数量的词：表示数量的词公式及其解释公式及其解释 个体常量：个体常量：a,

18、b,ca,b,c 个体变量：个体变量：x,y,zx,y,z 谓词符号：谓词符号：P,Q,RP,Q,R 量词符号：量词符号： , , 例如：例如：（1 1）所有的人都是要死的。）所有的人都是要死的。（2 2）有的人活到一百岁以上。）有的人活到一百岁以上。在个体域在个体域D D为人类集合时，可符号化为：为人类集合时，可符号化为： x x P P( (x x) )，其中，其中P P( (x x) )表示表示x x是要死的。是要死的。 x x Q Q( (x x), ), 其中其中Q Q( (x x) )表示表示x x活到一百岁以上。活到一百岁以上。引入特殊谓词引入特殊谓词R R( (x x) )表示

19、表示x x是人，可符号化为：是人，可符号化为：（1 1） x x（R R( (x x) ) P P( (x x) )）, , 其中，其中，R R( (x x) )表示表示x x是人；是人；P P( (x x) )表示表示x x是要死的。是要死的。（2 2） x x（R R( (x x) ) Q Q( (x x) )），），其中，其中，R R( (x x) )表示表示x x是人；是人；Q Q( (x x) )表示表示x x活到一百岁以上活到一百岁以上。 量词否定等值式：量词否定等值式：( ( x x）M M（x x）（ x x）M M（x x） ( ( x x）M M（x x）（ x x）M M

20、（x x）量词分配等值式：量词分配等值式：( ( x x）(P(P（x x）QQ（x x）)()( x x）P P（x x）( x x）Q Q（x x）( ( x x）(P(P（x x）Q Q（x x）) () ( x x）P P（x x）( ( x x）Q Q（x x）消去量词等值式：设个体域为有穷集合（消去量词等值式：设个体域为有穷集合（a a1 1, a, a2 2, , a an n）( ( x x）P P（x x）PP（a a1 1）PP（a a2 2） P P（a an n）( ( x x）P P（x x）PP（a a1 1）P P（a a2 2） P P（a an n）量词辖域收

21、缩与扩张等值式：量词辖域收缩与扩张等值式：( ( x x）( ( P P（x x） Q) (Q) ( x x）P P（x x） Q Q( ( x x）( ( P P（x x） Q) ( Q) ( x x）P P（x x） Q Q ( ( x x）( ( P P（x x） Q) (Q) ( x x）P P（x x） Q Q ( ( x x）( QP( QP（x x）) ) Q(Q( x x）P P（x x） ( ( x x）( ( P P（x x） Q) (Q) ( x x） P P（x x） Q Q( ( x x）( ( P P（x x） Q) ( Q) ( x x） P P（x x） Q Q

22、 ( ( x x）( ( P P（x x） Q) (Q) ( x x） P P（x x） Q Q ( ( x x）( Q( Q PP（x x）) ) Q(Q( x x） P P（x x）谓词归结子句形谓词归结子句形( ( SkolemSkolem 标准形标准形) ) 前束范式定义：前束范式定义： 如果如果A A中的一切量词都位于该公式的最左边（不含否中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端，则说定词），且这些量词的辖域都延伸到公式的末端，则说公式公式A A是一个前束范式。是一个前束范式。 即即: :把所有的量词都提到前面去，然后消掉所有量词把所有的量词

23、都提到前面去，然后消掉所有量词 (Q1x1)(Q2x2)(Q1x1)(Q2x2)(Qnxn)M(x1,x2,(Qnxn)M(x1,x2, ,xnxn) ) 约束变项换名规则：约束变项换名规则： ( (QxQx） M M（x x） （QyQy） M M（y y） ( (QxQx） M M（x,zx,z） （QyQy） M M（y,zy,z）量词消去原则：量词消去原则： 1. 1. 消去存在量词消去存在量词“ ”， 左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。如没有，改写成为常量。 2. 2. 略

24、去全程量词略去全程量词“ ”。例例: :将下式化为将下式化为SkolemSkolem标准形：标准形：( ( x)(x)( y)P(a,x,yy)P(a,x,y) () ( x)(x)( ( y)Q(y,b)R(xy)Q(y,b)R(x) 第一步，消去第一步，消去号，得：号，得：( ( ( x)(x)( y)P(a,x,yy)P(a,x,y) ( ( x)(x)( ( y)Q(y,b)R(xy)Q(y,b)R(x)第二步，深入到量词内部，得：第二步，深入到量词内部，得：( ( x)(x)( y)P(a,x,yy)P(a,x,y) ( ( x)(x)( y)Q(y,b)R(xy)Q(y,b)R(x

25、)( ( x)(x)( y)P(a,x,y)(y)P(a,x,y)( x)(x)( y)Q(y,b)R(xy)Q(y,b)R(x)第三步，变元易名，得第三步，变元易名，得( ( x)(x)( y)P(a,x,yy)P(a,x,y) ) ( ( u u)()( v v)(Q(v,b)(Q(v,b) ) R(uR(u)第四步，存在量词左移，直至所有的量词移到前面，得：第四步，存在量词左移，直至所有的量词移到前面，得： ( ( x)(x)( y)(y)( u u)()( v v)P(a,x,y)P(a,x,y) ) ( (Q(v,b)R(uQ(v,b)R(u)由此得到前由此得到前束束范式范式 ( (

26、 x)(x)( y)(y)( u u)()( v v)P(a,x,y)(Q(v,b)R(u)P(a,x,y)(Q(v,b)R(u)第五步，消去第五步，消去“ ”（存在量词），略去（存在量词），略去“ ”全称量词全称量词 消去消去( ( y)y)，因为它左边只有，因为它左边只有( ( x)x)，所以使用，所以使用x x的函的函数数f(xf(x) )代替之，这样得到：代替之，这样得到：( ( x)(x)( u)(u)( v)(P(a,x,f(x)Q(vv)(P(a,x,f(x)Q(v, , b)R(ub)R(u) 消去消去( ( u)u)，同理使用，同理使用g(xg(x) )代替之，这样得到：代替

27、之，这样得到：( ( x)(x)( v)(P(a,x,f(x)Q(v,b)R(g(xv)(P(a,x,f(x)Q(v,b)R(g(x)） 略去全称变量，原式的略去全称变量，原式的SkolemSkolem标准形为：标准形为： P(a,x,f(x)Q(v,b)R(g(xP(a,x,f(x)Q(v,b)R(g(x)置换与合一置换与合一 一阶谓词逻辑的归结比命题逻辑的归结要复杂得多一阶谓词逻辑的归结比命题逻辑的归结要复杂得多, ,其中一个原因其中一个原因就是谓词逻辑公式中含有个体变量与函数就是谓词逻辑公式中含有个体变量与函数. .因此因此, ,寻找互补子句的过程寻找互补子句的过程就比较复杂就比较复杂.

28、 . 例如例如, , P(xP(x) ) Q(yQ(y) ) 与与 P(aP(a) ) R(zR(z) ) 就不容易从直接比较中发现这两个子句中含有互补对就不容易从直接比较中发现这两个子句中含有互补对, ,但如果将但如果将x x 取取a a值值, ,则很明显这两个子句为互补对则很明显这两个子句为互补对. . 这就是将要讨论的置换与合一这就是将要讨论的置换与合一, ,即对个体变量做适当的替换即对个体变量做适当的替换. .置换置换置换置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：定义： 置换是形如置换是形如tt1 1/x/

29、x1 1, t, t2 2/x/x2 2, , , , t tn n/x/xn n 的有限集合。的有限集合。 其中，其中，x x1 1, x, x2 2, , , , x xn n是互不相同的变量，是互不相同的变量， t t1 1, t, t2 2, , , , t tn n是不同于是不同于x xi i的项（常量、变量、函数）；的项（常量、变量、函数）； t ti i/x/xi i表示用表示用t ti i置换置换x xi i，并且要求，并且要求t ti i与与x xi i不能相同，而且不能相同，而且x xi i不能循环地出现在另一个不能循环地出现在另一个t ti i中。中。例如例如a/xa/x

30、，c/yc/y，f(b)/zf(b)/z 是一个置换；是一个置换； g(y)/xg(y)/x，f(x)/yf(x)/y 不是一个置换。不是一个置换。置换的合成置换的合成 设设 tt1 1/x/x1 1, t, t2 2/x/x2 2, , , , t tn n/x/xn n ， uu1 1/y/y1 1, u, u2 2/y/y2 2, , , u, un n/ /y yn n ，是两个置换。，是两个置换。 则则 与与 的合成也是一个置换，记作的合成也是一个置换，记作 。它是从集合。它是从集合tt1 1 /x/x1 1, t, t2 2 /x/x2 2, , , , t tn n /x/xn

31、n, u, u1 1/y/y1 1, u, u2 2/y/y2 2, , , u, un n/ /y yn n 中删去以下两种元素：中删去以下两种元素： 1.1.当当t ti i =x=xi i时，删去时，删去t ti i /x/xi i (i = 1, 2, (i = 1, 2, , n);, n); 2. 2.当当y yi i xx1 1,x,x2 2, , , , x xn n 时，删去时，删去u uj j/y/yj j (j = 1, 2, (j = 1, 2, , m), m) 最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。 合成即是对合成即是对t ti i先做先做 置换然

32、后再做置换然后再做 置换，置换置换，置换x xi i置换的合成例子置换的合成例子 设：设： f(y)/xf(y)/x, , z/yz/y ， a/x, a/x, b/yb/y, , y/zy/z ，求，求 与与 的合成。的合成。 解：先求出集合解：先求出集合 f(b/y)/xf(b/y)/x, (, (y/z)/yy/z)/y, a/x, , a/x, b/yb/y, , y/zy/z f(b)/xf(b)/x, , y/yy/y, a/x, , a/x, b/yb/y, , y/zy/z 其中，其中，f(b)/xf(b)/x中的中的f(bf(b) )是置换是置换 作用于作用于f(yf(y)

33、)的结果的结果; ;y/yy/y中的中的y y是置是置换换 作用于作用于z z的结果。的结果。 在该集合中，在该集合中，y/yy/y满足定义中的条件满足定义中的条件i i，需要删除；，需要删除；a/xa/x，b/yb/y满足满足定义中的条件定义中的条件iiii，也需要删除。，也需要删除。 最后得最后得 f(b)/xf(b)/x，y/zy/z 合一合一 合一合一可以简单地理解为可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致寻找相对变量的置换，使两个谓词公式一致”。 定义：定义： 设有公式集设有公式集F FFF1 1，F F2 2，F Fn n ，若存在一个置换，若存在一个置换 ，可使，

34、可使F F1 1 F F2 2 = F= Fn n ，则称，则称 是是F F的一个合一。同时称的一个合一。同时称F F1 1，F F2 2，. . ，F Fn n是可合一的。是可合一的。 例：例： 设有公式集设有公式集F F P(xP(x, y, , y, f(yf(y), ), P(a,g(x),zP(a,g(x),z)， 则则 a/x, a/x, g(a)/yg(a)/y, , f(g(a)/zf(g(a)/z 是它的一个合一。是它的一个合一。 注意：一般说来，一个公式集的合一不是唯一的。注意：一般说来，一个公式集的合一不是唯一的。 归结式归结式 C1,C2C1,C2是两个没有公共变量的子

35、句是两个没有公共变量的子句,L1,L2,L1,L2分别是分别是C1,C2C1,C2的文字的文字, ,如果如果L1L1与与 L2L2有有mgumgu , ,则则 R=(c1 R=(c1 -L1 -L1 ) ) (c2 (c2 -L2 -L2 ) 通俗的说通俗的说: :如果两个子句中分别有可以合一的互补文字如果两个子句中分别有可以合一的互补文字, ,则可以通过置换则可以通过置换, ,减去互补对的并集便是归结式减去互补对的并集便是归结式. . 例例: : 1. 1. P(xP(x) ) Q(x,yQ(x,y) ) 与与P(aP(a) ) R(b,zR(b,z) )的归结式为的归结式为 Q(a,yQ(

36、a,y) ) R(b,zR(b,z) ) 2.P(x,y) 2.P(x,y)Q(x)Q(x)R(x)R(x)与与P(a,zP(a,z)Q(bQ(b) )的归结式有以下两种的归结式有以下两种: : Q(a)R(aQ(a)R(a)Q(bQ(b) ) 或或 P(b,y)R(bP(b,y)R(b)P(a,zP(a,z) ) 归结的注意事项：归结的注意事项：1.1.谓词的一致性，谓词的一致性，P()P()与与Q()Q()，不可以归结，不可以归结2.2.常量的一致性，常量的一致性，P(aP(a, , ) )与与P(bP(b, ,.).)，不可以归结，不可以归结 变量，变量，P(aP(a, ,.).)与与P

37、(xP(x, ,) )，可以归结，可以归结3.3.变量与函数，变量与函数，P(xP(x, ,.).)与与P(f(xP(f(x),),) )，不可以归结；，不可以归结；4.4.不能同时消去两个互补对不能同时消去两个互补对5.5.先进行内部简化（置换、合并）先进行内部简化（置换、合并） 例例: : c1= c1=P(y)QP(y)Q(x)(x)R(g(xR(g(x), c2=), c2=P(f(g(aP(f(g(a)Q(bQ(b) )归结的过程归结的过程 写出谓词关系公式写出谓词关系公式 用反演法写出谓词表达式用反演法写出谓词表达式SKOLEMSKOLEM标准形标准形 子句集子句集S S 对对S

38、S中可归结的子句做归结中可归结的子句做归结 归结式仍放入归结式仍放入S S中，反复归结过程中，反复归结过程 得到空子句得到空子句得证得证例题例题“快乐学生快乐学生”问题问题 假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。证：张是快乐的。 解：先将问题用谓词表示如下：解：先将问题用谓词表示如下：R1:R1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考

39、试并获奖的人都是快乐的”( ( x)(Pass(xx)(Pass(x, , computer)Win(xcomputer)Win(x, , prize)Happy(xprize)Happy(x)R2:R2:“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”( ( x)(x)( y)(Study(x)Lucky(x)Pass(xy)(Study(x)Lucky(x)Pass(x, y), y)R3:R3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhangStudy(zhang)Lucky(zhang) )R4:R4:“任何幸运的人都能获奖任何幸运的人都能获奖”( ( x)(Luck(x)Win(x,prizex)(Luck(x)Win(x,prize)结论：结论：“张是快乐的张是快乐的”的否定的否定 Happy(zhangHappy(zhang) )由由R1R1及逻辑转换公式及逻辑转换公式:PWH = :PWH = （PWPW） H H ，可得，可得(1)(1)Pass(xPass(x, computer), computer)Win(xWin(x, , prize)Happy(xprize)Happy(x) )由由R2R2： (2)(2)Study(y)Pass(y,