2. Quantoren
Zur Formulierung mathematischer Aussagen werden neben den Junktoren häufig Quantoren der Form „für alle“ und „es gibt ein“ verwendet. Einige Beispiele sind:
Es gibt ein x mit f (x) = 0. (f besitzt eine Nullstelle)
Für alle n gibt es ein p ≥ n, sodass p und p + 2 prim sind. (Existenz unendlich vieler Primzahlzwillinge)
Es gibt ein e mit x ∘ e = e ∘ x = x. (Existenz eines neutralen Elements)
Für alle x gibt es ein y mit x ∘ y = y ∘ x = e. (Existenz inverser Elemente)
Wie für die Junktoren können wir eine Tabelle angeben:
Zeichen | Bedeutung | Name |
∀ | für alle … | Allquantor |
∃ | es gibt (mindestens) ein … | Existenzquantor |
Die drei wichtigsten Quantorenregeln sind:
¬ ∀x A(x) | ↔ | ∃x ¬ A(x) |
¬ ∃x A(x) | ↔ | ∀x ¬ A(x) |
∃x ∀y A(x, y) | → | ∀y ∃x A(x, y) |
Beispiele
(1) | Sei A(x) = „Der Zwerg x hat rote Haare.“ Dann bedeuten ¬ ∀x A(x): „Nicht jeder Zwerg hat rote Haare.“ ∃x ¬ A(x): „Es gibt einen Zwerg, der keine roten Haare hat.“ Diese Aussagen sind äquivalent. |
(2) | Sei A(x, y) = „Der Lehrer x unterrichtet das Fach y.“ Dann bedeuten: ∃x ∀y A(x, y): „Es gibt einen Lehrer, der jedes Fach unterrichtet.“ ∀y ∃x A(x, y): „Jedes Fach wird von mindestens einem Lehrer unterrichtet.“ Die erste Aussage ist für viele Schulen falsch, die zweite für die meisten Schulen richtig. |