Mathe für Nicht-Freaks: Logik: Quantor

Was sind Quantoren?

Neben den Junktoren gibt es noch eine zweite wichtige Gruppe von Symbolen, die Quantoren, mit denen sich die Aussagenlogik zur sogenannten Prädikatenlogik erweitern lässt. Während Junktoren Aussagen miteinander verknüpfen, legen Quantoren fest, für welche Objekte $x$ einer Grundmenge eine Aussageform $A(x)$ gilt. Eine Aussageform (auch Prädikat genannt) $A(x)$ ist dabei ein sprachlich sinnvoller Ausdruck, in der die Variable $x$ vorkommt und die durch Belegung dieser Variablen mit einem konkreten Wert in eine Aussage übergeht. So sind die Ausdrücke „$x$ ist eine gerade Zahl“ und „$x$ ist ein Mensch“ Beispiele für solche Aussageformen $A(x)$, die von der Variablen $x$ abhängen.

Ich möchte dir den Begriff der Quantoren an einem Beispiel erklären. Stell dir dazu vor, wir untersuchen gerade reelle Zahlen. Dies bedeutet, dass alle Variablen, die wir benutzen, nur mit reellen Zahlen belegt werden sollen. Betrachte nun folgende Aussage:

Für alle $x$ gilt, dass $x^2\le 0$ ist.

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$ gültig sein soll. Wir können also folgende Struktur der obigen Aussage erkennen:

$\underbrace{\text{F} \ddot\mathrm{u} \text{r alle}}_{\text{Allquantor}} \ \underbrace{x}_\text{gebundene Variable} \text{ gilt, dass } \underbrace{x^2 \le 0}_{\text{Aussageform }A(x)\text{, in Abh} \ddot\mathrm{a} \text{ngigkeit von }x} \text{ ist.}$

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

$\forall x : x^2 \le 0$

Wir können aber auch andere Quantoren zur Bindung der Variablen $x$ in der Aussageform „$x^2 < 0$“ verwenden. Anstatt auszudrücken, dass die Aussageform „$x^2 < 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 $\exists$. So besitzt die Aussage „Es gibt mindestens ein $x$ mit $x^2 < 0$“ folgende Struktur:

$\underbrace{\text{Es gibt mindestens ein}}_\text{Existenzquantor} \ \underbrace{x}_{\text{gebundene Variable}} \text{ mit } \underbrace{x^2 < 0}_{\text{Aussageform }A(x)\text{, in Abh} \ddot\mathrm{a} \text{ngigkeit von }x}$

In der formellen Schreibweise, die du später kennen lernen wirst, wird daraus:

$\exists x: x^2 < 0$

Quantoren

Allquantor $\forall$

Allquantor
Symbol:	$\forall$
Bedeutung:	für alle
Schreibweise:	$\forall x: A(x)$

Im vorherigen Abschnitt hast du den Allquantor bereits kennen gelernt. Sein Symbol ist $\forall$ (ein umgedrehtes A – „für Alle“). Die Schreibweise des Allquantors ist $\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 $\bigwedge_{x} A(x)$ zu finden, die wir aber in diesem Buch 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 gerade natürliche Zahlen behandelst, so behauptet eine Aussage „$\forall x:\, A(x)$“ , dass die Aussageform $A(x)$ für alle Belegungen von $x$ aus den natürlichen Zahlen wahr ist. Untersuchst du reelle Zahlen, so behauptet „$\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 $\forall x \in M:\ A(x)$ verwenden. Diese bedeutet: „Für alle $x$ aus der Menge $M$ gilt die Aussage $A(x)$.“

Aufgabe: Überlege dir einige (mathematische) Aussagen, in denen du den Allquantor verwenden kannst und schreib diese auf.

Folgende Beispiele können mit dem Allquantor aufgeschrieben werden:

1. Für jedes Auto gilt: Es fährt oder es steht.
2. Für alle reellen Zahlen $x$ und alle natürlichen Zahlen $y$ ist $x+y=x\cdot y$.
3. Alle Schwäne sind weiß.

Frage: Wie lauten die obigen Aussagen in Quantorenschreibweise?

1. $\forall x:\ x\text{ ist ein Auto} \Rightarrow (x \mathrm{\ f\ddot ahrt} \or x \mathrm{\ steht})$
2. $\forall x\in\R \forall y\in\N: x+y=y\cdot x$
3. $\forall x:\ x\text{ ist ein Schwan} \Rightarrow x \mathrm{\ ist\ wei\beta}$

Existenzquantor $\exists$

Existenzquantor
Symbol:	$\exists$
Bedeutung:	es existiert mindestens ein
Schreibweise:	$\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 umgedrehtes E, welches für „es Existiert mindestens ein“ steht. Analog zum Allquantor haben Existenzaussagen die Form $\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 $\bigvee_{x} 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 $\exists x \in M:\, A(x)$ verwenden. Sie bedeutet: „Es gibt mindestens ein $x$ aus der Menge $M$, für welches die Aussage $A(x)$ wahr ist“.

Hinweis: In der Mathematik gibt es folgende Konvention: Eine Aussage der Form „Es gibt ein ...“ ist immer als Aussage der Form „Es gibt mindestens ein...“ zu verstehen.

Beispiele/Übungsaufgabe: Übersetze folgende Aussagen in die formelle Schreibweise mit dem Existenzquantor:

1. Es gibt eine Zahl $x$, so dass $x\cdot0=5$ ist.
2. Es gibt schöne Männer.
3. Jeder Mensch besitzt einen Seelenverwandten.

1. $\exists x: x\cdot0 =5$
2. $\exists x:\,x\text{ ist ein Mann } \and\ x\text{ ist sch}\ddot\mathrm o\text{n}$
3. $\forall x:\,\left(x\text{ ist ein Mensch} \Rightarrow \exists y:\, y\text{ ist ein Seelenverwandter von }x\right)$

Eindeutiger Existenzquantor $\exists!$

Eindeutiger Existenzquantor
Symbol:	$\exists!$
Bedeutung:	es existiert genau ein
Schreibweise:	$\exists! x: A(x)$

Den letzten Quantor, den ich dir vorstellen möchte, ist der eindeutige Existenzquantor $\exists!$. Die Schreibweise zu diesem Quantor (der auch Eindeutigkeitsquantor genannt wird) ist $\exists! x:\,A(x)$. Dies bedeutet soviel wie „Es gibt genau ein $x$, so dass die Aussageform $A(x)$ für dieses $x$ zu einer wahren Aussage ist.“. 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 $\exists! x\in M:\,A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\exists! x: x\in M \and A(x)$.

Freie, gebundene Variablen und Aussageformen

Du hast dich vielleicht schon darüber gewundert, dass ich manchmal den Begriff „Aussage“ und den Begriff „Aussageform“ benutze, die du streng auseinanderhalten solltest. Der Unterschied liegt darin, dass Aussageformen (auch Prädikate genannt) freie Variablen besitzen, während in Aussagen keine freien Variablen vorkommen. Doch was sind freie Variablen?

Freie und gebundene Variablen

Freie Variablen sind Leerstellen/ Platzhalter in einem sprachlichen Ausdruck, die durch Elemente der Grundmenge ersetzt werden können. Im Gegensatz dazu können gebundene Variablen nicht durch Elemente der Grundmenge ersetzt werden. Dies liegt daran, dass sie schon durch Quantoren gebunden sind. So ist die Variable $x$ im Ausdruck „$x\ge23$“ frei und im Ausdruck „$\forall x: x\ge23$“ durch den Allquantor $\forall$ gebunden. Hier noch einige Beispiele:

Beispiel (freie und gebundene Variablen): $\forall x: \underbrace{x}_\text{gebunden}+\underbrace{y}_\text{frei}=42$ $\underbrace{x}_\text{frei}=4 \Rightarrow \exists x: \underbrace{x}_\text{gebunden}+4=8$ $\exists x\,(\underbrace{y}_\text{frei} + \underbrace{x}_\text{gebunden} = 5 \and \forall y: \underbrace{x}_\text{gebunden} \cdot \underbrace{y}_\text{gebunden} = 8)$

Verständnisfrage: Welche der Variablen in den folgenden Ausdrücken sind frei und welche sind gebunden?

1. $a+b+c=5$
2. $a=b \or \exists b: a=b$
3. $\forall a, b: t = a + b$
4. $\forall x: a = 9$

Antwort:

• $\underbrace{a}_\text{frei}+\underbrace{b}_\text{frei}+\underbrace{c}_\text{frei}=5$
• $\underbrace{a}_\text{frei}=\underbrace{b}_\text{frei} \,\or\, \exists b: \underbrace{a}_\text{frei}=\underbrace{b}_\text{gebunden}$
• $\forall a, b: \underbrace{t}_\text{frei} = \underbrace{a}_\text{gebunden} + \underbrace{b}_\text{gebunden}$
• $\forall x: \underbrace{a}_\text{frei} = 9$

Aussageformen (Prädikate)

Nachdem du gelernt hast, was freie und gebundene Aussagen sind, kann ich dir nun erklären, was Aussageformen sind. Aussageformen sind sprachliche Ausdrücke mit freien Variablen, die durch Belegung dieser Variablen mit konkreten Werten aus einer Grundmenge jeweils in eine Aussage übergehen. Vereinfacht könnte man sagen: „Aussageformen sind Ausdrücke mit freien Variablen.“

Verständnisfrage: Welche der folgenden formalen Ausdrücke sind Aussagen und welche sind Aussageformen?

1. $x+y=y+x$
2. $\forall x: x+y=y+x$
3. $\forall x \forall y: x+y=y+x$
4. $x>0 \Rightarrow \exists x: x^2 = 4$
5. $\forall x: \left( x < 4 \and \exists y: x+y=23 \right)$

Antwort:

1. Aussageform ($x$ und $y$ kommen frei im Ausdruck vor)
2. Aussageform ($y$ kommt frei im Ausdruck vor)
3. Aussage (keine freien Variablen)
4. Aussageform ($x$ kommt frei im Ausdruck vor)
5. Aussage (keine freien Variablen)

Hinweis: Der Wahrheitsgehalt der Aussagen hängt jeweils von der gewählten oder vorgegebenen Grundmenge ab.