人工智能六.ppt

例 S＝｛P(f(x)，a，g(y)，b)｝ H0 ={a, b} H1 ={a, b, f(a), f(b), g(a), g(b)} H2＝{a, b, f(a), f(b), g(a), g(b), f(f(a)), f(f(b)), f(g(a)), f(g(b)), g(f(a)), g(f(b)), g(g(a)), g(g(b))} … 练习: 求S的Herbrand域 S＝{P(x) ? Q(y)，R(z) } S＝{Q(a) ?～P(f(x))， ～Q(b) ? P(g(x,y)) } 原子集 基例 基：把对象中的变量用常量代替后得到的无变量符号出现的对象。 基项、基项集、基原子、基原子集合、基文字、基子句、基子句集 定义 (原子集、Herbrand底) 设S是子句集，形如P(t1,…,tn)的基原子集合，称为S的Herbrand底或S的原子集． 其中P(x1，…，xn)是出现于S的所有n元谓词符号，t1，…，tn是S的H域中的元素． 定义（基例） 设S是子句集，C是S中的一个子句．用S的H域中元素代替C中所有变量所得到的基子句称为子句C的基例。 练习 已知S＝｛P(f(x)，a，g(y)，b)｝，求S的原子集， 给出P(f(x)，a，g(y)，b)的一个基例。 已知S＝{P(x) ? Q(y)，R(z) }，求S的原子集， 分别给出P(x) ? Q(y)， R(z)的所有基例。 已知S＝ {Q(a)?～P(f(x))，～Q(b)? P(g(x,y))}， 求S的原子集， 分别给出Q(a)?～P(f(x)) ， ～Q(b)? P(g(x,y))的一个基例。 设S＝{P(x), Q(f(y)) ? R(y) }，求S的H域， S的原子集， P(x)的基例, Q(f(y)) ? R(y) 的基例。 H解释 定义（子句集的H解释） 设S是子句集，H是S的H域，I*是S在H上的一个解释．称I*为S的一个H解释，如果I*满足如下条件： 1） I*映射S中的所有常量符号到自身。 2）若f是S中n元函数符号，h1，…，hn是H中元素，则I*指定映射： (h1，…，hn) ?f (h1，…，hn) 设A={A1，A2，…，An， … } 是S的原子集。于是S的一个H解释I可方便地表示为如下一个集合： I* ＝｛m1，m2，…，mn，…｝ 其中, mi = H解释的例子 例 S={P(x)?Q(x), R(f(y)) } S的H域={a, f(a), f(f(a)), … } S的原子集： A={P(a), Q(a), R(a), P(f(a)), Q(f(a)), R(f(a)), … } S的H解释： I1* ={ P(a), Q(a), R(a), P(f(a)), Q(f(a)), R(f(a)), … } I2* ={ ～P(a), ～Q(a), R(a), P(f(a)), ～Q(f(a)), ～R(f(a)), … } 练习 S={P(x)?Q(x), ～P(a), ～Q(b) }， 求S的所有H解释。 二、Herbrand解释与普通解释的关系 子句集S的H解释是S的普通解释。 S的普通解释不一定是S的H解释：普通解释不是必须定义在H域上，即使定义在H域上，也不一定是一个H解释。 任取普通解释I，依照I，可以按如下方法构造S的一个H解释I*，使得若 S在 I下为真则 S在I*下也为真。 例. S＝｛P(x), Q(y,f(y,a))｝ 令S的一个解释I如下： D＝{1，2} a f(1, 1) f(1, 2) f(2, 1) f(2, 2) 2 1 2 2 1 P(1) P(2) Q(1, 1) Q(1, 2) Q(2, 1) Q(2, 2) T F F T F T 对应于I的H解释I*： I*＝｛～P(a), Q(a, a), P(f(a, a)), ～Q(a, f(a, a)), Q(f(a, a), a), ～Q(f(a, a), f(a, a)), …｝ 例 S={P(x), Q(y, f(y, z))} 令S的一个解