02 Aussageformen und Quantoren

2. Aussageformen und Quantoren

Voraussetzung: 01 Aussagenlogik (Aussagen, Verknüpfungen, Äquivalenz)

2.1 Aussageform

Definition: Aussageform

Eine Aussageform über den Universen $U_1,\dots ,U_n$ ist ein Satz mit Variablen $x_1,\dots ,x_n$, der bei Einsetzung jedes $x_j$ durch ein Objekt aus $U_j$ zu einer Aussage wird.

Der Unterschied zur Aussage: Eine Aussageform hat selbst noch keinen Wahrheitswert — erst nach Einsetzen konkreter Werte für die Variablen entsteht eine Aussage.

Beispiele:

• ”$x$ ist Primzahl” ist eine Aussageform in der Variable $x$ über dem Universum der positiven ganzen Zahlen.
• "$x<y$" ist eine Aussageform mit den Variablen $x,y$ über den Universen $\mathbb{R},\mathbb{R}$.
  • Setzt man für $x$ einen konkreten Wert ein, z.B. 17, entsteht eine neue Aussageform in der verbleibenden Variable $y$, nämlich "$17<y$".

Definition: Prädikat

Eine Aussageform in genau einer Variable $x$ über einem Universum $U$ heißt Prädikat von $U$.

---

2.2 Quantoren

Sei $p(x)$ ein Prädikat über dem Universum $U$.

Allquantor

$\underset{\text{Allquantor}}{\underbrace{\forall }}x:p(x)$

bedeutet: “Für alle $x$ aus $U$ ist $p(x)$ wahr.”

Wahrheitswert: $\forall x:p(x)=\{\begin{array}{ll}w& \text{falls }p(x)\text{ fu¨r jedes }x\text{ aus }U\text{ den Wert }w\text{ hat}\\ f& \text{falls }p(x)\text{ fu¨r wenigstens ein }x\text{ aus }U\text{ den Wert }f\text{ hat}\end{array}$

Existenzquantor

$\exists x:p(x)$

bedeutet: “Es gibt wenigstens ein $x$ aus $U$, für das $p(x)$ wahr ist.”

Wahrheitswert: $\exists x:p(x)=\{\begin{array}{ll}w& \text{falls }p(x)\text{ fu¨r wenigstens ein }x\text{ aus }U\text{ den Wert }w\text{ hat}\\ f& \text{falls }p(x)\text{ fu¨r jedes }x\text{ aus }U\text{ den Wert }f\text{ hat}\end{array}$

Sonderfall: leeres Universum

Hat $U$ keine Objekte, gilt immer:

• $\forall x:p(x)$ ist wahr (es gibt kein Gegenbeispiel — “leer erfüllt”)
• $\exists x:p(x)$ ist falsch (es gibt kein Objekt, das $p(x)$ erfüllen könnte)

Merkhilfe

Der Allquantor ist “optimistisch, solange niemand widerspricht” — ohne Elemente kann niemand widersprechen, also wahr. Der Existenzquantor braucht einen konkreten Zeugen — ohne Elemente gibt es keinen, also falsch.

Schreibweisen

Falls $U$ eine Menge ist, schreibt man auch: $\forall x\in U:p(x),\exists x\in U:p(x),\underset{x\in U}{\underbrace{\forall }}p(x),\underset{x\in U}{\underbrace{\exists }}p(x)$

Quantoren bei endlichem Universum

Ist $U$ endlich mit den Objekten $x_1,\dots ,x_n$ (und keinen weiteren), dann gilt:

$\forall x:p(x)\text{a¨quivalent zu}p(x_1)\wedge \cdots \wedge p(x_n)$ $\exists x:p(x)\text{a¨quivalent zu}p(x_1)\vee \cdots \vee p(x_n)$

Der Allquantor ist also eine “große Konjunktion”, der Existenzquantor eine “große Disjunktion”. Daher gibt es folgende Alternativschreibweisen:

$\bigwedge x:p(x),\bigvee x:p(x),{\bigwedge }_{x\in U}p(x),{\bigvee }_{x\in U}p(x)$

---

2.3 Schachtelung von Quantoren

Sei $p(x,y)$ eine Aussageform mit zwei Variablen $x,y$ über den Universen $U,V$.

$\underset{\text{Aussage}}{\underbrace{\forall x:\underset{\text{Aussageform in der Variable }x}{\underbrace{\exists \underset{\begin{array}{c}\text{fu¨r jede Ersetzung von }x\text{ durch ein}\\ \text{Objekt aus }U\text{ entsteht eine Aussageform in }y\end{array}}{\underbrace{y:p(x,y)}}}}}}$

Man “baut” die Aussage von innen nach außen: Zuerst wird $y$ gebunden (bei festem $x$), das Ergebnis ist eine Aussageform in $x$; anschließend wird auch $x$ gebunden, und man erhält eine vollständige Aussage.

WICHTIG: Reihenfolge verschiedener Quantoren

Verschiedene Quantoren ($\forall ,\exists$) dürfen nicht vertauscht werden! $\forall x\exists y$ und $\exists x\forall y$ bedeuten im Allgemeinen etwas völlig anderes.

Beispiel: Reihenfolge macht den Unterschied

Betrachte "$x<y$" als Aussageform über $\mathbb{R},\mathbb{R}$.

$\forall x:\exists y:x<y$ ist wahr:

Beweis: Sei $x\in \mathbb{R}$ beliebig. Setze $y:=x+1$. Dann ist $y\in \mathbb{R}$ und $x<y$. q.e.d.

Aussage: “Zu jeder Zahl gibt es eine größere Zahl.” — offensichtlich wahr.

$\exists x:\forall y:x<y$ ist falsch:

Beweis (Widerspruch): Annahme: Es gibt ein $x\in \mathbb{R}$ mit $\forall y:x<y$. Dann gilt dies insbesondere für den Fall $y=x$: $x<x$. Das ist ein Widerspruch. Also muss die Annahme verworfen werden. q.e.d.

Aussage: “Es gibt eine Zahl, die kleiner ist als jede Zahl (auch kleiner als sich selbst).” — offensichtlich falsch.

Lerneffekt

Dieses Beispiel ist der Klassiker, um den Unterschied zwischen $\forall \exists$ und $\exists \forall$ zu verinnerlichen. Immer first prüfen: Wird die “Zeugen-Wahl” ($\exists$) vor oder nach der Festlegung der anderen Variable getroffen?

---

2.4 Regeln für Quantoren

Vertauschen gleichartiger Quantoren

Quantoren gleicher Art dürfen beliebig vertauscht werden:

$\forall x\forall y:p(x,y)\equiv \forall y\forall x:p(x,y)$ $\exists x\exists y:p(x,y)\equiv \exists y\exists x:p(x,y)$

Großes Assoziativgesetz

Sind $p,q$ Prädikate über $U$, so gilt:

$\forall x:p(x)\wedge q(x)\equiv \left(\forall x:p(x)\right)\wedge \left(\forall x:q(x)\right)$ $\exists x:p(x)\vee q(x)\equiv \left(\exists x:p(x)\right)\vee \left(\exists x:q(x)\right)$

Achtung

Das funktioniert nur in dieser Kombination ($\forall$ mit $\wedge$, $\exists$ mit $\vee$)! $\forall x:p(x)\vee q(x)$ ist nicht äquivalent zu $(\forall x:p(x))\vee (\forall x:q(x))$ — Gegenbeispiel: $p(x)$ = “x ist gerade”, $q(x)$ = “x ist ungerade” über den ganzen Zahlen. Links wahr, rechts falsch.

Großer Satz von De Morgan (für Quantoren)

Analog zu De Morgan in der Aussagenlogik (siehe 01 Aussagenlogik):

$\neg (\forall x:p(x))\equiv \exists x:\neg p(x)$ $\neg (\exists x:p(x))\equiv \forall x:\neg p(x)$

Merksatz: Negation vertauscht die Quantoren und wandert “nach innen” zum Prädikat.

Ausführliches Beispiel: Negation einer stark geschachtelten Aussage

Negiere: $\neg \left(\forall x\exists y\forall z\forall v\exists w:p(x,y,z)⟹q(v,w)\right)$

Schrittweise, immer eine Quantorenebene nach der anderen nach innen schieben (jeweils De Morgan für Quantoren anwenden, Quantorart kippt dabei um):

$\equiv \exists x:\neg \left(\exists y\forall z\forall v\exists w:p(x,y,z)⟹q(v,w)\right)$ $\equiv \exists x\forall y:\neg \left(\forall z\forall v\exists w:p(x,y,z)⟹q(v,w)\right)$ $\equiv \dots$ $\equiv \exists x\forall y\exists z\exists v\forall w:\neg \left(p(x,y,z)⟹q(v,w)\right)$

Im letzten Schritt wird noch die Negation der Implikation aufgelöst (siehe 01 Aussagenlogik, Abschnitt 1.4: $\neg (p⟹q)\equiv p\wedge \neg q$):

$\equiv \exists x\forall y\exists z\exists v\forall w:\left(p(x,y,z)\wedge \neg q(v,w)\right)$

Vorgehen bei solchen Aufgaben

1. Jeden Quantor beim “Durchschieben” der Negation kippen ($\forall \leftrightarrow \exists$).
2. Erst wenn alle Quantoren durchgeschoben sind, die innerste aussagenlogische Verknüpfung (hier die Implikation) mit den gewöhnlichen Regeln aus 01 Aussagenlogik negieren.