Hausaufgabenblatt 1
Aufgabe HA 1
Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels einer Wahrheitstabelle:
| (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) \) |
| (i) | Satz zum modus ponens - setze zur Abkürzung \( \varphi:=(a\to b)\wedge a\to b \) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Also ist \( (a\to b)\wedge a\to b \) eine Tautologie. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (ii) | Satz zum modus tollens - setze zur Abkürzung \( \varphi:=(a\to b)\wedge\neg b\to\neg a \) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Also ist \( (a\to b)\wedge\neg b\to\neg a \) eine Tautologie. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (iii) | Satz zum modus barbara - setze zur Abkürzung \( \varphi:=(a\to b)\wedge(b\to c)\to(a\to c) \) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Also ist \( (a\to b)\wedge(b\to c)\to(a\to c) \) eine Tautologie. |
Damit ist alles gezeigt.\( \qquad\Box \)
Aufgabe HA 2
Gegeben seien die 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. \]
Wir ermitteln \[ \begin{array}{l} \Omega\setminus A=\{0,4,5,6\}\,,\quad \Omega\setminus B=\{0,1,5,6\}\,, \\[0.6ex] A\cup B=\{1,2,3,4\}\,,\quad A\cap B=\{2,3\}\,, \\[0.6ex] A\setminus B=\{1\}\,,\quad B\setminus A=\{4\}\,. \end{array} \] Das war gesucht.\( \qquad\Box \)
Aufgabe HA 3
Es seien \( A \) und \( B \) Teilmengen einer Menge \( X. \) Beweisen Sie \[ X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B). \]
Wir gehen wie folgt vor: \[ \begin{array}{l} 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) \end{array} \] Das zeigt die Inklusion \( X\setminus(A\cap B)\subseteq(X\setminus A)\cup(X\setminus B). \) Weiter ist \[ \begin{array}{l} 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) \end{array} \] Das zeigt die Inklusion \( (X\setminus A)\cup(X\setminus B)\subseteq X\setminus(A\cap B) \) und damit die Behauptung.\( \qquad\Box \)
Aufgabe HA 4
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) \) |
| (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 \)