Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 2

Sprache als Symbolketten

Wir knüpfen an die Überlegungen der ersten Vorlesung an, ob es eine Maschine (einen Computer, einen Algorithmus) gibt, die mathematische Aussagen ausdrücken, ausdrucken, überprüfen, beweisen oder widerlegen kann. Eine solche Maschine operiert mit Zeichenreihen, die wir in diesem Zusammenhang eine (formale) Sprache nennen.

Definition

Es sei ${}A$ eine Menge von Symbolen. Dann nennt man jede endliche Zeichenreihe, die man mit den Elementen aus ${}A$ aufstellen kann, ein Wort über dem Alphabet ${}A$.

Die Menge aller Wörter über dem Alphabet ${}A$ bezeichnen wir mit ${}A^{*}$.

Das zugrunde liegende Alphabet kann endlich oder unendlich sein, für praktische Anwendungen reicht ein endliches Alphabet. Die Elemente des Alphabets nennt man Buchstaben, Zeichen oder Symbole. Mit einer Zeichenreihe meint man eine hintereinander geschriebene Buchstabenkette (oder Symbolkette). Dazu gehören die einelementigen Ketten, also die Elemente aus ${}A$ selbst, aber auch die leere Kette (das leere Wort), die wir mit ${}\emptyset$ bezeichnen. Bei dieser Definition kommt es nicht auf irgendeine Sinnhaftigkeit der Wörter an, es handelt sich um eine rein formale Definition.

Beispiel

Es sei ein einelementiges Alphabet ${}A=\{{|}\}$ gegeben. Dann besitzt jedes Wort über ${}A$ die Gestalt

${|}{|}{|}\ldots {|}$

mit einer gewissen Anzahl von Strichen. Zwei solche Wörter sind genau dann gleich, wenn ihre Strichanzahl übereinstimmt. In diesem Fall entsprechen also die Wörter den natürlichen Zahlen (das leere Wort entspricht der ${}0$).

Beispiel

Die DNA-Stränge, die die Erbinformationen aller Lebewesen tragen, sind Doppelketten in Helixform aus Nukleotiden. Die entscheidenden Bestandteile der Nukleotiden sind die Basen, wofür es nur vier Möglichkeiten gibt, nämlich Adenin (A), Thymin (T), Guanin (G) und Cytosin (C). Die Nukleotiden treten in der Helix stets mit einem festen Partner (nämlich Adenin mit Thymin und Guanin mit Cytosin) auf, sodass die Struktur durch die eine Hälfte der Helix festgelegt ist. Daher entspricht (bis auf die Leserichtung und die Strangauswahl) die genetische Information eines DNA-Stranges einem Wort über dem Alphabet mit den Buchstaben A,T,G,C.

Wenn zu einem Alphabet ${}A$ ein neues Zeichen ${}-$ als „Leerzeichen“ hinzugenommen wird, so werden manchmal die Wörter aus ${}A$ als (eigentliche) Wörter und die Wörter aus dem Alphabet ${}A\cup \{-\}$ als Texte (oder Sätze) bezeichnet. Mit der Hinzunahme eines weiteren Satzbeendungssymbols kann man auch zwischen Sätzen und Texten unterscheiden.

Die geschriebene natürliche Sprache umfasst das Alphabet, das aus den Großbuchstaben A,B,C,...,Z,Ä,Ö,Ü, den Kleinbuchstaben a,b,c,...,z,ä,ö,ü,ß, den Ziffern, den Satzzeichen und einem Leerzeichen für den Abstand zwischen den Wörtern besteht. Jede lineare Hintereinanderreihung dieser Zeichen gilt für uns als Text. Im Moment interessieren wir uns nicht dafür, ob die geschriebenen Texte syntaktisch richtig gebildet oder semantisch erlaubt sind. Im Moment ist also z.B.

$!!fL33kAs.,r$

ein erlaubter Text.

In der Definition von einem Wort über einem Alphabet haben wir von einer Menge gesprochen und somit eine naive Mengenlehre vorausgesetzt. Im endlichen Fall wird die Symbolmenge einfach durch Auflisten ihrer Elemente gegeben. Für die gebildeten Wörter haben wir implizit verwendet, dass das Bilden von linearen Zeichenreihen unproblematisch ist.

Rekursive Definitionen

Ein wichtiges Prinzip, Mengen zu definieren, ist das der rekursiven Definition. Eine rekursive Definition besteht aus zwei Sorten von Regeln. (1) Einerseits gewisse Startregeln, die sagen, was direkt zu der Menge gehört, und (2) Rekursionsregeln, die die Form einer Bedingung haben, und besagen, dass wenn gewisse Objekte zu der Menge gehören, und wenn neue Objekte aus diesen Objekten in bestimmter Weise gebildet sind, dass dann diese neuen Objekte ebenfalls dazu gehören (die dritte stillschweigende Bedingung an eine rekursive Definition ist, dass es keine weitere Möglichkeit gibt, zu der Menge zu gehören, außer den in (1) und (2) genannten).

Die Menge der Wörter über einem Alphabet ${}A$ kann man auch folgendermaßen rekursiv definieren.

1. ${}\emptyset$ ist ein Wort über ${}A$.
2. Wenn ${}x$ ein Wort ist und ${}a\in A$ ein Buchstabe, so ist auch ${}xa$ ein Wort.

Hier repräsentiert ${}x$ (eine Variable) ein beliebiges schon konstruiertes Wort. Dabei ist ${}\emptyset a$ als ${}a$ zu lesen, so dass die beiden erlaubten Konstruktionsschritte (also der Anfangsschritt und der Rekursionsschritt) sichern, dass die einzelnen Symbole aus ${}A$ Wörter sind. Wenn das Alphabet durch ${}A=\{a,b,c\}$ gegeben ist, so würde der rekursive Nachweis, dass ${}abbac$ ein Wort ist, folgendermaßen gehen.

1. Wegen der Anfangsbedingung ist ${}\emptyset$ ein Wort.
2. Deshalb und wegen des Rekursionsschrittes ist ${}\emptyset a=a$ ein Wort.
3. Deshalb und wegen des Rekursionsschrittes ist ${}ab$ ein Wort (hier ist also ${}x=a$ das schon nachgewiesene Wort und der Buchstabe ${}b$ wird angehängt).
4. Deshalb und wegen des Rekursionsschrittes ist ${}abb$ ein Wort (hier ist also ${}x=ab$ das schon nachgewiesene Wort und der Buchstabe ${}b$ wird angehängt).
5. Deshalb und wegen des Rekursionsschrittes ist ${}abba$ ein Wort (hier ist also ${}x=abb$ das schon nachgewiesene Wort und der Buchstabe ${}a$ wird angehängt).
6. Deshalb und wegen des Rekursionsschrittes ist ${}abbac$ ein Wort (hier ist also ${}x=abba$ das schon nachgewiesene Wort und der Buchstabe ${}c$ wird angehängt).

Natürlich kann man ${}abbac$ sofort ansehen, dass es sich um eine linear angeordnete Zeichenreihe über ${}\{a,b,c\}$ handelt, und der rekursive Nachweis scheint übertrieben pedantisch zu sein. Bei komplexer gebildeten Mengen ist aber die rekursive Definition unerlässlich, vor allem auch deshalb, da sie ermöglicht, Eigenschaften der Elemente einer Menge über den rekursiven Aufbau nachzuweisen.

Eine Sprache besteht aus sinnvollen Wörtern und sinnvollen Sätzen, nicht aus der beliebigen Aneinanderreihung von Symbolen oder Buchstaben (oder Lauten). Es ist aber vorteilhaft, erstmal alle Möglichkeiten zuzulassen und daraus durch eine Vorgabe von Regeln die sinnvollen Ausdrücke, Wörter, Lautkombinationen herauszufiltern. So funktioniert auch der kleinkindliche Spracherwerb und der Aufbau der formalen Sprachen. Wir werden nun den rekursiven Aufbau von syntaktisch korrekten Termen besprechen.

Terme

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$.

Abschließend erklären wir, was die Variablenmenge eines Terms ist. Diese ist stets eine Teilmenge der Variablenmenge ${}V$ und enthält diejenigen Variablen, die in dem Term irgendwo vorkommen. Die rekursive Definition lautet folgendermaßen.

1. Wenn ${}t=x$ eine Variable ist, so ist ${}\operatorname {Var} (x)=\{x\}$.
2. Wenn ${}t=c$ eine Konstante ist, so ist ${}\operatorname {Var} (c)=\emptyset$.
3. Wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist und wenn ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist ${}\operatorname {Var} (ft_{1},\ldots ,t_{n})=\operatorname {Var} (t_{1})\cup \ldots \cup \operatorname {Var} (t_{n})$.

Fußnoten

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)