1、8/10/202216.3 合一算法合一算法8/10/20222例：例：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)l替换和合一是为了处理谓词逻辑中子句之间的模式匹配而引进.8/10/20223一、替换与最一般合一替换一、替换与最一般合一替换l定义定义(替换替换)一个替换是形如一个替换是形如t1/v1,tn/vn 的一个有限集合，其中的一个有限集合，其中vi是变量符号，是变量符号，ti是不是不同于同于vi的项。并且在此集合中没有在斜线符的项。并且在此集合中没有在斜线符号
2、后面有相同变量符号的两个元素，称号后面有相同变量符号的两个元素，称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是基项时，称此替换为基替换。是基项时，称此替换为基替换。空替换：空替换：没有元素的替换称为空替换，记为没有元素的替换称为空替换，记为。8/10/20224替换定义（改名）定义（改名）设替换设替换 =t1/x1,tn/xn 如果如果t1,tn是不同的变量符号，则称是不同的变量符号，则称 为一个改为一个改名替
3、换，简称改名。名替换，简称改名。替换作用对象：替换作用对象：表达式表达式（项、项集、原子、原子集、（项、项集、原子、原子集、文字、子句、子句集）。文字、子句、子句集）。基表达式：基表达式：没有变量符号的表达式。没有变量符号的表达式。子表达式：子表达式：出现在表达式出现在表达式E中的表达式称为中的表达式称为E的子的子表达式。表达式。8/10/20225E的例l 定义（定义（E的例）的例）设设 =t1/v1,tn/vn 是一个是一个替换，替换，E是一个表达式。将是一个表达式。将E中出现的每一个中出现的每一个变量符号，变量符号，vi(1 i n)，都用项，都用项ti替换，这样替换，这样得到的表达式记
4、为得到的表达式记为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)8/10/20226练习：l E=P(x,g(y),h(x,z),=a/x,f(b)/y,g(w)/zE=P(a,g(f(b),h(a,g(w)l E=P(x,y,z),=y/x,z/y E=P(y,z,z).EP(z,z,z).8/10/20227替换的乘积替换的乘积 l定义（替换的乘积）定义（替换的乘积）设设 =t1/x1,tn/xn，=u
5、1/y1,um/ym 是两个替换。将下面集合是两个替换。将下面集合 t1/x1,tn/xn,u1/y1,um/ym 中任意符合下面条件的元素删除：中任意符合下面条件的元素删除：1）ui/yi，当，当yi x1,xn 时；时；2）ti/xi，当，当ti =xi 时。时。如此得到一个替换，称为如此得到一个替换，称为 与与 的乘积，记为的乘积，记为 。l例例.令令 =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 8/10/
6、20228=a/x,=b/x =a/x =b/x可见：8/10/20229 例子例子: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)8/10/202210引理引理 若若E是表达式，是表达式，是两个替换，是两个替换，则则E()=(E)证明：证明：设设vi是是E中任意一个变量符号，而中任意一个变量符号，而 =t1/x1,tn/xn，=u1/y1,um/ym l若若vi既不在既不在 x1,xn 中，也不在中，也不在 y1,ym 中，
7、则中，则vi在在E()中和在中和在(E)中都不变。中都不变。l若若vi=xj(1 j n)，则，则E中的中的vi，在，在(E)中先变成中先变成tj，然后，然后再变成再变成tj；E中的中的vi在在E()中立即就变成了中立即就变成了tj。故。故E中中vi在在(E)中和在中和在E()中有相同变化。中有相同变化。l若若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的任意性，故引
8、理得证。的任意性，故引理得证。8/10/202211引理引理 设设，是三个替换，是三个替换，于是于是()()证明：证明：设设E是任一表达式，由上面引理知是任一表达式，由上面引理知 E()=(E()=(E)E()=(E)()=(E)所以所以 E()=E()由于由于E的任意性，故的任意性，故()()8/10/202212l定义定义(合一合一)称替换称替换 是表达式集合是表达式集合E1,Ek的的合一，当且仅当合一，当且仅当E1 E2=Ek。表达式集合表达式集合E1,Ek称为可合一的，如果称为可合一的，如果存在关于此集合的一个合一。存在关于此集合的一个合一。l定义定义(最一般合一最一般合一)表达式集合
9、表达式集合E1,Ek的合一的合一 称为是最一般合一称为是最一般合一(most general unifier,简写为简写为mgu)，当且仅当对此集合的每，当且仅当对此集合的每一个合一一个合一，都存在替换，都存在替换，使得，使得 8/10/202213二、合一算法二、合一算法定义（差异集合）定义（差异集合）设W是非空表达式集合，W的差异集合是如下一个集合：首先找出W的所有表达式中不是都相同的第一个符号，然后从W的每一个表达式中抽出占有这个符号位置的子表达式。所有这些子表达式组成的集合称为这步找到的W的差异集合D。8/10/202214W不可合一的三种情况不可合一的三种情况（1）若D中无变量符号为
10、元素，则W是不可合一的。l例例.W=P(f(x),P(g(x)D=f(x),g(x)（2）若D中有奇异元素和非奇异元素，则W是不可合一的。l例例.W=P(x),P(x,y)D=,y（3）若D中元素有变量符号x和项t，且x出现在t中，则W是不可合一的。l例例.W=P(x),P(f(x)D=x,f(x)8/10/202215l换名换名:P(f(x),x),P(x,a);如果不换名：D=f(x),x.换名:P(f(y),y),P(x,a);mgu:f(a)/x,a/y8/10/202216步骤1：置 k=0,Wk=W,k=步骤2：若Wk只有一个元素，则停止，k是W的最一般合一；否则，找出Wk的差异集
11、合。步骤3：若Dk非奇异，Dk中存在元素vk和tk，其中vk是变量符号，并且 不出现在tk中，则转步骤4；否则，算法停止，W是不可合一的。步骤4：令 k+1=ktk/vk，Wk+1=Wk （注：Wk+1=W ）步骤5：置 k=k+1，转步骤2。合一算法（合一算法（Unification algorithm）/kkvt1k8/10/202217例例.令 W=Q(f(a),g(x),Q(y,y),求W的mgu。l步骤1：k=0,W0=W,0=。l步骤2：D0=f(a),y。l步骤3：有v0=y D0，v0不出现在t0f(a)中。l步骤4：令 1=0t0/v0=f(a)/y,W1=Q(f(a),g(
12、x),Q(f(a),f(a)l步骤5：k=k+1=1l步骤2：D1=g(x),f(a)。l步骤3：D1中无变量符号，算法停止，W不可合一。8/10/202218例例 令令 W=P(a,x,f(g(y),P(z,f(z),f(u)，求出求出W的的mgu。步骤1：k=0,W0=W,0=。步骤2：D0=a,z。步骤3：有v0=z D0，v0不出现在t0a中。步骤4：令 1=0t0/v0=a/z=a/z，W1=W0t0/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：D1=x,f(a)。步骤3：有v1=
13、x D1，且v1不出现在t1f(a)中。步骤4：令 2=1t1/v1=a/z f(a)/x=a/z,f(a)/x，W2=W1t1/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)8/10/202219例例.步骤步骤5：k=k+1=2步骤步骤2：D2=g(y),u。步骤步骤3：有：有v2=u D2，且，且v2不出现在不出现在t2g(y)中。中。步骤步骤4：令：令 3=2 t2/v2=a/z,f(a)/x g(y)/u =a/z,f(a)/x,g(y)/u，W3=W2t2/v2=P(a,f(a),f(g(y),P(
14、a,f(a),f(u)g(y)/u =P(a,f(a),f(g(y)步骤步骤5:k=k+1=3步骤步骤2：W3只有一个元素。算法停止。只有一个元素。算法停止。3=a/z,f(a)/x,g(y)/u 是是W的最一般合一。的最一般合一。8/10/202220定理定理 若若W是关于表达式的是关于表达式的有限非空可合一有限非空可合一集合，则合一集合，则合一算法终将结束在步骤算法终将结束在步骤2，并且最后的，并且最后的 k是是W的最一般合一。的最一般合一。证明：（1）终止性。否则将产生一个无穷序列：W，W ，W ，其中每一个直接后继集合比它的前任都少一个变量符号（注意：W 包含vk，而W 不包含vk）。
15、但这是不可能的，因为W仅含有限个变量符号。（2）k是W的合一。若算法停止在步骤2，则Wk=W只含有一个元素，所以k是W的合一。01nk1k8/10/202221（3）用归纳法证明算法必不会停止在步骤用归纳法证明算法必不会停止在步骤3，并，并且对任意且对任意W的一个合一的一个合一，任意，任意k，都存在替换，都存在替换 k，使得，使得 =kk 亦即亦即 k是是W的的mgu。当当k=0时，因时，因 0=，取，取 0=，于是，于是=00。8/10/202222假设对假设对0 k n，=kk成立成立 往证：存在往证：存在 n+1，使得，使得=n+1n+1。若若W 只含有一个元素，则合一算法结束在步骤只含
16、有一个元素，则合一算法结束在步骤2。因为。因为=nn，且，且 n是是W的合一，故的合一，故 n是是W的的mgu。定理得证。定理得证。若若W 不只含有一个元素不只含有一个元素,按照算法按照算法,将找出将找出W的差异集合的差异集合Dn。因为因为=nn是是W的合一，所以的合一，所以W中表达式经替换中表达式经替换 作用后作用后都变成同一个相同的表达式。而都变成同一个相同的表达式。而W中表达式经中表达式经 n作用后，作用后，产生了差异集合产生了差异集合Dn，所以，所以Dn必须被必须被 n所统一，即所统一，即 n是是D n的的合一。合一。nn8/10/202223 因为因为Dn是可合一的（是可合一的（n就
17、是就是Dn的合一），所的合一），所以必有变量符号以必有变量符号vn Dn；Dn中至少有两个不同中至少有两个不同元素。所以可设元素。所以可设tn Dn，且，且tnvn。显然，变量。显然，变量符号符号vn不出现在不出现在tn中（否则，中（否则，vn n tn n，这与，这与 n是是Dn的合一矛盾）。的合一矛盾）。因此算法不能停止在步骤因此算法不能停止在步骤3，所以算法必然停，所以算法必然停止在步骤止在步骤2。8/10/202224令令 n+1=n tn/vn。因为。因为vn n=tn n,所以所以tn n/vnn令令 n+1=n-tn n/vn。因。因vn不出现在不出现在tn中，所以中，所以于是于
18、是 故故归纳法完成。即对所有归纳法完成。即对所有k0,都存在替换都存在替换 k，使，使=kk。所以算法终止步骤。所以算法终止步骤2时，时，k是是W的最的最一般合一。一般合一。tttnnnnnnnnnvt/1nnnnnnnnnnnnnnnvtvtvtvtvtnnnn/(11111111)/()/(nnnnnnnnnnnnvtvt8/10/2022256.4 一阶逻辑中的归结原理一阶逻辑中的归结原理8/10/202226定义（因子）定义（因子）如果子句如果子句C中，两个或两个以上的文中，两个或两个以上的文字有一个最一般合一字有一个最一般合一，则，则C 称为称为C的因子；的因子；如果如果C 是单元子
19、句，则是单元子句，则C 称为称为C的单因子。的单因子。例例.C=P(x)P(f(y)Q(x)令令 f(y)/x，于是，于是 C=P(f(y)Q(f(y)是是C的因子。的因子。8/10/202227二元归结式定义定义 设设C1,C2是两个是两个无公共变量无公共变量的子句的子句(称为亲本子句称为亲本子句),L1,L2分别是分别是C1,C2中的两个文字。中的两个文字。如果如果L1和和L2有最一般合一，则子句有最一般合一，则子句 (C1-L1)(C2-L2)称为称为C1和和C2的二元归结式，的二元归结式，L1和和L2称为归结文字。称为归结文字。例例.设设C1=P(x)Q(x),C2=P(a)R(x)将
20、将C2中中x改名为改名为y。取。取L1P(x),L2=P(a),=a/x,于是于是(C1-L1)(C2-L2)(P(a),Q(a)-P(a)(P(a),R(y)-P(a)=Q(a),R(y)=Q(a)R(y)-C1和和C2的二元归结式的二元归结式.8/10/202228在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：（1）若被归结的子句）若被归结的子句C1 和和C2中具有相同的变元时，需要将其中一中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法合一，从而没有办法进行归结。个子句的变元更名，否则可能无法合一，从而没有办
21、法进行归结。（2）在求归结式时，不能同时消去两个互补文字对，消去两个互）在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。补文字对所得的结果不是两个亲本子句的逻辑推论。（3）如果在参加归结的子句内含有可合一的文字，则在进行归结）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的化简。之前，应对这些文字进行合一，以实现这些子句内部的化简。8/10/202229归结式归结式定义定义 子句子句C1,C2的一个归结式是下列二元归结式之一：的一个归结式是下列二元归结式之一：(1)C1和和C2的二元归结式。的
22、二元归结式。(2)C1和和C2的因子的二元归结式。的因子的二元归结式。(3)C1的因子和的因子和C2的二元归结式。的二元归结式。(4)C1的因子和的因子和C2的因子的二元归结式。的因子的二元归结式。例例.设设 C1=P(x)P(f(y)R(g(y)C2=P(f(g(a)Q(b)C1的因子的因子C1=P(f(y)R(g(y)。于是。于是C1和和C2的二元归结的二元归结式，从而也是式，从而也是C1和和C2的归结式为的归结式为 R(g(g(a)Q(b)8/10/202230一阶逻辑归结原理的完备性一阶逻辑归结原理的完备性提升引理提升引理 如果C1和C2分别是子句C1和C2的例，C是C1和C2的归结式
23、，则存在C1和C2的一个归结式C，使C是C的例。8/10/202231一阶逻辑归结原理的完备性一阶逻辑归结原理的完备性l定理定理 若子句集若子句集S是不可满足的，则存在从是不可满足的，则存在从S推推出空子句的归结演绎。出空子句的归结演绎。证明证明:设子句集设子句集S是不可满足的，由是不可满足的，由Herbrand定定理理II知，存在知，存在S的一个基例集的一个基例集S也是不可满也是不可满足的。根据命题足的。根据命题逻辑归结原理的完备性逻辑归结原理的完备性，存在，存在从从S推出空子句的归结演绎推出空子句的归结演绎D。由提升引理知，。由提升引理知，可将可将D提升成一个从提升成一个从S推出空子句的归
24、结演绎推出空子句的归结演绎D。定理得证。定理得证。8/10/2022326.5 归结原理的几种改进归结原理的几种改进8/10/202233一、支架集归结一、支架集归结定义子句集定义子句集S的子集的子集T称为称为S的支架集，如果（的支架集，如果（S-T）是可满足的。一个）是可满足的。一个支架集归结是一个不同时属于（支架集归结是一个不同时属于（S-T）的两个子句的归结。）的两个子句的归结。例例.设设S是如下子句集：是如下子句集：(1)PQ(2)PQ(3)PQ(4)PQ令令 T=PQ，显然，显然 T 是支架集。如下的演绎是支架集归结演绎：是支架集。如下的演绎是支架集归结演绎：(5)P 由由(1)、(
25、2)(6)Q 由由(1)、(3)(7)Q 由由(5)、(4)(8)由由(6)、(7)8/10/202234二、语义归结二、语义归结定义（语义互撞）定义（语义互撞）设I是子句集S的一个解释，P是S中谓词符号的一个顺序，有限子句序列 E1,Eq,N (q1)称为关于P和I的语义互撞（简称PI-互撞），当且仅当E1,Eq,N 满足下面条件：(1)E1,Eq在I下为假；(2)令R1=N，对每个 i=1,q，存在Ri和Ei的归结式Ri+1。(3)Ei中的归结文字是Ei中最大谓词符号。(4)Rq+1在I下为假。于是，Rq+1称为此PI-互撞的PI-归结式。8/10/202235例例.设S是如下子句集：(1
26、)PQR(2)PR(3)QR(4)R令 I=P,Q,R，PQR。于是在I下为假的子句只有两个：Si=PR,QR我们可得如下PI-演绎：(5)R 由(2)、(3)、(1)(6)由(5)、(4)8/10/202236三、线性归结三、线性归结定义（线性归结演绎）定义（线性归结演绎）设S是一个子句集，C0是S中的一个子句。以C0为顶子句，从S到Cn的线性归结演绎是如下一个演绎：(1)对于 i=0,1,n-1，Ci+1是Ci和Bi的归结式。(2)每个Bi或者属于S，或者是一个Cj，其中j i。8/10/202237四、锁归结四、锁归结定义（锁归结式）定义（锁归结式）设C是子句，若将C中每一个文字都附上一
27、个整数，则称子句C已配锁。设C1和C2是两个配锁子句，R(C1,C2)是C1和C2的归结式，如果C1和C2中的归结文字分别是C1和C2中带有最小锁的文字，则称R(C1,C2)为C1和C2 的锁归结式。例例.设S是如下配锁子句集(1)1P2Q(2)3P4Q(3)6P5Q(4)8P7Q于是，从S推出的锁演绎如下：(5)6P (3)、(4)(6)2Q (1)、(5)(7)4Q(8)8/10/202238五、广义归结五、广义归结定义（广义子句）定义（广义子句）设A1,An是一些原子,(A1,An)是以逻辑联结词、联结这些原子和一些0，1做成的公式,称为广义子句,其中 0代表F，1代表T。如果一个广义子
28、句中没有原子，只有0或者1，则称其为常子句。其值为0的常子句称为零子句，其值为1的常子句称为壹子句。定义定义（广义子句的因子广义子句的因子）设(A1,An)是一个广义子句，Ai1,Air有一个mgu（1 ij n,j=1,r），则称 为的因子。8/10/202239定义（广义归结式）定义（广义归结式）设,是无公共变元的广义子句,是合一Ai1,Air所得的因子，是合一Bj1,Bjs所得的因子。设是Ai1和Bj1的mgu，于是，(Ai1=0)(Bj1=1)(Ai1=1)(Bj1=0)都称为与的广义归结式。8/10/202240l例例.设S是如下一个广义子句集：(1)PQ(2)P(3)Q从S推出零子句的一个广义归结演绎如下：(4)(1Q)0 (1)、(2)(5)(10)0(1)=0 (3)、(4)
