Variablen, Substitutionen

• Terme und Variablen: Term($\Sigma$, V): Menge der Terme mit Symbolen aus $\Sigma$ und Variablen aus V.
• Vereinbarung: Variablen am Ende des Alphabets ( x, y,...), Funktionssymbole am Anfang ( f, g, a, b,...)
• Menge der in einem Term t vorkommende Variablen: Var(t)
• Substitution $\sigma$ ist Abbildung V$\to$Term($\Sigma$, W)
• eine Substitution $\sigma$ angewendet auf einen Term t erzeugt Term t$\sigma$

  Beispiel t = f (x), Var(t) = {x}, $\sigma$ : x $\mapsto$ g(2, 2), t$\sigma$ = f (g(2, 2)).