Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Looking at various examples online, some seem concrete, but some seem to not be explained properly.

Can $f(x)$ be substituted with $g(x)$? I know that $x$ cannot be substituted with $f(x)$, but $x$ can be substituted with $y$ or $a$ or $f(y)$ (assuming $y$ is a variable and $a$ is a constant).

share|improve this question

2 Answers 2

up vote 3 down vote accepted

In short, you can unify two terms only if following conditions are true:

  • $x$ and $y$:
    • always.
  • $x$ and $f(\ldots)$:
    • the second term does not contain $x$.
  • $\alpha(x_1, \ldots, x_n)$ and $\beta(y_1, \ldots, y_m)$:
    • $\alpha = \beta$, e.g. $f = f$, but $f \neq g$,
    • $n = m$,
    • $x_i$ can be unified with $y_i$ for all $1 \leq i \leq n$.

I don't know the context, so this is not precise (e.g. there are some subleties if you have both bound and free variables, some quantifiers or Skolem constants), but it should give you enough intuition to work out any issues yourself.

Cheers!

share|improve this answer
    
See also the Wikipedia. –  dtldarek Dec 9 '12 at 22:24

you can't unify two terms if no substitution makes them equal.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.