Zahlen/Terme/Einführung/Textabschnitt

Betrachten wir die sinnvollen Ausdrücke, die für eine natürliche Zahl stehen können. Mit dem Ziffernalphabet ${}Z=\{0,1,2,3,4,5,6,7,8,9\}$ kann man mit der rekursiven Vorschrift zur Generierung von Zeichenreihen aus einem Alphabet alle natürlichen Zahlen (im Zehnersystem) aufschreiben, z.B. ${}530386275$. Allerdings gibt es hier ein paar Schwierigkeiten, es sind nämlich auch die Zahlen ${}0530386275$, ${}00530386275$, u.s.w. erlaubt (und untereinander verschieden, da sie eben unterschiedliche Symbolfolgen sind). Der „Zahlenwert“ steht im Moment noch nicht zur Verfügung. Ferner möchte man das leere Zahlwort nicht als erlaubte Ziffernfolge ansehen.

Mit dieser Menge an erlaubten Zahlwörtern kann man Telefonnummern oder Internetadressen bezeichnen, aber noch nicht das machen, was man eigentlich mit Zahlen machen möchte, nämlich Zählen, Rechnen, Probleme formulieren und lösen. Für die innerhalb der natürlichen Zahlen ausführbaren Rechenoperationen, insbesondere das Nachfolgernehmen (also das Zählen) und die Addition und die Multiplikation, brauchen wir neue Symbole. Eine Aussage wie

${}5\cdot 3=8+7\,$

ist natürlich wahr, da links und rechts ${}15$ „steht“, wie man durch „ausrechnen“ (also das korrekte Anwenden der Rechenregeln) überprüfen kann. Wenn man allerdings solche Gleichungen logisch verstehen und analysieren möchte, so sollte man die beiden Seiten nicht als ${}15$ lesen, sondern jeweils als ein neues „komplexes Zahlwort“, das sich aus den Ziffernsymbolen ${}5$ und ${}3$ und dem Malzeichen ${}\cdot$ bzw. den Ziffernsymbolen ${}8$ und ${}7$ und dem Pluszeichen ${}+$ zusammensetzt. Die linke und die rechte Seite sind hier sogenannte Terme, also sinnvolle mathematische Ausdrücke, die einen Zahlwert annehmen können bzw. formal den Charakter einer Zahl haben (der Vergleich der beiden Terme durch ${}=$ macht aus den beiden Termen eine Aussage, das spielt jetzt aber noch keine Rolle). Ein weiteres Beispiel ist eine Gleichung der Form

${}4\cdot x=3\cdot (8+y)\,,$

wo vermutlich nach den erlaubten Werten für ${}x$ und ${}y$ gesucht wird, die diese Gleichung erfüllen. Aber unabhängig von dieser typischen Interpretation stehen links und rechts ebenfalls Terme, in denen jeweils eine Variable vorkommt. Solche Terme sind ein konstitutiver Bestandteil der Prädikatenlogik und werden, ausgehend von einer Variablenmenge (keine Aussagenvariablenmenge), einer Konstantenmenge und verschiedenen Funktionssymbolmengen, rekursiv definiert.

Definition

Eine Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.

1. eine Variablenmenge ${}V$,
2. eine Konstantenmenge ${}K$,
3. zu jedem ${}n\in \mathbb {N} _{+}$ eine Menge ${}F_{n}$ von Funktionssymbolen.

Dabei können die auftretenden Mengen leer sein, es ist für die Funktionssymbole sogar typisch, dass es nicht zu jeder Stelligkeit (zu jedem ${}n$) ein Funktionssymbol gibt (die Variablenmenge wird hingegen meistens als nicht leer angesetzt, und zwar mit unendlich vielen Variablen, die häufig als ${}x_{1},x_{2},x_{3},\ldots$ angesetzt werden). Die Konstanten kann man auch als nullstellige Funktionssymbole auffassen. Unter dem Termalphabet versteht man die Vereinigung ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$.

Die arithmetische Grundtermmenge besteht aus den beiden Konstanten ${}0,1$, den beiden zweistelligen Funktionssymbolen ${}\{+,\cdot \}$ und einer Variablenmenge.

Definition

Zu einer Grundtermmenge ${}G=(V,K,F_{n})$ ist die zugehörige Termmenge (oder die Menge der ${}G$-Terme) diejenige Teilmenge ${}T=T(G)$ der Wörter ${}A^{*}$ über dem Termalphabet ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$, die durch die folgenden rekursiven Vorschriften festgelegt wird.

1. Jede Variable ${}v\in V$ ist ein Term.
2. Jede Konstante ${}c\in K$ ist ein Term.
3. Für jedes ${}f\in F_{n}$ und ${}n$ Terme ${}t_{1},t_{2},\ldots ,t_{n}$ ist auch ${}ft_{1}t_{2}\ldots t_{n}$ ein Term.

Hierbei sind ${}(1)$ und ${}(2)$ die Anfangsbedingungen und ${}(3)$ die Rekursionsregel, da darin auf schon gebildete Terme Bezug genommen wird. Wie bei jeder rekursiven Definition ist ein Wort nur dann ein Term, wenn es gemäß dieser Regeln gebildet werden kann.

Gemäß dieser Definition verzichten wir auf Klammern, und die Funktionssymbole werden einheitlich links geschrieben und daran werden rechts davon die Terme angefügt (das wird später so interpretiert, dass in ${}n$-stellige Funktionen ${}n$ Elemente eingesetzt werden). Schon in einfachen Beispielen ist es aber wegen der Lesbarkeit sinnvoll, auch Klammern zu verwenden und von der strengen Reihenfolge bei den Funkltionssymbolen abzuweichen und beispielsweise ${}s+t$ statt ${}+st$ zu schreiben. Solche Schreibweisen sind als Ersatz für die formal korrekt gebildeten Terme zu interpretieren, sie gehören aber nicht zu den Termen.

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:

Beispiel

Wir betrachten ein Modell für die Termmenge der natürlichen Zahlen. Als Grundtermmenge nehmen wir eine Variablenmenge ${}V$, die Konstantenmenge ${}K=\{0\}$, die einstelligen Funktionssymbolmenge ${}F_{1}=\{N\}$ (${}N$ steht für Nachfolger) und die zweistellige Funktionssymbolmenge ${}F_{2}=\{\alpha ,\mu \}$ (für Addition und Multiplikation). Allein aus der Konstante ${}0$ und dem Nachfolgersymbol ${}N$ kann man dann für jede natürliche Zahl eine Repräsentierung finden, nämlich

$N0\,,NN0,\,NNN0,\,NNNN0,\,etc.$

Typische Terme sind dann Ausdrücke wie (${}u,v,w$ seien Variablen)

$\alpha NN0NNNv,\,\mu NN0\alpha NN0NNN0,\,\mu \alpha NNN0\mu NNuN0NNNNw,\,{\text{etc}}.$

Wenn man ${}x'$ statt ${}Nx$, ${}(x+y)$ statt ${}\alpha xy$ und ${}(x\cdot y)$ statt ${}\mu xy$ schreibt, so „verschönern“ sich diese Terme zu

$(0^{\prime \prime }+v^{\prime \prime \prime }),\,(0^{\prime \prime }\cdot (0^{\prime \prime }+0^{\prime \prime \prime })),\,((0^{\prime \prime \prime }+(u^{\prime \prime }\cdot 0^{\prime }))\cdot w^{\prime \prime \prime \prime }),\,{\text{etc}}.$

Mit den Abkürzungen ${}1=0^{\prime }$, ${}2=0^{\prime \prime }$ etc. wird daraus

$2+v^{\prime \prime \prime },\,(2\cdot (2+3)),\,((3+(u^{\prime \prime }\cdot 1))\cdot w^{\prime \prime \prime \prime }),\,{\text{etc}}..$

Man beachte, dass die Einführung dieser Abkürzungen nicht bedeutet, dass dadurch die üblicherweise mit diesen Symbolen verwendeten Rechenregeln erlaubt sind. Der zweite Term oben ist nicht gleich ${}10$, dem zehnten Nachfolger der ${}0$.

Fußnoten