Benutzer:Jürgen-Michael Glubrecht/Prädikatenlogik

Prädikatenlogik

Für den Umgang mit Junktoren habe wir mit den Wahrheitstaellen ein Verfahren kennengelernt, mit dem wir immer ermitteln können, ob eine Aussage allgemeingültig ist. Für Aussagen, in denen Quantoren vorkommen, reicht das nicht. Was macht uns also sicher, dass die Äquivalenz

$\neg (\forall x:A(x))\iff \exists x:\neg A(x)$

immer richtig ist, egal was $A(x)$ genau bedeutet? Betrachten wir als Beispiel die folgende Aussage über die natürlichen Zahlen: $N$:

Alle ungeraden Zahlen ab 3 sind Primzahlen.

Wir können anfangen, das der Reihe nach zu testen: 3 ist eine Primzahl, 5 ist eine Primzahl, 7 ist eine Primzahl, usw. Aber da es bekanntlich unendlich viele natürliche Zahlen gibt, werden wir damit nicht fertig. Im Beispiel haben wir Glück, denn schon die nächste Zahl liefert ein Gegenbeispiel: 9 ist keine Primzahl. Also ist die Aussage falsch. Da wir nicht unendlich viele Aussagen durchprobieren können, müssen wir uns für die Quantoren einen anderen Weg suchen, Aussagen zu beweisen.

Eine formale Sprache

Für die Prädikatenlogik erweitern wir die Sprache der Aussagenlogik.

Alphabet

In der Prädikatenlogik gibt es 9 Arten von Zeichen:

1. Aussagenkonstante $\alpha$, $\beta$, $\gamma$, ...
2. Junktoren $\top$, $\bot$, $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$
3. Klammern $($, $)$
4. Individuenkonstanten $a$, $b$, $c$, ...
5. Prädikate $P$, $Q$, $R$, ...
6. Variable $x$, $y$, $z$, ...
7. Quantoren $\forall$, $\exists$

Die ersten drei Arten von Zeichen entsprechen denen der Aussagenlogik.

Grammatik

In der Prädikatenlogik gibt es zwei Arten von wohlgeformten Zeichenreihen, nämmlich Formeln und Terme. Die ersten drei Regeln entsprechen denen der Aussagenlogik:

1. Jede Aussagenkonstante ist eine Formel, $\top$ und $\bot$ sind Formeln.
2. Ist $\phi$ eine Formel, so ist auch $\neg \phi$ eine Formel.
3. Sind sowohl $\phi \,$ als auch $\psi \,$ Formeln, so sind auch $(\phi \wedge \psi )$, $(\phi \vee \psi )$, $(\phi \rightarrow \psi )$ und $(\phi \leftrightarrow \psi )$ Formeln.
4. Jede Individuenkonstante und jede Variable ist ein Term.
5. Ist $P$ ein $n$-stelliges Prädikat, und sind $t_{1},t_{2},t_{3},\dotsc ,t_{n}$ Terme, so ist $P(t_{1},t_{2},t_{3},\dotsc ,t_{n})$ eine Formel.
6. Ist $\phi$ eine Formel und $x$ eine Variable, so sind $\forall x\phi$ und $\exists x\phi$ Formeln.

Es gibt keine weiteren Formeln und Terme. Aus dieser Definition ergibt sich sofort:

Die Regeln 1. bis 3. der Grammatik stimmen zwar wörtlich mit denen der Aussaglogik überein, aber ihr Anwendungsbereich ist sehr viel umfangreicher. Ist $P$ ein 1-stelliges Prädikat, $c$ eine Individuenkonstante und $x$ eine Variable, so sind beispielsweise $P(c)$ und $\exists x\,P(x)$ Formeln nach den Regeln 6. und 8. Mit der Regel 3. können wir daraus die Formel $(P(c)\rightarrow \exists x\,P(x))$ bilden.

Die Anzahl der Formeln und Terme hängt nun nicht allein von der Anzahl der Aussagenkonstanten ab, wie das in der Aussagenlogik war. Vielmehr hängt es auch von der Anzahl der Individuenkonstanten, der Relationen, der Funktionszeichen und der Variablen ab, wieviele Formeln und Terme es gibt.

Die Bedeutung

In der Prädikatenlogik muss nicht nur den Formeln einer der Wahrheitswerte Wahr oder Falsch zugeordnet werden, sondern es muss auch für die Terme eine Bedeutung festgelegt werden.

Definition:

Eine Bewertung ${\mathcal {J}}$

1. legt eine nichtleere Menge ${\mathfrak {B}}$ als Individuenbereich fest,
2. ordnet allen Individuenkonstanten $c$ ein Element von ${\mathfrak {B}}$ zu,
3. ordnet jeder $n$-stelligen Relation $R$ eine $n$-stellige Relation über ${\mathfrak {B}}^{n}$ zu,
4. ordnet allen Variablen $x$ ein Element aus ${\mathfrak {B}}$ zu,
5. ordnet allen Aussagenkonstanten $\alpha$ einen Wahrheitswert ${\mathsf {W}}$ oder ${\mathsf {F}}$ zu.

Es gilt als für eine Bewertung ${\mathcal {J}}$:

1. ${\mathfrak {B}}\neq \varnothing$
2. ${\mathcal {J}}(c)\in {\mathfrak {B}}$
3. ${\mathcal {J}}(R)\subseteq {\mathfrak {B}}^{n}$
4. ${\mathcal {J}}(x)\in {\mathfrak {B}}$
5. ${\mathcal {J}}(\alpha )\in \{{\mathsf {W}},{\mathsf {F}}}\$

Wir setzen die Bewertung wie folgt auf alle Terme und Formeln fort:

1. ${\mathcal {J}}(R(x_{1},x_{2},x_{3},\dots ,x_{n}))={\begin{cases}{\mathsf {W}},&({\mathcal {J}}(x_{1}),{\mathcal {J}}(x_{2}),{\mathcal {J}}(x_{3}),\dots ,{\mathcal {J}}(x_{n}))\in {\mathfrak {B}}^{n}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
2. ${\mathcal {J}}(\top )={\mathsf {W}}$   und   ${\mathcal {J}}(\bot )={\mathsf {F}}$
3. ${\mathcal {J}}(\neg \phi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {F}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
4. ${\mathcal {J}}(\phi \land \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
5. ${\mathcal {J}}(\phi \lor \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
6. ${\mathcal {J}}(\phi \rightarrow \psi )={\begin{cases}{\mathsf {W}},&{\text{sonst}}\\{\mathsf {F}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {F}}\end{cases}}$
7. ${\mathcal {J}}(\phi \leftrightarrow \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathcal {J}}(\psi )\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
8. ${\mathcal {J}}(\forall x\phi (x))={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}{^{x}_{b}}(\phi (x)){\text{ für alle }}b\in {\mathfrak {B}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
9. ${\mathcal {J}}(\exists x\phi (x))={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}{^{x}_{b}}(\phi (x)){\text{ für ein }}b\in {\mathfrak {B}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$

Kalkül

Grundregeln

Regeln für den Allquantor
${\frac {\Gamma ,\phi \vdash \Delta }{\Gamma ,\forall x\,\phi \vdash \Delta }}$	${\frac {\Gamma \vdash \phi ,\Delta }{\Gamma \vdash \forall x\,\phi ,\Delta }}$ wenn $x$ nicht frei in $\Gamma$ und $\Delta$

Regeln für den Existenzquantor
${\frac {\Gamma ,\phi \vdash \Delta }{\Gamma ,\exists x\,\phi \vdash \Delta }}$ wenn $x$ nicht frei in $\Gamma$ und $\Delta$	${\frac {\Gamma \vdash \phi ,\Delta }{\Gamma \vdash \exists x\,\phi ,\Delta }}$