Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 6

Aus Wikiversity
Prädikatenlogik


Mit der Aussagenlogik kann man keine gehaltvollen mathematischen Aussagen behandeln. Beispielsweise fehlt in ihr das Gleichheitszeichen, und man kann nicht über Variabeln, die sich auf eine Grundmenge beziehen, quantifizieren. Dies führt zur Prädikatenlogik, der wir uns nun zuwenden, und mit der man einen Großteil der (in einem gewissen Sinn die ganze) Mathematik ausdrücken kann. Von der mathematischen Praxis her ist sie aber immer noch recht restriktiv. Wir erinnern kurz an den Abbildungsbegriff und den Relationsbegriff der Mathematik und setzen eine naive Mengenlehre und die natürlichen Zahlen „zum Zählen“ voraus.


Definition  

Seien und Mengen. Eine Abbildung von nach ist dadurch gegeben, dass jedem Element der Menge genau ein Element der Menge zugeordnet wird. Das zu eindeutig bestimmte Element wird mit bezeichnet. Die Abbildung drückt man als Ganzes häufig durch

aus.


Definition  

Es seien zwei Mengen und gegeben. Dann nennt man die Menge

die Produktmenge der beiden Mengen.

Für uns ist insbesondere das -fache Produkt einer Menge mit sich selbst, also

(mit Faktoren) wichtig.


Definition  

Es sei eine Menge. Unter einer -stelligen Abbildung auf versteht man eine Abbildung

vom - fachen Produkt von mit sich selbst nach .


Definition  

Unter einer -stelligen Relation auf einer Menge versteht man eine Teilmenge der -fachen Produktmenge .

Eine -stellige Funktion kann auch als eine -stellige Relation aufgefasst werden, bei der es zu jedem -Tupel genau ein gibt derart, dass zur Relation gehört. Dieses ist dann der Funktionswert der zugehörigen Funktion an der Stelle .



Terme

Betrachten wir die sinnvollen Ausdrücke, die für eine natürliche Zahl stehen können. Mit dem Ziffernalphabet kann man mit der rekursiven Vorschrift zur Generierung von Zeichenreihen aus einem Alphabet alle natürlichen Zahlen (im Zehnersystem) aufschreiben, z.B. . Allerdings gibt es hier ein paar Schwierigkeiten, es sind nämlich auch die Zahlen , , 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

ist natürlich wahr, da links und rechts „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 lesen, sondern jeweils als ein neues „komplexes Zahlwort“, das sich aus den Ziffernsymbolen und und dem Malzeichen bzw. den Ziffernsymbolen und 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

wo vermutlich nach den erlaubten Werten für und 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[1]) Mengen.

  1. eine Variablenmenge ,
  2. eine Konstantenmenge ,
  3. zu jedem eine Menge 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 ) ein Funktionssymbol gibt (die Variablenmenge wird hingegen meistens als nicht leer angesetzt, und zwar mit unendlich vielen Variablen, die häufig als angesetzt werden). Die Konstanten kann man auch als nullstellige Funktionssymbole auffassen. Unter dem Termalphabet versteht man die Vereinigung .

Die arithmetische Grundtermmenge besteht aus den beiden Konstanten , den beiden zweistelligen Funktionssymbolen und einer Variablenmenge.


Definition  

Zu einer Grundtermmenge ist die zugehörige Termmenge (oder die Menge der -Terme) diejenige Teilmenge der Wörter über dem Termalphabet , die durch die folgenden rekursiven Vorschriften festgelegt wird.

  1. Jede Variable ist ein Term.
  2. Jede Konstante ist ein Term.
  3. Für jedes und Terme ist auch ein Term.

Hierbei sind und die Anfangsbedingungen und 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[2] und daran werden rechts davon die Terme angefügt (das wird später so interpretiert, dass in -stellige Funktionen 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 statt 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 , eine Konstantenmenge , die einstelligen Funktionssymbole und die zweistelligen Funktionssymbole gegeben. Dann sind die folgenden Wörter Terme.

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 gehört das Funktionssymbol?) und dann die folgenden Symbole in die geforderten 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

kann man mit (suggestiven) Klammern und Kommata nach und nach lesbarer gestalten. Er beginnt mit dem zweistelligen Funktionssymbol , also muss das Folgende aus zwei Termen bestehen. Es folgt zunächst das ebenfalls zweistellige Funktionssymbol , 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 verlangt wird. Die beiden Terme des an zweiter Stelle stehenden sind und . Man kann also den Term nach dieser Analyse auch als

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

Ü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[3] nebeneinander aufgeführt. Sie bilden die -te Reihe des Baumes. Wenn ein -stelliges Funktionssymbol auf 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 , die Konstantenmenge , die einstelligen Funktionssymbolmenge ( steht für Nachfolger) und die zweistellige Funktionssymbolmenge (für Addition und Multiplikation). Allein aus der Konstante und dem Nachfolgersymbol kann man dann für jede natürliche Zahl eine Repräsentierung finden, nämlich

Typische Terme sind dann Ausdrücke wie ( seien Variablen)

Wenn man statt , statt und statt schreibt, so „verschönern“ sich diese Terme zu

Mit den Abkürzungen , etc. wird daraus

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 , dem zehnten Nachfolger der .


Wir erklären noch, was die Variablenmenge eines Terms ist. Diese ist stets eine Teilmenge der Variablenmenge und enthält diejenigen Variablen, die in dem Term irgendwo vorkommen. Die rekursive Definition lautet folgendermaßen.

  1. Wenn eine Variable ist, so ist .
  2. Wenn eine Konstante ist, so ist .
  3. Wenn ein -stelliges Funktionssymbol ist und wenn Terme sind, so ist .
Aristoteles (384-322 v.C.) gilt als Erfinder der Prädikatenlogik. Er verwendet in seiner Analytik Variablen, einstellige Prädikate, Quantoren und die logischen Junktoren.

Nachdem wir die Terme zur Verfügung haben, fahren mit dem syntaktischen Aufbau der Ausdrücke in der Prädikatenlogik (mit Identität) fort. Um den Aufbau dieser formalen Sprache zu motivieren und das Verständnis der zunächst rein formalen Ausdrücke zu erleichtern, ist es hilfreich, an Bildungsweisen von mathematischen Aussagen zu erinnern. Der konsequente Aufbau der Syntax und der Semantik folgt in der nächsten Vorlesung.



Relationen

Ein Term kann weder wahr noch falsch sein, und zwar unabhängig davon, ob man ihn einfach als ein nach gewissen formalen Regeln aufgebautes Symbolwort auffasst oder ihn in einer bestimmten Menge (etwa den natürlichen Zahlen) interpretiert. Wahr oder falsch können nur Aussagen sein. Wichtig sind für uns zunächst die formalen Eigenschaften einer Aussage. In mathematischen Aussagen kommen häufig Terme zusammen mit einem Vergleichssymbol vor, z. B. in der (wahren) Gleichung

oder der (falschen) Abschätzung

Mit zwei Termen und dem Gleichheitszeichen oder Kleinerzeichen gelangt man also zu Aussagen, man spricht von zweistelligen Relationen (in Logik und Grammatik auch von zweistelligen Prädikaten). Der Wahrheitsgehalt hängt dabei von den zwei Eingaben ab.

Eine einstellige Relation oder ein Prädikat ist eine Eigenschaftsform, die einem Element zukommen kann oder nicht, z.B. die Eigenschaft einer natürlichen Zahl, prim zu sein oder gerade zu sein oder eine Quadratzahl zu sein, oder das Positivitätsprädikat, das besagt, dass eine reelle Zahl positiv ist. Einstellige Prädikate definieren eine Teilmenge einer gegebenen Grundmenge: Einem einstelligen Prädikat wird diejenige Teilmenge zugeordnet, die aus allen Elementen besteht, für die das Prädikat gilt. Daher entspricht die Mengenlehre weitgehend der Prädikatenlogik mit nur einstelligen Prädikaten.

Mit -stelligen Relationenssymbolen und Termen gelangt man ebenfalls zu einer Aussage. Wenn z.B. als Punkte in der Ebene interpretiert werden können, und die Relation „bildet ein gleichseitiges Dreieck“ bedeutet, so bedeutet , dass diese drei Punkte ein gleichseitiges Dreieck bilden. Der Wahrheitsgehalt hängt natürlich von der Lage der Punkte ab, hier interessiert aber lediglich, dass eine sinnvolle Aussageform repräsentiert.

Andere geometrische Beispiele für dreistellige Relationen sind die Eigenschaften, dass die drei Punkte auf einer Geraden liegen, sagen wir , oder dass die drei Punkte ein rechtwinkliges Dreieck bilden, wobei der rechte Winkel an dem zuerst genannten Eckpunkt liegen muss, sagen wir . Man kann sich darüber streiten, ob bei einem Dreieck die Eckpunkte alle verschieden sein müssen, jedenfalls kann man die Eigenschaft der drei Punkte, dass sie paarweise verschieden sind, durch ein dreistelliges Prädikat ausdrücken, sagen wir .



Quantoren

Mathematische Aussage enthalten häufig auch Existenzaussagen. Wenn wir bei dem eben erwähnten Beispiel bleiben, so bedeutet

die Aussage, dass es zu gegebenen festen und ein gibt derart, dass die drei Punkte ein gleichseitiges Dreieck bilden (diese Aussage ist in der reellen Zahlenebene wahr). In dem Beispielsatz wird nur über quantifiziert, nicht über und . Dies kann man durch die folgenden Aussagen erreichen.

was bedeutet, dass es Punkte gibt, die ein gleichseitiges Dreieck bilden, die wahr ist, aber deutlich schwächer als die Aussage

ist, die behauptet, dass es zu (beliebig vorgegebenen) Eckpunkten und stets einen dritten Punkt gibt, so dass ein gleichseitiges Dreieck entsteht.[4] Die Ausdrücke „es gibt“ und „für alle“ nennt man Quantoren. Für diese Quantoren gibt es spezielle Symbole, nämlich für „es gibt“ und für „für alle“. Die obigen Beispielsätze schreibt man dann formal als

bzw. als

Auf die Reihenfolge bei gleichartigen Quantoren kommt es nicht an (dies ist von der inhaltlichen Bedeutung her klar, wird später aber auch formal im Ableitungskalkül nachgebildet), sie ist aber bei wechselnden Quantoren entscheidend. Beispielsweise ist die Aussage

(also die Aussage, dass es einen Punkt gibt, der mit je zwei beliebigen weiteren Punkten ein gleichseitiges Dreieck bildet) im Gegensatz zur vorherigen Aussage nicht wahr.



Junktoren

Eine weitere Art von mathematischen Aussagen entsteht dadurch, dass man Aussagen selbst zueinander in eine logische Beziehung setzt, indem man beispielsweise sagt, dass aus der Aussage die Aussage folgt, oder dass und zueinander äquivalent sind. Der Satz des Pythagoras besagt, dass wenn zwischen drei Punkten in der Ebene die Beziehung der Rechtwinkligkeit am Punkt besteht, dass dann zwischen den durch die drei Punkte definierten Streckenlängen ebenfalls eine bestimmte Beziehung zwischen den Abständen[5] besteht. Wenn man die Rechtwinkligkeit wie oben mit dem dreistelligen Relationssymbol und die pythagoreische Längenbeziehung mit dem dreistelligen Relationssymbol bezeichnet, so gilt also

was wir formal als

schreiben. Gilt davon auch die Umkehrung? Folgt also aus , dass ein rechter Winkel an vorliegt? Dies ist in der Tat der Fall! Der Kosinussatz besagt für ein beliebiges (echtes) Dreieck mit einem an anliegenden Winkel , dass

gilt, wobei den Abstand zwischen zwei Punkten bezeichne. Der „Störterm“ rechts entfällt genau dann, wenn ist, und dies ist nur bei Grad der Fall. Daher gilt die Äquivalenz

(ein Dreieck, bei dem zwei Eckpunkte zusammenfallen, akzeptieren wir als rechtwinklig an dem doppelten Punkt).

Unser Rechtwinkligkeitsprädikat besagt, dass der Winkel am Eckpunkt ein Rechter ist. Wenn man sich dafür interessiert, ob überhaupt ein rechtwinkliges Dreieck vorliegt, so muss oder oder gelten. Die Oderverknüpfung wird formal als

geschrieben (die Assoziativität der oder-Verknüpfung steht im Moment noch nicht zur Verfügung).

Für ein echtes Dreieck haben wir oben gefordert, dass die konstituierenden Punkte paarweise verschieden sind. Die Gleichheit von zwei Punkten wird durch und die Negation davon, also die Verschiedenheit der beiden Punkte, wird in der Mathematik durch , in der Logik aber durch ausgedrückt. Dass drei Punkte paarweise verschieden sind, erfordert ein logisches und, das durch symbolisiert wird, so dass sich die Echtheit eines Dreiecks durch

ausdrücken lässt.



Fußnoten
  1. Zwei Mengen und heißen disjunkt, wenn ihr Durchschnitt ist.
  2. Man spricht von polnischer Notation.
  3. Dies ist die graphentheoretische Bezeichnung für die Startpunkte eines Baumes.
  4. Die Gültigkeit dieser Aussagen setzt voraus, dass wir über den reellen Zahlen bzw. in der reellen Zahlenebene arbeiten. Siehe Aufgabe 6.16.
  5. Zur Erinnerung: Das Quadrat der Streckenlänge zwischen und (die Hypotenuse) ist gleich der Summe der Quadrate der beiden Streckenlängen zwischen und und und (den Katheten).


<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2016) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)