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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Prädikatenlogik
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.

Wir beginnen mit dem syntaktischen Aufbau der Prädikatenlogik mit Identität. 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 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 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.[1] 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 anderen beliebigen Punkten eine 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[2] besteht. Wenn man die Rechtwinkligkeit wie oben mit dem dreistelligen Relationssymbol und die Streckenbeziehung mit dem dreistelligen Relationssymbol bezeichnet, so gilt also

was wir formal als

schreiben. Gilt davon auch die Umkehrung? Folgt also aus der (für den Satz des Pythagoras typischen Streckenbeziehung) , 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 können wir die Äquivalenz

schreiben (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.



Sprachen erster Sufe

Die erwähnten Konstruktionsmöglichkeiten für Aussagen sind im Wesentlichen schon erschöpfend. Mit ihnen kann man formale Sprachen aufbauen, deren Aussagekraft prinzipiell groß genug ist, um die gesamte Mathematik auszudrücken (für viele Bereiche wäre es aber künstlich, sich auf diese Sprachen zu beschränken). Diese formalen Sprachen nennt man Sprachen erster Stufe, wir beginnen mit den zugehörigen Alphabeten.


Definition  

Ein Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.

  1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
  2. Zu jeder natürlichen Zahl eine Menge von -stelligen Relationssymbolen.
  3. Die aussagenlogischen Junktoren
  4. Das Gleichheitszeichen .
  5. Die Quantoren und .
  6. Klammern, also und .

Die aussagenlogischen Junktoren werden als Negation, Konjunktion (und), Disjunktion (Alteration, einschließliches Oder), Implikation (wenn, dann) und Äquivalenz (genau dann, wenn) bezeichnet. Der Quantor heißt Allquantor und heißt Existenzquantor. Diese Liste ist etwas redundant, da man, von der späteren Interpretation her gesehen, einige aussagenlogische Junktoren durch andere ersetzen kann, beispielsweise ist für zwei Aussagen und die Aussage gleichwertig mit , und so könnte man den Implikationspfeil auch weglassen. Ebenso kann man den einen Quantor mit Hilfe des anderen und der Negation ausdrücken, es ist nämlich gleichbedeutend mit . Um die Lesbarkeit von Ausdrücken zu erhöhen ist es aber alles in allem vorteilhaft, nicht allzu minimalistisch sein zu wollen (man könnte die unnötigen Symbole auch als Abkürzungen einführen). Das Gleichheitszeichen könnte man zwar auch als ein weiteres zweistelliges Relationssymbol auffassen, allerdings sind die weiter unten einzuführenden Schlussregeln für das Gleichheitszeichen (insbesondere die Möglichkeit einzusetzen) für die Logik erster Stufe konstitutiv. Da ein Alphabet einer Sprache erster Stufe eine Termgrundmenge enthält, ist klar, was als Term in der Sprache zu gelten hat. Als nächstes erklären wir formal, was wir als einen Ausdruck (oder eine formale Aussage) in dieser Sprache ansehen.


Definition  

Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann nennt man die folgenden rekursiv definierten Wörter über diesem Alphabet die Ausdrücke dieser Sprache.

  1. Wenn und Terme sind, so ist

    ein Ausdruck.

  2. Wenn ein -stelliges Relationssymbol ist und Terme sind, so ist

    ein Ausdruck.

  3. Wenn und Ausdrücke sind, so sind auch

    Ausdrücke.

  4. Wenn ein Ausdruck ist und eine Variable, so sind auch

    Ausdrücke.

Die Klammern sind hier auch nur nötig, weil wir die zweistelligen Junktoren anders als die Funktionssymbole in der Mitte schreiben. Die Menge der Konstanten, der Variablen, der Funktionssymbole und der Relationssymbole nennt man zusammen auch das Symbolalphabet der Sprache. Die anderen Symbole (Junktoren, Quantoren, Gleichheitszeichen, Klammern) sind immer gleich, so dass eine Sprache erster Stufe im Wesentlichen nur von der gewählten Symbolmenge abhängt. Für die zugehörige Sprache schreibt man .



Freie und gebundene Variablen

In einem Ausdruck über einem Symbolalphabet nennt man die Variablen, die (und zwar für jedes Vorkommen) innerhalb der Reichweite eines Quantors stehen, gebunden, die anderen frei. Dies wird streng über den Aufbau der Ausdrücke definiert.

  1. für ein -stelliges Relationssymbol und Terme .

  2. für einen Ausdruck .

  3. für Ausdrücke und . Ebenso für .

  4. für einen Ausdruck und eine Variable .

  5. für einen Ausdruck und eine Variable .

Einen Ausdruck ohne freie Variablen nennt man einen Satz, auch wenn diese Bezeichnung nicht ganz glücklich ist, da „Satz“ die Gültigkeit einer Aussage suggeriert. Die Menge der Sätze wird mit bezeichnet, die Menge der Ausdrücke mit genau einer freien Variablen (die aber in dem Ausdruck beliebig oft vorkommen darf) mit .



Fußnoten
  1. Die Gültigkeit dieser Aussagen setzt voraus, dass wir über den reellen Zahlen bzw. in der reellen Zahlenebene arbeiten.
  2. 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 2011-2012) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)