Lektion 3.1

Von Aussagen zu Prädikaten

12 min Lesezeit

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: p3,p5,p7,…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)P(x): "xx ist eine Primzahl"
- G(x)G(x): "xx ist gerade"
- K(x,y)K(x, y): "xx ist kleiner als yy"

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

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

P(x) wird zu einer Aussage, wenn man fu¨r x ein Objekt einsetztP(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:

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

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

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

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

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

Mathematische Aussagen formalisieren

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

∀x:(Prim(x)∧x>2)→Ungerade(x)\forall x: (\text{Prim}(x) \land x > 2) \rightarrow \text{Ungerade}(x)

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

"Es gibt unendlich viele Primzahlen."

∀n:∃p:(p>n∧Prim(p))\forall n: \exists p: (p > n \land \text{Prim}(p))

Gelesen: "Zu jeder Zahl nn existiert eine Primzahl pp, die größer als nn ist."

Zusammenfassung

  • Die Aussagenlogik kann keine Quantoren ("alle", "existiert") ausdrücken

  • Prädikate sind Aussagen mit Lücken: P(x)P(x)

  • ∀x\forall x (Allquantor): "für alle x"

  • ∃x\exists x (Existenzquantor): "es existiert ein x"

Übungen

Aufgabe 1Multiple Choice

Welche Aussage kann die Aussagenlogik NICHT ausdrücken?

Lektion 3.1 · Prädikatenlogik
• • •

Von Aussagen zu Prädikaten

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: p3,p5,p7,…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)P(x): "xx ist eine Primzahl"
- G(x)G(x): "xx ist gerade"
- K(x,y)K(x, y): "xx ist kleiner als yy"

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

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

P(x) wird zu einer Aussage, wenn man fu¨r x ein Objekt einsetztP(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:

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

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

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

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

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

Mathematische Aussagen formalisieren

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

∀x:(Prim(x)∧x>2)→Ungerade(x)\forall x: (\text{Prim}(x) \land x > 2) \rightarrow \text{Ungerade}(x)

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

"Es gibt unendlich viele Primzahlen."

∀n:∃p:(p>n∧Prim(p))\forall n: \exists p: (p > n \land \text{Prim}(p))

Gelesen: "Zu jeder Zahl nn existiert eine Primzahl pp, die größer als nn ist."

Zusammenfassung

  • Die Aussagenlogik kann keine Quantoren ("alle", "existiert") ausdrücken

  • Prädikate sind Aussagen mit Lücken: P(x)P(x)

  • ∀x\forall x (Allquantor): "für alle x"

  • ∃x\exists x (Existenzquantor): "es existiert ein x"

—