Logische Begriffe – Analysis I (Kap. 1-9)

1.3 Logische Begriffe

Die logischen Begriffe und die dazugehörende Theorie der Logik haben sich seit der Antike stark geändert, doch seit der Begriffsschrift von Frege (1848-1925) im Jahre 1879 nicht mehr so stark. Da ein Verständnis dieser logischen Sprache für die Mathematik notwendig ist, wollen wir diese hier besprechen. Für historisch Interessierte verweisen wir auch auf den Podcast der BBC, den man sich anhören kann, wenn man schon zu müde ist, um Übungen zu lösen oder man Probleme hat einzuschlafen.

Mathematische Aussagen sind, wenn ein klar definierter Rahmen gegeben ist und der Wert für etwaige Variablen bekannt ist, entweder wahr oder falsch. Diese strenge Sichtweise ist notwendig, damit wir von Bekanntem ausgehend wahre Aussagen (Lemmata und Propositionen zum Beispiel) folgern können, auf die wiederum Verlass ist (das heisst, ohne dass man Spezialfälle ausschliessen muss). Sie haben vielleicht schon einmal Sudoku gespielt und wissen, wie schwerwiegend ein kleiner Denkfehler werden kann.

1.3.1 Aussagenlogik und die Boolesche Algebra

Da eine mathematische Aussage nur zwei „Werte“ annehmen kann, wahr (w) und falsch (f), können wir gewissermassen „Rechenoperationen“ für solche Aussagen sehr einfach und schnell definieren. Dies wurde erstmals von George Boole im Jahre 1847 formal ausgeführt (siehe [Boo47]) und stellt sowohl für die Grundlagen der Mathematik als auch für die Informatik und Elektrotechnik einen historisch bedeutsamen Schritt dar. Im Folgenden werden mathematische Aussagen mit Grossbuchstaben A, B, …dargestellt.

Die einfachste Operation ist die Negation einer Aussage: Sei A eine Aussage. Die Negation von A ist die Aussage „A gilt nicht“, die wir kurz mit „Nicht A“ bezeichnen und als „ $\neg$ A“ schreiben. Die Aussage „ $\neg$ A“ hat den Wert f, falls A den Wert w hat und den Wert w, falls A den Wert f hat. Wir stellen dies in einer sogenannten Wahrheitstabelle wie folgt dar:

$A$	$\neg A$

$w$	$f$
$f$	$w$

Wir verwenden das Symbol „ $=$ “ für die Gleichheit und können es gebrauchen, um die Aussage „ $x = y$ “ über zwei Objekte $x, y$ zu bilden. Des Weiteren schreiben wir „ $x \neq y$ “ für die Negation „ $\neg (x = y)$ “ der Gleichheit.

Sei nun B eine weitere Aussage. Die Und-Operation angewendet auf A und B ist die Aussage „ sowohl A als auch B gelten“, kurz „A und B“ und symbolisch geschrieben „A $\land$ B“. Die zugehörige Wahrheitstabelle ist

$A$	$B$	$A \land B$

$w$	$w$	$w$
$w$	$f$	$f$
$f$	$w$	$f$
$f$	$f$	$f$

Die Oder-Operation angewendet auf die beiden Aussagen A,B ergibt die Aussage „ A gilt oder B gilt“, kurz „A oder B“ und symbolisch geschrieben „A $\lor$ B“. Die zugehörige Wahrheitstabelle ist:

$A$	$B$	$A \lor B$

$w$	$w$	$w$
$w$	$f$	$w$
$f$	$w$	$w$
$f$	$f$	$f$

Man sollte an dieser Stelle bemerken, dass, wie oben ersichtlich ist, das „logische Oder“ (und daher auch das „mathematische Oder“) das „einschliessende Oder“ ist, welches auch zutrifft, falls beide Aussagen zutreffen. Dies unterscheidet sich teilweise vom umgangssprachlichen Gebrauch des Wortes „ oder“ , das oft auch exklusiv gemeint ist (als „entweder … oder“). Die Aussage „entweder A oder B“ kann über die drei Grundoperationen Negation, Und und Oder definiert werden (siehe Übung 1.4).

Die Algebraisierung der Logik hat den entscheidenden Vorteil, dass wir mittels Klammern klar darstellen können, wie Verknüpfungen von logischen Aussagen zu verstehen sind. In der Umgangssprache gibt es keine Klammern und Aussagen der Form

„Sokrates hat einen Hund und
ein Hund ist das beste Haustier oder
eine Katze ist das beste Haustier.“

sind zweideutig. (Inkludiert Obiges die Behauptung „Sokrates hat einen Hund“ oder kann es auch sein, dass die Aussage „Sokrates hat keinen Hund und eine Katze ist das beste Haustier“ gilt?)

Wir können Verknüpfungen (wenn nötig mit Klammern) verwenden, um neue logische Operationen zu definieren. Beispielsweise ist die logische Implikation „A $\Rightarrow$ B“ als die Aussage „( $\neg$ A) $\lor$ B“ definiert. „ A $\Rightarrow$ B“ wird als „ A impliziert B“ ausgesprochen und auch in diesem Sinne verwendet. Denn falls A wahr ist und „A $\Rightarrow$ B“ wahr ist, dann muss auch B wahr sein. Auffallend sind folgende Eigenheiten:

•

Jegliche Kausalität oder auch der konkrete Zusammenhang zwischen den beiden Aussagen wird ignoriert.

•

Die Implikation ist immer richtig, falls die Annahme A falsch ist. Also ist zum Beispiel die Aussage

\begin{align} „ (0 = 1) \Rightarrow (die Welt ist eckig) “ & (1.3) \end{align}

dadurch wahr.

Die logische Äquivalenz der Aussagen A und B wird als „A $\Leftrightarrow$ B“ geschrieben, als „ A genau dann wenn B“ oder als „A ist äquivalent zu B“ ausgesprochen und durch die Aussage „(A $\Rightarrow$ B) $\land$ (B $\Rightarrow$ A)“ definiert.

Es ist hilfreich, sich die logischen Operationen auch als elektrische Schaltungen vorzustellen (siehe zum Beispiel Sektion 3.1 in [SS12]). Mit dieser Analogie im Hinterkopf sind die Eigenheiten der obigen Diskussion bzgl. Kausalität oder das Beispiel (1.3) leichter verständlich, denn einer Schaltung ist egal, wer (Frau, Mann, Kind, Hund oder Maschine) den Schalter betätigt oder warum (absichtlich oder unabsichtlich) dieser betätigt wurde. Auch unsere Beweise werden manchmal keine echte Kausalität herstellen, sondern nur aufzeigen, dass es keine andere Möglichkeit gibt.

Sei A eine Aussage. Die Aussage „A $\lor$ ( $\neg$ A)“ ist eine sogenannte Tautologie, denn sie trifft unabhängig vom Wahrheitswert von A stets zu. In der Tat, wenn A wahr ist, dann ist „A $\lor$ ( $\neg$ A)“ wahr und wenn A falsch ist, dann ist „ $\neg$ A“ wahr und „A $\lor$ ( $\neg$ A)“ auch wahr.

Übung 1.4.

Seien A,B zwei Aussagen.

(i): Bestimmen Sie die Wahrheitstabellen zu „A $\Rightarrow$ B“ und zu „ A $\Leftrightarrow$ B“.
(ii): Definieren Sie die logische Operation des auschliessenden Oder „A XOR B“ mittels der obigen Operationen. Die Aussage „A XOR B“ soll genau dann zutreffen, wenn A oder B zutrifft, aber nicht beide zutreffen.
(iii): Überprüfen Sie, dass die Aussagen „A $\Leftrightarrow$ ( $\neg$ ( $\neg$ A))“ und „ (A $\land$ B) $\Leftrightarrow$ ( $\neg$ ( $\neg$ A $\lor \neg$ B))“ Tautologien sind.

Wir werden anstelle der Symbole „ $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$ “ meist die Worte „nicht, und, oder, impliziert, ist äquivalent zu“ verwenden, wobei „oder“ immer einschliessend zu verstehen ist. Da wir keine Prioritätsregel (wie die bekannte Punkt- vor Strichrechnung) festgelegt haben, sollten wir stets Klammern verwenden um Zweideutigkeiten zu vermeiden. Eine übliche Prioritätsregel ist „ $\land$ “ vor „ $\lor$ “, womit die Aussage „ $A \land B \lor C$ “ als „ $(A \land B) \lor C$ “ zu verstehen wäre. Nichtsdestotrotz werden wir letztere Schreibweise bevorzugen und nur die Prioritätsregel verwenden, dass die Operation $\neg$ immer Vorrang hat. Also kann zum Beispiel „( $\neg$ A) $\lor$ B“ auch als „ $\neg$ A $\lor$ B“ geschrieben werden.

Seien A, B zwei Aussagen. Eine sehr nützliche Tautologie ist die Aussage

\begin{align} „ (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A) “ & (1.4) \end{align}

Um zu überprüfen, dass es sich bei (1.4) tatsächlich um eine Tautologie handelt, verwenden wir zuerst die Definition der logischen Implikation und sehen, dass die linke Seite „ $\neg$ A $\lor$ B“ ist. Die rechte Seite wiederum ist „ $\neg (\neg$ B) $\lor \neg$ A“, was zu „ B $\lor \neg$ A“ und damit auch zu „ $\neg$ A $\lor$ B“ äquivalent ist.

Die Tautologie (1.4) wird oft in Beweisen verwendet: Angenommen wir wollen zeigen, dass die Aussage A die Aussage B impliziert. Dann ist es manchmal einfacher und wegen (1.4) stets ausreichend zu zeigen, dass falls B nicht zutrifft auch A nicht zutrifft (dies wird Kontraposition genannt, siehe auch Abschnitt 1.8.2).

An dieser Stelle sollte man davor warnen, die Aussagen „A $\Rightarrow$ B“ und „ $\neg$ A $\Rightarrow \neg$ B“ zu verwechseln; sie sind grundverschieden (auch wenn der Unterschied in politischen Diskussionen manchmal gern ignoriert wird). Wir empfehlen Ihnen, Beispiele mathematischer und nicht-mathematischer Art zu finden, die den Unterschied zwischen „A $\Rightarrow$ B“ und „ $\neg$ A $\Rightarrow \neg$ B“ gut belegen.

Übung 1.5 (Ritter und Knappen).

Auf der Insel der Ritter und Knappen ist jeder Einwohner entweder ein Ritter oder ein Knappe (und jeder weiss den Status von allen anderen Einwohnern). Es ist wichtig zu wissen, dass

•

Ritter immer die Wahrheit sagen.

•

Knappen immer lügen.

Sie werden auf Einwohner der Insel treffen und Ihre Aufgabe ist bei jedem zu entscheiden, ob er ein Ritter oder ein Knappe ist.

(i): Sie treffen Johannes und Willhelm auf der Insel. Johannes sagt „Willhelm und ich sind Ritter.“ Willhelm sagt „Das ist eine Lüge, Johannes ist ein Knappe!“ Was sind sie?
(ii): Sie treffen Gildas, Ergard und Telones auf der Insel. Gildas sagt „Seien Sie vorsichtig, wir sind nicht alle drei Ritter.“ Ergard sagt: „Wir sind auch nicht alle drei Knappen.“ Telones sagt „Hören Sie nicht auf sie, ich bin der einzige Ritter.“ Was sind sie?
(iii): Sie treffen Heinrich und Arthur auf der Insel. Heinrich murmelt irgend etwas Unverständliches. Arthur sagt „Er sagte, er sei ein Knappe. Das ist er sicher – vertrauen Sie ihm nicht!“ Was sind sie?

Dieses Beispiel entstammt aus [Smu78], wo Sie noch viele andere Rätsel dieser Art finden können.

1.3.2 Prädikatenlogik

Die logischen Begriffe, die wir oben vorgestellt haben, sind zwar grundlegend für alles weitere, aber nicht genügend komplex um interessante Aussagen zu bilden. Oft werden Aussagen formuliert, die für Elemente einer bestimmten Menge (an Zahlen, Vektoren, Äpfeln, …; mehr zu Mengen später) wahr oder falsch sein können. Zum Beispiel könnte $x$ für eine natürliche (oder rationale, reelle, …; mehr zu Zahlen später) Zahl stehen und „ $x = x^{2}$ “ ist dann eine Aussage über $x$ , die wahr oder falsch sein kann. Für derartige Aussagen „ $A (x)$ “ über Elemente $x$ einer Menge $X$ gibt es nun zwei weitere fundamentale Operationen, sogenannte Quantoren, um weitere Aussagen zu bilden.

Der Allquantor, geschrieben $\forall$ , wird verwendet um eine Aussage über alle Elemente von $X$ zu treffen. Genauer steht die Aussage „ $\forall x \in X : A (x)$ “ für die Aussage „ Für alle $x$ in $X$ gilt die Aussage $A (x)$ “. Diese Aussage kann wahr oder falsch sein. Zum Beispiel ist die Aussage

\begin{array}{l} „ \forall n \in ℕ : n = n^{2} “ \end{array}

falsch, aber die Aussage

\begin{array}{l} „ \forall n \in ℕ : (n = n^{2} \Rightarrow n = 1) “ \end{array}

ist richtig (denn wir werden $ℕ$ als ${1, 2, 3, \dots}$ definieren).

Der Existenzquantor, geschrieben $\exists$ , wird verwendet um auszudrücken, dass es ein $x \in X$ mit einer gewissen Eigenschaft gibt. Genauer steht „ $\exists x \in X : A (x)$ “ für „ Es gibt ein $x$ in $X$ , für das die Aussage $A (x)$ gilt“ . Zum Beispiel ist die Aussage

\begin{array}{l} „ \exists n \in ℕ : n = n^{2} “ \end{array}

richtig, da $n = 1$ eine natürliche Zahl ist, die $1^{2} = 1$ erfüllt. Weiters ist auch die Aussage

\begin{array}{l} „ \exists n \in ℕ : (n = n^{2} \Rightarrow n = 1) “ \end{array}

richtig. In der Tat können wir hier $n = 1$ verwenden, um die Existenz zu bestätigen. Alternativ können wir aber $n = 5$ verwenden: denn da $5 \neq 25 = 5^{2}$ , ist die Implikation „ $5 = 5^{2} \Rightarrow 5 = 1$ “ wahr.

Es ist noch wichtig zu bemerken, dass die Variable $x$ in „ $\forall x \in X : A (x)$ “ oder „ $\exists x \in X : A (x)$ “ nur innerhalb der Aussage „ $A (x)$ “ eine Bedeutung hat und wir auch ohne Änderung der Bedeutung der Aussage eine andere Variable (ohne vorgegebener Bedeutung) verwenden könnten. Der Geltungsbereich der Variable des Quantors geht bis zum Ende der Aussage oder dem Schliessen einer Klammer, die vor dem Quantor geöffnet wurde.

Bemerkung (Alternative Notation).

Anstelle der Symbole $\forall$ respektive $\exists$ werden teilweise auch die weniger gebräuchlichen Symbole $⋀$ respektive $⋁$ als Synonyme verwendet. Letztere haben den Vorteil, dass sie andeuten, dass $⋀$ ein erwachsen gewordenes $\land$ und $⋁$ ein erwachsen gewordenes $\lor$ darstellt. Um diesen Kommentar besser zu verstehen, nehmen wir an, dass $X = {x_{1}, x_{2}, x_{3}, \dots, x_{n}}$ eine endliche Menge ist, die genau die Elemente $x_{1}, \dots, x_{n}$ enthält. Dann gilt

\begin{array}{l} „ (⋀ x \in X : A (x)) \Leftrightarrow (A (x_{1}) \land A (x_{2}) \land \dots \land A (x_{n})) “ \end{array}

und

\begin{array}{l} „ (⋁ x \in X : A (x)) \Leftrightarrow (A (x_{1}) \lor A (x_{2}) \lor \dots \lor A (x_{n})) “ \end{array}

Später werden wir sehen, dass die Symbole $\cap, ⋂$ für den Durchschnitt von Mengen den Symbolen $\land, \forall$ und die Symbole $\cup, ⋃$ für die Vereinigung von Mengen den Symbolen $\lor, \exists$ entsprechen.

Kombinieren wir $\forall$ und $\exists$ so treten sehr schnell für den allgemeinen Sprachgebrauch vielleicht subtile aber für die Logik und die Mathematik fundamentale Nichtvertauschbarkeit der Quantoren zu Tage: Seien $X, Y$ Mengen und für jedes $x \in X$ und $y \in Y$ sei $A (x, y)$ eine Aussage. Dann haben die Aussagen

\begin{align} „ \forall x \in X \exists y \in Y : A (x, y) “ & (1.5) \end{align}

und

\begin{align} „ \exists y \in Y \forall x \in X : A (x, y) “ & (1.6) \end{align}

sehr verschiedene Bedeutungen.

In Worten würde man (1.5) vielleicht als eine individuelle Existenz und im Zusammenhang der Analysis als punktweise Existenz beschreiben. Denn es gibt zwar für jedes $x$ ein geeignetes individuelles $y$ mit der gewünschten Eigenschaft, doch hängt das $y$ vielleicht von der Wahl von $x$ ab. Hingegen ist (1.6) eine universelle oder gleichmässige Existenz. Denn das $y$ wird am Anfang der Aussage ein für alle Mal gewählt und die gewünschte Eigenschaft gilt dann für alle $x$ gleichermassen.

Beispiel 1.6 (Nicht-vertauschbare Quantoren).

Angenommen $X$ steht für die Menge der Studienanfänger an der ETH, $Y$ für die Menge der Vorlesungen für Studienanfänger. Zu $x \in X$ und $y \in Y$ sei $A (x, y)$ die Aussage „ Student $x$ interessiert sich für die Vorlesung $y$ “. Dann ist „ $\forall x \in X \exists y \in Y : A (x, y)$ “ hoffentlich wahr (oder es gibt Studenten, die sich für das völlig falsche Studium entschieden haben). Die Aussage „ $\exists y \in Y \forall x \in X : A (x, y)$ “ ist jedoch falsch, denn es gibt sicher zwei Studienanfänger, die keine gemeinsame Vorlesung besuchen und auch komplett verschiedene Interessen haben.

Ein mathematisches Beispiel für das gleiche Phänomen:

Beispiel 1.7 (Nicht-vertauschbare Quantoren).

Sei $Y = X$ eine beliebige Menge. Die Aussage „ $\forall x \in X \exists y \in X : x = y$ “ ist dann sicher richtig, da wir für jedes $x \in X$ einfach $y = x$ wählen können. Die Aussage „ $\exists y \in X \forall x \in X : x = y$ “ hingegen ist nur für sehr spezielle Mengen richtig, welche?

Teillösung.

Die zweite Aussage ist genau dann richtig, wenn $X$ genau ein Element hat: Auf Grund der Existenzbehauptung enthält $X$ zumindest ein Element $y$ , und der anschliessende Allquantor besagt nun, dass es kein anderes Element in $X$ geben kann.

Übung 1.8 (Nicht-vertauschbare Quantoren).

Sei $X = Y = ℕ$ und betrachten Sie die Aussage „ $x < y$ “. Was bedeuten die Aussagen (1.5) und (1.6) in diesem Fall? Treffen die Aussagen zu?

Lösung.

Die individuelle Existenz (1.5) behauptet bloss, dass es zu jeder natürlichen Zahl auch eine grössere gibt. Die universelle Existenz (1.6) behauptet hingegen fälschlicherweise, dass es eine natürliche Zahl gibt, die echt grösser als alle natürliche Zahlen (auch inklusive sich selbst) ist.

Diese Beispiele sind möglicherweise zu einfach; wir werden jedoch der Problematik, dass man einen Existenz- mit einem Allquantor nicht vertauschen darf, in komplizierten Situationen wieder begegnen. Für zwei Quantoren der gleichen Sorte ist die Situation einfacher:

Wichtige Übung 1.9 (Vertauschbarkeit von Quantoren).

Seien $X, Y$ zwei Mengen und für jedes $x \in X$ und $y \in Y$ sei „ $A (x, y)$ “ eine Aussage. Überzeugen Sie sich oder noch besser eine Mitstudentin/einen Mitstudenten davon, dass

\begin{array}{l} „ (\forall x \in X \forall y \in Y : A (x, y)) \Leftrightarrow (\forall y \in Y \forall x \in X : A (x, y)) “ \\ „ (\exists x \in X \exists y \in Y : A (x, y)) \Leftrightarrow (\exists y \in Y \exists x \in X : A (x, y)) “ \end{array}

wahre Aussagen sind.

Auf Grund der Aussage in Übung 1.9 werden wir, gegeben eine Aussage „ $A (x, y)$ “ über zwei Elemente einer Menge $X$ , anstelle von der Aussage „ $\forall x \in X \forall y \in X : A (x, y)$ “ auch „ $\forall x, y \in X : A (x, y)$ “ und anstelle von „ $\exists x \in X \exists y \in X : A (x, y)$ “ auch „ $\exists x, y \in X : A (x, y)$ “ schreiben.

Wir bemerken noch eine sonderbare Eigenheit des Allquantors. Sei $\emptyset$ die Menge, die keine Elemente enthält (die sogenannte „leere Menge“ – siehe nächster Abschnitt). Dann ist „ $\forall x \in \emptyset : A (x)$ “ immer wahr, unabhängig davon, welche Aussage $A (x)$ ist. Hingegen ist „ $\exists x \in \emptyset : A (x)$ “ immer falsch, da es ja keine Elemente in $\emptyset$ gibt.

Man kann die Quantoren und die logischen Operationen auf sehr viele Arten kombinieren und sehr schnell sehr komplizierte Aussagen bilden. Später werden wir viele Beispiele sehen. Gute gewählte Definitionen werden uns aber helfen, komplizierte verschachtelte Aussagen in Prädikatenlogik übersichtlicher, einfacher und intuitiver zu machen.

Als nächstes möchten wir hier aber noch die Negation von Quantoren besprechen. Intuitiv ist die Negation des Allquantors ein Existenzquantor und die Negation des Existenzquantors ein Allquantor. Besser und genauer ausgedrückt gelten für eine beliebige Aussage „ $A (x)$ “ über Elemente $x$ einer Menge $X$ die folgenden Aussagen:

\begin{aligned} „ \neg (\forall x \in X : A (x)) \Leftrightarrow \exists x \in X : \neg A (x) “ \\ „ \neg (\exists x \in X : A (x)) \Leftrightarrow \forall x \in X : \neg A (x) “ \end{aligned}

(1.7)

Damit diese Äquivalenzen wirklich immer (also auch für die leere Menge) gelten, müssen wir auch die obig erwähnte Eigenheit des Allquantors für die leere Menge akzeptieren.

Beispielsweise ist die Negation von „Auf jedem Planeten herrscht Gravitation“ die Aussage „Es gibt einen Planeten, auf dem keine Gravitation herrscht“. Bei mehreren Quantoren verhält sich die Negation ähnlich wie ein Minus-Symbol vor einem geklammerten Ausdruck und kann nach Innen geschoben werden. Wir empfehlen dies in folgender Übung zu überdenken.

Wichtige Übung 1.10 (Negation und verkettete Quantoren).

Sei $X$ eine Teilmenge der reellen Zahlen $ℝ$ . Bilden Sie die Negation folgender Aussagen und versuchen Sie die Negation so weit wie möglich nach rechts zu verschieben (obwohl die Aussagen geometrische Bedeutung haben, muss man diese weder kennen noch verstehen, um die Aufgabe zu lösen):

•

„

\forall y \in ℝ \forall 𝜀 > 0 \exists x \in X : | x - y | < 𝜀

“

•

„

\forall y \in X \exists 𝜀 > 0 \forall x \in X : | x - y | < 𝜀 \Rightarrow x = y

“

•

„

\forall 𝜀 > 0 \forall x \in X \exists y \in X : (y \neq x) \land | x - y | < 𝜀

“

Hier ist „ $\forall 𝜀 > 0 : A (𝜀)$ “ eine gebräuchliche Kurzform für „ $\forall 𝜀 \in ℝ : 𝜀 > 0 \Rightarrow A (𝜀)$ “ oder anders ausgedrückt für „ $\forall 𝜀 \in {x \in ℝ ∣ x > 0} : A (𝜀)$ “. Die Aussage „ $\exists 𝜀 > 0 : A (𝜀)$ “ steht für „ $\exists 𝜀 \in ℝ : 𝜀 > 0 \land A (𝜀)$ “ oder äquivalenterweise für „ $\exists 𝜀 \in {x \in ℝ ∣ x > 0} : A (𝜀)$ “. Sie können für die Negation von „ $| x - y | < 𝜀$ “ auch einfach „ $\neg (| x - y | < 𝜀)$ “ schreiben, doch ist dies auf Grund üblicher Definitionen und Eigenschaften von $ℝ$ äquivalent zu „ $| x - y | \geq 𝜀$ “.

Eine Lösung zum ersten Teil.

Wir demonstrieren die Vorgehensweise am ersten Teil der Übung. Auf Grund der direkt vor der Übung erwähnten „Rechenregeln“ mit Quantoren erhalten wir

\begin{array}{l} „ \neg (\forall y \in ℝ & \forall 𝜀 > 0 \exists x \in X : | x - y | < 𝜀) “ \\ \Leftrightarrow „ \exists y \in ℝ : \neg (\forall 𝜀 > 0 \exists x \in X : | x - y | < 𝜀) “ \\ \Leftrightarrow „ \exists y \in ℝ \exists 𝜀 > 0 : \neg (\exists x \in X : | x - y | < 𝜀) “ \\ \Leftrightarrow „ \exists y \in ℝ \exists 𝜀 > 0 \forall x \in X : \neg (| x - y | < 𝜀) “ \\ \Leftrightarrow „ \exists y \in ℝ \exists 𝜀 > 0 \forall x \in X : | x - y | \geq 𝜀 “ . \end{array}

Übung 1.11 (Verknüpfung von Quantoren).

Wir wollen in dieser Übung untersuchen, welche Eigenschaften All- und Existenzquantor gemeinsam mit der Und- und Oder-Operation erfüllen. Seien „ $A (x)$ “ und „ $B (x)$ “ zwei Aussagen über Elemente $x$ einer Menge $X$ . Untersuchen Sie jeweils die beiden Aussagen in einer Zeile und überlegen Sie sich, ob diese äquivalent sind oder ob bloss eine der Aussagen impliziert. Im zweiten Fall bestimmen Sie die „stärkere“ und die „schwächere“ Aussage und begründen Sie die Implikation. Beide der erwähnten Möglichkeiten treten zweimal auf.

\begin{array}{l} „ \forall x \in X : (A (x) \land B (x)) “ & „ (\forall x \in X : A (x)) \land (\forall x \in X : B (x)) “ \\ „ \forall x \in X : (A (x) \lor B (x)) “ & „ (\forall x \in X : A (x)) \lor (\forall x \in X : B (x)) “ \\ „ \exists x \in X : (A (x) \land B (x)) “ & „ (\exists x \in X : A (x)) \land (\exists x \in X : B (x)) “ \\ „ \exists x \in X : (A (x) \lor B (x)) “ & „ (\exists x \in X : A (x)) \lor (\exists x \in X : B (x)) “ \end{array}

Für die Untersuchung dieser Fragen empfiehlt es sich die Variablen in den beiden Quantoren rechts statt zweimal mit $x$ besser getrennt mit $x_{1}$ und $x_{2}$ zu bezeichnen.

Lösung.

Verwandte Operationen ( $\forall, \land$ beziehungsweise $\exists, \lor$ ) vertragen sich hier sehr gut und ergeben Äquivalenzen: In der ersten Zeile wird in beiden Aussagen behauptet, dass sowohl „ $A (x)$ “ als auch „ $B (x) “$ für alle $x$ in $X$ gilt. In der letzten Zeile wird in beiden Aussagen behauptet, dass es ein $x$ gibt, für dass zumindest eine der Aussagen „ $A (x)$ “ oder „ $B (x)$ “ zutrifft. Die Aussagen links und rechts unterscheiden sich in diesen beiden Fällen nur in der Formulierung.

In der zweiten Zeile gilt aber bloss die Implikation

\begin{array}{l} „ ((\forall x_{1} \in X : A (x_{1})) \lor (\forall x_{2} \in X : B (x_{2}))) \Rightarrow (\forall x \in X : (A (x) \lor B (x))) “ . \end{array}

Denn wenn links zum Beispiel „ $\forall x_{1} \in X : A (x_{1})$ “ zutrifft, so trifft natürlich auch „ $\forall x \in X : (A (x) \lor B (x))$ “ zu. Die Umkehrung stimmt im Allgemeinen nicht, da in der Aussage „ $\forall x \in X : (A (x) \lor B (x))$ “ die Aussagen $„ A (x) “$ und $„ B (x) “$ für verschiedene $x$ in $X$ abwechselnd zutreffen könnten, und dann sowohl „ $\forall x_{1} \in X : A (x_{1})$ “ als auch „ $\forall x_{2} \in X : B (x_{2})$ “ falsch sein könnten.

In der dritten Zeile gilt hingegen

\begin{array}{l} „ (\exists x \in X : (A (x) \land B (x))) \Rightarrow ((\exists x_{1} \in X : A (x_{1})) \land (\exists x_{2} \in X : B (x_{2}))) “ \end{array}

Denn wenn für ein bestimmtes $x \in X$ sowohl „ $A (x)$ “ als auch „ $B (x)$ “ zutreffen, so gelten die beiden Aussagen „ $\exists x_{1} \in X : A (x_{1})$ “ und „ $\exists x_{2} \in X : B (x_{2})$ “ auf jeden Fall (in dem man $x_{1} = x_{2} = x$ für ein $x$ in $X$ mit „ $A (x) \land B (x)$ “ wählt). Wiederum stimmt aber die Umkehrung im Allgemeinen nicht: In der Aussage „ $(\exists x_{1} \in X : A (x_{1})) \land (\exists x_{2} \in X : B (x_{2})$ “ gibt es vielleicht nur zwei verschiedene $x_{1} \neq x_{2}$ in $X$ mit „ $A (x_{1}) \land B (x_{2})$ “ ohne dass es ein gemeinsames $x$ in $X$ mit „ $A (x) \land B (x)$ “ geben muss.

Ein dritter Quantor, der häufig verwendet wird, ist der Quantor der eindeutigen Existenz, geschrieben $\exists!$ . Dieser lässt sich mit Hilfe der beiden Quantoren $\forall$ und $\exists$ wie folgt definieren: Die Aussage „ $\exists! x \in X : A (x)$ “ wird durch

\begin{array}{l} „ (\exists x \in X : A (x)) \land (\forall x, y \in X : (A (x) \land A (y) \Rightarrow x = y)) “ \end{array}

definiert. Sie bedeutet, dass es ein $x$ in $X$ gibt, das die Aussage „ $A (x)$ “ erfüllt und dass dieses $x$ durch die Aussage eindeutig bestimmt ist. Es gibt also kein weiteres Element $y \in X$ , welches nicht gleich $x$ ist und „ $A (y)$ “ erfüllt.

Übung 1.12.

Formulieren Sie ein konkretes Beispiel zu obigem. In anderen Worten: finden Sie eine Aussage über Elemente einer Menge, die von genau einem Element erfüllt wird.

Eine Warnung: Sei $X$ eine Menge und „ $A (x)$ “ eine Aussage über Elemente von $X$ . Nach dem Satz „Es gibt ein eindeutig bestimmtes $x_{0}$ in $X$ , das $A (x_{0})$ erfüllt.“ wird oft dieses $x_{0}$ in weiteren Argumenten verwendet. Da $x_{0}$ eindeutig festgelegt ist, ist dies akzeptabel und oft auch sehr natürlich. Manchmal wird aber auch nach dem Satz „ Es gibt ein $x$ in $X$ , das $A (x)$ erfüllt.“ so ein $x$ in der Argumentation benötigt. Hier sollte man erwähnen, dass so ein $x$ gewählt wird. Des Weiteren sollte man, wenn nötig, sicher stellen, dass das darauf Folgende nicht (oder nur auf unwesentliche Weise) von der Wahl von $x$ abhängt.

Übung 1.13.

Zum Spass: Betrachten Sie den Satz „Everybody loves my babe, but my babe loves no one but me“ (leicht adaptiert nach Louis Armstrong) vom streng logischen Standpunkt. Handelt er von einem Liebespaar?

1.3.3 Eine kurze Übersicht

Wir wollen die wichtigsten logischen Begriffe der Aussagen- und Prädikatenlogik hier nochmals kurz in einer Tabelle zusammenfassen.

Abkürzung	Bedeutung	Negation

$\neg A$	$A$ gilt nicht.	$A$
$A \land B$	$A$ und $B$ gelten.	$\neg A \lor \neg B$
$A \lor B$	$A$ oder $B$ (einschliessend) gilt.	$\neg A \land \neg B$
$A \Rightarrow B$	$A$ impliziert $B .$	$A \land \neg B$
$A \Leftrightarrow B$	$A$ und $B$ sind äquivalent.	$(A \land \neg B) \lor (\neg A \land B)$
$\forall x \in X : A (x)$	Für alle $x$ in $X$ gilt $A (x)$ .	$\exists x \in X : \neg A (x)$
$\exists x \in X : A (x)$	Es existiert ein $x$ in $X$ mit $A (x)$ .	$\forall x \in X : \neg A (x)$
$\exists! x \in X : A (x)$	Es existiert genau ein $x$ in $X$ mit $A (x)$ .
$\forall x \in X \exists y \in Y : A (x, y)$	„Individuelle/punktweise Existenz“
$\exists y \in Y \forall x \in X : A (x, y)$	„Universelle/gleichmässige Existenz“

Für die letzten beiden Zeilen verweisen wir auf die Diskussion nach (1.5)-(1.6). Wir überlassen es der Leserin/dem Leser die Tabelle zu vervollständigen und so lange mit Kolleginnen und Kollegen zu besprechen, bis alle auftretenden Zeilen für Sie logisch sind.