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

Dieser Abschnitt ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib den Autoren 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 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 $\div$ 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 $\leq$. Die weiteren Ordnungen lassen sich dann definieren. Ein 1-stelliges Prädikat ${\mathcal {N}}$ 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 $\forall ,\exists ,\exists !$. Natürlich stehen die Junktoren $\neg ,\land ,\lor ,{\dot {\lor }},\Rightarrow ,\Leftrightarrow$ 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\land B$ wiedergeben. Nun geht es so:

$(2\leq 36)\land {\mathcal {G}}(5)$

Dabei ist ${\mathcal {G}}$ 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:

${\mathcal {G}}(z)\Leftrightarrow \exists x:({\mathcal {N}}(x)\land 2\cdot x=z)$

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."

$\forall x:\forall y:(\neg (x=y)\land x\leq y\Rightarrow \neg {\mathcal {N}}(x-y))$

Mit der Definition von Echt-kleiner ${\color {OrangeRed}x<y}:\iff \neg (x=y)\land x\leq y$ lässt sich das noch vereinfachen:

$\forall x:\forall y:(x<y\Rightarrow \neg {\mathcal {N}}(x-y))$

Die Sprache der Prädikatenlogik

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 $K_{0},K_{1},K_{2},\dots$, ${\mathsf {W}}$ und ${\mathsf {F}}$,
2. die Junktoren $\neg$, $\land$, $\lor$, ${\dot {\lor }}$, $\Rightarrow$ und $\Leftrightarrow$,
3. die Klammern $($ und $)$,
4. die Individuenkonstanten $c_{0},c_{1},c_{2},\dots$,
5. die Operationssymbole $F_{0},F_{1},F_{2},\dots$,
6. die Prädikate $P_{0},P_{1},P_{2},\dots$,
7. das Gleichheitszeichen $=$,
8. die Variable $v_{0},v_{1},v_{2},\dots$,
9. die Quantoren $\forall$, $\exists$ und $\exists !$.

Jedem Prädikat und jedem Operationssymbol ist eine natürliche Zahl $n$ 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 $c$ ist ein Term.
2. Sind $t_{1},t_{2},\dots ,t_{n}$ Terme und ist $F$ ein $n$-stelliges Operationssymbol, so ist $F(t_{1},t_{2},\dots ,t_{n})$ 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, ${\mathsf {W}}$ und ${\mathsf {F}}$ sind Formeln.
2. Ist $A$ eine Formel, so ist auch $\neg A$ eine Formel.
3. Sind $A$ und $B$ Formeln, so sind auch $(A\land B)$, $(A\lor B)$, $(A{\dot {\lor }}B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$ Formeln.
4. Sind $t_{1},t_{2},\dots ,t_{n}$ Terme und ist $P$ ein $n$-stelliges Prädikat, so ist $P(t_{1},t_{2},\dots ,t_{n})$ eine Formel.
5. Sind $t$ und $s$ Terme, so ist $t=s$ eine Formel.
6. Ist $x$ eine Variable und ist $A$ eine Formel, so sind   $\forall x:A$,   $\exists x:A$   und   $\exists !x:A$   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.