最通用的统一器 (Prolog)

Question

有一个关于序言中 m.g.u（最通用的统一器）的快速问题。

我们被问到 m.g.u 是什么：

f(X, g(Y, h(Z))) = f(Z, g(P, h(a))).

有 2 个可能的答案

1. θ = {X/Z,Y/P,Z/a}.
2. θ = {X/a,Y/P,Z/a}.

我认为第二个答案是最通用的统一器，但是，第一个答案似乎是正确的。

我已经尝试了两种替换，它们都产生了相同的结果，但是第二个答案是替换较少，这就是为什么我认为它是 m.g.u

任何帮助将不胜感激，谢谢！

   +-----------X
   |
   |     +-----Y
   |     |
f--+--g--+
         |
         +--h--Z
         
         
   +-----------Z
   |
   |     +-----P
   |     |
f--+--g--+
         |
         +--h--a

Answer 1

mgu 的定义是没有分解 θ = λτ，其中 λ,τ 是非平凡的（不是身份，新引入的变量的名称无关紧要）。存在 1 的替换导致 2（我可以稍后编辑解决方案，如果你找不到它）这样 2 就不是最一般的替换。

还有一个警告：如果您将 θ = {X/Z,Y/P,Z/a} 应用于 X，您最终会得到 Z，而不是 a。替换总是同时发生。

最通用的统一器 (Prolog)

Most General Unifier (Prolog)

prolog

unification