合 一
4、合成的性质：
合成具有以下性质：
（1）(Es1)s2=E(s1s2)，即置换s1和s2依次作用于表达式E相当于置换s1和s2的合成s1s2作用于E。
（2）(s1s2)s3=s1(s2s3)，即合成满足结合律。一般来说，合成不满足交换律，即s1s2=s2s1通常是不成立的。
把置换s作用于集合{Ei}中的每一个公式得到的例的集合用{Ei}s表示。如果存在一个置换s，使Es1=Es2=Es3=...，则称公式集{Ei}是可合一的，置换s称为{Ei}的合一者。例如有公式集合
{Ei}={P[x，f(y),b],P[x,f(b),b]}和一个置换s={A/x,b/x}，使得
{Ei}s={P[A,f(b),b],P[A,f(b),b]}
因此公式集{Ei}是可合一的，且置换s为{Ei}的合一者。但s并不是最简单的，因为置换{b/y}就是足以使公式集{Ei}合一。为此，我们定义最简合一者mgu(Most General unifier)。如果对公式集{Ei}所有的合一者S，都存在一个置换s'，使{Ei}s={Ei}gs'，则称g为公式集{Ei}的最简合一者。可以证明，除了变量的符号可以不同外，一个公式的最简合一者是唯一的。
下面给出一个求最简合一者的程序UNIFY，它使用表结构来表示表达式，例如公式P[x，f(A,y)]表示成(P x (f A y))。
递归过程UNIFY(E1,E2)
（1）if ATOM(E2) then 变换E1和E2的位置；如果E1、E2之中至少有一个是原子的话，把该原子放在前面。
（2）if ATOM(E1) then
（3） begin
（4） if E1=E2 then return NIL；NIL为空。
（5） if E1为变量
（6） begin
（7） if E2中有E1 then return FaiL； f(x)不能代替x。
（8） return {E2/E1}
（9） end
（10） if E2为变量 then return {E1/E2}
（11） return FaiL
（12） end
（13）F1¬(car E1), T1¬(cDR E1)
（14）F2¬(car E2), T2¬(cDR E2)
（15）Z1¬UNIFY(F1, F2)
（16）if Z1=FaiL then return FaiL
（17）G1¬T1Z1；Z1作用于T1
（18）G2¬T2Z1；Z1作用于T2
（19）Z2¬UNIFY(G1, G2)
（20）if Z2=FaiL then return FaiL
（21）return Z1Z2；返回Z1、Z2的合成
当E1和E2可合一时，程序返回E1和E2的最简合一者，否则推导失败，下面是对几个公式集得到的结果：
{P(x),P(A)} ®{A/x}
{P[f(x),y,g(y)],P[f(x),z,g(x)]} ®{x/y,x/z}
{P[f(x,g(A,y)),g(A,y)], P[f(x,z), z]} ®{g(A,y)/z}
合一可用来解决两个表达式的匹配问题，合一过程得到的最简合一者作用于两个表达式就可得到匹配的例。但模式匹配中只允许一个表达式有变量，因此合一过程更为一般化。
习题
1、求出集合{P(x,y,z),P(w,u,w),P(A,u,u)}的mgu。