Term/Variablenmenge/Funktionssymbole/Grundmenge/Phantasie/Beispiel

Eine Grundtermmenge sei durch die Variablenmenge ${}V=\{x,y,z\}$, eine Konstantenmenge ${}K=\{c_{1},c_{2}\}$, die einstelligen Funktionssymbole ${}F_{1}=\{f,g\}$ und die zweistelligen Funktionssymbole ${}F_{2}=\{\alpha ,\beta ,\gamma \}$ gegeben. Dann sind die folgenden Wörter Terme.

$x,y,z,c_{1},c_{2},fx,fc_{1},gz,\alpha xy,\alpha xx,\alpha xfy,\alpha fxgc_{1},\gamma \gamma xxx,\beta \alpha xgc_{2}\gamma fy\alpha gzx.$

Auch wenn es für das Auge etwas ungewohnt aussieht, so sind diese Terme auch ohne Klammern allesamt wohldefiniert. Davon überzeugt man sich, indem man die Terme von links nach rechts liest, und dabei bei jedem Funktionssymbol die zugehörige Stelligkeit bestimmt (zu welchem ${}F_{n}$ gehört das Funktionssymbol?) und dann die folgenden Symbole in die geforderten ${}n$ Terme aufspaltet (wenn dies nicht geht, so ist das Wort kein Term). Dabei entsteht schnell eine große Verschachtelungstiefe. Den letzten angeführten Term, also

$\beta \alpha xgc_{2}\gamma fy\alpha gzx,$

kann man mit (suggestiven) Klammern und Kommata nach und nach lesbarer gestalten. Er beginnt mit dem zweistelligen Funktionssymbol ${}\beta$, also muss das Folgende aus zwei Termen bestehen. Es folgt zunächst das ebenfalls zweistellige Funktionssymbol ${}\alpha$, worauf zwei Terme folgen müssen. Wenn diese gefunden sind, muss der verbleibende Rest (also alles, was weiter rechts steht) den zweiten Term bilden, der von ${}\beta$ verlangt wird. Die beiden Terme des an zweiter Stelle stehenden ${}\alpha$ sind ${}x$ und ${}gc_{2}$. Man kann also den Term nach dieser Analyse auch als

$\beta (\alpha (x,g(c_{2})),\gamma fy\alpha gzx)$

schreiben. Wenn man ebenso den zweiten Term für das äußere ${}\beta$ auflöst, so erhält man

$\beta (\alpha (x,g(c_{2})),\gamma (f(y),\alpha (g(z),x))).$

Übrigens kann man auch bei einem beliebigen Funktionssymbol mittendrin beginnen und die zugehörigen Terme, auf die es Bezug nimmt, bestimmen. Besonders übersichtlich wird die Termstruktur durch einen Termstammbaum ausgedrückt. Dabei werden die verwendeten Variablen und Konstanten (mehrfach, um die unterschiedlichen Stellen, in die sie eingesetzt werden, beachten zu können) als Blätter nebeneinander aufgeführt. Sie bilden die ${}0$-te Reihe des Baumes. Wenn ein ${}n$-stelliges Funktionssymbol auf ${}n$ solche Blätter angewendet wird, so zeichnet man einen Knoten, bezeichnet ihn mit dem Funktionssymbol (bzw. dem Funktionssymbol mit den eingelesenen Termen) und verbindet es mit den eingelesenen Blättern (die Einlesungsreihenfolge entspricht der Blätterreihenfolge). So entsteht aus allen Funktionssymbolen, die nur auf Variablen und Konstanten Bezug nehmen, die erste Reihe des Baumes. Die Funktionssymbole, die auf solche Knoten (und Blätter) Bezug nehmen, bilden die nächste Reihe, u.s.w. Der Stamm des Baumes ist dann der in Frage stehende Term. In unserem Beispiel sieht das so aus: