Mathe für Nicht-Freaks: Quantor

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

Was sind Quantoren?

Neben den Junktoren gibt es noch eine zweite wichtige Gruppe von logischen Symbolen, die Quantoren. Während Junktoren Aussagen miteinander verknüpfen, legen Quantoren fest, für welche Objekte $x$ einer Grundmenge eine Aussageform $A(x)$ gilt. Eine Aussageform $A(x)$ ist dabei ein sprachlich sinnvoller Ausdruck, in dem die Variable $x$ vorkommt und der durch Belegung dieser Variablen mit einem konkreten Wert in eine Aussage übergeht. So sind die Ausdrücke

und

Beispiele für solche Aussageformen $A(x)$, die von der Variablen $x$ abhängen.

Wir möchten den Begriff „Quantor“ an einem Beispiel erklären. Stelle dir dazu vor, wir verwenden gerade die Menge der reellen Zahlen. Dies bedeutet, dass alle Variablen, die wir benutzen, nur mit reellen Zahlen belegt werden sollen. Betrachte nun folgende Aussage:

In diesem Beispiel ist „für alle“ ein Quantor, der Allquantor. Er behauptet, dass die Aussageform $x^2\le 0$ für alle Belegungen der Variablen $x$ wie zum Beispiel $x=-\frac{1}{2}$, $x=42$ oder $x=0$ gültig sein soll. Wir können also folgende Struktur der obigen Aussage erkennen:

Wie auch bei Junktoren werden für Quantoren bestimmte Symbole verwendet. Für den Allquantor ist das Symbol $\mathrm{\forall }$ am geläufigsten. So kann die obige Aussage „Für alle $x$ gilt, dass $x^2\le 0$ ist“ auch so geschrieben werden:

Wir können aber auch andere Quantoren zur Bindung der Variablen $x$ in der Aussageform $x^2\le 0$ verwenden. Anstatt auszudrücken, dass die Aussageform $x^2\le 0$ für alle Belegungen von $x$ gültig ist, können wir auch sagen, dass diese Aussageform für mindestens eine reelle Zahl $x$ wahr ist. Dieser Quantor „es gibt mindestens ein“ wird Existenzquantor genannt und hat das Symbol $\mathrm{\exists }$. So besitzt die Aussage „Es gibt mindestens ein $x$ mit $x^2\le 0$“ folgende Struktur:

Formal aufgeschrieben wird daraus:

Arten von Quantoren

Allquantor Vorlage:Anker

Allquantor

Symbol:	$\mathrm{\forall }$
Bedeutung:	„für alle“ oder „für jede(s)“
Schreibweise:	$\mathrm{\forall }x:A(x)$

Im vorherigen Abschnitt hast du den Allquantor bereits kennen gelernt. Sein Symbol ist $\mathrm{\forall }$ (ein umgedrehtes A – „für Alle“). Die Schreibweise des Allquantors ist $\mathrm{\forall }x:A(x)$. Dies bedeutet „Für alle $x$ gilt $A(x)$“ oder „Für jedes $x$ gilt $A(x)$“. Dabei ist $A(x)$ eine beliebige Aussageform, in der die Variable $x$ vorkommt. In der Literatur ist auch die Schreibweise $\underset{x}{\bigwedge }A(x)$ zu finden, die wir aber in diesem Projekt nicht verwenden werden.

Die Menge der Objekte, auf die sich der Quantor bezieht, muss eindeutig bestimmt sein (und kann sich zum Beispiel aus dem Kontext ergeben). Wenn du eben natürliche Zahlen behandelst, so behauptet eine Aussage $\mathrm{\forall }x:A(x)$, dass die Aussageform $A(x)$ für alle Belegungen von $x$ aus den natürlichen Zahlen zu einer wahren Aussage wird. Untersuchst du reelle Zahlen, so behauptet $\mathrm{\forall }x:A(x)$, dass die Aussageform $A(x)$ für alle reellen Zahlen $x$ zu einer wahren Aussage wird.

Wenn du die Bezugsmenge des Allquantors explizit angeben möchtest oder musst, kannst du die deutlichere Schreibweise $\mathrm{\forall }x\in M:A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\mathrm{\forall }x:x\in M\Rightarrow A(x)$ und bedeutet: „Für alle $x$ aus der Menge $M$ gilt die Aussage $A(x)$.“

Existenzquantor Vorlage:Anker

Existenzquantor

Symbol:	$\mathrm{\exists }$
Bedeutung:	es existiert mindestens ein
Schreibweise:	$\mathrm{\exists }x:A(x)$

Dieser Quantor wird für Aussagen folgender Form verwendet: „Es gibt mindestens ein $x$, so dass $A(x)$ gilt“. Dieser Quantor heißt Existenzquantor. Sein Symbol ist ein horizontal gespiegeltes E, welches für „es Existiert mindestens ein“ steht. Analog zum Allquantor haben Existenzaussagen die Form $\mathrm{\exists }x:A(x)$. Diese Schreibweise steht für „Es gibt mindestens ein $x$, so dass $A(x)$ gilt“ oder „Es existiert mindestens ein $x$, für welches $A(x)$ gilt“. Auch hier ist $x$ eine Variable und $A(x)$ eine Aussageform, die von $x$ abhängt. In der Literatur kannst du auch die Schreibweise $\underset{x}{\bigvee }A(x)$ finden.

Wie auch beim Allquantor muss die Bezugsmenge $M$ des Quantors klar sein (z. B. aus dem Kontext). Muss die Bezugsmenge explizit angegeben werden, so kannst du die Schreibweise $\mathrm{\exists }x\in M:A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\mathrm{\exists }x:x\in M\wedge A(x)$ und bedeutet: „Es gibt mindestens ein $x$ aus der Menge $M$, für welches die Aussage $A(x)$ wahr ist“.

Eindeutiger Existenzquantor Vorlage:Anker

Eindeutiger Existenzquantor

Symbol:	$\mathrm{\exists }!$
Bedeutung:	es existiert genau ein
Schreibweise:	$\mathrm{\exists }!x:A(x)$

Der letzte Quantor, den wir dir vorstellen möchten, ist der eindeutige Existenzquantor $\mathrm{\exists }!$. Die Schreibweise zu diesem Quantor (der auch Eindeutigkeitsquantor genannt wird) ist $\mathrm{\exists }!x:A(x)$. Dies bedeutet so viel wie Vorlage:- Beachte den Unterschied zwischen dem Existenzquantor und dem eindeutigen Existenzquantor: Während beim Existenzquantor die Aussageform $A(x)$ für mindestens eine Belegung von $x$ gilt, gilt beim eindeutigen Existenzquantor die Aussageform $A(x)$ für genau eine Belegung von $x$ aus der Grundmenge.

Auch bei diesem Quantor muss sich die Bezugsmenge durch den Kontext ergeben. Wenn du sie explizit angeben möchtest, kannst du die Schreibweise $\mathrm{\exists }!x\in M:A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\mathrm{\exists }!x:x\in M\wedge A(x)$ und bedeutet: „Es gibt genau ein $x$ aus der Menge $M$, für welches die Aussage $A(x)$ wahr ist.“ Alternative und in der Literatur auch verbreitete Schreibweisen für den eindeutigen Existenzquantor sind ${\mathrm{\exists }}_1$ und $\stackrel{1}{\mathrm{\exists }}$.

Der eindeutige Existenzquantor $\mathrm{\exists }!$ lässt sich mit Hilfe des Existenzquantors $\mathrm{\exists }$ und des Allquantors $\mathrm{\forall }$ beschreiben, nämlich so:

Die Formulierungen (*) und (**) beschreiben genau denselben Sachverhalt! Das ist der Grund dafür, dass der Quantor $\mathrm{\exists }!$ üblicherweise wie folgt definiert wird:

Damit ist auch klar, wie Aussagen mit $\mathrm{\exists }!$ zu beweisen sind:

• Zunächst wird $\mathrm{\exists }x:A(x)$ bewiesen,
• anschließend wird gezeigt, dass aus $A(x)$ und $A(y)$ für beliebige $x$ und $y$ die Gleichheit $x=y$ folgt.

Notation

Für Ausdrücke mit Quantoren werden in der Literatur verschiedene Schreibweisen verwendet. So findet man anstelle vom Ausdruck $\mathrm{\forall }x:A(x)$ auch die Notationen:

• $\mathrm{\forall }xA(x)$
• $\mathrm{\forall }x.A(x)$
• $\mathrm{\forall }x(A(x))$
• ${\mathrm{\forall }}_{x}A(x)$

Gleiches gilt für den Existenzquantor $\mathrm{\exists }x:A(x)$:

• $\mathrm{\exists }xA(x)$
• $\mathrm{\exists }x.A(x)$
• $\mathrm{\exists }x(A(x))$
• ${\mathrm{\exists }}_{x}A(x)$

Manchmal werden in der Literatur auch Existenzquantoren der Art ${\mathrm{\exists }}_{=n}$ bzw. ${\mathrm{\exists }}_{\le n}$ verwendet. Ihre Bedeutung ist:

• ${\mathrm{\exists }}_{=n}x:A(x)$ bedeutet, es gibt genau $n$ Objekte $x$ mit der Eigenschaft $A(x)$
• ${\mathrm{\exists }}_{\le n}x:A(x)$ bedeutet, es gibt höchstens $n$ Objekte $x$ mit der Eigenschaft $A(x)$
• ${\mathrm{\exists }}_{\ge n}x:A(x)$ bedeutet, es gibt mindestens $n$ Objekte $x$ mit der Eigenschaft $A(x)$

Wir werden in diesem Projekt aber die Schreibweise $\mathrm{\forall }x:A(x)$ und $\mathrm{\exists }x:A(x)$ verwenden. Auch kann man aufeinanderfolgende Quantoren vom selben Typ zusammenfassen, indem man die verschiedenen eingeführten Variablen durch Kommata trennt. So kannst du anstelle von $\mathrm{\forall }x\mathrm{\forall }y:A(x,y)$ auch folgende Schreibweise benutzen: $\mathrm{\forall }x,y:A(x,y)$. Analog kann man anstelle von $\mathrm{\exists }x\mathrm{\exists }y:A(x,y)$ auch kürzer $\mathrm{\exists }x,y:A(x,y)$ schreiben.

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}