1.3 Quantoren
Aussagefunktionen
Offene Ausdrücke wie „\(x\) ist gerade“ werden präzise, sobald ihr Definitionsbereich und die Rolle der Variablen festgelegt sind.
Definition 1.5 (Aussagefunktion). Sei \(X\) eine Menge. Ein Ausdruck \(a(x)\), der für jedes \(x\in X\) eine Aussage liefert, heißt Aussagefunktion oder Prädikat auf \(X\).
Beispielsweise wird aus
\[a(x):\Leftrightarrow \text{„$x$ ist eine Primzahl“}\]
für \(X=\mathbb N\) durch Einsetzen eine Aussage: \(a(5)\) ist wahr, \(a(10)\) ist falsch.
Der Definitionsbereich gehört wesentlich zum Prädikat. Für \(p(x):\Leftrightarrow x^2=2\) hat die Existenzaussage „Es gibt ein \(x\) mit \(p(x)\)“ über \(\mathbb Q\) einen anderen Wahrheitswert als über \(\mathbb R\).
Quantoren
Mit Quantoren können wir aus einer Aussagefunktion wieder eine Aussage machen und dabei ausdrücken, für wie viele Elemente sie gelten soll.
Definition 1.6 (Quantoren). Für eine Aussagefunktion \(a(x)\) verwenden wir:
| Schreibweise | Bedeutung |
|---|---|
| \(\forall x\in X:\;a(x)\) | Für alle \(x\) aus \(X\) gilt \(a(x)\). |
| \(\exists x\in X:\;a(x)\) | Es gibt mindestens ein \(x\) aus \(X\) mit \(a(x)\). |
| \(\exists!x\in X:\;a(x)\) | Es gibt genau ein \(x\) aus \(X\) mit \(a(x)\). |
| \(\nexists x\in X:\;a(x)\) | Es gibt kein \(x\) aus \(X\) mit \(a(x)\). |
Ist der Grundbereich aus dem Zusammenhang eindeutig, kann „\(\in X\)“ weggelassen werden. So bedeutet etwa \(\forall\varepsilon>0:\;a(\varepsilon)\): Für jede positive reelle Zahl \(\varepsilon\) gilt \(a(\varepsilon)\).
Quantoren negieren
Der folgende Satz übersetzt die Negation quantifizierter Aussagen in eine Form, die sich unmittelbar lesen und prüfen lässt.
Satz 1.5 (Negation von Quantoren). Beim Negieren werden All- und Existenzquantor vertauscht und das Prädikat negiert:
\[ \begin{aligned} \overline{\bigl(\forall x\in X:\;a(x)\bigr)} &\Leftrightarrow \exists x\in X:\;\overline{a(x)},\\[0.5em] \overline{\bigl(\exists x\in X:\;a(x)\bigr)} &\Leftrightarrow \forall x\in X:\;\overline{a(x)}. \end{aligned} \tag{1.2}\]
Gleichung 1.2 macht sichtbar: Ein Gegenbeispiel widerlegt eine Allaussage, während eine negierte Existenzaussage eine Allaussage erzeugt.
Die erste Regel sagt: Um „Alle Elemente besitzen die Eigenschaft“ zu widerlegen, genügt ein Gegenbeispiel. Die zweite Regel sagt: „Es gibt kein Element mit der Eigenschaft“ bedeutet, dass jedes Element die Eigenschaft nicht besitzt.
Das nächste Beispiel führt diese sprachliche Regel an einer einfachen Existenzaussage aus.
Beispiel: Negation einer Existenzaussage
Aufgabenstellung. Negieren Sie die Aussage
\[\exists x\in\mathbb N:\;x^2=40\]
ohne die Formulierung „Es gilt nicht, dass …“.
Mehrstellige Prädikate
Ein Prädikat kann mehrere Variablen besitzen. Auf der Menge \(M\) aller Personen auf einem Campus sei
\[k(x,y):\Leftrightarrow\text{„Person $x$ kennt Person $y$“}.\]
Dabei muss \(k(x,y)\) nicht dasselbe bedeuten wie \(k(y,x)\).
Quantorenreihenfolge
Vergleichen Sie
\[ f:\Leftrightarrow\forall y\in M\;\exists x\in M:\;k(x,y) \]
und
\[ g:\Leftrightarrow\exists x\in M\;\forall y\in M:\;k(x,y). \]
Abbildung 1.1 zeigt den Unterschied: Jede Person kann einen eingehenden Pfeil besitzen, ohne dass ein einzelner Knoten Pfeile zu allen Personen besitzt. Bei verschiedenen Quantoren darf ihre Reihenfolge deshalb nicht vertauscht werden.
Freie und gebundene Variablen
In \(\exists y:\;a(x,y,z)\) ist \(y\) durch den Quantor gebunden; \(x\) und \(z\) sind frei. Der Ausdruck ist daher noch keine Aussage, sondern eine zweistellige Aussagefunktion in \(x\) und \(z\). Erst wenn auch diese Variablen eingesetzt oder quantifiziert werden, entsteht eine Aussage.
Das folgende Beispiel hilft dabei, gebundene und freie Variablen in einer Formel zuverlässig auseinanderzuhalten.
Beispiel: gebundene und freie Variablen
\[ \forall x\in\mathbb R:\;x+y>z. \]
Aufgabenstellung. Bestimmen Sie die gebundenen und freien Variablen. Wie ändert sich die Antwort, wenn zusätzlich ein Existenzquantor für \(y\) ergänzt wird?
Zusammenfassung
- Eine Aussagefunktion wird erst durch Einsetzen oder Quantifizieren ihrer freien Variablen zu einer Aussage; ihr Definitionsbereich ist wesentlich.
- \(\forall\) bezeichnet eine Aussage über alle Elemente, \(\exists\) die Existenz mindestens eines passenden Elements.
- Beim Negieren werden All- und Existenzquantor vertauscht und das Prädikat negiert.
- Bei mehrstelligen Aussagefunktionen beeinflusst die Reihenfolge unterschiedlicher Quantoren im Allgemeinen die Bedeutung.
- Gebundene Variablen stehen im Wirkungsbereich eines Quantors; freie Variablen bleiben Argumente der Aussagefunktion.