Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 2/kontrolle
- Sprache als Symbolketten
Wir knüpfen an die Überlegungen der ersten Vorlesung an, ob es eine Maschine (einen Computer, einen Algorithmus) gibt, der (alle korrekten) mathematische Aussagen ausdrücken, ausdrucken, überprüfen, beweisen oder widerlegen kann. Eine solche Maschine operiert mit Zeichenreihen, die wir in diesem Zusammenhang Wörter einer (formalen) Sprache nennen. Wir beschreiben daher den Aufbau einer formalen Sprache.
Es sei eine Menge von Symbolen. Dann nennt man jede endliche Zeichenreihe, die man mit den Elementen aus aufstellen kann, ein Wort über dem Alphabet .
Die Menge aller Wörter über dem Alphabet bezeichnen wir mit .
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 selbst, aber auch die leere Kette (das leere Wort), die wir mit bezeichnen. Bei dieser Definition kommt es nicht auf irgendeine Sinnhaftigkeit der Wörter an, es handelt sich um eine rein formale Definition.
Es sei ein einelementiges Alphabet gegeben. Dann besitzt jedes Wort über die Gestalt
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 ).
Der Binärcode besteht aus den beiden Symbolen und , der Morsecode besteht aus drei Zeichen: kurzes Signal, langes Signal, Pause. Grundsätzlich führt jedes nichtleere endliche Alphabet zu einer abzählbar-unendlichen Menge an Wörtern und hat somit prinzipiell die gleiche Ausdrucksstärke.
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 ein neues Zeichen als „Leerzeichen“ hinzugenommen wird, so werden manchmal die Wörter aus als (eigentliche) Wörter und die Wörter aus dem Alphabet 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 sinnvoll sind. Im Moment ist also z.B.
ein erlaubter Text.
- Rekursive Definitionen
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.
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 (Generierungsregeln), 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 kann man auch folgendermaßen rekursiv definieren.
- ist ein Wort über .
- Wenn ein Wort ist und ein Buchstabe, so ist auch ein Wort.
Hier repräsentiert (eine Variable) ein beliebiges schon konstruiertes Wort. Dabei ist als zu lesen, sodass die beiden erlaubten Konstruktionsschritte (also der Anfangsschritt und der Rekursionsschritt) sichern, dass die einzelnen Symbole aus Wörter sind. Wenn das Alphabet durch gegeben ist, so würde der rekursive Nachweis, dass ein Wort ist, folgendermaßen gehen.
- Wegen der Anfangsbedingung ist ein Wort.
- Deshalb und wegen des Rekursionsschrittes ist ein Wort.
- Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
- Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
- Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
- Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
Natürlich kann man sofort ansehen, dass es sich um eine linear angeordnete Zeichenreihe über 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.
Es sei eine rekursiv definierte Menge, die durch eine Startmenge und gewisse Rekursionsvorschriften gegeben sei. Nehmen wir an, wir möchten für alle Elemente der Menge eine gewisse Eigenschaft nachweisen. Das Beweisprinzip durch Rekursion[1] oder Beweisprinzip über den rekursiven Aufbau der Menge funktioniert folgendermaßen.
- Man zeigt, dass jedes Element aus der Startmenge die Eigenschaft erfüllt (Rekursionsanfang).
- Man zeigt für jede Rekursionsvorschrift, dass unter der Voraussetzung, dass die in dieser Vorschrift verwendeten Elemente die Eigenschaft besitzen, dann auch das durch die Vorschrift produzierte Element die Eigenschaft besitzt (Rekursionsschritt).
Daraus kann man dann schließen, dass jedes Element aus die Eigenschaft erfüllt. Die Richtigkeit dieses Beweisprinzips beruht auf folgender Betrachtung: Es sei die Menge aller Elemente, für die die Eigenschaft gilt. Aufgrund des Rekursionsanfangs gilt . Aufgrund des Rekursionsschrittes ist abgeschlossenen unter sämtlichen Rekursionsvorschriften. Dies ist aber die Definition für , also ist und die Eigenschaft gilt für ganz .
Ein Spezialfall dieses Beweisprinzips ist das Prinzip der vollständigen Induktion für natürliche Zahlen. Die natürlichen Zahlen sind rekursiv durch das Startelement und eine einzige Rekursionsregel, nämlich die Nachfolgerregel festgelegt: Wenn eine natürliche Zahl ist, so ist auch der Nachfolger von eine natürliche Zahl.
Es sei eine rekursiv definierte Menge mit der Startmenge . Verwandt mit dem Beweisprinzip über den rekursiven Aufbau der Menge ist das Prinzip, eine Abbildung von in eine weitere Menge rekursiv zu definieren. Dazu geht man folgendermaßen vor.
- Man legt eine Abbildung
fest.
- Für jede Rekursionsvorschrift erklärt man, wie man aus den schon festgelegten Werten der Elemente , auf die die Vorschrift Bezug nimmt, den Wert unter für das durch die Vorschrift produzierte Element festlegt.
- Man muss sicherstellen, dass, falls es für ein Element mehrere Möglichkeiten gibt, dieses rekursiv zu erzeugen, die verschiedenen Möglichkeiten zum gleichen Wert führen.
Wenn diese Bedingungen erfüllt sind, ist eine wohldefinierte Abbildung
definiert.
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 Aussagen besprechen.
Die mathematische Logik beschäftigt sich hauptsächlich mit Prädikatenlogik, da in dieser ein Großteil der Mathematik beschrieben werden kann. Als Vorstufe dazu behandeln wir jetzt die Aussagenlogik. Wie bei der Prädikatenlogik später folgen wir dem Schema
Formale Sprache - Interpretationen und semantische Tautologien - Syntaktische Tautologien und Ableitungskalkül - Vollständigkeit.
- Die Sprache der Aussagenlogik
Die formallogische Sprache der Aussagenlogik wird ausgehend von einer Variablenmenge und einer einfachen Menge an Junktoren rekursiv aufgebaut. Die Aussagenvariablen werden wir zumeist mit etc. bezeichnen. Sie repräsentieren Aussagen, haben aber keinen eigenen Inhalt, sondern teilen mit Aussagen lediglich gewisse syntaktische Eigenschaften (semantische Eigenschaften werden hier noch nicht besprochen). Beispiele für solche syntaktischen Eigenschaften sind, dass man zu einer Aussage eine Negation bilden kann, oder dass man zwei Aussagen durch „und“ verknüpfen kann. Die Aussagenvariablen repräsentieren Grundaussagen, die durch solche Verknüpfungen zu komplexeren Aussagen zusammengesetzt werden können, die selbst wiederum zu weiter verschachtelten Aussagen verbunden werden können. Die folgende Definition fixiert die formale Sprache der Aussagenlogik; es handelt sich um eine rekursive Definition, wobei die Aussagenvariablen die Startelemente sind und die logischen Operationen als Generierungsregeln auftreten. Das dieser rekursiven Definition zugrunde liegende Alphabet besteht neben einer Menge an Aussagenvariablen aus den Symbolen
die als
nicht, und, oder, impliziert, genau dann, wenn, Klammer auf, Klammer zu
gelesen werden; die zugehörigen Substantive sind Negation, Konjunktion, Disjunktion, Implikation und Äquivalenz. Die Bezeichnungen orientieren sich natürlich an den später einzuführenden Bedeutungen, im Moment sind es lediglich Wörter für bestimmte Symbole. Die Sprache der Aussagenlogik wird als Teilmenge von realisiert, wobei ist.
Es sei eine Menge (deren Elemente wir als Aussagenvariable bezeichnen). Dann wird die zugehörige Sprache der Aussagenlogik (zu ) rekursiv durch folgende Regeln definiert.
- Jedes gehört zu .
- Wenn ist, so ist auch .
- Wenn sind, so sind auch .
Häufig verwendet man weniger Symbole, beispielsweise verzichtet man auf . Die Klammerungen werden oft auch anders gesetzt. Z.B. erlaubt man manchmal (ohne Klammer) oder man macht die Klammern außen, also . Sehr oft lässt man Klammern, um die Lesbarkeit der Aussagen zu erhöhen, einfach weg, obwohl dies vom syntaktischen Standpunkt aus ein schweres Vergehen ist.
Es seien Aussagenvariablen. Dann sind beispielsweise
korrekt gebildete Aussagen, d.h. sie gehören zu . Dagegen sind
keine Aussagen in (aber natürlich Wörter über dem gegebenen Alphabet).
Der Nachweis, dass ein gegebenes Wort eine korrekt gebildete Aussage ist, erfolgt über eine Ableitungskette oder einen Aussagestammbaum. Bei einer Ableitungskette listet man Zeile für Zeile korrekt gebildete Aussagen auf, wobei diese Aussagen entweder Aussagenvariablen oder aber mittels einer Rekursionsregel aus vorhergehenden Aussagen entstanden sind. Die letzte Zeile enthält die Aussage, deren Korrektheit man zeigen will.
Eine Ableitungskette für
sieht folgendermaßen aus.
- (Aussagenvariable),
- (Aussagenvariable),
- (Aussagenvariable),
- (Negation auf 2),
- (Konjunktion auf 1 und 3),
- (Disjunktion auf 4 und 3),
- (Implikation auf 5 und 6).
Ein Aussagenstammbaum ist eine graphisch übersichtliche Version einer Ableitungskette. Er beginnt mit den verwendeten Aussagenvariablen als Blättern und erzeugt dann Schritt für Schritt durch Vereinigungen von Zweigen die beteiligten Teilaussagen, bis schließlich die in Frage stehende Aussage als Stamm erzeugt ist.
Wir wollen uns anhand eines Stammbaumes klar machen, dass die Zeichenkette
eine Aussage ist, also gemäß den Regeln korrekt gebildet ist. Der Abstammungsbaum entsteht ausgehend von den Blättern, die die vorkommenden Aussagenvariablen (mit ihrer Häufigkeit) repräsentieren, indem man Schritt für Schritt komplexere Teilaussagen zusammensetzt.
Jede Aussage hat eine eindeutige „rekursive Geschichte“, d.h. es gibt für jede Aussage nur eine Abfolge von Rekursionsschritten (bis auf die Reihenfolge), um sie aus Aussagenvariablen aufzubauen, siehe Aufgabe 2.20.
- Aussagenlogische Interpretationen
Wir kommen zur Interpretation einer aussagenlogischen Sprache und insbesondere der darin auftretenden Junktoren. Der Ansatz ist, dass eine Aussagenvariable nur wahr oder falsch sein kann.
Es sei eine Menge von Variablen und die zugehörige aussagenlogische Sprache. Unter einer Wahrheitsbelegung versteht man eine Abbildung
(oder mit als Wertebereich).
Eine Wahrheitsbelegung ist also einfach dadurch gegeben, dass einer jeden Aussagenvariablen ein Wahrheitswert, nämlich oder bzw. oder zugeordnet wird. Eine solche Wahrheitsbelegung möchte man auf die gesamte Sprache fortsetzen, wobei die folgenden Festlegungen die inhaltliche Bedeutungen der Junktoren widerspiegeln. Die folgende Definition ist möglich, da der rekursive Aufbau einer Aussage eindeutig bestimmt ist.
Definition Definition 2.12 ändern
Es sei eine Menge von Variablen, die zugehörige aussagenlogische Sprache und
eine Wahrheitsbelegung. Unter der zugehörigen Interpretation versteht man die über den rekursiven Aufbau der Sprache festgelegte Abbildung
mit
- für jede Aussagenvariable .
- Bei
ist
- Bei
ist
- Bei
ist
- Bei
ist
- Bei
ist
Bei
sagt man, dass der Ausdruck bei der Wahrheitsbelegung (oder der Interpretation ) wahr wird (oder gilt), andernfalls, dass er falsch wird (nicht gilt). Dafür schreibt man auch bzw. . Mit bezeichnen wir die Menge aller bei der Interpretation wahren Ausdrücke aus der Sprache. Wenn eine Menge an Ausdrücken ist, so bedeutet , dass für alle gilt. Dafür sagt man auch, dass bei der Interpretation gilt oder dass ein Modell für ist.
Es sei und sei die Wahrheitsbelegung mit . Es sei die zugehörige Interpretation. Zur Berechnung des Wahrheitswertes von
unter dieser Interpretation muss man rekursiv gemäß Definition 2.12 die einzelnen Bestandteile auswerten. Es ist
und somit
Also ist
Andererseits ist
und daher ist
Der Ausdruck ist also bei dieser Wahrheitsbelegung nicht wahr.
- Fußnoten
- ↑ Oft spricht man einfach von einem Beweis durch Induktion.