统一算法不需要注射性？

Question

在学习一般统一算法时，我们学习了分解的规则，统一

$$ g \ cup \ {f（a_0，... a_k）= f（b_0，...，b_k）\} \ lightarrow g \ cup \ {a_0= b_0，... a_k= b_k \}。$$

问题，“如果 $ f $ 不是注射的？”站在我身上。说 $ f $ 不是注射的，我们遍历计算的分支 $ f（a_0，... a_k）= f（b_0，...，b_k）\ lightarrow \ {a_0= b_0，...，a_k= b_k \} $ 并导致失败。是否有可能为另一种方法分配 $ a_0，...，a_k $ to $ b_0，... b_k $ 使它是潜水的？

我在想一个例子来证明我的意思。这可能不是一个很好的例子，但是我们考虑 $ f（x，y）= x + y $ ，我们想要unify $ f（h（a），g（b））= f（g（c），h（d））$ 然后我们将通过分配 $ \ {h（a）= g（c），g（b），g（b）= h（d）\} $ 通过分解，但如果我们首先切换 $ f $ （自 $ f（a，b）= f（b，a）$ ），这将收益<跨越类=“math-container”> $ \ {a \ mapsto d，b \ mapsto c \} $ 。

我在这个纸张在第6页，他们在分解方面讨论了严格的概念，但我不太了解它，更普遍地我们如何在常规 $上对其进行分解的统一步骤f $ 没有以某种方式回溯失败。

Answer 1

此处 $ f $ 不是数学函数。相反，它是一个功能符号。不要考虑 $ f（a，b）$ ，因为评估参数 $ a，b $ 。相反，将其视为符号表达式中的术语 - 它是一个句法对象，不打算以您解释它的方式解释。

如果您愿意，您可以考虑它，好像符号表达式中的每个功能符号都是注射功能;但这并不是真的准确，这只是一个思考象征性表达的原始方法。

您无法定义 $ f（x）= x + y $ 。 $ f $ 是一个未解释的函数符号。您不允许定义特定功能。相反， $ f $ 是尚未定义的函数的站立。考虑一下的方式是您从统一中得出的任何结论都是结论，应该持有所有函数 $ f $ （不仅仅是一个单个）。< / p>