Инъективность не требуется для алгоритмов объединения?

Question

При изучении общего алгоритма унификации мы узнали правило разлагаться , в которых говорится, что объединяет

$$ g \ cup \ {f (a_0, ... a_k)= f (b_0, ..., b_k) \} \ prightarrow g \ cup \ {a_0= b_0, ... a_k= b_k \}. $$

Вопрос: «Что, если $ F $ не инъективно?" выставил мне. Скажем, $ f $ не инъективно, и мы проходим к тому, что отделение вычислений, где $ f (a_0, ... a_k)= f (b_0, ..., b_k) \ proverarrow \ {a_0= b_0, ..., a_k= b_k \} $ и приведет к неудаче. Возможно ли, что есть другой способ назначить $ a_0, ..., a_k $ на $ b_0, ... b_k $ такое, что это Unifiable?

Я думал, может быть, пример, чтобы продемонстрировать то, что я имею в виду. Это может не быть хорошим примером, но сказать, что мы рассмотрим $ f (x, y)= x + y $ , и мы хотим унифицировать $ f (h (a), g (b))= f (g (c), h (d)) $ Тогда мы потерпите неудачу путем назначения $ \ {h (a)= g (c), g (b)= h (d) \} $ путем разложения, но преуспеть в объединении, если вместо этого мы впервые выключаем аргументы $ f $ (Действительно, поскольку $ f (a, b)= f (b, a) $ ), который даст < Spaness Class="Математический контейнер"> $ \ {a \ mapsto d, b \ mapsto c \} $ .

Я немного читал об этом в Это бумаги На стр. 6, где они обсуждают идею строгости с точки зрения разложения, но я не совсем понимаю его, и в целом, как мы можем выполнить этот шаг объединения в целом $ f $ без каким-то возвращения на неудачу.

Answer 1

Здесь $ F $ не является математической функцией. Скорее, это a Символ функции . Не думайте о $ f (a, b) $ в результате оценки функции при параметрах $ a, b $ . Скорее, думайте об этом как об этом как срок в символическом выражении - это синтаксический объект, который не предназначен для интерпретации так, как вы интерпретируете его.

Если вам нравится, вы можете думать об этом, как будто каждая функция функции в символическом выражении является инъективной функцией; Но это не совсем точно, это просто грубый способ подумать о символических выражениях.

Вы не можете определить $ f (x)= x + y $ . $ F $ - неиспользованный символ функции. Вам не разрешено определять конкретную функцию. Скорее, $ f $ - это средство для функции, которая еще не определена. Один из способов подумать о том, что любые выводы, которые вы рисуете из объединения, являются выводами, которые должны храниться для всех функций $ F $ (не просто один). < / P >.