《人工智能,第三章》由会员分享，可在线阅读，更多相关《人工智能,第三章（81页珍藏版）》请在金锄头文库上搜索。
1、谓词归结子句形( Skolem 标准形) 为了能够像命题逻辑那样进行 归结，首先必须解决谓词逻辑中的 量词问题。 前束范式：如果A中的一切量词都 位于该公式的最左边（不含否定词 ），且这些量词的辖域都延伸到公 式的末端。 谓词归结子句形( Skolem 标准形) Skolem标准形 前束范式中消去所有的量词。 Skolem函数 如果某个存在量词是在其他任意量词 的辖域内，就存在某种依赖关系，可 以用一个函数描述这种依赖关系，叫 做Skolem函数。 谓词归结子句形( Skolem 标准形) 量词消去原则： 存在量词。将该量词约束的变量用任意 常量（a，b等）或任意变量的函数（ f(x)，g(y
2、)等）代替。 左边有任意量词的存在量词，消去时该 变量改写成为任意量词的函数；如没有 ，改写成为常量。 任意量词。简单地省略掉该量词。 谓词归结子句形( Skolem 标准形) 例:将下式化为Skolem标准形： (x)(y)P(a, x, y) (x)(y)Q(y, b)R(x) 解： 第一步，消去，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) 第二步，深入到量词内部，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) (x)(y)P(a, x, y) (x) (y)Q(y, b) R(x) 第三步，任意量词左移，得： (x)(y)P
3、(a, x, y) (y)(Q(y, b) R(x) 谓词归结子句形( Skolem 标准形) 第四步，变量易名，存在量词左移，直至 所有的量词移到前面，得： (x)(y)P(a, x, y) (y)(Q(y, b) R(x) (x)(y)P(a, x, y) (z)(Q(z, b) R(x) (x)(y) (z) (P(a, x, y) Q(z, b) R(x) 由此得到前述范式 谓词归结子句形( Skolem 标准形) 第五步，消去存在量词，略去任意量 词 消去(y)，因为它左边只有(x)，所 以使用x的函数f(x)代替，这样得到： (x)(z)( P(a, x, f(x) Q(z, b)
4、 R(x) 消去(z)，同理使用g(x)代替，这样 得到： (x) ( P(a, x, f(x) Q(g(x), b) R(x) 略去任意量词，原式的Skolem标准形为： P(a, x, f(x) Q(g(x), b)R(x) 谓词归结子句形( Skolem 标准形) Skolem定理： 谓词逻辑的任意公式都可以化为 与之等价的前束范式，但其前束 范式不唯一。 注意：谓词公式G的Skolem标准形 同G并不等值。 谓词归结子句形 子句与子句集 文字：不含任何连接词的谓词公式。 子句：一些文字的析取（谓词的和）。 空子句：不含任何文字的子句。记作NIL或 子句集：所有子句的集合。 对于任何一个
5、谓词公式G，都可以通过 Skolem标准形，建立起一个子句集与之对 应。 谓词归结子句形 子句集S的求取： 将谓词公式G转换成前束范式； 生成Skolem标准形； 将各个子句提出，以“，”取代“”，并表示 为集合形式 。 谓词归结子句形 定理3.1 谓词公式G是不可满足的，当且 仅当其子句集 S是不可满足的。 G与S不等价，但在不可满足的意义下是一 致的。 注意：G真不一定S真，而S真必有G真。 即： S = G 谓词归结子句形 定理3.1的推广 对于形如G = G1 G2 G3 Gn 的谓词公式 G的子句集可以分解成几个部分单独处 理。 有 SG = S1 U S2 U S3 U U Sn
6、则SG 与 S1 U S2 U S3 U U Sn在不可满 足的意义上是一致的。即SG 不可满足 S1 U S2 U S3 U U Sn不可满足。 可以对一个复杂的谓词公式分而治之。 求取子句集例(1) 例：对所有的x,y,z来说，如果y是x的父亲，z又 是y的父亲，则z是x的祖父。又知每个人都有 父亲，试问对某个人来说谁是他的祖父？ 求：用一阶逻辑表示这个问题，并建立子句集 。 解：这里我们首先引入谓词： P(x, y) 表示y是x 的父亲 Q(x, y) 表示y是x的祖父 ANS(x) 表示问题的解答 求取子句集例(2) 对于第一个条件，“如果y是x的父亲， z又是y的父亲，则z是 x的祖
7、父”，一阶逻辑表达式如下： A1：(x)(y)(z)(P(x, y)P(y, z)Q(x, z) S A1：P(x ,y)P(y, z)Q(x, z) 对于第二个条件：“每个人都有父亲”，一阶逻辑表达式： A2：(x)(y)P(x, y) S A2：P(x,f(x) 对于结论：某个人是他的祖父 B：(x)(y)Q(x, y) 否定后得到子句： ( (x)(y)Q(x, y)ANS(y) SB：Q(x, y)ANS(y) 则得到的相应的子句集为： S A1，S A2，SB 置换与合一 一阶谓词逻辑得归结比命题逻辑的 归结要复杂的多，其中一个原因就 是谓词逻辑公式中含有个体变量与 函数。 如P(x
8、) Q(y)与P(a) R(z) 所以要考虑置换与合一。即对变量 作适当的替换。 置换 置换：可以简单的理解为是在一个谓词公式中用 置换项去置换变量。 定义： 置换是形如t1/x1, t2/x2, , tn/xn的有限集合。其 中，x1, x2, , xn是互不相同的变量，t1, t2, , tn是 不同于xi的项（常量、变量、函数）；ti/xi表示用 ti置换xi，并且要求ti与xi不能相同，而且xi不能循 环地出现在另一个ti中。 例如： a/x，c/y，f(b)/z是一个置换。 g(y)/x，f(x)/y不是一个置换。 置换的合成 设t1/x1, t2/x2, , tn/xn， u1/y
9、1, u2/y2, , un/yn，是两个置换。 则与的合成也是一个置换，记作。它是从集合 t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , un/yn 中删去以下两种元素： 当ti=xi时，删去ti/xi (i = 1, 2, , n); 当yix1,x2, , xn时，删去uj/yj (j = 1, 2, , m) 最后剩下的元素所构成的集合。 合成即是对ti先做置换然后再做置换 置换的合成 例： 设：f(y)/x, z/y，a/x, b/y, y/z，求与的合 成。 解：先求出集合 f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x,
10、 y/y, a/x, b/y, y/z 其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y 中的y是置换作用于z的结果。在该集合中，y/y满 足定义中的条件i，需要删除；a/x，b/y满足定义中 的条件ii，也需要删除。最后得 f(b)/x，y/z 合一 合一可以简单地理解为“寻找相对变量的置换， 使两个谓词公式一致”。 定义：设有公式集FF1，F2，Fn，若存在 一个置换，可使F1F2= Fn，则称是F 的一个合一。同时称F1，F2，. ，Fn是可合一的 。 例： 设有公式集FP(x, y, f(y), P(a,g(x),z)，则 a/x, g(a)/y, f(g(a)/z是它
11、的一个合一。 注意：一般说来，一个公式集的合一不是唯一的。 最一般合一（mgu） 设是谓词公式集F的一个合一，如果对F的任意 一个合一都存在一个置换，使得=.，则称 是一个最一般合一。 最一般合一求取方法 令W=F1,F2 令k=0,W0=W, 0= 如果Wk已合一，停止， k=mgu,否则找Dk 若Dk中存在元素vk和tk，其中，vk不出现在tk中，转下 一步，否则，不可合一。 令k+1= k.tk/vk,Wk+1=Wktk/vk=W k+1 K=k+1转第3步。 最一般合一（mgu） 例：W=P(a,x,f(g(y),P(z,f(a),f(u),其中， F1 P(a,x,f(g(y)，F2
12、 P(z,f(a),f(u) 求F1和F2的mgu 解：由mgu算法 (1)W= P(a,x,f(g(y),P(z,f(a),f(u) (2)W0=W,0= (3) W0 未合一，从左到右找差异集，有 D0=a,z (4)取V0=z,t0a 最一般合一（mgu） (5)令1= 0. t0/v0=a/z W1= W0 1=P(a,x,f(g(y),P(a,f(a),f(u) (3) W1 未合一，找差异集，有D1=x,f(a) (4)取v1=x,t1f(a) (5)令2=1. t1/v1= a/z,f(a)/x W2= W12=P(a,f(a),f(g(y),P(a,f(a),f(u) (3)
13、W2 未合一，找差异集，有D2=g(y),u (4)取v2=u,t2g(y) 最一般合一（mgu） (5)令3=2. t2/v2=a/z,f(a)/x,g(y)/u W3= W2 3=P(a,f(a),f(g(y),P(a,f(a),f(g(y) (3) W3 已合一 3= a/z,f(a)/x,g(y)/u 便是F1和F2的mgu。 算法的第(4)步，当不存在vk或不存在tk或出 现差异集为x,f(x),都会导致不可合一。此 时，算法返回失败。 最一般合一（mgu） 谓词逻辑的归结方法和命题逻辑基本 相同，但在进行归结之前，应采用最一般 合一方法对待归结的一对子句进行置换。 然后再判断是否可
14、以进行归结。 归结原理 归结时的注意事项： n谓词的一致性，P()与Q()， 不可以 n常量的一致性，P(a, )与P(b,.)， 不可以。 变量与函数，P(a, x, .)与P(x, f(x), )，不可以； n不能同时消去两个互补对，PQ与P Q得空，不可以 n先进行内部简化再进行置换与合并。 归结原理 归结的过程 写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准形 求子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 命题得证。 例题“快乐学生”问题 例：假设任何通过计算机考试并获奖的人都是快 乐的，任何肯学习或幸运的人都可以通过所有 的考试，张不肯学习但他是幸运的，任何幸运 的人都能获奖。求证：张是快乐的。 解：先将问题用谓词表示如下： R1:任何通过计算机考试并获奖的人都是快乐的 (x)(Pass(x, computer)Win(x, prize)Happy(x) R2:“任何肯学习或幸运的人都可以通过所有考 试” (x)(y)(Study(x)Lucky(x)Pass(x, y) 例题“快乐学生”问题 R3:“
