人工智能第六章6.3-6.5.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,6.3,合一算法,1/12/2026,1,例：,C,1,：,P(x,),Q(x,),C,2,：,P(f(x,),R(x,),没有互补对,;,C,1,：,P(y,),Q(y,),y/x,C,1,：,P(f(x,),Q(,f(x,),),f(x)/y,C,3,：,R(x,),Q(,f(x,),),替换和合一是为了处理谓词逻辑中子句之间的模式匹配而引进.,1/12/2026,2,一、替换与最一般合一替换,定义,(,替换,),一个替换是形如,t,1,/v,1,t,n,/v,n,的一个有限集合，其中,v,i,是变量符号，,t,i,是不同于,v,i,的项。并且在此集合中没有在斜线符号后面有相同变量符号的两个元素，称,t,i,为替换的分子，,v,i,为替换的分母。,例,.,a/x,g(y)/y,f(g(b)/z,是,替换,;,x/x,y/f(x,),a/x,g(y)/y,f(g(b)/y,不是,替换,;,基替换,:,当,t,1,t,n,是基项时，称此替换为基替换。,空替换：,没有元素的替换称为空替换，记为,。,1/12/2026,3,替换,定义（改名）,设替换,=t,1,/x,1,t,n,/x,n,如果,t,1,t,n,是不同的变量符号，则称,为一个改名替换，简称改名。,替换作用对象：,表达式,（项、项集、原子、原子集、文字、子句、子句集）。,基表达式：,没有变量符号的表达式。,子表达式：,出现在表达式,E,中的表达式称为,E,的子表达式。,1/12/2026,4,E,的例,定义（,E,的例）,设,=t,1,/v,1,t,n,/v,n,是一个替换，,E,是一个表达式。将,E,中出现的每一个变量符号，,v,i,(1,i,n),，都用项,t,i,替换，这样得到的表达式记为,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),1/12/2026,5,练习：,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).,1/12/2026,6,替换的乘积,定义（替换的乘积）,设,=t,1,/x,1,t,n,/x,n,，,=u,1,/y,1,u,m,/,y,m,是两个替换。将下面集合,t,1,/x,1,t,n,/x,n,u,1,/y,1,u,m,/,y,m,中任意符合下面条件的元素删除：,1,）,u,i,/y,i,，当,y,i,x,1,x,n,时；,2,）,t,i,/x,i,，当,t,i,=x,i,时。,如此得到一个替换，称为,与,的乘积，记为,。,例,.,令,=,f(y)/x,z/y,=a/x,b/y,y/z,于是得集合,t,1,/x,1,t,2,/x,2,u,1,/y,1,u,2,/y,2,u,3,/y,3,=,f(b)/x,y/y,a/x,b/y,y/z,与,的乘积为,=,f(b)/x,y/z,1/12/2026,7,=,a/x,=,b/x,=,a/x,=,b,/x,可见：,1/12/2026,8,例子,:,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,),1/12/2026,9,引理,若,E,是表达式，,，,是两个替换，则,E,(,),=(E,),证明：,设,v,i,是,E,中任意一个变量符号，而,=t,1,/x,1,t,n,/x,n,，,=u,1,/y,1,u,m,/,y,m,若,v,i,既不在,x,1,x,n,中，也不在,y,1,y,m,中，则,v,i,在,E,(,),中和在,(E,),中都不变。,若,v,i,=,x,j,(1,j,n),，则,E,中的,v,i,，在,(E,),中先变成,t,j,，然后再变成,t,j,；,E,中的,v,i,在,E,(,),中立即就变成了,t,j,。故,E,中,v,i,在,(E,),中和在,E,(,),中有相同变化。,若,v,i,=,y,j,(1,j,m),，且,y,j,x,1,x,n,，则,E,中,v,i,在,(E,),中变为,u,j;,E,中,v,i,在,E,(,),中也变为,u,j,(,注意,:,y,j,x,1,x,n,，所以,u,j,/y,j,），故,E,中,v,i,在,(E,),中和在,E,(,),中有相同变化。,由于,v,i,的任意性，故引理得证。,1/12/2026,10,引理,设,，,，,是三个替换，于是,(,),(,),证明：设,E,是任一表达式，由上面引理知,E,(,),),=(E,(,),),=(E,),),E,(,(,),=(E,),(,),=(E,),),所以,E,(,),),=E,(,(,),由于,E,的任意性，故,(,),(,),1/12/2026,11,定义,(,合一,),称替换,是表达式集合,E,1,E,k,的合一，当且仅当,E,1,E,2,=,E,k,。,表达式集合,E,1,E,k,称为可合一的，如果存在关于此集合的一个合一。,定义,(,最一般合一,),表达式集合,E,1,E,k,的合一,称为是最一般合一,(most general unifier,简写为,mgu,),，当且仅当对此集合的每一个合一,，都存在替换,，使得,1/12/2026,12,二、,合一算法,定义（差异集合）,设,W,是非空表达式集合，,W,的差异集合是如下一个集合：首先找出,W,的所有表达式中不是都相同的第一个符号，然后从,W,的每一个表达式中抽出占有这个符号位置的子表达式。所有这些子表达式组成的集合称为这步找到的,W,的差异集合,D,。,1/12/2026,13,W,不可合一的三种情况,（,1,）若,D,中无变量符号为元素，则,W,是不可合一的。,例,.,W=,P(f(x,),P(g(x,),D=,f(x,),g(x,),（,2,）若,D,中有奇异元素和非奇异元素，则,W,是不可合一的。,例,.W=,P(x,),P(x,y),D=,y,（,3,）若,D,中元素有变量符号,x,和项,t,，且,x,出现在,t,中，则,W,是不可合一的。,例,.,W=,P(x,),P(f(x,),D=x,f(x,),1/12/2026,14,换名,:,P(f(x,),x),P(x,a);,如果不换名：,D=,f(x,),x.,换名,:,P(f(y,),y),P(x,a);,mgu,:,f(a)/x,a/y,1/12/2026,15,步骤,1,：置,k=0,W,k,=W,k,=,步骤,2,：若,W,k,只有一个元素，则停止，,k,是,W,的最一般合一；,否则，找出,W,k,的差异集合。,步骤,3,：若,D,k,非奇异，,D,k,中存在元素,v,k,和,t,k,，其中,v,k,是变量符号，并且 不出现在,t,k,中，则转步骤,4,；,否则，算法停止，,W,是不可合一的。,步骤,4,：令,k+1,=,k,t,k,/v,k,，,W,k+1,=W,k,（注：,W,k+1,=W,）,步骤,5,：置,k=k+1,，转步骤,2,。,合一算法（,Unification algorithm,）,1/12/2026,16,例,.,令,W=,Q(f(a,),g(x,),Q(y,y),求,W,的,mgu,。,步骤,1,：,k=0,W,0,=W,0,=,。,步骤,2,：,D,0,=,f(a,),y,。,步骤,3,：有,v,0,=y,D,0,，,v,0,不出现在,t,0,f(a,),中。,步骤,4,：令,1,=,0,t,0,/v,0,=,f(a)/y,W,1,=,Q(f(a,),g(x,),Q(f(a,),f(a,),步骤,5,：,k=k+1=1,步骤,2,：,D,1,=,g(x,),f(a,),。,步骤,3,：,D,1,中无变量符号，算法停止，,W,不可合一。,1/12/2026,17,例,令,W=,P(a,x,f(g(y,),P(z,f(z,),f(u,),，求出,W,的,mgu,。,步骤,1,：,k=0,W,0,=W,0,=,。,步骤,2,：,D,0,=a,z,。,步骤,3,：有,v,0,=z,D,0,，,v,0,不出现在,t,0,a,中。,步骤,4,：令,1,=,0,t,0,/v,0,=,a/z=a/z,，,W,1,=W,0,t0/v0,=,P(a,x,f(g(y),P(z,f(z),f(u),a/z,=,P(a,x,f(g(y),P(a,f(a),f(u,),步骤,5,：,k=k+1=1,步骤,2,：,D,1,=x,f(a,),。,步骤,3,：有,v,1,=x,D,1,，且,v,1,不出现在,t,1,f(a,),中。,步骤,4,：令,2,=,1,t,1,/v,1,=a/z,f(a)/x,=a/z,f(a)/x,，,W,2,=W,1,t1/v1,=,P(a,x,f(g(y),P(a,f(a),f(u),f(a)/x,=,P(a,f(a),f(g(y),P(a,f(a),f(u,),1/12/2026,18,例,.,步骤,5,：,k=k+1=2,步骤,2,：,D,2,=,g(y,),u,。,步骤,3,：有,v,2,=u,D,2,，且,v,2,不出现在,t,2,g(y,),中。,步骤,4,：令,3,=,2,t,2,/v,2,=a/z,f(a)/x,g(y)/u,=a/z,f(a)/x,g(y)/u,，,W,3,=W,2,t2/v2,=,P(a,f(a,),f(g(y,),P(a,f(a,),f(u,),g(y)/u,=,P(a,f(a,),f(g(y,),步骤,5:k=k+1=3,步骤,2,：,W,3,只有一个元素。算法停止。,3,=a/z,f(a)/x,g(y)/u,是,W,的最一般合一。,1/12/2026,19,定理,若,W,是关于表达式的,有限非空可合一,集合，则合一算法终将结束在步骤,2,，并且最后的,k,是,W,的最一般合一。,证明：,（,1,）终止性,。,否则将产生一个无穷序列：,W,，,W,，,，,W,，,其中每一个直接后继集合比它的前任都少一个变量符号（注意：,W,包含,v,k,，而,W,不包含,v,k,）。但这是不可能的，因为,W,仅含有限个变量符号。,（,2,）,k,是,W,的合一。若算法停止在步骤,2,，则,W,k,=W,只含有一个元素，所以,k,是,W,的合一。,1/12/2026,20,（,3,）,用归纳法证明算法必不会停止在步骤,3,，并且对任意,W,的一个合一,，任意,k,，都存在替换,k,，使得,=,k,k,亦即,k,是,W,的,mgu,。,当,k=0,时，因,0,=,，取,0,=,，于是,=,=,0,0,。,1/12/2026,21,假设对,0,k,n,，,=,k,k,成立,往证：存在,n+1,，使得,=,n+1,n+1,。,若,W,只含有一个元素，则合一算法结束在步骤,2,。因为,=,n,n,，且,n,是,W,的合一，故,n,是,W,的,mgu,。定理得证。,若,W,不只含有一个元素,按照算法,将找出,W,的差异集合,D,n,。,因为,=,n,n,是,W,的合一，所以,W,中表达式经替换,作用后都变成同一个相同的表达式。而,W,中表达式经,n,作用后，产生了差异集合,D,n,，所以,D,n,必须被,n,所统一，即,n,是,D,n,的合一。,1/12/2026,22,因为,D,n,是可合一的（,n,就是,D,n,的合一），所以必有变量符号,v,n,D,n,；,D,n,中至少有两个不同元素。所以可设,t,n,D,n,，且,t,n,v,n,。显然，变量符号,v,n,不出现在,t,n,中（否则，,v,n,n,t,n,n,，这与,n,是,D,n,的合一矛盾）。,因此算法不能停止在步骤,3,，所以算法必然停止在步骤,2,。,1/12/2026,23,令,n+1,=,n,t,n,/v,n,。因为,v,n,n,=,t,n,n,所以,t,n,n,/v,n,n,令,n+1,=,n,-,t,n,n,/v,n,。因,v,n,不出现在,t,n,中，所以,于是,故,归纳法完成。即对所有,k0,都存在替换,k,，使,=,k,k,。所以算法终止步骤,2,时，,k,是,W,的最一般合一。,1/12/2026,24,6.4,一阶逻辑中的归结原理,1/12/2026,25,定义（因子）,如果子句,C,中，两个或两个以上的文字有一个最一般合一,，则,C,称为,C,的因子；,如果,C,是单元子句，则,C,称为,C,的单因子。,例,.C=,P(x,),P(f(y,),Q(x,),令,f(y)/x,，于是,C,=,P(f(y,),Q(f(y,),是,C,的因子。,1/12/2026,26,二元归结式,定义 设,C,1,C,2,是两个,无公共变量,的子句,(,称为亲本子句,),L,1,L,2,分别是,C,1,C,2,中的两个文字。,如果,L,1,和,L,2,有最一般合一，则子句,(C,1,-L,1,),(C,2,-L,2,),称为,C,1,和,C,2,的二元归结式，,L,1,和,L,2,称为归结文字。,例,.,设,C,1,=,P(x,),Q(x,),C,2,=,P(a,),R(x,),将,C,2,中,x,改名为,y,。取,L,1,P(x,),L,2,=,P(a,),=a/x,于是,(C,1,-L,1,),(C,2,-L,2,),(,P(a,),Q(a)-P(a,),(,P(a,),R(y,)-,P(a,),=,Q(a,),R(y,)=,Q(a,),R(y,),-,C,1,和,C,2,的二元归结式,.,1/12/2026,27,在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：,（,1,）若被归结的子句,C,1,和,C,2,中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法合一，从而没有办法进行归结。,（,2,）在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。,（,3,）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的化简。,1/12/2026,28,归结式,定义 子句,C,1,C,2,的一个归结式是下列二元归结式之一：,C,1,和,C,2,的二元归结式。,C,1,和,C,2,的因子的二元归结式。,C,1,的因子和,C,2,的二元归结式。,C,1,的因子和,C,2,的因子的二元归结式。,例,.,设,C,1,=,P(x,),P(f(y,),R(g(y,),C,2,=,P(f(g(a,),Q(b,),C,1,的因子,C,1,=,P(f(y,),R(g(y,),。于是,C,1,和,C,2,的二元归结式，从而也是,C,1,和,C,2,的归结式为,R(g(g(a,),Q(b,),1/12/2026,29,一阶逻辑归结原理的完备性,提升引理,如果,C,1,和,C,2,分别是子句,C,1,和,C,2,的例，,C,是,C,1,和,C,2,的归结式，则存在,C,1,和,C,2,的一个归结式,C,，使,C,是,C,的例。,1/12/2026,30,一阶逻辑归结原理的完备性,定理,若子句集,S,是不可满足的，则存在从,S,推出空子句的归结演绎。,证明,:,设子句集,S,是不可满足的，由,Herbrand,定,理,II,知，存在,S,的一个基例集,S,也是不可满足的。根据命题,逻辑归结原理的完备性,，存在从,S,推出空子句的归结演绎,D,。由提升引理知，可将,D,提升成一个从,S,推出空子句的归结演绎,D,。定理得证。,1/12/2026,31,6.5,归结原理的几种改进,1/12/2026,32,一、支架集归结,定义子句集,S,的子集,T,称为,S,的支架集，如果（,S-T,）是可满足的。一个支架集归结是一个不同时属于（,S-T,）的两个子句的归结。,例,.,设,S,是如下子句集：,(1)PQ,(2)P,Q,(3),PQ,(4),P,Q,令,T=PQ,，显然,T,是支架集。如下的演绎是支架集归结演绎：,(5)P,由,(1),、,(2),(6)Q,由,(1),、,(3),(7),Q,由,(5),、,(4),(8),由,(6),、,(7),1/12/2026,33,二、语义归结,定义（语义互撞）,设,I,是子句集,S,的一个解释，,P,是,S,中谓词符号的一个顺序，有限子句序列,E,1,E,q,N (q,1),称为关于,P,和,I,的语义互撞（简称,PI-,互撞），当且仅当,E,1,E,q,N,满足下面条件：,E,1,E,q,在,I,下为假；,令,R,1,=N,，对每个,i=1,q,，存在,R,i,和,E,i,的归结式,R,i+1,。,E,i,中的归结文字是,E,i,中最大谓词符号。,R,q+1,在,I,下为假。,于是，,R,q+1,称为此,PI-,互撞的,PI-,归结式。,1/12/2026,34,例,.,设,S,是如下子句集：,(1),P,QR,(2)PR,(3)QR,(4),R,令,I=,P,Q,R,，,P,Q,R,。于是在,I,下为假的子句只有两个：,Si=PR,QR,我们可得如下,PI-,演绎：,(5)R,由,(2),、,(3),、,(1),(6),由,(5),、,(4),1/12/2026,35,三、线性归结,定义（线性归结演绎）,设,S,是一个子句集，,C,0,是,S,中的一个子句。以,C,0,为顶子句，从,S,到,C,n,的线性归结演绎是如下一个演绎：,对于,i=0,1,n-1,，,C,i+1,是,C,i,和,B,i,的归结式。,每个,B,i,或者属于,S,，或者是一个,C,j,，其中,j,i,。,1/12/2026,36,四、锁归结,定义（锁归结式）,设,C,是子句，若将,C,中每一个文字都附上一个整数，则称子句,C,已配锁。设,C,1,和,C,2,是两个配锁子句，,R(C,1,C,2,),是,C,1,和,C,2,的归结式，如果,C,1,和,C,2,中的归结文字分别是,C,1,和,C,2,中带有最小锁的文字，则称,R(C,1,C,2,),为,C,1,和,C,2,的锁归结式。,例,.,设,S,是如下配锁子句集,1P2Q,3P4,Q,6,P5Q,8,P7,Q,于是，从,S,推出的锁演绎如下：,(5)6,P (3),、,(4),(6)2Q (1),、,(5),(7)4,Q,(8),1/12/2026,37,五、广义归结,定义（广义子句）,设,A,1,A,n,是一些原子,(A,1,A,n,),是以逻辑联结词,、,、,、,、,联结这些原子和一些,0,，,1,做成的公式,称为广义子句,其,中,0,代表,F,，,1,代表,T,。,如果一个广义子句中没有原子，只有,0,或者,1,，则称其为,常子句。,其值为,0,的常子句称为零子句，其值为,1,的常子句称为壹,子句。,定义,（,广义子句的因子,）,设,(A,1,A,n,),是一个广义子句，,A,i1,A,ir,有一个,mgu,（,1,i,j,n,j=1,r,），则称,为,的因子。,1/12/2026,38,定义（广义归结式）,设,是无公共变元的广义子句,是合一,A,i1,A,ir,所得的因子，,是合一,B,j1,B,js,所得的因子。设,是,A,i1,和,B,j1,的,mgu,，于是，,(A,i1,=0),(B,j1,=1),(A,i1,=1),(B,j1,=0),都称为,与,的广义归结式。,1/12/2026,39,例,.,设,S,是如下一个广义子句集：,(1)P,Q,(2)P,(3),Q,从,S,推出零子句的一个广义归结演绎如下：,(4)(1,Q)0 (1),、,(2),(5)(1,0)0(,1)=0 (3),、,(4),1/12/2026,40,