Aufgaben zur Logik – Serlo „Mathe für Nicht-Freaks“

Die Liebe formalisieren

Im Folgenden bedeutet $L(x,y)$, dass $x$ die Person $y$ liebt:

$L(x,y):\Leftrightarrow x{\text{ liebt }}y$

Außerdem sollen sich für diese Aufgabe alle Quantoren auf den Individuenbereich der Menschen beziehen. Dies bedeutet, dass zum Beispiel eine Aussage der Form $\forall x:\,A(x)$ bedeutet „Für alle Menschen $x$ gilt $A(x)$“.

Teilaufgabe 1

Aufgabe (Die Liebe formalisieren)

Übersetze folgende Aussagen in die natürliche Sprache:

1. $\forall x:\,\forall y:\,L(x,y)$
2. $\exists x:\,\forall y:\,L(x,y)$
3. $\exists !x:\,\forall y:\,L(y,x)$
4. $\forall x:\,\forall y:\,L(x,y)\Rightarrow L(y,x)$
5. $\forall x:\,\left(L(x,x)\Rightarrow \exists y:\,y\neq x\land L(y,x)\right)$

Lösung (Die Liebe formalisieren)

Lösung zur Übersetzung in die natürliche Sprache:

1. Jeder liebt jeden.
2. Es gibt mindestens einen Menschen, der jeden Menschen liebt.
3. Es gibt genau einen Menschen, der von jedem Menschen geliebt wird.
4. Liebst du jemanden, dann wirst du auch von ihm geliebt.
5. Wer sich selbst liebt, der wird auch von einer anderen Person geliebt.

Teilaufgabe 2

Aufgabe

Übersetze folgende Aussagen in die formale Aussagenlogik:

1. Es gibt zwei verschiedene Menschen, die sich gegenseitig lieben.
2. Es gibt keine Liebe. (Im Sinne von: Niemand liebt niemanden – nicht einmal sich selbst.)
3. Jeder liebt nur sich selbst. (Im Sinne von: Jeder liebt sich selbst und nur sich selbst.)
4. Für jeden Menschen gibt es einen anderen Menschen, der ihn liebt.
5. Liebt sich eine Person selbst, dann wird sie von keiner anderen Person geliebt.

Lösung

Lösung zur Übersetzung in die formale Aussagenlogik:

1. $\exists x:\,\exists y:\,\left(x\neq y\land L(x,y)\land L(y,x)\right)$
2. $\forall x:\,\forall y:\,\neg L(x,y)$
3. $\forall x:\,\left(L(x,x)\land \forall y:\,\left(y\neq x\Rightarrow \neg L(x,y)\right)\right)$
4. $\forall x:\,\exists y:\,\left(x\neq y\land L(y,x)\right)$
5. $\forall x:\,\left(L(x,x)\Rightarrow \forall y:\,y\neq x\Rightarrow \neg L(y,x)\right)$

Bestimmung des Wahrheitswerts quantifizierter Aussagen

Aufgabe

Gegeben sei die Aussageform:

$A(x,y):x{\text{ ist eine Stadt in }}y$

und die Mengen:

1. $X_{1}=\{{\text{Bern}},\,{\text{Hamburg}},\,{\text{Leipzig}}\}$
2. $X_{2}=\{{\text{Aachen}},\,{\text{Köln}},\,{\text{Leipzig}}\}$
3. $X_{3}=\{{\text{Brüssel}},\,{\text{Amsterdam}},\,{\text{Bern}}\}$
4. $Y_{1}=\{{\text{Deutschland}},\,{\text{Nordrhein-Westfalen}}\}$
5. $Y_{2}=\{{\text{Schweiz}},\,{\text{Holland}},\,{\text{Belgien}}\}$
6. $Y_{3}=\{{\text{Deutschland}},\,{\text{Schweiz}},\,{\text{Nordrhein-Westfalen}}\}$

Welche der folgenden Aussagen sind wahr und welche sind falsch?

1. $\forall x\in X_{1}\,\exists y\in Y_{1}:A(x,y)$
2. $\forall x\in X_{3}\,\exists y\in Y_{3}:A(x,y)$
3. $\forall x\in X_{3}\,\exists y\in Y_{2}:A(x,y)$
4. $\forall x\in X_{2}\,\exists y\in Y_{1}:A(x,y)$
5. $\exists y\in Y_{1}\,\forall x\in X_{1}:A(x,y)$
6. $\exists y\in Y_{3}\,\forall x\in X_{2}:A(x,y)$
7. $\exists y\in Y_{2}\,\forall x\in X_{3}:A(x,y)$
8. $\forall x\in X_{2}\,\forall y\in Y_{1}:A(x,y)$
9. $\forall y\in Y_{1}\,\exists x\in X_{1}:A(x,y)$
10. $\exists x\in X_{3}\,\forall y\in Y_{2}:A(x,y)$
11. $\exists x\in X_{2}\,\forall y\in Y_{1}:A(x,y)$
12. $\exists x\in X_{1}\,\forall y\in Y_{1}:A(x,y)$
13. $\forall y\in Y_{1}\,\exists x\in X_{2}:A(x,y)$
14. $\exists x\in X_{3}\,\forall y\in Y_{3}:A(x,y)$
15. $\exists x\in X_{2}\,\forall y\in Y_{1}:A(x,y)$
16. $\forall y\in Y_{2}\,\exists x\in X_{3}:A(x,y)$
17. $\exists x\in X_{2}\,\exists y\in Y_{3}:A(x,y)$

Lösung

Nummer	Aussage	Bedeutung	Wahrheitswert
1	$\forall x\in X_{1}\,\exists y\in Y_{1}:A(x,y)$	Zu jedem $x\in X_{1}$ existiert ein $y\in Y_{1}$ mit $A(x,y)$.	falsch
2	$\forall x\in X_{3}\,\exists y\in Y_{3}:A(x,y)$	Zu jedem $x\in X_{3}$ existiert ein $y\in Y_{3}$ mit $A(x,y)$.	falsch
3	$\forall x\in X_{3}\,\exists y\in Y_{2}:A(x,y)$	Zu jedem $x\in X_{3}$ existiert ein $y\in Y_{2}$ mit $A(x,y)$.	wahr
4	$\forall x\in X_{2}\,\exists y\in Y_{1}:A(x,y)$	Zu jedem $x\in X_{2}$ existiert ein $y\in Y_{1}$ mit $A(x,y)$.	wahr
5	$\exists y\in Y_{1}\,\forall x\in X_{1}:A(x,y)$	Es gibt ein $y\in Y_{1}$, so dass für alle $x\in X_{1}$ die Aussageform $A(x,y)$ erfüllt ist.	falsch
6	$\exists y\in Y_{3}\,\forall x\in X_{2}:A(x,y)$	Es gibt ein $y\in Y_{1}$, so dass für alle $x\in X_{3}$ die Aussageform $A(x,y)$ erfüllt ist.	wahr
7	$\exists y\in Y_{2}\,\forall x\in X_{3}:A(x,y)$	Es gibt ein $y\in Y_{2}$, so dass für alle $x\in X_{3}$ die Aussageform $A(x,y)$ erfüllt ist.	falsch
8	$\forall x\in X_{2}\,\forall y\in Y_{1}:A(x,y)$	Für alle $x\in X_{2}$ und für alle $y\in Y_{2}$ gilt $A(x,y)$.	falsch
9	$\forall y\in Y_{1}\,\exists x\in X_{1}:A(x,y)$	Zu jedem $y\in Y_{1}$ gibt es ein $x\in X_{1}$ mit $A(x,y)$.	falsch
10	$\exists x\in X_{3}\,\forall y\in Y_{2}:A(x,y)$	Es existiert ein $x\in X_{3}$, so dass für alle $y\in Y_{2}$ die Aussageform $A(x,y)$ erfüllt ist.	falsch
11	$\exists x\in X_{2}\,\forall y\in Y_{1}:A(x,y)$	Es existiert ein $x\in X_{2}$, so dass für alle $y\in Y_{1}$ die Aussageform $A(x,y)$ erfüllt ist.	wahr
12	$\exists x\in X_{1}\,\forall y\in Y_{1}:A(x,y)$	Es existiert ein $x\in X_{1}$, so dass für alle $y\in Y_{1}$ die Aussageform $A(x,y)$ erfüllt ist.	falsch
13	$\forall y\in Y_{1}\,\exists x\in X_{2}:A(x,y)$	Zu jedem $y\in Y_{1}$ gibt es ein $x\in X_{2}$ mit $A(x,y)$.	wahr
14	$\exists x\in X_{3}\,\forall y\in Y_{3}:A(x,y)$	Es existiert ein $x\in X_{3}$, so dass für alle $y\in Y_{3}$ gilt $A(x,y)$.	falsch
15	$\exists x\in X_{2}\,\forall y\in Y_{1}:A(x,y)$	Es existiert ein $x\in X_{2}$, so dass für alle $y\in Y_{1}$ gilt $A(x,y)$.	wahr
16	$\forall y\in Y_{2}\,\exists x\in X_{3}:A(x,y)$	Zu jedem $y\in Y_{2}$ gibt es ein $x\in X_{3}$ mit $A(x,y)$.	wahr
17	$\exists x\in X_{2}\,\exists y\in Y_{3}:A(x,y)$	Es gibt ein $x\in X_{2}$ und ein $y\in Y_{3}$, so dass die Aussageform $A(x,y)$ erfüllt ist.	wahr

Wahrheitswert von Aussagen über natürliche Zahlen

Aufgabe

Die Grundmenge sei $\mathbb {N}$. Welche der folgenden Aussagen ist wahr?

1. $\forall y\,\forall z\,\exists x:x=y-z$
2. $\exists x\,\exists y\,\forall z:2x=y-z$
3. $\forall y\,\exists x\,\forall z:x=yz$
4. $\forall x\,\forall z\,\exists y:x=y+z$
5. $\exists z\,\forall x\,\exists y:x=yz$

Lösung

1. falsch
2. falsch
3. falsch
4. falsch
5. wahr

Fehlerhafte Aussagen korrigieren

Aufgabe

Wo liegt der Fehler in folgenden Aussagen? Verändere die Aussagen so, dass sie wahr werden.

1. $\forall a,b\in \mathbb {R} :(a-b)^{2}\in \mathbb {R} ^{+}$
2. $\forall a,b\in \mathbb {R} :a^{2}=b^{2}\Rightarrow a=b$
3. $\forall a,b,x\in \mathbb {R} :a\cdot x=b\cdot x\Rightarrow a=b$

Teilaufgabe 1

Frage: Wo liegt der Fehler?

Für $a=b$ ist $(a-b)^{2}=0$ und damit $(a-b)^{2}\notin \mathbb {R} ^{+}$.

Frage: Wie lautet die korrigierte Aussage?

Es gibt keine eindeutige Lösung hier. Folgende Aussagen sind Beispiele für richtige Lösungen:

• $\forall a,b\in \mathbb {R} :a\neq b\Rightarrow (a-b)^{2}\in \mathbb {R} ^{+}$
• $\forall a,b\in \mathbb {R} :(a-b)^{2}\in \mathbb {R} _{0}^{+}$
• $\forall a,b\in \mathbb {R} :(a-b)^{2}\in \mathbb {R}$

Teilaufgabe 2

Frage: Wo liegt der Fehler?

Gegenbeispiel: Sei $a=2$ und $b=-2$. Es ist dann $a^{2}=4=b^{2}$, aber $a\neq b$.

Frage: Wie lautet die korrigierte Aussage?

Folgende Korrekturen sind Beispiele für wahre Aussagen:

• $\forall a,b\in \mathbb {R} :a^{2}=b^{2}\Rightarrow |a|=|b|$
• $\forall a,b\in \mathbb {R} :a\geq 0\land b\geq 0\Rightarrow a^{2}=b^{2}\Rightarrow a=b$
• $\forall a,b\in \mathbb {R} ^{-}:a^{2}=b^{2}\Rightarrow a=b$

Teilaufgabe 3

Frage: Wo liegt der Fehler?

Ist $x=0$, dann ist stets $a\cdot x=0=b\cdot x$, auch wenn $a\neq b$ ist.

Frage: Wie lautet die korrigierte Aussage?

Folgende Korrekturen sind Beispiele für wahre Aussagen:

• $\forall a,b,x\in \mathbb {R} :x\neq 0\land a\cdot x=b\cdot x\Rightarrow a=b$
• $\forall a,b,x\in \mathbb {R} :a\cdot x=b\cdot x\Rightarrow a=b\lor x=0$
• $\forall a,b\in \mathbb {R} \,\forall x\in \mathbb {R} \setminus \{0\}:a\cdot x=b\cdot x\Rightarrow a=b$

Logik-Rätsel

Du bist auf einer dieser berüchtigten Inseln mit ziemlich spleenigen Leuten gelandet. Ein Teil der Bewohner, die sog. Aufrichtigen, sprechen stets die Wahrheit. Ein anderer Teil, die Verworfenen, lügen immer. Und dann sind da noch die Wechselbälger, die mal die Wahrheit sagen, mal lügen. Alle geben nur Aussagen von sich. Du lauschst während deines dortigen Aufenthalts folgenden drei Gesprächen und versuchst herauszufinden, um welche Charaktere es sich jeweils handelt.

Hinweis

Wir setzen bei den folgenden Aufgaben voraus, dass alle Aussagen einen eindeutigen Wahrheitswert haben! Da sich hier die Aussagen aufeinander beziehen, ist das nicht selbstverständlich. Beispiel: „Dieser Satz ist falsch.“

Teilaufgabe 1

Aufgabe

1. Gespräch

• Typ Nr. 1: „Einer von uns beiden ist ein Aufrichtiger.“
• Typ Nr. 2: „Einer von uns beiden ist verworfen.“
• Typ Nr. 1: „Du sprichst wahre Worte.“

Lösung

Es handelt sich bei beiden um Wechselbälger.

Teilaufgabe 2

Aufgabe

2. Gespräch

• Typ A: „Ich bin ja so ein Wechselbalg.“
• Typ B: „Genau eine der ersten beiden Aussagen ist wahr.“
• Typ A: „Genau eine der ersten drei Aussagen ist wahr.“
• Typ B: „Mindestens drei unserer vier Aussagen sind falsch.“

Wie kommt man auf den Beweis?

Wenn die 1. Aussage wahr ist und die zweite auch, führt das zu einem Widerspruch, da dann 2 Aussagen wahr sind und das der 2. Aussage widerspricht. Dass die erste wahr ist und die zweite falsch, ist ebenfalls unmöglich, da dann genau eine Aussage wahr ist. Wenn die erste falsch und die zweite wahr ist, könnte die dritte weder wahr noch falsch sein, da wenn sie wahr ist, zwei Aussagen wahr sind und wenn sie unwahr ist, genau eine Aussage wahr ist. Möglich ist aber, dass beide falsch sind, und da alle Aussagen wahr oder falsch sein müssen, ist das nach dem Ausschlussprinzip auch der Fall.

Frage: Was ist mit den Aussagen drei und vier?

Drittens muss falsch sein, denn Typ A ist kein Wechselbalg und hat einmal gelogen, ist also verworfen. Aussage 4 ist daher wahr.

Lösung

Typ A ist ein Verworfener, Typ B ein Wechselbalg.

Teilaufgabe 3

Aufgabe

3. Gespräch (In dieser Gruppe tritt jeder Charakter genau einmal auf)

• Typ X: „Y ist der Aufrichtige.“
• Typ Y: „Z ist das Wechselbalg.“
• Typ Z: „X ist ja so was von verworfen.“

Lösung

Typ X ist verworfen, Typ Y wechselhaft und Typ Z aufrichtig.

Logik-Rätsel 2: Ungeklärter Mordfall

Aufgabe

Graf Eutin ist ermordet worden. Als Mörder kommen nur Fräulein Ming, Professor Bloom, Frau Weiß oder Oberst von Gatow in Frage. Versuche an Hand der Aussagen dieser vier Personen den Möder/die Mörderin zu überführen. Dabei darfst du annehmen, dass bis auf den Mörder/die Mörderin alle anderen die Wahrheit sagen.

• Fräulein Ming: „Ich war zur Tatzeit mit Professor Bloom zusammen.“
• Professor Bloom: „Oberst von Gatow war zur Tatzeit im Saloon.“
• Frau Weiß: „Fräulein Ming, Oberst von Gatow und ich waren zur Tatzeit nicht im Saloon.“
• Oberst von Gatow: „Ich bin unschuldig. Der Mord ist im Saloon passiert.“

Wer ist der Mörder/die Mörderin?

Wie kommt man auf den Beweis?

Da bis auf den Mörder/die Mörderin alle die Wahrheit sagen, können wir zur Aufklärung der Tat folgendermaßen vorgehen: Wir streichen nacheinander jeweils eine der vier Aussagen und überprüfen die anderen drei. Dabei muss sich in genau einem dieser vier Fälle bei den anderen Aussagen kein Widerspruch ergeben. Die in diesem Fall gestrichene Aussage war die des Mörders/der Mörderin. Auf diese Weise sollten selbst unbegabte Hobbykriminalisten die Tat aufklären können!  

Lösung

Fall 1: Fräulein Ming lügt.

Prof. Bloom: „Oberst von Gatow war zur Tatzeit im Saloon.“ ✔

Fr. Weiss: „Frl. Ming, Oberst von Gatow und ich waren zur Tatzeit nicht im Saloon.“ ↯

Fall 2: Professor Bloom lügt.

Frl. Ming: „Ich war zur Tatzeit mit Professor Bloom zusammen.“ ✔

Fr. Weiss: „Frl. Ming, Oberst von Gatow und ich waren zur Tatzeit nicht im Saloon.“ ✔

Oberst von Gatow: „Ich bin unschuldig. Der Mord ist im Saloon passiert.“ ↯

Fall 3: Oberst von Gatow lügt.

Frl. Ming: „Ich war zur Tatzeit mit Professor Bloom zusammen.“ ✔

Prof. Bloom: „Oberst von Gatow war zur Tatzeit im Saloon.“ ✔

Fr. Weiss: „Frl. Ming, Oberst von Gatow und ich waren zur Tatzeit nicht im Saloon.“ ↯

Fall 4: Frau Weiss lügt.

Frl. Ming: „Ich war zur Tatzeit mit Professor Bloom zusammen.“ ✔

Prof. Bloom: „Oberst von Gatow war zur Tatzeit im Saloon.“ ✔

Oberst von Gatow: „Ich bin unschuldig. Der Mord ist im Saloon passiert.“ ✔

Also ist Frau Weiß die Einzige der Tatverdächtigen, die lügt, und ist somit als Mörderin überführt.

Logik-Rätsel 3: Existenz von Superman

Aufgabe

Begründe, dass die folgenden Aussage richtig ist:

„Wenn Superman in der Lage und willig ist, Übel zu verhindern, dann würde er es tun. Wenn Superman nicht in der Lage ist Übel zu verhindern, dann wäre er impotent. Wenn Superman nicht willig wäre, Übel zu verhindern, dann wäre er bösartig. Superman verhindert kein Übel. Wenn Superman existiert, dann ist er weder impotent noch bösartig. Deswegen existiert Superman nicht.“

Wie kommt man auf den Beweis?

Die gesamte Aussage besteht aus sechs Teilaussagen. Formuliere diese zunächst. Stelle nun, mit Hilfe der Teilaussagen und Junktoren, eine aussagenlogische Formel für die gesamte Aussage auf. Bei der aussagenlogischen Formel handelt es sich um eine Implikation. Hier ist es einfacher zu zeigen, dass diese nicht falsch sein kann. Dies trifft nur in einem Fall zu. Begründe, dass dieser nicht eintreten kann.

Lösung

Beweisschritt: Formulierung der Teilaussagen.

• L: Superman ist in der Lage Übel zu verhindern.
• W: Superman ist willig Übel zu verhindern.
• V: Superman verhindert Übel.
• I: Superman ist impotent.
• B: Superman ist bösartig.
• E: Superman existiert.

Beweisschritt: Formulierung der gesamten Aussage.

Bei der Aussage handelt es sich um eine Implikation. Diese lautet:

$[((L\land W)\Longrightarrow V)\land (\neg L\Longrightarrow I)\land (\neg W\Longrightarrow B)\land (\neg V)\land (E\Longrightarrow (\neg I\land \neg B))]\Longrightarrow \neg E$

Beweisschritt: Nachweis, dass die Aussage wahr ist.

Wie im Lösungsweg beschrieben ist es hier einfacher zu zeigen, dass die Implikation nicht falsch sein kann. Die Implikation ist nur dann falsch, wenn aus einer wahren Aussage eine falsche Aussage folgt. D.h. wenn

• $\neg E$ falsch ist, d.h. $E$ wahr ist, und
• $((L\land W)\Longrightarrow V)\land (\neg L\Longrightarrow I)\land (\neg W\Longrightarrow B)\land (\neg V)\land (E\Longrightarrow (\neg I\land \neg B))$ wahr ist.

Die zweite Aussage besteht nun aus lauter „und“-Verknüpfungen. Sie ist daher genau dann wahr, wenn jede der Einzelaussagen wahr ist. D.h. wenn

1. $((L\land W)\Longrightarrow V)$ wahr,
2. $(\neg L\Longrightarrow I)$ wahr,
3. $(\neg W\Longrightarrow B)$ wahr,
4. $(\neg V)$ wahr, und
5. $(E\Longrightarrow (\neg I\land \neg B))$ wahr

ist.

Da nun $E$ wahr sein muss, müssen nach 5. auch $(\neg I\land \neg B)$ wahr sein. Also müssen $\neg I$ und $\neg B$ wahr sein, d.h. $I$ und $B$ müssen falsch sein.

Nach 4. muss $V$ falsch sein.

Da $B$ nach 5. falsch sein muss, muss nach 3. auch $\neg W$ falsch, also $W$ wahr sein.

Genauso muss $L$ nach 2. wahr sein, da $I$ nach 5. falsch war.

Nun ergibt sich aber aus 1. ein Widerspruch, da $W$ und $I$ wahr gewählt werden mussten, und $V$ falsch, ist $(L\land W)\Longrightarrow V$ falsch!

Damit gibt es keine Belegung für die die Implikation $[((L\land W)\Longrightarrow V)\land (\neg L\Longrightarrow I)\land (\neg W\Leftrightarrow B)\land (\neg V)\land (E\Longrightarrow (\neg I\land \neg B))]\Longrightarrow \neg E$ falsch ist.

Damit existiert Superman nicht, außer in Hollywood! ;-)