人工智能第六章6.3-6.5VIP免费

12/29/2416.3合一算法12/29/242例：–C1：P(x)Q(x)–C2：~P(f(x))R(x)没有互补对;–C1：P(y)Q(y){y/x}–C1：P(f(x))Q(f(x)){f(x)/y}–C3：R(x)Q(f(x))替换和合一是为了处理谓词逻辑中子句之间的模式匹配而引进.12/29/243一、替换与最一般合一替换定义(替换)一个替换是形如{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是基项时，称此替换为基替换。空替换：没有元素的替换称为空替换，记为。12/29/244替换定义（改名）设替换={t1/x1,…,tn/xn}如果t1,…,tn是不同的变量符号，则称为一个改名替换，简称改名。替换作用对象：表达式（项、项集、原子、原子集、文字、子句、子句集）。基表达式：没有变量符号的表达式。子表达式：出现在表达式E中的表达式称为E的子表达式。12/29/245E的例定义（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)12/29/246练习：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).12/29/247替换的乘积定义（替换的乘积）设={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}12/29/248={a/x},={b/x}={a/x}={b/x}可见：12/29/249•例子:–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))12/29/2410引理若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()中有相同变化。由于vi的任意性，故引理得证。12/29/2411引理设，，是三个替换，于是()＝()证明：设E是任一表达式，由上面引理知E(())=(E())=((E))E(())=(E)()=((E))所以E(())=E(())由于E的任意性，故()＝()12/29/2412定义(合一)称替换是表达式集合{E1,…,Ek}的合一，当且仅当E1＝E2=…=Ek。表达式集合｛E1,…,Ek｝称为可合一的，如果存在关于此集合的一个合一。定义(最一般合一)表达式集合｛E1,…,Ek｝的合一称为是最一般合一(mostgeneralunifier,简写为mgu)，当且仅当对此集合的每一个合一，都存在替换，使得＝12/29/2413二、合一算法定义（差异集合）设W是非空表达式集合，W的差异集合是如下一个集合：首先找出W的所有表达式中不是都相同的第一个符号，然后从W的每一个表达式中抽出占有这个符号位置的子表达式。所有这些子表达式组成的集合称为这步找到的W的差异集合D。12/29/2414W不可合一的三...