Mathe für Nicht-Freaks: Prädikatenlogik

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

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

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

• $3\cdot (1+2)-x$
• $(17+4):7$

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 $\le$. Die weiteren Ordnungen lassen sich dann definieren. Ein 1-stelliges Prädikat $𝒩$ mit der Bedeutung "... ist eine natürliche Zahl" ersetzt $N$, 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 $\mathrm{\forall },\mathrm{\exists },\mathrm{\exists }!$. Natürlich stehen die Junktoren $\mathrm{\neg },\wedge ,\vee ,\dot{\vee },\Rightarrow ,\iff$ 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 "$2$ ist kleiner als $36$ und $5$ ist gerade." nur in der Form $A\wedge B$ wiedergeben. Nun geht es so:

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

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

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

Mit der Definition von Echt-kleiner $x<y:⟺\mathrm{\neg }(x=y)\wedge x\le y$ lässt sich das noch vereinfachen:

Die Sprache der Prädikatenlogik

Wir erweitern das Alphabet der Aussagenlogik wie folgt:

Mathe für Nicht-Freaks: Vorlage:Definition Die Prädikate werden auch Relationszeichen genannt und die Operationssymbole heißen auch Funktionszeichen.

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:

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

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}