Prädikatenlogik – Serlo „Mathe für Nicht-Freaks“

Aus Wikibooks

Dieser Abschnitt ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib den Autoren Zeit, den Inhalt anzupassen!

Arithmetische Operationssymbole

In den beiden Kapiteln Quantoren und Aussageform und Substitution haben wir Begriffe eingführt, die über die Aussagenlogik hinaus gehen und zur Prädikatenlogik gehören. Wir fassen diese Begriffe am Beispiel der Arithmetik noch einmal zusammen.

Beispiel Arithmetik[Bearbeiten]

Wenn wir über die natürlichen Zahlen reden wollen, dann brauchen wir Variable , die für beliebige natürliche Zahlen stehen. Für die speziellen Zahlen benötigen wir Konstanten. Des Weiteren brauchen wir Operationssymbole für die vier Rechenarten . Anstelle von und werden oft auch die Symbole und verwendet. Diese Operationen sind alle 2-stellig. Mit diesem Material können wir Terme bilden, die weitere Zahlen bezeichnen, zum Beispiel:

Um auszudrücken, dass zwei Terme dieselbe Zahl bezeichnen benötigen wir das Gleichheitszeichen und für Ungleichungen das 2-stellige Prädikat Kleiner-oder-gleich . Die weiteren Ordnungen lassen sich dann definieren. Ein 1-stelliges Prädikat mit der Bedeutung "... ist eine natürliche Zahl" ersetzt , die Menge der natürlichen Zahlen. Diese steht erst in der sogenannten Klassenlogik zur Verfügung. Und der wichtigste Teil der Prädikatenlogik sind die Quantoren . Natürlich stehen die Junktoren weiterhin zur Verfügung. Damit können wir wesentlich mehr Formeln bilden als in der Aussagenlogik. Insbesondere können wir die atomaren Formeln der Aussagenlogik nun genauer analysieren.

Beispiel 1: In der Aussagenlogik konnten wir die Aussage " ist kleiner als und ist gerade." nur in der Form wiedergeben. Nun geht es so:

Dabei ist ein einstelliges Prädikat mit der Bedeutung "... ist gerade".

Beispiel 2: Eine Zahl ist bekanntlich genau dann gerade, wenn sie das Doppelte einer natürlichen Zahl ist. Das heißt, dass es eine natürliche Zahl gibt, so dass gilt:

Beispiel 3: Wie können wir folgende Aussage formalisieren? "Für beliebige Zahlen und gilt: Ist verschieden von und kleiner-oder-gleich , dann ist die Differenz von und keine natürliche Zahl."

Mit der Definition von Echt-kleiner lässt sich das noch vereinfachen:

Die Sprache der Prädikatenlogik[Bearbeiten]

Wir erweitern das Alphabet der Aussagenlogik wie folgt:

Definition (Alphabet der Prädikatenlogik)

Die Sprache der Prädikatenlogik hat neun Arten von Zeichen:

  1. die Aussagenkonstanten , und ,
  2. die Junktoren , , , , und ,
  3. die Klammern und ,
  4. die Individuenkonstanten ,
  5. die Operationssymbole ,
  6. die Prädikate ,
  7. das Gleichheitszeichen ,
  8. die Variable ,
  9. die Quantoren , und .

Jedem Prädikat und jedem Operationssymbol ist eine natürliche Zahl als Stellenzahl zugeordnet.

Die Prädikate werden auch Relationszeichen genannt und die Operationssymbole heißen auch Funktionszeichen.

Definition (Terme der Prädikatenlogik)

Die Terme der Prädikatenlogik werden nach folgenden Regeln gebildet:

  1. Jede Individuenkonstante ist ein Term.
  2. Sind Terme und ist ein -stelliges Operationssymbol, so ist ein Term.

Es gibt keine weiteren Terme.

Definition (Formeln der Prädikatenlogik)

Die Formeln der Aussagenlogik werden nach folgenden Regeln gebildet:

  1. Jede Aussagenkonstante ist eine Formel, und sind Formeln.
  2. Ist eine Formel, so ist auch eine Formel.
  3. Sind und Formeln, so sind auch , , , und Formeln.
  4. Sind Terme und ist ein -stelliges Prädikat, so ist eine Formel.
  5. Sind und Terme, so ist eine Formel.
  6. Ist eine Variable und ist eine Formel, so sind   ,     und     Formeln.

Es gibt keine weiteren Formeln.

Die Regeln 1. bis 3. sind dieselben, wie in der Aussagenlogik. Deshalb sind alle Formeln der Aussagenlogik auch Formeln der Prädikatenlogik! Zusätzlich können die Regeln 2. und 3. auf weitere Formeln angewendet werden, z.B. auf Formeln, die mit Prädikaten und Quantoren gebildet wurden. Wir halten fest:

Satz

Alle Formeln der Aussagenlogik sind auch Formeln der Prädikatenlogik.

Ein Ausdruck der Prädikatenlogik ist ein Term oder eine Formel.