Lektion 3.2

Quantoren verstehen

15 min Lesezeit

In der letzten Lektion haben wir die Quantoren ∀\forall und ∃\exists kennengelernt. Jetzt vertiefen wir unser Verständnis: Wie liest man komplexe Formeln? Wie negiert man Quantoren?

Definition

Kombination von Quantoren

Oft brauchen wir mehrere Quantoren:

∀x:∃y:x<y\forall x: \exists y: x < y
"Für jedes xx gibt es ein yy mit x<yx < y."
(Zu jeder Zahl gibt es eine größere.)

∃y:∀x:x<y\exists y: \forall x: x < y
"Es gibt ein yy, sodass für alle xx gilt: x<yx < y."
(Es gibt eine größte Zahl.)

Achtung: Die Reihenfolge der Quantoren ist wichtig!
Die erste Aussage ist wahr (in N\mathbb{N}), die zweite ist falsch.

∀x:∃y:P(x,y)≠∃y:∀x:P(x,y)\forall x: \exists y: P(x,y) \quad \neq \quad \exists y: \forall x: P(x,y)
Beispiel

Die Reihenfolge macht den Unterschied

Beispiel 1: "Jeder Mensch hat eine Mutter."
∀x:∃y:Mutter(y,x)\forall x: \exists y: \text{Mutter}(y, x)
(Zu jedem Menschen xx existiert ein Mensch yy, der Mutter von xx ist.)

Beispiel 2: "Es gibt eine Frau, die Mutter aller Menschen ist."
∃y:∀x:Mutter(y,x)\exists y: \forall x: \text{Mutter}(y, x)
(Es existiert ein Mensch yy, der von allen Menschen Mutter ist.)

Die erste Aussage ist wahr, die zweite offensichtlich falsch!

Definition

Negation von Quantoren

Die Negation von Quantoren folgt einfachen Regeln:

¬(∀x:P(x))≡∃x:¬P(x)\neg(\forall x: P(x)) \equiv \exists x: \neg P(x)

¬(∃x:P(x))≡∀x:¬P(x)\neg(\exists x: P(x)) \equiv \forall x: \neg P(x)

In Worten:

  • "Nicht alle..." bedeutet "Es gibt mindestens eins, das nicht..."
  • "Es gibt kein..." bedeutet "Alle sind nicht..."
¬∀≡∃¬und¬∃≡∀¬\neg \forall \equiv \exists \neg \quad \text{und} \quad \neg \exists \equiv \forall \neg
Beispiel

Negationen bilden

Aussage: "Alle Schwäne sind weiß."
∀x:Schwan(x)→Weiß(x)\forall x: \text{Schwan}(x) \rightarrow \text{Weiß}(x)

Negation: "Nicht alle Schwäne sind weiß."
∃x:Schwan(x)∧¬Weiß(x)\exists x: \text{Schwan}(x) \land \neg\text{Weiß}(x)
"Es gibt einen Schwan, der nicht weiß ist."

Aussage: "Es gibt eine reelle Zahl, deren Quadrat negativ ist."
∃x∈R:x2<0\exists x \in \mathbb{R}: x^2 < 0

Negation: "Keine reelle Zahl hat ein negatives Quadrat."
∀x∈R:x2≥0\forall x \in \mathbb{R}: x^2 \geq 0

Zusammenfassung

  • Die Reihenfolge der Quantoren ist wichtig!

  • ¬(∀x:P(x))≡∃x:¬P(x)\neg(\forall x: P(x)) \equiv \exists x: \neg P(x)

  • ¬(∃x:P(x))≡∀x:¬P(x)\neg(\exists x: P(x)) \equiv \forall x: \neg P(x)

Übungen

Aufgabe 1Freitext

Negiere die Aussage: "Alle natürlichen Zahlen sind positiv."