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:

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

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

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

\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."
$\forall x: \exists y: \text{Mutter}(y, x)$
(Zu jedem Menschen $x$ existiert ein Mensch $y$ , der Mutter von $x$ ist.)

Beispiel 2: "Es gibt eine Frau, die Mutter aller Menschen ist."
$\exists y: \forall x: \text{Mutter}(y, x)$
(Es existiert ein Mensch $y$ , 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:

$\neg(\forall x: P(x)) \equiv \exists x: \neg 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..."

\neg \forall \equiv \exists \neg \quad \text{und} \quad \neg \exists \equiv \forall \neg

Beispiel

Negationen bilden

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

Negation: "Nicht alle Schwäne sind weiß."
$\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."
$\exists x \in \mathbb{R}: x^2 < 0$

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

Zusammenfassung

Die Reihenfolge der Quantoren ist wichtig!
$\neg(\forall x: P(x)) \equiv \exists x: \neg 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."

Quantoren verstehen

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:

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

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

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

\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."
$\forall x: \exists y: \text{Mutter}(y, x)$
(Zu jedem Menschen $x$ existiert ein Mensch $y$ , der Mutter von $x$ ist.)

Beispiel 2: "Es gibt eine Frau, die Mutter aller Menschen ist."
$\exists y: \forall x: \text{Mutter}(y, x)$
(Es existiert ein Mensch $y$ , 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:

$\neg(\forall x: P(x)) \equiv \exists x: \neg 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..."

\neg \forall \equiv \exists \neg \quad \text{und} \quad \neg \exists \equiv \forall \neg

Beispiel

Negationen bilden

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

Negation: "Nicht alle Schwäne sind weiß."
$\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."
$\exists x \in \mathbb{R}: x^2 < 0$

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

Zusammenfassung

Die Reihenfolge der Quantoren ist wichtig!
$\neg(\forall x: P(x)) \equiv \exists x: \neg P(x)$
$\neg(\exists x: P(x)) \equiv \forall x: \neg P(x)$

—