归结反演

       上承

   设已知下列句子：

   （1）Whoever can read is literate（能阅读的都是有文化的）。

               ("x)[R(x) ® L(x)]

   （2）Dolphins are not literate（海豚是没有文化的）。

               ("x)[D(x) ® ØL(x)]

   （3）Some dolphins are intelligent（某些海豚是有智能的）。

               ($z)[D(z)ÙI(z)]

    证明语句：

   （4）Some who are intelligent cannot read（某些有智能的并不能阅读）。

               ($w)[I(w)ÙØR(w)]

    已知的三个语句对应的子句集为

   （1）{ØR(x)Ú L(x)}

   （2）{ØD(y)ÚØ L(y)} 

   （3）{D(A)Ú I(A)} 

目标语句的否定为

        ("w)[ØI(w)ÚR(w)]

将目标语句的否定式化成子句形式：

   （4） {ØI(w)ÚR(w)}

   采用归结反演方法，根据（1）——（4）列出的子句集进行归结，将归结式加入到子句集中去，再继续进行归结，直至产生空子句或无法归结为止。如果归结出空子句，则证明成功的结束。本例的归结过程如下图所示：

                           图4—1

    上图为上面例子的一棵反演树，它由空子句及其祖先组成。图中的结点表示子句和子句生成的归结式。图中并没有画出所有生成的结点，我们称包括所有生成的结点的整个搜索图为引导图。

    归结反演过程主要就是证明一个集合S是不可满足的过程，即从集合S归结出空子句的过程。该过程可表示如下：

    过程RESOLUTION

    (1) cLAUSES ¬ S

    (2) until NIL Î cLAUSES,do

    (3)   begin

    (4)   在cLAUSES中选则两个不同的可归结的子句c_i和c_j。

    (5)   计算c_i和c_j的归结式r_ij

    (6)   cLAUSES ¬  cLAUSES ∪{r_ij}

    (7)   end

    习题

    1、用归结反演法证明下列公式的永真性。

    (1)  ($x){[P(x)® P(A)]Ù[P(x)® P(b)]}

    (2)    ("z)[Q(z) ® P(z)]® ($x){[Q(x)® P(A)]Ù[Q(x)® P(b)]}

    2、我们来考虑下列一段指示：Tony、Mike和John属于Alpine俱乐部，Alpine俱乐部的成员不是滑雪运动员就是登山运动员。登山运动员不喜欢雨，而且任何不喜欢雪的人不是滑雪运动员。Mike讨厌Tony所喜欢的一切东西，而喜欢Tony所讨厌的一切东西。Tony喜欢雨和雪。

    以谓词演算语句的集合表示这段知识，用归结反演的方法回答问题：“有没有Alpine俱乐部的一个成员，他是一个登山运动员但不是一个滑雪运动员呢？”  

                                    返回