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

UnderCon icon.svg

Dieser Abschnitt ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib der Autorin oder dem Autor Zeit, den Inhalt anzupassen!

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.

Arithmetische Operationssymbole

Beispiel ArithmetikBearbeiten

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ädikatenlogikBearbeiten

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.