人工智能第六章2014PPT.ppt

例1 C1：P(x) ? Q(y) C2：~P(a) ? R(z) 例2 C1：P(x) ? Q(x) C2：~P(f(x)) ? R(x) 替换和合一是为了处理谓词逻辑中子句之间的模式匹配而引进. 一、替换与最一般合一替换 定义(替换)一个替换是形如{t1/v1, … , tn/vn }的一个有限集合，其中vi是变量符号，ti是不同于vi的项。并且在此集合中没有在斜线符号后面有相同变量符号的两个元素，称ti为替换的分子，vi为替换的分母。 例. {a/x, g(y)/y, f(g(b))/z}是替换; {x/x}, {y/f(x)}, {a/x, g(y)/y, f(g(b))/y}不是替换; 基替换:当t1,…,tn是基项时，称此替换为基替换。 空替换：没有元素的替换称为空替换，记为?。 替换 定义（改名） 设替换 ? ={ t1/x1, … , tn/xn } 如果t1, … , tn是不同的变量符号，则称?为一个改 名替换，简称改名。 替换作用对象：表达式（项、项集、原子、原子集、 文字、子句、子句集） 基表达式：没有变量符号的表达式。 子表达式：出现在表达式E中的表达式称为E的子 表达式。 E的例 定义（E的例） 设 ? ={ t1/v1, … , tn/vn }是一个替换，E是一个表达式。将E中出现的每一个变量符号，vi (1? i ?n) ，都用项ti替换，这样得到的表达式记为E?。称E? 为E的例。 若E? 不含变量，则E? 为E的基例。 例. 令 ? = {a/x, f(b)/y, c/z}，E=P(x, y, z) 于是E的例（也是E的基例）为 E? = P(a, f(b), c) 练习： E=P(x, g(y), h(x,z)), ?={a/x, f(b)/y, g(w)/z} E?=P(a, g(f(b)), h(a,g(w))) E=P(x, y, z), ?={y/x, z/y} E?=P(y, z, z). E??P(z, z, z). 替换的乘积 定义（替换的乘积）设? ={ t1/x1, … , tn/xn }，? ={ u1/y1, … , um/ym} 是两个替换。将下面集合 { t1?/x1, … , tn?/xn , u1/y1, … , um/ym } 中任意符合下面条件的元素删除： 1）ui/yi，当yi?{x1, … , xn }时； 2）ti?/xi，当ti? = xi 时。 如此得到一个替换，称为?与?的乘积，记为? ??。 例. 令 ? ={f(y)/x, z/y} ? ={a/x, b/y, y/z} 于是得集合 { t1?/x1, t2?/x2 , u1/y1, u2/y2 , u3/y3 } = {f(b)/x, y/y, a/x, b/y, y/z } ? 与?的乘积为 ? ?? = {f(b)/x, y/z } ?={a/x}, ?={b/x} ???={a/x} ???={b/x} 可见：??? ? ??? 例子: E=P(x, y, z) ?={a/x, f(z)/y, w/z} E?=P(a, f(z), w) ?={t/z, g(b)/w} (E?)?=P(a, f(t), g(b)) ???={a/x, f(t)/y, g(b)/z,g(b)/w} E???=P(a, f(t), g(b)) 引理 若E是表达式，?，?是两个替换， 则E (? ??) = (E?)? 证明： 设vi是E中任意一个变量符号，而 ? ={ t1/x1, … , tn/xn }， ? ={ u1/y1, … , um/ym } 若vi既不在{ x1, … , xn }中，也不在{ y1, … , ym }中，则vi在E (? ??)中和在(E?)?中都不变。 若vi=xj (1?j?n)，则E中的vi，在(E?)?中先变成tj，然后再变成tj?；E中的vi在E(???)中立即就变成了tj?。故E中vi在(E?)?中和在E(???)中有相同变化。 若vi=yj (1?j?m)，且yj?{ x1,…,xn }，则E中vi在(E?)?中变为uj;E中vi在E(???)中也变为uj(注意:yj?{x1,…, xn}，所以uj/yj????），故E中vi在(E?)?中和在E (??