1. Grundlagen


 

Einleitung

 

In diesem ersten Kapitel unserer Vorlesung stellen wir wichtige Grundlagen der mathematischen Logik und - darauf aufbauend - der Mengenlehre zur Verfügung.

 

Erste Vorlesungseinheit: Mathematische Logik

 

Im ersten Abschnitt Mathematische Logik führen wir Aussagen und ihre Verknüpfungen ein. Von besonderer Wichtigkeit sind einmal die aussagenlogischen Beweisprinzipien, die wir zu jeder Zeit in allen Vorlesungen des Mathematikstudiums  gebrauchen, und zweitens die prädikatenlogischen Quantoren. Alle diese Begriffe gehören zum elementaren Wortschatz der Mathematik.

 

Zweite Vorlesungseinheit: Mengenlehre

 

Den Begriff einer Menge werden wir nicht definieren, er wird vielmehr über ein geeignetes Axiomensystem eingeführt, was aber nicht im Rahmen unserer Vorlesung liegt. Rechenregeln für Mengen leiten wir direkt aus den aussagenlogischen Gesetzmäßigkeiten ab. Den in den Abschnitten 1.1.4 und 1.1.5 eingeführten Begriffen über die Charakterisierung von Abbildungen bzw. den der Mächtigkeit von Mengen werden Sie an unzähligen Stellen ihres Mathematikstudiums wiederbegegnen.

1.1 Mathematische Logik

 

1.1.1 Aussagen und Aussageformen

 

Mathematik ist das Aufstellen und Analysieren von Aussagen, wie zum Beispiel

  • Die Zahl \( 3 \) ist eine Primzahl.
  • Die Zahl \( 4 \) ist eine Primzahl.
  • Es gibt unendlich viele Primzahlzwillinge.

Die erste Aussage ist richtig, die zweite falsch. Über den Wahrheitsgehalt der dritten Aussage können wir nicht abschließend entscheiden, sind aber überzeugt, dass sie entweder wahr oder falsch ist.

 

Definition: Eine Aussage ist ein umgangssprachlicher Satz, der entweder wahr oder falsch ist.

 

Diese Definition beinhaltet die Zweiwertigkeit Aussagenlogik: Außer wahr und falsch gibt es keine weitere Möglichkeit.

 

Es gibt auch sprachliche Formulierungen, die keine Aussagen sind, da wir ihnen auf sinnvolle Weise keinen Wahrheitswert zuordnen können, wie Glückwünsche, Fragen oder Aufforderungen der folgenden Art:

  • Herzlichen Glückwunsch!
  • Wollen wir wetten?
  • Komm jetzt endlich!

Mathematische Ausdrücke, wie

  • \( x+7=28 \)
  • \( {\mathcal R}(0,3,1) \)

bezeichnen wir als Aussageformen. Sie werden zu Aussagen, nachdem wir einmal den „Platzhalter“ \( x \) durch eine Zahl substituieren und so \( x+7=28 \) zu einer wahren oder falschen Aussage machen, oder \( {\mathcal R}(x,y,z) \) beispielsweise als die Relation \( x\lt y\lt z \) interpretieren, was die Aussage \( {\mathcal R}(x,y,z) \) in unserem Beispiel falsch macht.

 

Aufgaben zu diesem Abschnitt

 


 

 

1.1.2 Verknüpfungen von Aussagen

 

Mathematische Aussagen bezeichnen wir mit kleinen Buchstaben \( a, \) \( b, \) \( c \) usw. Wir ordnen ihnen genau einen der beiden Wahrheitswerte zu

 

entweder    \( 1 \) (wahr)    oder    \( 0 \) (falsch).

 

Aussagen setzen wir durch folgende Junktoren miteinander in Beziehung \[ \neg\,,\quad \wedge\,,\quad \vee\,,\quad \to\,,\quad \leftrightarrow\,. \] In dieser Reihenfolge bedeuten sie: nicht, und, oder, folgt (impliziert), äquivalent.

 

Die Bedeutungen dieser Verknüpfungen definieren wir anhand einer Wahrheitstabelle:

 

\( a \) \( b \) \( \neg a \) \( \neg b \) \( a\wedge b \) \( a\vee b \) \( a\to b \) \( b\to a \) \( a\leftrightarrow b \)
\( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
\( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 0 \)
\( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)

 

 

Beispiel: Es besitzen \( a\to b \) und \( \neg a\vee b \) dieselben Wahrheitstabellen:

 

\( a \) \( b \) \( a\to b \) \( \neg a \) \( \neg a\vee b \)
\( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
\( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \)
\( 1 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \)

 

Sie heißen daher im aussagenlogischen Sinn äquivalent, i.Z. \[ (a\to b)\equiv(\neg a\vee b). \] Die runden Klammern geben dabei an, in welcher Reihenfolge die Verknüpfungen auszuführen sind. Wir vereinbaren: Von der höchsten zur niedrigsten Priorität sind der Reihe nach auszuführen \( \neg, \) \( \wedge, \) \( \vee, \) \( \to, \) \( \leftrightarrow. \)

 

Aufgaben zu diesem Abschnitt

 


 

 

1.1.3 Aussagenlogische Beweisprinzipien

 

Definition: Unter einer Tautologie verstehen wir eine Aussage, die unabhängig von der Belegung ihrer Variablen durch die Wahrheitswerte \( 0 \) oder \( 1 \) stets wahr ist.

 

Beispiele solcher Tautologien, die auch gleichzeitig grundlegende mathematische Beweisprinzipien darstellen, beinhaltet der

 

Satz: Die folgenden Aussagen sind Tautologien:

\( \circ \) Satz vom ausgeschlossenen Dritten \( a\vee\neg a \)
\( \circ \) Satz vom Widerspruch \( \neg(a\wedge\neg a) \)
\( \circ \) Satz von der doppelten Verneinung \( \neg(\neg a)\to a \)
\( \circ \) Satz von der Kontraposition \( (a\to b)\leftrightarrow(\neg b\to\neg a) \)
\( \circ \) Satz zum modus ponens \( (a\to b)\wedge a\to b \)
\( \circ \) Satz zum modus tollens \( (a\to b)\wedge\neg b\to\neg a \)
\( \circ \) Satz zum modus barbara (Kettenschluss) \( (a\to b)\wedge(b\to c)\to(a\to c) \)

 

Hieraus möchten wir vier Beweisprinzipien in Worte wiedergeben:

\( \circ \) Satz vom ausgeschlossenen Dritten
  entweder es gilt \( a, \) oder es gilt nicht \( a \)
\( \circ \) Satz vom Widerspruch
  eine Aussage \( a \) und ihre Negation \( \neg a \) können nicht gleichzeitig wahr sein
\( \circ \) modus ponens (direkter Beweis)
  gilt \( a, \) und folgt \( b \) aus \( a, \) so gilt auch \( b \)
\( \circ \) modus tollens (indirekter Beweis)
  gilt \( \neg b, \) kann aber \( b \) aus \( a \) abgeleitet werden, so ist \( a \) falsch

 

Im Gegensatz zu Tautologien sind Kontradiktionen Aussagen, die unabhängig von der Belegung ihrer Variablen durch Wahrheitswerte stets falsch sind.

 

Aufgaben zu diesem Abschnitt

 


 

 

1.1.4 Quantoren

 

Wir haben wir es stets mit Variablen \( x,y,\ldots \) als Elemente von Individuenmengen zu tun. Für ihre Beschreibung benötigen wir die beiden folgenden Quantoren.

 

Definition: Es sei \( p \) eine von einer Variablen \( x \) aus einer Individuenmenge \( X \) abhängige Aussageform. Der Allquantor \( \forall \) und der Existenzquantor \( \exists \) sind dann wie folgt definiert:

\( \circ \) \( \forall x\in X\,p(x) \)
  für alle Elemente \( x \) aus \( X \) ist die Aussage \( p(x) \) wahr
\( \circ \) \( \exists x\in X\,p(x) \)
  es existiert ein Element \( x \) aus \( X, \) für welches die Aussage \( p(x) \) wahr ist

 

Im zweiten Punkt bedeutet „es existiert“ die Existenz wenigstens eines Elementes \( x \) aus der Individuenmenge \( X. \)

 

Beispiel: Eine reellwertige Funktion \( f\colon\Omega\to\mathbb R \) heißt in einem Punkt \( x_0\in\Omega \) stetig, wenn gilt \[ \forall\varepsilon>0\,\exists\delta>0\,\forall x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\to\lvert f(x)-f(x_0)\rvert\lt\varepsilon) \] bzw. in Worten:

 

Für alle \( \varepsilon\gt 0 \) existiert ein \( \delta\ge 0, \) so dass für alle \( x\in\Omega: \) \( |x-x_0|\lt\delta \) impliziert \( |f(x)-f(x_0)|\lt\varepsilon. \)

 

Wir benötigen hierin vier Variablen \( x, \) \( x_0, \) \( \delta, \) \( \varepsilon, \) wobei \( x, \) \( \varepsilon, \) \( \delta \) von den Quantoren \( \forall \) bzw. \( \exists \) gebunden werden, während \( x_0 \) frei bleibt.

 

Die Relationen \( \in \) und \( \lt \) sind Beispiele sogenannter Prädikate. Logische Formeln dieser und ähnlicher Art sind Gegenstand der Prädikatenlogik und werden als prädikatenlogische Formeln bezeichnet.

 

Definition: Der Allquantor \( \forall \) und der Existenzquantor \( \exists \) werden wie folgt negiert \[ \neg\forall x\,p(x)\equiv\exists x\,\neg p(x),\quad \neg\exists x\,p(x)\equiv\forall x\,\neg p(x). \] Linksseitig wirkt der Negationsoperator jeweils auf die gesamten Ausdrücke \( \forall x\,p(x) \) bzw. \( \exists x\,p(x). \)

 

Beispiel: Wir ermitteln \[ \neg\forall x\,\exists y\,p(y)\equiv\exists x\,\neg\exists y\,p(y)\equiv\exists x\forall y\,\neg p(y). \]

 

Aufgaben zu diesem Abschnitt

 


 

 

1.1.5 Aufgaben

 

Aufgaben zu Aussagen und Aussageformen

 

Aufgabe 1.1.1: (Beispiele für Aussagen)

Welche der folgenden Sätze sind Aussagen, welche sind keine Aussagen?

(i) Berlin ist die Hauptstadt der Bundesrepublik Deutschland.
(ii) Alle Studenten sind fleißig.
(iii) Gestern hat es den ganzen Tag geregnet.
(iv) Reisen bildet.
(v) Hat die Vorlesung bereits begonnen?
(vi) Mathematik soll also schwer sein!

 

Lösung

 

(i) Es handelt sich um eine Aussage.
(ii) Es handelt sich um eine Aussage.
(iii) Es handelt sich um eine Aussage.
(iv) Es handelt sich um eine Aussage.
(v) Es handelt sich nich um eine Aussage.
(vi) Es handelt sich nicht um eine Aussage.

 

 

Aufgabe 1.1.2: (Aussageformen)

Geben Sie jeweils ein Beispiel einer mathematischen Aussageform \( {\mathcal R}(x) \) mit einer, \( {\mathcal S}(x,y) \) mit zwei und \( {\mathcal T}(x,y,z) \) mit drei freien Variablen, so dass

(i) \( {\mathcal R}(6) \) wahr ist,
(ii) \( {\mathcal S}(1,7) \) wahr ist,
(iii) \( {\mathcal T}(1,3,12) \) wahr ist.

 

Lösung

 

(i) \( {\mathcal R}(x)\,:\,x-6=0, \) denn \( {\mathcal R}(6)\,:\,6-6=0 \) ist wahr
(ii) \( {\mathcal S}(x,y)\,:\,7x-y=0, \) denn \( {\mathcal S}(1,7)\,:\,7\cdot 1-7=0 \) ist wahr
(iii) \( {\mathcal T}(x,y,z)\,:\,3x+3y-z=0, \) denn \( {\mathcal T}(1,3,12)\,:\,3\cdot 1+3\cdot 3-12=0 \) ist wahr

 

 

Aufgaben zu Verknüpfungen von Aussagen

 

Aufgabe 1.1.3: (Doppelte Verneinung)

Beweisen Sie die aussagenlogische Äquivalenz vermittels einer Wahrheitstabelle \[ \neg\neg a\equiv a. \]

 

Lösung

 

Betrachte die folgende Wahrheitstabelle:

\( a \) \( \neg a \) \( \neg\neg a \)
\( 0 \) \( 1 \) \( 0 \)
\( 1 \) \( 0 \) \( 1 \)

Also gilt \( a\equiv\neg\neg a. \)

 

 

Aufgabe 1.1.4: (Äquivalenzen der Implikation)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( a\to b\equiv \neg a\vee b \)
(ii) \( a\to b\equiv \neg b\to\neg a \)
(iii) \( a\leftrightarrow b\equiv(a\vee\neg b)\wedge(\neg a\vee b) \)

 

Lösung

 

(i) Setze \( \alpha:=a\to b \) und \( \beta:=\neg a\vee b. \) Dann ist
 
\( a \) \( \neg a \) \( b \) \( \alpha \) \( \beta \)
\( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
\( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
  Also gilt \( a\to b\equiv \neg a\vee b. \)
(ii) Setze \( \alpha:=a\to b \) und \( \beta:=\neg b\to\neg a. \) Dann ist
 
\( a \) \( \neg a \) \( b \) \( \neg b \) \( \alpha \) \( \beta \)
\( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
\( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
  Also gilt \( a\to b\equiv \neg b\to \neg a. \)
(iii) Setze \( \alpha:=a\leftrightarrow b \) und \( \beta:=(a\vee\neg b)\wedge(\neg a\vee b). \) Dann ist
 
\( a \) \( \neg a \) \( b \) \( \neg b \) \( a\vee\neg b \) \( \neg a\vee b \) \( \alpha \) \( \beta \)
\( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
  Also gilt \( a\leftrightarrow b\equiv(a\vee\neg b)\wedge(\neg a\vee b). \)

 

 

Aufgabe 1.1.5: (Distributivgesetze der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c) \)
(ii) \( a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c) \)

 

Lösung

 

(i) Setze \( \alpha:=a\wedge(b\vee c) \) und \( \beta:=(a\wedge b)\vee(a\wedge c). \) Dann ist
 
\( a \) \( b \) \( c \) \( a\wedge b \) \( a\wedge c \) \( b\vee c \) \( \alpha \) \( \beta \)
\( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \)
\( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \)
\( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \)
\( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \)
\( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
  Also gilt \( a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c). \)
(ii) Setze \( \alpha:=a\vee(b\wedge c) \) und \( \beta:=(a\vee b)\wedge(a\vee c). \) Dann ist
 
\( a \) \( b \) \( c \) \( a\vee b \) \( a\vee c \) \( b\wedge c \) \( \alpha \) \( \beta \)
\( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \)
\( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 0 \)
\( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 0 \) \( 0 \)
\( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
\( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
\( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
  Also gilt \( a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c). \)

 

 

Aufgabe 1.1.6: (de Morgansche Regeln der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( \neg(a\wedge b)\equiv\neg a\vee\neg b \)
(ii) \( \neg(a\vee b)\equiv\neg a\wedge\neg b \)

 

Lösung

 

Lösung von Michelle-Christin Bein, Sarah Drescher und Dimitar Georgiev:

 

 

Aufgaben zu Aussagenlogische Beweisprinzipien

 

Aufgabe 1.1.7: (Beispiele aussagenlogischer Tautologien I)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

(i) \( a\vee(b\wedge\neg b)\to a \)
(ii) \( a\wedge(b\vee\neg b)\to a \)

Die Aussage (ii) bezeichnet man auch als reductio ad absurdum (indirekter Beweis oder Beweis durch Widerspruch).

 

Lösung

 

(i) Setze zur Abkürzung \( \varphi:=a\vee(b\wedge\neg b)\to a, \) und betrachte folgende Wahrheitstabelle:
 
\( a \) \( b \) \( \neg b \) \( b\wedge\neg b \) \( a\vee(b\wedge\neg b) \) \( \varphi \)
\( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \)
\( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 0 \) \( 1 \)
\( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \)
\( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \)
  Also stellt \( a\vee(b\wedge\neg b)\to a \) eine Tautologie dar.
(ii) Setze zur Abkürzung \( \varphi:=a\wedge(b\vee\neg b)\to a, \) und betrachte folgende Wahrheitstabelle:
 
\( a \) \( b \) \( \neg b \) \( b\vee\neg b \) \( a\wedge(b\vee\neg b) \) \( \varphi \)
\( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \)
\( 0 \) \( 1 \) \( 0 \) \( 1 \) \( 0 \) \( 1 \)
\( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
  Also stellt \( a\wedge(b\vee\neg b)\to a \) eine Tautologie dar.

 

 

Aufgabe 1.1.8: (Beispiele aussagenlogischer Tautologien II)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

(i) Satz vom ausgeschlossenen Dritten \( a\vee\neg a \)
(ii) Satz vom Widerspruch \( \neg(a\wedge\neg a) \)
(iii) Satz von der doppelten Verneinung \( \neg(\neg a)\to a \)
(iv) Satz von der Kontraposition \( (a\to b)\to(\neg b\to\neg a) \)

 

Lösung

 

(i) Betrachte die folgende Wahrheitstabelle:
 
\( a \) \( \neg a \) \( a\vee\neg a \)
\( 0 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 1 \)
  Also stellt \( a\vee\neg a \) eine Tautologie dar.
(ii) Betrachte die folgende Wahrheitstabelle:
 
\( a \) \( \neg a \) \( a\wedge\neg a \) \( \neg(a\wedge\neg a) \)
\( 0 \) \( 1 \) \( 0 \) \( 1 \)
\( 1 \) \( 0 \) \( 0 \) \( 1 \)
  Also stellt \( \neg(a\wedge\neg a) \) eine Tautologie dar.
(iii) Betrachte die folgende Wahrheitstabelle:
 
\( a \) \( \neg\neg a \) \( \neg\neg a\to a \)
\( 0 \) \( 0 \) \( 1 \)
\( 1 \) \( 1 \) \( 1 \)
  Also stellt \( \neg(\neg a)\to a \) eine Tautologie dar.
(iv) Setze zur Abkürzung \( \varphi:=(a\to b)\to(\neg b\to\neg a), \) und betrachte folgende Wahrheitstabelle:
 
\( a \) \( b \) \( a\to b \) \( \neg b \) \( \neg a \) \( \neg b\to\neg a \) \( \varphi \)
\( 0 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \) \( 1 \)
\( 0 \) \( 1 \) \( 1 \) \( 0 \) \( 1 \) \( 1 \) \( 1 \)
\( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \)
\( 1 \) \( 1 \) \( 1 \) \( 0 \) \( 0 \) \( 1 \) \( 1 \)
  Also stellt \( (a\to b)\to(\neg b\to\neg a) \) eine Tautologie dar.

 

 

Aufgabe 1.1.9: (Beispiele aussagenlogischer Tautologien III)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

(i) Satz zum modus ponens \( (a\to b)\wedge a\to b \)
(ii) Satz zum modus tollens \( (a\to b)\wedge\neg b\to\neg a \)
(iii) Satz zum modus barbara \( (a\to b)\wedge(b\to c)\to(a\to c) \)

 

Lösung

 

Lösung von Carina Michaela Maria Caprano und Pia-Lotte Sutter:

 

 

Aufgaben zu Quantoren

 

Aufgabe 1.1.10: (Mathematische Aussagen)

Es bezeichne \( \mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\} \) die Menge der ganzen Zahlen. Schreiben Sie die folgenden Aussagen als prädikatenlogische Formeln. Welche Aussage ist wahr, welche ist falsch?

(i) Es existieren ein \( x\in\mathbb Z \) und ein \( y\in\mathbb Z \) mit \( x+y=0. \)
(ii) Für alle \( x\in\mathbb Z \) existiert ein \( y\in\mathbb Z \) mit \( x+y=0. \)
(iii) Es existiert ein \( x\in\mathbb Z, \) so dass für alle \( y\in\mathbb Z \) gilt \( x+y=0. \)
(iv) Für alle \( x\in\mathbb Z \) und für alle \( y\in\mathbb Z \) gilt \( x+y=0. \)

 

Lösung

 

(i) \( \exists x\,\exists y\,(x+y=0) \)
  Die Aussage ist wahr, wähle beispielsweise \( x=1 \) und \( y=-1. \)
(ii) \( \forall x\,\exists y\,(x+y=0) \)
  Die Aussage ist wahr, denn wähle \( y=-x \) zu vorgelegtem \( y. \)
(iii) \( \exists x\,\forall y\,(x+y=0) \)
  Die Aussage ist falsch, ein solches \( x \) existiert nicht.
(iv) \( \forall x\,\forall y\,(x+y=0) \)
  Die Aussage ist falsch, denn wähle beispielsweise \( x=1 \) und \( y=2. \)

 

 

Aufgabe 1.1.11: (Negation der Stetigkeit)

Negieren Sie obige prädikatenlogische Formel der Stetigkeit einer Funktion in einem Punkt \( x_0\in\Omega, \) d.h. \[ \forall\varepsilon\gt 0\,\exists\delta\gt 0\,\forall x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\to\lvert f(x)-f(x_0)\rvert\lt\varepsilon) \] mit dem Ergebnis \[ \exists\varepsilon>0\,\forall\delta\gt 0\,\exists x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\wedge\lvert f(x)-f(x_0)\rvert\ge\varepsilon). \]

 

Lösung

 

Lösung von Tobias Glaszner:

 

 


 

 

1.1.6 Wiederholungsfragen

 

1. Was versteht man unter einer Aussage?
2. Was versteht man unter der Zweiwertigkeit der Aussagenlogik?
3. Wie sind die Junktoren \( \neg, \) \( \wedge, \) \( \vee, \) \( \to \) und \( \leftrightarrow \) definert?
4. Wann heißen zwei Aussagen äquivalent?
5. Was versteht man unter einer Tautologie?
6. Wie lautet der Satz vom ausgeschlossenen Dritten?
7. Wie lautet der Satz vom Widerspruch?
8. Wie lautet der Satz von der doppelten Verneinung?
9. Wie lautet der Satz von der Kontraposition?
10. Wie lautet der Satz zum modus ponens?
11. Wie lautet der Satz zum modus tollens?
12. Wie lautet der Satz zum modus barbara?
13. Wie wurden der Allquantor \( \forall \) und der Existenzquantor \( \exists \) eingeführt?
14. Wie werden die Quantoren \( \forall \) und \( \exists \) negiert?

 


 

1.2 Mengenlehre

 

1.2.1 Charakterisierung von Mengen

 

Eine Menge \( M \) lässt sich auf zwei Arten charakterisieren, nämlich:

\( \circ \) durch Angabe ihrer Elemente \( m_1, \) \( m_2, \) \( m_3 \) usw., i.Z.
 
\( M=\{m_1,m_2,m_3,\ldots\}, \)
  wobei die Reihenfolge der Elemente nicht wichtig ist, und Elemente werden nicht mehrfach angegeben werden;
\( \circ \) durch Angabe einer definierenden Eigenschaft, z.B.
 
\( M=\{x\in X\,:\,p(x)\}, \)
  d.h. \( M \) besteht aus allen Elementen \( x\in X \) mit der Eigenschaft \( p(x). \)

 

Beispiele:

Einmal durch Aufzählen der Elemente:

(i) Die Menge \( M=\{1\} \) besitzt \( 1 \) als einziges Element.
(ii) Die Menge \( M=\{1,\{1\}\} \) besteht aus den beiden Elementen \( 1 \) und \( \{1\}. \)
(iii) Die Menge \( \mathbb N=\{1,2,3,\ldots\} \) ist die Menge der natürlichen Zahlen ohne \( 0, \) also \( 1,2,3,\ldots \)

Ein zweites Mal durch Angabe einer charakterisierenden Eigenschaft:

(iv) Es ist \( \{x\in\mathbb R\,:\,x^2=2\}=\{\sqrt{2},-\sqrt{2}\} \) mit der Menge \( \mathbb R \) der reellen Zahlen.
(v) Es ist \( \{n\in\mathbb N\,:\,2^n\lt n^2\}=\{3\}. \)

 

Nach der axiomatischen Mengenlehre von Zermelo und Fraenkel existiert genau eine leere Menge \( \emptyset, \) welche kein Element enthält. Sie ist sie Teilmenge jeder Menge (siehe unten). Es ist insbesondere \[ \{x\in X\,:\,p(x)\} \] gleich der leeren Menge, falls die Aussage \( p(x) \) für kein \( x\in X \) wahr, also widersprüchlich ist. Jede andere Menge, die nicht gleich der leeren Menge ist, besitzt wenigstens ein Element.

 

Wir sprechen von einer endlichen Menge, falls die Anzahl ihrer Elemente eine endliche Zahl ist, andernfalls von einer unendlichen Menge (für eine genaue Definition siehe Abschnitt 1.2.4 unten).

 

Aufgaben zu diesem Abschnitt

 


 

 

1.2.2 Mengenrelationen und Mengenoperationen

 

Zunächst die zentralen Mengenrelationen:

 

Definition: Seien \( A \) und \( B \) zwei beliebige Mengen. Dann erklären wir

  \( A=B \) \( A \) ist gleich \( B \) \( x\in A\,\leftrightarrow x\in B \)
  \( A\subseteq B \) \( A \) ist Teilmenge von \( B \) \( x\in A\,\to x\in B \)
  \( A\subset B \) \( A \) ist echte Teilmenge von \( B \) \( A\subseteq B\,\wedge\,A\not=B \)

 

mit \( A\not= B \) für \( \neg(A=B). \)

 

Die Mengengleichheit \( A=B \) können wir auch so auffassen: \[ A=B\quad\mbox{genau dann, wenn}\quad A\subseteq B\ \mbox{und}\ B\subseteq A. \] Schließlich sind \( A\supseteq B \) gleichbedeutend mit \( B\subseteq A \) und \( A\supset B \) gleichbedeutend mit \( B\subset A. \)

 

Zweitens die wichtigsten Mengenoperationen:

 

Definition: Seien \( A \) und \( B \) zwei beliebige Mengen. Dann erklären wir ihre Vereinigung, ihren Durchschnitt und ihre Differenz gemäß

  \( A\cup B \) \( A \) vereinigt \( B \) \( \{x\,:\,x\in A\vee x\in B\} \)
  \( A\cap B \) \( A \) geschnitten \( B \) \( \{x\,:\,x\in A\wedge x\in B\} \)
  \( A\setminus B \) \( A \) weniger \( B \) \( \{x\,:\,x\in A\wedge x\not\in B\} \)

 

Definition: Seien \( A \) und \( B \) zwei beliebige Mengen. Dann erklären wir ihr kartesisches Produkt gemäß \[ A\times B:=\{(x,y)\,:\,x\in A,\ y\in B\}\,. \]

 

Das Symbol \( a:=b \) bedeutet, dass der neu einzuführende Ausdruck \( a \) definiert wird als der Ausdruck \( b. \) Dazu muss \( b \) bekannt sein.

 

Definition: Sei \( A\subseteq X \) Teilmenge einer Obermenge \( X. \) Dann erklären wir ihr Komplement gemäß \[ A^c:=\{x\,:\,x\in X\setminus A\} \]

 

Vereinigung, Durchschnitt, Differenz, kartesisches Produkt und Komplement von Mengen sind wieder Mengen.

 

Aufgaben zu diesem Abschnitt

 


 

 

1.2.3 Rechenregeln für Mengen

 

In Verallgemeinerung der bekannten aussagenlogischen Formeln \[ a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c),\quad a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c) \] gilt der folgende

 

Satz: (Distributivgesetz der Mengenlehre)

Für drei beliebige Mengen \( A, \) \( B \) und \( C \) gelten \[ A\cap(B\cup C)=(A\cap B)\cup(A\cap C),\quad A\cup(B\cap C)=(A\cup B)\cap(A\cup C). \]

 

Beweis: Wir zeigen nur die erste Behauptung. Wir wählen ein \( x\in A\cap(B\cup C) \) beliebig. Dann ist unter Verwendung des aussagenlogischen Distributivgesetzes für \( \wedge \) und \( \vee \) in der dritten Zeile, angewandt auf die Aussagen \( x\in A \) usw. (achten Sie darauf, wie die Mengenoperationen \( \cap \) und \( \cup \) aufgelöst werden)

\[ \begin{array}{lll} x\in A\cap(B\cup C) & \longrightarrow & (x\in A)\wedge(x\in B\cup C) \\ & \longrightarrow & (x\in A)\wedge(x\in B\vee x\in C) \\ & \longrightarrow & (x\in A\wedge x\in B)\vee(x\in A\wedge x\in C) \\ & \longrightarrow & (x\in A\cap B)\vee(x\in A\cap C) \\ & \longrightarrow & x\in(A\cap B)\cup(A\cap C). \end{array} \]

Es ist also \( x\in(A\cap B)\cup(A\cap C), \) falls \( x\in A\cap(B\cup C), \) und da \( x \) beliebig gewählt wurde, folgt \[ A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C). \] Die umgekehrte Inklusion \( \supseteq \) verbleibt als Übung.\( \qquad\Box \)

 

Die de Morganschen Regeln der Aussagenlogik übertragen sich wie folgt:

 

Satz: (de Morgansche Regeln der Mengenlehre)

Sind \( A \) und \( B \) zwei beliebige Teilmengen einer Obermenge \( X, \) so gelten \[ X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B),\quad X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B). \]

 

Aufgaben zu diesem Abschnitt

 


 

 

1.2.4 Abbildungen zwischen Mengen

 

Wir betrachten Abbildungen \( f\colon A\longrightarrow B. \)

 

Definition: Eine Abbildung \( f\colon A\to B \) zwischen zwei Mengen \( A \) und \( B \) heißt

\( \circ \) surjektiv, wenn für jedes \( b\in B \) ein \( a\in A \) mit \( f(a)=b \) existiert;
\( \circ \) injektiv, wenn \( f(a)=b \) für gegebenes \( b\in B \) höchstens eine Lösung \( a\in A \) besitzt, d.h.
 
sind \( a_1,a_2\in A \) mit \( a_1\not=a_2, \) so gilt \( f(a_1)\not=f(a_2) \)
  bzw.
 
sind \( a_1,a_2\in A \) mit \( f(a_1)=f(a_2), \) so gilt \( a_1=a_2\,; \)
\( \circ \) bijektiv, wenn \( f \) injektiv und surjektiv ist.

 

Insbesondere ist eine Abbildung \( f\colon A\to B \)

\( \circ \) nicht surjektiv, falls es ein \( b\in B \) gibt, welches nicht im Bildraum der Funktion liegt,
\( \circ \) nicht injektiv, falls es \( a_1\not=a_2 \) aus \( A \) gibt mit \( f(a_1)=f(a_2). \)

 

Eine bijektive Abbildung \( f\colon A\to B \) ordnet jedem Element \( a\in A \) genau ein Element \( b\in B \) zu, und umgekehrt wird jedes Element \( b\in B \) auf genau ein Element \( a\in A \) abgebildet, und zwar vermöge der in diesem Fall existierenden Umkehrabbildung \[ f^{-1}\colon B\longrightarrow A. \] Diese Umkehrabbildung besitzt die Eigenschaften \[ \begin{array}{l} f^{-1}\circ f(a):=f^{-1}(f(a))=a\quad\mbox{für alle}\ a\in A, \\ f\circ f^{-1}(b):=f(f^{-1}(b))=b\quad\mbox{für alle}\ b\in B. \end{array} \]

 

Definition: Eine Menge \( A \) heißt endlich, falls eine natürliche Zahl \( n\in\mathbb N \) und eine bijektive Abbildung \[ f\colon\{1,\ldots,n\}\longrightarrow A \] existieren. In diesem Fall setzen wir \( |A|:=n. \)

 

Aufgaben zu diesem Abschnitt

 


 

 

1.2.5 Mächtigkeit von Mengen

 

Unter der Mächtigkeit einer endlichen Menge \( A \) mit Elementen \( a_1,\ldots,a_n \) verstehen wir die Anzahl \( n \) ihrer Elemente und schreiben \[ |A|:=n. \] Im Fall unendlicher Mengen können wir aber nicht von einer solchen Anzahl sprechen. Uns genügt stattdessen die auf G. Cantor zurückgehende

 

Definition: Zwei Mengen \( A \) und \( B \) heißen gleichmächtig, wenn eine bijektive Abbildung \( f\colon A\to B \) existiert.

 

Für eine beliebige Menge \( A \) bezeichnen wir nun mit \( {\mathcal P}(A) \) ihre Potenzmenge, d.h. die Menge, deren Elemente genau die Teilmengen von \( A \) sind.

 

Beispiel: Es ist \[ {\mathcal P}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}\,, \] denn \( \emptyset, \) \( \{1\}, \) \( \{2\} \) und \( \{1,2\} \) sind die vier möglichen Teilmengen von \( \{1,2\}. \) Beachte dabei, dass die leere Menge \( \emptyset \) Teilmenge jeder Menge ist.

 

Tatsächlich gilt für jede endliche Menge \( A \) \[ |A|<|{\mathcal P}(A)|=2^{|A|}\,. \] Der Fall unendlicher Mengen wird uns im zweiten Kapitel begegnen.

 

Aufgaben zu diesem Abschnitt

 


 

 

1.2.6 Aufgaben

 

Aufgaben - Charakterisierung von Mengen

 

Aufgabe 1.2.1: (Darstellung von Mengen)

Welche Elemente besitzen die folgenden Mengen?

(i) \( M=\{(x,y)\in\mathbb N\,:\,1\le x\le 17\ \mbox{und}\ x\ \mbox{ist Primzahl}\} \)
(ii) \( M=\{(x,y)\in\mathbb N\times\mathbb N\,:\,x-y\ \mbox{ist ohne Rest durch}\ 2\ \mbox{teilbar}\} \)
(iii) \( M=\{(x,y)\in\mathbb Z\times\mathbb Z\,:\,x-y\ \mbox{ist ohne Rest durch}\ 3\ \mbox{teilbar}\} \)

 

Lösung

 

(i) \( M=\{2,3,5,7,11,13,17\} \)
(ii) \( M=\{(x,y)\in\mathbb N\times\mathbb N\,:\,x-y=2k\ \mbox{für ein}\ k\in\mathbb Z\} \)
(iii) \( M=\{(x,y)\in\mathbb Z\times\mathbb Z\,:\,x-y=3k\ \mbox{für ein}\ k\in\mathbb Z\} \)

 

 

Aufgaben - Mengenrelationen und Mengenoperationen

 

Aufgabe 1.2.2: (Rechenübung zu den Mengenoperationen)

Gegeben seien eine Grundmenge \( \Omega=\{0,1,2,3,4,5,6\} \) sowie die Teilmengen \[ A=\{1,2,3\}\,,\quad B=\{2,3,4\}\,. \] Ermitteln Sie \[ \Omega\setminus A,\quad \Omega\setminus B,\quad A\cup B,\quad A\cap B,\quad A\setminus B,\quad B\setminus A. \]

 

Lösung

 

\( \circ \) \( \Omega\setminus A=\{0,4,5,6\} \)
\( \circ \) \( A\cup B=\{1,2,3,4\} \)
\( \circ \) \( A\cap B=\{2,3\} \)
\( \circ \) \( A\setminus B=\{1\} \)
\( \circ \) \( B\setminus A=\{4\} \)

 

 

Aufgabe 1.2.3: (Kartesisches Produkt von Mengen)

Bilden Sie das kartesische Produkt \( M\times N \) der folgenden Mengen:

(i) \( M=\{1,2,3,4\} \) und \( N=\{a,b\} \)
(i) \( M=\{a,b,c\} \) und \( N=\{x,y\} \)
(iii) \( M=\{1,2,3,4,\ldots\} \) und \( N=\{1,2,3,4,\ldots\} \)
(iv) \( M=\{x\in\mathbb N\,:\,2\le x\le 3\} \) und \( N=\{x\in\mathbb N\,:\,6\le x\lt 9\} \)

 

Lösung

 

(i) \( M\times N=\{(1,a),(2,a),(3,a),(4,a),(1,b),(2,b),(3,b),(4,b) \)
(ii) \( M\times N=\{((a,x),(b,x),(c,x),(a,y),(b,y),(c,y)\} \)
(iii) \( M\times N=\{(m,n)\,:\,m,n\in\mathbb N\} \)
(iv) \( M\times N=\{(2,6),(2,7),(2,8),(3,6),(3,7),(3,8)\} \)

 

 

Aufgaben - Rechenregeln für Mengen

 

Aufgabe 1.2.4: (Distributivgesetze der Mengenlehre)

Es seien \( A, \) \( B \) und \( C \) drei beliebige Mengen. Beweisen Sie:

(i) \( A\cap(B\cup C)=(A\cap B)\cup(A\cap C) \)
(ii) \( A\cup(B\cap C)=(A\cup B)\cap(A\cup C) \)

 

Lösung

 

(i) Wir gehen wie folgt vor:
 
\( x\in A\cap(B\cup C) \)
\( \qquad\Longrightarrow \) \( x\in A\,\wedge\,x\in B\cup C \)
\( \qquad\Longrightarrow \) \( x\in A\wedge(x\in B\,\vee\,x\in C) \)
\( \qquad\Longrightarrow \) \( (x\in A\,\wedge\,x\in B)\vee(x\in A\,\wedge\,x\in C) \)
\( \qquad\Longrightarrow \) \( (x\in A\cap B)\vee(x\in A\cap C) \)
\( \qquad\Longrightarrow \) \( x\in(A\cap B)\cup(A\cap C) \)
  Das zeigt die Inklusion \( A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C). \) Weiter ist
 
\( x\in(A\cap B)\cup(A\cap C) \)
\( \qquad\Longrightarrow \) \( (x\in A\cap B)\vee(x\in A\cap C) \)
\( \qquad\Longrightarrow \) \( (x\in A\,\wedge\,x\in B)\vee(x\in A\,\wedge\,x\in C) \)
\( \qquad\Longrightarrow \) \( x\in A\wedge(x\in B\,\vee\,x\in C) \)
\( \qquad\Longrightarrow \) \( x\in A\wedge(x\in B\cup C) \)
\( \qquad\Longrightarrow \) \( x\in A\cap(B\cup C) \)
  Das zeigt die Inklusion \( (A\cap B)\cup(A\cap C)\subseteq A\cap(B\cup C) \) und damit die Behauptung.
(ii) Wir gehen wie folgt vor:
 
\( x\in A\cup(B\cap C) \)
\( \qquad\Longrightarrow \) \( x\in A\,\vee\,x\in B\cap C \)
\( \qquad\Longrightarrow \) \( x\in A\vee(x\in B\,\wedge\,x\in C) \)
\( \qquad\Longrightarrow \) \( (x\in A\,\vee\,x\in B)\wedge(x\in A\,\vee\,x\in C) \)
\( \qquad\Longrightarrow \) \( (x\in A\cup B)\wedge(x\in A\cup C) \)
\( \qquad\Longrightarrow \) \( x\in(A\cup B)\cap(A\cup C) \)
  Das zeigt die Inklusion \( A\cup(B\cap C)\subseteq(A\cup B)\cap(A\cup C). \) Weiter ist
 
\( x\in(A\cup B)\cap(A\cup C) \)
\( \qquad\Longrightarrow \) \( (x\in A\cup B)\wedge(x\in A\cup C) \)
\( \qquad\Longrightarrow \) \( (x\in A\,\vee\,x\in B)\wedge(x\in A\,\vee\,x\in C) \)
\( \qquad\Longrightarrow \) \( x\in A\vee(x\in B\,\wedge\,x\in C) \)
\( \qquad\Longrightarrow \) \( x\in A\vee(x\in B\cap C) \)
\( \qquad\Longrightarrow \) \( x\in A\cup(B\cap C) \)
  Das zeigt die Inklusion \( (A\cup B)\cap(A\cup C)\subseteq A\cup(B\cap C) \) und damit die Behauptung.

Damit sind die Distributivgesetze der Mengenlehre bewiesen.\( \qquad\Box \)

 

 

Aufgabe 1.2.5: (de Morgansche Regeln der Mengenlehre)

Es seien \( A \) und \( B \) zwei beliebige Teilmengen einer nichtleeren Obermenge \( X. \) Beweisen Sie:

(i) \( X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B) \)
(ii) \( X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B) \)

 

Lösung

 

(i) Wir gehen wie folgt vor:
 
\( x\in X\setminus(A\cup B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,x\not\in A\cup B \)
\( \qquad\Longrightarrow \) \( x\in X\wedge\neg\,x\in A\cup B \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,\neg\,(x\in A\,\vee\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(\neg\,x\in A\,\wedge\,\neg\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(x\not\in A\,\wedge\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( (x\in X\,\wedge\,x\not\in A)\wedge(x\in X\,\wedge\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( (x\in X\setminus A)\wedge(x\in X\setminus B) \)
\( \qquad\Longrightarrow \) \( x\in(X\setminus A)\cap(X\setminus B) \)
  Das zeigt die Inklusion \( X\setminus(A\cup B)\subseteq(X\setminus A)\cap(X\setminus B). \) Weiter ist
 
\( x\in(X\setminus A)\cap(X\setminus B) \)
\( \qquad\Longrightarrow \) \( x\in X\setminus A\,\wedge\,x\in X\setminus B \)
\( \qquad\Longrightarrow \) \( (x\in X\,\wedge\,x\not\in A)\wedge(x\in X\,\wedge\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(X\not\in A\,\wedge\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(\neg\,x\in A\,\wedge\,\neg\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,\neg\,(x\in A\,\vee\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,\neg\,(x\in A\cup B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,x\not\in A\cup B \)
\( \qquad\Longrightarrow \) \( x\in X\setminus(A\cup B) \)
  Das zeigt die Inklusion \( (X\setminus A)\cap(X\setminus B)\subseteq X\setminus(A\cup B) \) und damit die Behauptung.
(ii) Wir gehen wie folgt vor:
 
\( x\in X\setminus(A\cap B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,x\not\in A\cap B \)
\( \qquad\Longrightarrow \) \( x\in X\wedge\neg\,x\in A\cap B \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,\neg\,(x\in A\,\wedge\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(\neg\,x\in A\,\vee\,\neg\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(x\not\in A\,\vee\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( (x\in X\,\wedge\,x\not\in A)\,\vee\,(x\in X\,\wedge\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\setminus A\,\vee\,x\in X\setminus B \)
\( \qquad\Longrightarrow \) \( x\in(X\setminus A)\cup(X\setminus B) \)
  Das zeigt die Inklusion \( X\setminus(A\cap B)\subseteq(X\setminus A)\cup(X\setminus B). \) Weiter ist
 
\( x\in(X\setminus A)\cup(X\setminus B) \)
\( \qquad\Longrightarrow \) \( x\in X\setminus A\,\vee\,x\in X\setminus B \)
\( \qquad\Longrightarrow \) \( (x\in X\,\wedge\,x\not\in A)\vee(x\in X\,\wedge\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(X\not\in A\,\vee\,x\not\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,(\neg\,x\in A\,\vee\,\neg\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,\neg\,(x\in A\,\wedge\,x\in B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,\neg\,(x\in A\cap B) \)
\( \qquad\Longrightarrow \) \( x\in X\,\wedge\,x\not\in A\cap B \)
\( \qquad\Longrightarrow \) \( x\in X\setminus(A\cap B) \)
  Das zeigt die Inklusion \( (X\setminus A)\cup(X\setminus B)\subseteq X\setminus(A\cap B) \) und damit die Behauptung.

Damit sind die de Morganschen Regeln bewiesen.\( \qquad\Box \)

 

 

Aufgabe 1.2.6: (Enthalten oder sogar gleich?)

Es seien \( A, \) \( B, \) \( C, \) \( D \) beliebige Mengen. Welche der folgenden Behauptungen ist richtig, welche falsch? Beweisen Sie bzw. begründen Sie durch ein Gegenbeispiel.

(i) \( (A\cap C)\cup(B\cap D)\subseteq(A\cup B)\cap(C\cup D) \)
(ii) \( (A\cap C)\cup(B\cap D)=(A\cup B)\cap(C\cup D) \)

 

Lösung

 

(i) Die behauptete Inklusion gilt. Denn wähle ein \( x\in(A\cap C)\cup(B\cap D) \) beliebig, so ist

\[ (x\in A\wedge x\in C)\quad\mbox{oder}\quad(x\in B\wedge x\in D). \]

  Wir betrachten daher zwei Fälle:
  \( \circ\qquad \) \( x\in A\wedge x\in C \) bzw. ausführlicher

\[ \begin{array}{ccc} x\in A & \quad\Longrightarrow & \quad x\in A\cup B \\ x\in C & \quad\Longrightarrow & \quad x\in C\cup D \end{array} \]

  \( \circ\qquad \) \( x\in B\wedge x\in D \) bzw. ausführlicher

\[ \begin{array}{ccc} x\in B & \quad\Longrightarrow & \quad x\in A\cup B \\ x\in D & \quad\Longrightarrow & \quad x\in C\cup D \end{array} \]

  In beiden Fällen folgt \( x\in(A\cup B)\cap(C\cup D) \) für beliebiges \( x \) und daher

\[ (A\cap C)\cup(B\cap D)\subseteq(A\cup B)\cap(C\cup D). \]

(ii) Gleichheit gilt nicht: Wir betrachten als Gegenbeispiel die Mengen

\[ A=\{a\},\quad B=\{b,\omega\},\quad C=\{a,\omega\},\quad D=\{b\} \]

  und ermitteln

\[ (A\cap C)\cup(B\cap D) =\{a\}\cup\{b\} =\{a,b\} \]

  sowie

\[ (A\cup B)\cap(C\cup D) =\{a,b,\omega\}\cap\{a,\omega,b\} =\{a,b,\omega\}\,. \]

  Es gilt also \( (A\cap C)\cup(B\cap D)\not=(A\cup B)\cap(C\cup D). \)

Damit ist alles gezeigt.\( \qquad\Box \)

 

 

Aufgaben - Abbildungen zwischen Mengen

 

Aufgabe 1.2.7: (Injektive und surjektive Abbildungen)

Finden Sie jeweils Beispiele von Mengen \( A \) und \( B \) sowie eine Abbildung \( f\colon A\to B, \) so dass gilt:

(i) \( f \) ist weder injektiv noch surjektiv
(ii) \( f \) ist injektiv, aber nicht surjektiv
(iii) \( f \) ist surjektiv, aber nicht injektiv
(iv) \( f \) ist sowohl injektiv als auch surjektiv

Begründen Sie.

 

Lösung

 

(i) \( f\colon[-1,1]\to[-1,1] \) vermöge \( f(x)=x^2 \) ist weder injektiv noch surjektiv
(ii) \( f\colon[-1,1]\to[-2,2] \) vermöge \( f(x)=x \) ist injektiv, aber nicht surjektiv
(iii) \( f\colon[-1,1]\to[0,1] \) vermöge \( f(x)=x^2 \) ist surjektiv, aber nicht injektiv
(iv) \( f\colon[0,1]\to[0,1] \) vermöge \( f(x)=x^2 \) ist injektiv und surjektiv

 

 

Aufgabe 1.2.8: (Abbildungen von Teilmengen)

Es sei \( f\colon A\to B \) eine Abbildung zwischen den Mengen \( A \) und \( B. \) Weiter seien \( M,N\subseteq A \) zwei Teilmengen von \( A \) mit der Eigenschaft \( M\subseteq N. \) Beweisen Sie \[ f(M)\subseteq f(N). \]

 

Lösung

 

Wähle ein \( y\in f(M). \) Dann existiert ein \( x\in M \) mit \( y=f(x). \) Wegen \( M\subseteq N \) gelten auch \( x\in N \) und damit \( y\in f(N). \) Das bedeutet aber \( f(M)\subseteq f(N), \) und die Behauptung ist gezeigt.\( \qquad\Box \)

 

 

Aufgabe 1.2.9: (Abbildung und Umkehrabbildung)

Es seien \( A \) und \( B \) zwei nichtleere Mengen und \( f\colon A\to B \) sowie \( g\colon B\to A \) zwei Abbildungen mit der Eigenschaft \[ g\circ f(a)=a\quad\mbox{für alle}\ a\in A. \] Beweisen Sie, dass \( f \) injektiv und \( g \) surjektiv ist.

 

Lösung

 

\( \circ \) Wir zeigen, dass \( f \) injektiv ist. Denn angenommen \( f(x)=f(y) \) mit \( x,y\in A, \) dann ist
 
\( g(f(x))=g(f(y))\quad\mbox{bzw. nach Voraussetzung}\quad x=y. \)
  Also ist \( f \) injektiv.
\( \circ \) Wir zeigen, dass \( g \) surjektiv ist. Wähle dazu \( x\in A \) beliebig, dann ist
 
\( x=g(f(x))=g(y)\quad\mbox{mit}\quad y:=f(x)\in B. \)
  Also ist \( g \) surjektiv.

Damit sind alle Behauptungen gezeigt.\( \qquad\Box \)

 

 

Aufgaben - Mächtigkeit von Mengen

 

Aufgabe 1.2.10: (Potenzmengen endlicher Mengen)

Bestimmen Sie die Potenzmengen der folgenden Mengen \( M: \)

(i) \( M=\emptyset \)
(ii) \( M=\{a\} \)
(iii) \( M=\{a,b\} \)
(iv) \( M=\{a,b,c\} \)
(v) \( M={\mathcal P}(\emptyset) \)
(vi) \( M={\mathcal P}(\{a\}) \)

 

Lösung

 

(i) \( {\mathcal P}(M)=\{\emptyset\} \)
(ii) \( {\mathcal P}(M)=\{\emptyset,\{a\}\} \)
(iii) \( {\mathcal P}(M)=\{\emptyset,\{a\},\{b\},\{a,b\}\} \)
(iv) \( {\mathcal P}(M)=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\} \)
(v) \( {\mathcal P}(M)={\mathcal P}(\{\emptyset\})=\{\emptyset,\{\emptyset\}\} \)
(vi) \( {\mathcal P}(M)={\mathcal P}(\{\emptyset,\{a\}\})=\{\emptyset,\{\emptyset\},\{\{a\}\},\{\emptyset,\{a\}\}\} \)

 

 

Aufgabe 1.2.11: (Potenzmenge auf Vereinigung und Durchschnitt)

Es seien \( A \) und \( B \) zwei beliebige Mengen.

(i) Zeigen Sie durch Angabe eines Gegenbeispiels, dass nicht gilt
 
\( {\mathcal P}(A\cup B)={\mathcal P}(A)\cup{\mathcal P}(B). \)
(ii) Beweisen Sie die Richtigkeit der Aussage
 
\( {\mathcal P}(A\cap B)={\mathcal P}(A)\cap{\mathcal P}(B). \)

 

Lösung

 

(i) Wähle \( A=\{1\} \) und \( B=\{2\}. \) Dann gilt

\[ \{1,2\}\in{\mathcal P}(A\cup B), \quad\mbox{aber}\quad \{1,2\}\not\in{\mathcal P}(A)\ \mbox{und}\ \{1,2\}\not\in{\mathcal P}(B) \]

  und daher \( \{1,2\}\not\in{\mathcal P}(A)\cup{\mathcal P}(B). \) Das zeigt die erste Behauptung.
(ii) Wähle ein \( M\in{\mathcal P}(A\cap B) \) beliebig. Dann ist

\[ M\subseteq A\cap B \quad\Longrightarrow\quad M\subseteq A\,\wedge\,M\subseteq B \quad\Longrightarrow\quad M\in{\mathcal P}(A)\,\wedge\,M\in{\mathcal P}(B) \]

  bzw. \( M\in{\mathcal P}(A)\cap{\mathcal P}(B), \) weshalb gilt

\[ {\mathcal P}(A\cap B)\subseteq{\mathcal P}(A)\cap{\mathcal P}(B). \]

  Sei nun umgekehrt ein \( M\in{\mathcal P}(A)\cap{\mathcal P}(B) \) beliebig gewählt. Dann ist

\[ M\in{\mathcal P}(A)\,\wedge\,M\in{\mathcal P}(B) \quad\Longrightarrow\quad M\subseteq A\,\wedge\,M\subseteq B \quad\Longrightarrow\quad M\subseteq A\cap B \]

  bzw. \( M\in{\mathcal P}(A\cap B), \) weshalb gilt

\[ {\mathcal P}(A)\cap{\mathcal P}(B)\subseteq{\mathcal P}(A\cap B). \]

  Insgesamt folgt die behauptete Mengengleichheit.

Damit ist alles gezeigt.\( \qquad\Box \)

 

 


 

 

1.2.7 Wiederholungsfragen

 

1. Wie lassen sich Mengen charakterisieren?
2. Wie sind die Mengenrelationen \( =, \) \( \subseteq, \) \( \subset, \) \( \supseteq \) und \( \supset \) erklärt?
3. Wie sind die Mengenoperationen \( \cup, \) \( \cap, \) \( \setminus \) und \( \times \) definiert?
4. Was versteht man unter dem Komplement einer Menge?
5. Wie lauten die Distributivgesetze der Mengenlehre?
6. Wie lauten die de Morganschen Regeln der Mengenlehre?
7. Wann heißt eine Abbildung \( f\colon A\to B \) surjektiv?
8. Wann heißt eine Abbildung \( f\colon A\to B \) injektiv?
9. Wann heißt eine Abbildung \( f\colon A\to B \) bijektiv?
10. Wann heißt eine Menge endlich?
11. Was versteht man unter der Mächtigkeit einer endlichen Menge?
12. Wann heißen zwei Mengen gleichmächtig?
13. Was versteht man unter der Potenzmenge einer Menge?
14. Wie viele Elemente besitzt die Potenzmenge einer endlichen Menge mit \( n \) Elementen?

 


 

1.3 Anhang zur mathematischen Logik

 

1.3.2 Aufgaben

 

Aufgaben zu Aussagen und Aussageformen

 

Aufgabe 1.3.1: Eigene Beispiele für Aussagen

Finden Sie wenigstens

(i) fünf eigene Beispiele für Aussagen,
(ii) fünf eigene Beispiele von Sätzen, die keine Aussagen sind.

 

Lösung

 

(i) Fünf Beispiele von Aussagen:
  \( \circ\qquad \)Lesen bildet.
  \( \circ\qquad \)Schwimmen ist gut für die Muskulatur.
  \( \circ\qquad \)Mathematische Logik ist wichtig.
  \( \circ\qquad \)Schokolade ist ungesund.
  \( \circ\qquad \)Üben ist wichtig für das Verstehen.
(ii) Fünf Beispiele von Sätzen, die keine Aussagen sind:
  \( \circ\qquad \)Gehen wir zusammen ins Kino?.
  \( \circ\qquad \)Das darf doch nicht wahr sein!
  \( \circ\qquad \)Wann, wenn nicht jetzt?
  \( \circ\qquad \)Mögen Sie Robert Schumanns Klavierkonzert?
  \( \circ\qquad \)Lernen, lernen und nochmals lernent.

 

 

Aufgaben zu Logische Paradoxien

 

Aufgabe 1.3.2: Zoglauers Satz mit drei Fehlern

Vorgelegt sei die Aussage: $$\mbox{Dieser Sats enthält drei Feler.}$$ Welche drei Fehler sind gemeint?

 

Lösung

 

Der Satz enthält zwei syntaktische Fehler in Form von Rechtschreibfehlern, und auf metasprachlicher Ebene findet sich der dritte Fehler, nämlich die Behauptung, es gäbe drei Fehler, was der dritte gesuchte Fehler ist.

 

 

Aufgaben zu Verknüpfungen von Aussagen

 

Aufgabe 1.3.3: Idempotenzgesetze der Aussagenlogik

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( a\equiv a\vee a \)
(ii) \( a\equiv a\wedge a \)

 

Lösung

 

...

 

 

Aufgabe 1.3.4: Kommutativität der Disjunktion und Konjunktion

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( a\vee b\equiv b\vee a \)
(ii) \( a\wedge b\equiv b\wedge a \)

 

Lösung

 

...

 

 

Aufgabe 1.3.5: Assoziativgesetze der Aussagenlogik

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( a\vee(b\vee c)\equiv(a\vee b)\vee c \)
(ii) \( a\wedge(b\wedge c)\equiv(a\wedge b)\wedge c \)

 

Lösung

 

...

 

 

Aufgabe 1.3.6: Verschmelzung von Disjunktion und Konjunktion

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

(i) \( a\equiv a(a\vee b) \)
(ii) \( a\equiv a(a\wedge b) \)

 

Lösung

 

...

 

 


 

1.4 Anhang zur Mengenlehre