Logik und Mengenlehre

Zurück zur Hauptseite

1. Logik und Mengenlehre

1.1 Mathematische Logik

1.2 Mengenlehre

1.3 Aufgaben

1.1 Mathematische Logik

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 Zahl $3$ ist eine Primzahl.
Die Zahl $4$ ist eine Primzahl.
Es gibt unendlich viele Primzahlzwillinge.

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

$x+7=18$

heißt eine Aussageform oder Formel. Nach Ersetzen von $x$ durch eine Zahl wird sie zu einer wahren oder falschen Aussage.

Aufgaben zu diesem Abschnitt

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}$

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.

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)$

Aufgaben zu diesem Abschnitt

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., in Zeichen
	$M=\{m_1,m_2,m_3,\ldots\},$
	wobei die Reihenfolge der Elemente nicht wichtig ist, und Elemente werden nicht mehrfach angegeben;
$\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:

(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.

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.$

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.

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$ (

$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 zu diesem Abschnitt

1.3 Aufgaben

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!

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 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.

Lösung

...

Aufgabe 1.1.3: (Eigene Beispiele von Aussageformen)

Formulieren Sie drei eigene Beispiele von Aussageformen.

Lösung

...

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).$

Lösung

...

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)$

Lösung

...

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$

Lösung

...

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.

Lösung

...

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}\}$

Lösung

...

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.$

Lösung

...

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)$

Lösung

...

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)$

Lösung

...

Zurück zur Hauptseite