1. Logik und Mengenlehre
1.1.1 Aussagen und Aussageformen
Die Mathematik beginnt mit der
Vereinbarung: Eine Aussage ist ein umgangssprachlicher Satz, der entweder wahr (1) oder falsch (0) ist.
Diese Vereinbarung beinhaltet die Zweiwertigkeit der Aussagenlogik:
⟶ Außer wahr und falsch gibt es keine weitere Möglichkeit.
Beispiele:
Die erste Aussage ist wahr, die zweite falsch. Den Wahrheitsgehalt der dritten Aussage wissen wir nicht, sind aber überzeugt, dass sie entweder wahr oder falsch ist.
Ein Ausdruck der Form
heißt eine Aussageform oder Formel. Nach Ersetzen von \( x \) durch eine Zahl wird sie zu einer wahren oder falschen Aussage.
1.1.2 Verknüpfungen von Aussagen
Mathematische Aussagen bezeichnen wir mit \( a,b,c,\ldots \) Wir ordnen ihnen einen der beiden Wahrheitswerte zu \[ 0\quad\mbox{(falsch)}\qquad\mbox{oder}\qquad 1\quad\mbox{(wahr)}. \]
Folgende Junktoren verknüpfen sie zu neuen Aussagen:
| \( \neg \) | Negation | nicht | |
| \( \vee \) | Disjunktion | oder | |
| \( \wedge \) | Konjunktion | sprich: | und |
| \( \to \) | Implikation | folgt | |
| \( \leftrightarrow \) | Äquivalenz | genau dann, wenn |
Die Wirkungen definieren wir vermittels 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 \) |
Die Äquivalenz \( \leftrightarrow \) können wir offenbar auch durch \( \to \) ausdrücken: \[ a\leftrightarrow b\quad\mbox{ist gleichbedeutend mit}\quad(a\to b)\wedge(b\to a) \] in dem Sinne, dass die Wahrheitstabellen beider zusammengesetzter Aussagen übereinstimmen. Aussagen mit denselben Wahrheitstabellen heißen semantisch äquivalent, in Zeichen \( a\equiv b. \) Es gilt also beispielsweise \[ (a\leftrightarrow b)\equiv(a\to b)\wedge(b\to a). \]
Satz: Es gelten die Distributivgesetze der Aussagenlogik \[ \begin{array}{l} a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c), \\ a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c) \end{array} \] sowie die de Morganschen Regeln der Aussagenlogik \[ \begin{array}{l} \neg(a\wedge b)\equiv\neg a\vee\neg b, \\ \neg(a\vee b)\equiv\neg a\wedge\neg b. \end{array} \]
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.
Ein Beispiel einer Tautologie ist die Aussage \( a\vee\neg a: \)
| \( a \) | \( \neg a \) | \( a\vee\neg a \) |
| \( 0 \) | \( 1 \) | \( 1 \) |
| \( 1 \) | \( 0 \) | \( 1 \) |
Tautologien dienen uns als grundlegende mathematische Beweisprinzipien.
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) \) |
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., in Zeichen |
|
|
|
| wobei die Reihenfolge der Elemente nicht wichtig ist, und Elemente werden nicht mehrfach angegeben; | |
| \( \circ \) | durch Angabe einer definierenden Eigenschaft, z.B. |
|
|
|
| d.h. \( M \) besteht aus allen Elementen \( x\in X \) mit der Eigenschaft \( p(x). \) |
Beispiele:
| (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 \) |
| (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\}. \) |
Es existiert genau eine leere Menge \( \emptyset, \) welche kein Element enthält. Sie ist 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.
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. \]
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: Sei \( A\subseteq X \) Teilmenge einer Obermenge \( X. \) Dann erklären wir ihr Komplement bez. \( X \) gemäß \[ A^c:=\{x\,:\,x\in X\setminus A\} \]
Vereinigung, Durchschnitt, Differenz, kartesisches Produkt und Komplement von Mengen sind wieder 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 \) (\( N\supseteq M \) bedeutet \( M\subseteq N \)) 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 - Aussagen und Aussageformen
Aufgabe 1.1.1: (Beispiele und Gegenbeispiele von 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! |
| (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 nicht um eine Aussage. |
| (vi) | Es handelt sich nicht um eine Aussage! |
Aufgabe 1.1.2: (Eigene Beispiele von Aussagen)
Formulieren Sie drei eigene Beispiele von Aussagen.
...
Aufgabe 1.1.3: (Eigene Beispiele von Aussageformen)
Formulieren Sie drei eigene Beispiele von Aussageformen.
...
Aufgaben - Verknüpfungen von Aussagen
Aufgabe 1.1.4: (Darstellung der Äquivalenz)
Beweisen Sie vermittels einer Wahrheitstabelle \[ (a\leftrightarrow b)\equiv(a\to b)\wedge(b\to a). \]
...
Aufgabe 1.1.5: (Distributivgesetze der Aussagenlogik)
Beweisen Sie 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) \) |
...
Aufgabe 1.1.6: (de Morgansche Regeln der Aussagenlogik)
Beweisen Sie vermittels Wahrheitstabellen:
| (i) | \( \neg(a\wedge b)\equiv\neg a\vee\neg b \) |
| (ii) | \( \neg(a\vee b)\equiv\neg a\wedge\neg b \) |
...
Aufgaben - Aussagenlogische Beweisprinzipien
Aufgabe 1.1.7: (Beispiele aussagenlogischer Beweisprinzipien)
Beweisen Sie vermittels Wahrheitstabellen, dass es sich bei folgenden Aussagen um Tautologien handelt.
| (i) | \( a\vee\neg a \) |
| (ii) | \( \neg(a\wedge\neg a) \) |
| (iii) | \( \neg(\neg a)\to a \) |
| (iv) | \( (a\to b)\to(\neg b\to\neg a) \) |
| (v) | \( (a\to b)\wedge a\to b \) |
| (vi) | \( (a\to b)\wedge\neg b\to\neg a \) |
| (vii) | \( (a\to b)\wedge(b\to c)\to(a\to c) \) |
Erläutern Sie diese Aussagen mit eigenen Worten.
...
Aufgaben - Charakterisierung von Mengen
Aufgabe 1.2.1: (Elemente 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}\} \) |
...
Aufgaben - Mengenrelationen und Mengenoperationen
Aufgabe 1.2.1: (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. \]
...
Aufgaben - Rechnen mit Mengen
Aufgabe 1.2.3: (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) \) |
...
Aufgabe 1.2.4: (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) \) |
...