Präsenzblatt 1
Aufgabe PA 1
Beweisen Sie die folgenden de Morganschen Regeln der Aussagenlogik vermittels einer Wahrheitstabelle.
| (i) | \( \neg(a\wedge b)\equiv\neg a\vee\neg b \) |
| (ii) | \( \neg(a\vee b)\equiv\neg a\wedge\neg b \) |
| (i) | Betrachte die folgende Wahrheitstabelle: | |||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
| Also gilt \( \neg(a\wedge b)\equiv\neg a\vee\neg b. \) | ||||||||||||||||||||||||||||||||||||
| (ii) | Betrachte die folgende Wahrheitstabelle: | |||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
| Also gilt \( \neg(a\vee b)\equiv\neg a\wedge\neg b. \) |
Damit ist alles gezeigt.\( \qquad\Box \)
Aufgabe PA 2
Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels einer Wahrheitstabelle:
| (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) \) |
| (i) | Betrachte die folgende Wahrheitstabelle: | |||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
| Also stellt \( a\vee\neg a \) eine Tautologie dar. | ||||||||||||||||||||||||||||||||||||
| (ii) | Betrachte die folgende Wahrheitstabelle: | |||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
| Also stellt \( \neg(a\wedge\neg a) \) eine Tautologie dar. | ||||||||||||||||||||||||||||||||||||
| (iii) | Betrachte die folgende Wahrheitstabelle: | |||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
| 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: | |||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
| Also stellt \( (a\to b)\to(\neg b\to\neg a) \) eine Tautologie dar. |
Damit ist alles gezeigt.\( \qquad\Box \)
Aufgabe PA 3
Es seien \( A \) und \( B \) Teilmengen einer Menge \( X. \) Beweisen Sie \[ X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B). \]
Wir gehen wie folgt vor: \[ \begin{array}{l} x\in X\setminus(A\cup B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,x\not\in A\cup B \\ \qquad\Longrightarrow\quad x\in X\wedge\neg\,x\in A\cup B \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,\neg\,(x\in A\,\vee\,x\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,(\neg\,x\in A\,\wedge\,\neg\,x\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,(x\not\in A\,\wedge\,x\not\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,x\not\in A)\wedge(x\in X\,\wedge\,x\not\in B) \\ \qquad\Longrightarrow\quad (x\in X\setminus A)\wedge(x\in X\setminus B) \\ \qquad\Longrightarrow\quad x\in(X\setminus A)\cap(X\setminus B) \end{array} \] Das zeigt die Inklusion \( X\setminus(A\cup B)\subseteq(X\setminus A)\cap(X\setminus B). \) Weiter ist \[ \begin{array}{l} x\in(X\setminus A)\cap(X\setminus B) \\ \qquad\Longrightarrow\quad x\in X\setminus A\,\wedge\,x\in X\setminus B \\ \qquad\Longrightarrow\quad (x\in X\,\wedge\,x\not\in A)\wedge(x\in X\,\wedge\,x\not\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,(X\not\in A\,\wedge\,x\not\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,(\neg\,x\in A\,\wedge\,\neg\,x\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,\neg\,(x\in A\,\vee\,x\in B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,\neg\,(x\in A\cup B) \\ \qquad\Longrightarrow\quad x\in X\,\wedge\,x\not\in A\cup B \\ \qquad\Longrightarrow\quad x\in X\setminus(A\cup B) \end{array} \] Das zeigt die Inklusion \( (X\setminus A)\cap(X\setminus B)\subseteq X\setminus(A\cup B) \) und damit die Behauptung.\( \qquad\Box \)
Aufgabe PA 4
Beweisen Sie, dass die folgenden Menge \[ A:=\{1,2,3\}\,,\quad B:=\{a,b,c\} \] die gleiche Mächtigkeit besitzen. Finden Sie dazu eine explizite Bijektion zwischen \( A \) und \( B. \) Wie können Sie die Bijektivität zeigen?
Es sind \( A \) und \( B \) gleichmächtig. Wähle nämlich \( f\colon A\to B \) vermöge \[ f(1):=a,\quad f(2):=b,\quad f(3):=c. \] Es ist \( f \) surjektiv, denn für jedes \( y\in B \) existiert ein \( x\in A \) mit \( f(x)=y. \) Es ist \( f \) auch injektiv, denn jedes \( b\in B \) besitzt nicht nur ein Urbild, sondern genau ein Urbild:
Also ist \( f \) surjektiv und injektiv und damit auch bijektiv, und \( A \) und \( B \) sind gleichmächtig. Das war zu zeigen.\( \qquad\Box \)