Von Aussagen zu Prädikaten · Prädikatenlogik

Die Aussagenlogik ist mächtig, aber sie hat Grenzen. Betrachte diese mathematische Aussage:

"Alle Primzahlen größer als 2 sind ungerade."

Wie würden wir das in Aussagenlogik ausdrücken? Wir könnten für jede Primzahl eine Variable einführen: $p_3, p_5, p_7, \ldots$

Aber es gibt unendlich viele Primzahlen – wir bräuchten unendlich viele Variablen! Außerdem verlieren wir den Zusammenhang zwischen "ist Primzahl" und "ist ungerade".

Für solche Aussagen brauchen wir ein neues Werkzeug: Die Prädikatenlogik.

Das Problem: "Alle" und "Es gibt"

Die Aussagenlogik kann folgende Formulierungen nicht direkt ausdrücken:

"Für alle Zahlen gilt..."
"Es existiert eine Zahl, die..."

Diese Wörter heißen Quantoren:

$\forall$ – "für alle" (Allquantor)
$\exists$ – "es existiert" (Existenzquantor)

Die Prädikatenlogik erweitert die Aussagenlogik um diese Quantoren.

Definition

Prädikate

Ein Prädikat ist eine Aussage mit einer "Lücke", die erst durch ein Objekt zur echten Aussage wird.

Beispiele:

$P(x)$ : " $x$ ist eine Primzahl"
$G(x)$ : " $x$ ist gerade"
$K(x, y)$ : " $x$ ist kleiner als $y$ "

Für sich allein ist $P(x)$ keine Aussage – es fehlt ein konkreter Wert für $x$ .

Erst $P(7)$ ("7 ist eine Primzahl") ist eine Aussage (und zwar eine wahre).

P(x) \text{ wird zu einer Aussage, wenn man für } x \text{ ein Objekt einsetzt}

Definition

Quantoren

Mit Quantoren machen wir aus Prädikaten Aussagen:

$\forall x: P(x)$ – "Für alle $x$ gilt $P(x)$ "

$\exists x: P(x)$ – "Es existiert ein $x$ mit $P(x)$ "

Beispiele:
$\forall x \in \mathbb{N}: x + 1 > x$ ("Jede natürliche Zahl ist kleiner als ihr Nachfolger")

$\exists x \in \mathbb{N}: x > 100$ ("Es gibt eine natürliche Zahl größer als 100")

\forall x: P(x) \quad \text{und} \quad \exists x: P(x)

Beispiel

Mathematische Aussagen formalisieren

"Alle Primzahlen größer als 2 sind ungerade."

$\forall x: (\text{Prim}(x) \land x > 2) \rightarrow \text{Ungerade}(x)$

Gelesen: "Für alle $x$ gilt: Wenn $x$ eine Primzahl ist und $x > 2$ , dann ist $x$ ungerade."

"Es gibt unendlich viele Primzahlen."

$\forall n: \exists p: (p > n \land \text{Prim}(p))$

Gelesen: "Zu jeder Zahl $n$ existiert eine Primzahl $p$ , die größer als $n$ ist."

Zusammenfassung

Die Aussagenlogik kann keine Quantoren ("alle", "existiert") ausdrücken
Prädikate sind Aussagen mit Lücken: $P(x)$
$\forall x$ (Allquantor): "für alle x"
$\exists x$ (Existenzquantor): "es existiert ein x"

Mathematische Aussagen formalisieren

Zusammenfassung

Übungen