Kombinieren wie ein Meisterdetektiv


4

1. Einführung

Dieser Artikel ist ein Versuch, die von einigen Studenten als „trocken“ empfundene Theorie der Aussagenlogik im Kontext der Japanischen Popkultur zu erklären. Wir begleiten dabei den Oberschülerdetektiv Shinichi Kudo bei der Lösung eines Falls. Die Schlussfolgerungen basieren dabei auf den Prinzipien der Aussagenlogik.

Die Figuren bzw. das Setting stammen aus dem Anime „Meitantei Konan“ (zu Deutsch: Detektiv Conan).

 

2. Der Fall

Oberschülerdetektiv Shinichi Kudo hilft der Polizei wieder bei der Aufklärung eines schwierigen Mordfalls. Nachdem er den Tatort untersucht und die Zeugen befragt hat, wird ihm schnell klar, wer der Mörder ist. Er führt nun in gewohnter Form aus:

„Wenn Herr Kirigaya nicht der Täter ist, dann ereignete sich der Mordfall 5km von Herrn Kirigayas Wohnung entfernt. Entweder hat der Mordfall nicht 5km von Herrn Kirigayas Wohnung stattgefunden oder Frau Takahashi hat die Schreie des Opfers gehört. Wenn Herr Kirigaya sich vor der Tatzeit nicht in einem Love Hotel aufgehalten hat, dann hat Frau Takahashi die Schreie des Opfers nicht gehört. Wenn Herr Kirigaya sich vor der Tatzeit in dem Love Hotel befunden hat, dann ereignete sich der Mord auch 5km von seiner Wohnung entfernt und der Täter hätte die Halskette des Opfers gestohlen. Aber, wie Sie sehen, wurde die Halskette nicht gestohlen! Das Opfer trägt Sie immer noch. Damit sind Sie der Täter, Herr Kirigaya!“

Wie kommt Shinichi auf diese Schlussfolgerung? Ist der Täter damit überführt?

3. Aussagenlogik

Um die einzelnen Schritte in Shinichis Beweisführung logisch nachvollziehen zu können, benötigen wir Grundkenntnisse in der Aussagenlogik. Wir beschränken uns dabei auf die Aspekte, die für das Verständnis von elementarer Bedeutung sind, da durch eine allumfassende Einführung der Fokus auf den Fall verlorengehen würde.

Definition: Aussage

Eine Aussage ist ein sprachliches Gebilde, dem man auf sinnvolle Weise einen Wahrheitswert zuordnen kann. Als Wahrheitswerte kommen nur „wahr“ (\(1\)) oder „falsch“ (\(0\)) infrage. \(\diamond\)

Beispiel:

- \(A_1:=\) Mein Name ist André.
- \(A_2:=\) Der Mord ereignete sich im Beika-Viertel.
- \(A_3:=1+1=42\)

Bei den Aussagen \(A_1\) und \(A_2\) kommt es auf die Situation an, ob sie wahr oder falsch sind (wichtig ist hier nur, dass die Aussagen entweder wahr oder falsch sind). \(A_3\) ist offensichtlich eine falsche Aussage.

Die folgenden Äußerungen sind keine Aussagen, da man ihnen keinen Wahrheitswert zuordnen kann.

- \(A_4:=\) Magst Du Mathe auch so sehr wie ich?
- \(A_5:=\) Hilfst Du mir bitte beim Kochen?
- \(A_6:=\) Hallo Welt.
- \(A_7:=\) Reiche mir das Wasser!

Die Antwort auf eine Frage ist kein Wahrheitswert. Eine Frage ist niemals eine Aussage. Genauso kann eine Aufforderung (in der Deutschen Sprache meist durch ein Ausrufezeichen am Satzende gekennzeichnet) ebenfalls keine Aussage sein.

Definition: Prämisse

Eine Prämisse ist eine Aussage, die vor dem logischen Operator \(\Longrightarrow\) (Implikation, dazu später mehr) steht. Eine Aussage, die auf der rechten Seite des Implikationspfeils steht, nennen wir Schlussfolgerung. \(\diamond\)

Beispiel:

Für \(A\Longrightarrow B\) ist \(A\) die Prämisse und \(B\) die Schlussfolgerung.

4. Logische Verknüpfungen

Man kann Aussagen mit logischen Operatoren (Junktoren) zu komplexeren Aussagen verknüpfen.

Definition: Negation

Sei \(A\) eine Aussage. Die Negation \(\neg A\) von \(A\) (in Worten: „nicht \(A\)“) ist genau dann wahr, wenn \(A\) selbst falsch ist und genau dann falsch, wenn \(A\) selbst wahr ist. \(\diamond\)

Die dazugehörige Wahrheitstafel sieht folgendermaßen aus: $$\begin{array}{|c|c|} \hline A & \neg A\\\hline 0 & 1\\\hline 1 & 0\\\hline \end{array}$$ 

Beispiel:

- Die Negation der Aussage „Das Verbrechen hat stattgefunden“ lautet „Das Verbrechen hat nicht stattgefunden“, da es nur die beiden Möglichkeiten stattgefunden und nicht stattgefunden gibt.

- Die Negation der Aussage „\(\pi\) ist gerade“ lautet „\(\pi\) ist nicht gerade“.

Wichtig: Die Negation der zweiten Aussage aus dem vorangegangenen Beispiel lautet nicht „\(\pi\) ist ungerade“, da beide Aussagen sonst falsch wären. Das ist ein häufig gemachter Fehler! Wenn z. B. etwas nicht schwarz ist, dann ist es nicht automatisch weiß. Es könnte auch violett, orange, blau oder irgendeine andere Farbe im sichtbaren Farbspektrum des menschlichen Auges sein. Das umgangssprachliche Gegenteil ist in den meisten Fällen etwas anderes als die logische Verneinung.

Definition: Konjunktion

Seien \(A\) und \(B\) Aussagen. Die Konjunktion \(A\wedge B\) von \(A\) und \(B\) (in Worten: „\(A\) und \(B\)“) ist genau dann wahr, wenn \(A\) und \(B\) beide wahr sind. Ansonsten ist die Aussage falsch. \(\diamond\)

Die dazugehörige Wahrheitstafel sieht folgendermaßen aus: $$\begin{array}{|c|c|c|} \hline A & B & A\wedge B\\\hline 0 & 0 & 0 \\\hline 0 & 1 & 0 \\\hline 1 & 0 & 0 \\\hline 1 & 1 & 1 \\\hline \end{array}$$ 

Definition: Disjunktion

Seien \(A\) und \(B\) Aussagen. Die Disjunktion \(A\vee B\) von \(A\) und \(B\) (in Worten: „\(A\) oder \(B\)“) ist genau dann wahr, wenn \(A\) oder \(B\)  oder beide wahr sind. Ansonsten ist die Aussage falsch. \(\diamond\)

Die dazugehörige Wahrheitstafel sieht folgendermaßen aus: $$\begin{array}{|c|c|c|} \hline A & B & A\vee B\\\hline 0 & 0 & 0 \\\hline 0 & 1 & 1 \\\hline 1 & 0 & 1 \\\hline 1 & 1 & 1 \\\hline \end{array}$$  Umgangssprachlich meinen wir mit „oder“ meist „entweder ... oder“. Die Disjunktion entspricht dem Milch-oder-Zucker-Oder. Wenn man in einem Restaurant Kaffee bestellt, bekommt man meist die Frage „Wollen Sie Milch oder Zucker in Ihren Kaffee?“ gestellt. Man wird jedoch nicht schief angeschaut, wenn man beides nimmt. Dieses Oder ist also nicht kontravalent.

Anders ist das Exklusiv-Oder (XOR) zu interpretieren. Übertragen wir das XOR auf die Situation in einem Restaurant, so hat dies zur Folge, dass man sich z. B. bei einem Menü-Angebot, in dem ein Getränk (Cola oder Wasser) enthalten ist, für eines entscheiden muss. Wird hier „Cola oder Wasser?“ gefragt, meint man auch entweder Cola oder Wasser (nicht beides!).

Definition: Implikation

Seien \(A\) und \(B\) Aussagen. Unter der Implikation von \(A\) und \(B\) versteht man die Aussage \(A\Longrightarrow B\) (in Worten: „\(A\) impliziert \(B\)“ oder „aus \(A\) folgt \(B\)“ oder „wenn \(A\), dann \(B\)“). Dabei nennen wir \(A\) die Prämisse und \(B\) die Folgerung. Eine Implikation ist nur dann falsch, wenn die Prämisse wahr und die Folgerung falsch ist. Aus einer falschen Prämisse darf alles (auch Falsches) gefolgert werden und die Aussage ist immer noch wahr.

Die dazugehörige Wahrheitstafel sieht folgendermaßen aus: $$\begin{array}{|c|c|c|} \hline A & B & A\Longrightarrow B\\\hline 0 & 0 & 1 \\\hline 0 & 1 & 1 \\\hline 1 & 0 & 0 \\\hline 1 & 1 & 1 \\\hline \end{array}$$ 

Beispiel

- Gegeben sei die Implikation „Wenn es regnet, dann ist die Straße nass“. Diese Aussage stimmt nur dann nicht, wenn es regnet und die Straße nicht nass ist. Wenn es nicht geregnet hat, dann könnte die Straße trotzdem nass sein, z. B. weil jemand einen Eimer Wasser ausgekippt oder der Regen bereits aufgehört hat. Die Straße kann aber auch trocken sein und die Aussage würde immer noch stimmen, denn die Prämisse ist nicht erfüllt.

- Die Implikation „Wenn \(6\) keine Primzahl ist, dann ist \(5\) ungerade“ ist wahr, denn die Prämisse „\(6\) ist keine Primzahl“ ist wahr und auch die Folgerung „\(5\) ist ungerade“ ist wahr. Somit ist die Implikation wahr.

Definition: Äquivalenz

Seien \(A\) und \(B\) Aussagen. Unter der Äquivalenz von \(A\) und \(B\) versteht man die Aussage \(A\Longleftrightarrow B\) (in Worten: „\(A\) gilt genau dann, wenn \(B\) gilt“). Diese ist genau dann wahr, wenn \(A\Longrightarrow B\wedge B\Longrightarrow A\) wahr ist.

Die dazugehörige Wahrheitstafel sieht folgendermaßen aus: $$\begin{array}{|c|c|c|} \hline A & B & A\Longleftrightarrow B\\\hline 0 & 0 & 1 \\\hline 0 & 1 & 0 \\\hline 1 & 0 & 0 \\\hline 1 & 1 & 1 \\\hline \end{array}$$ 

Beispiel

- Die Aussagen \(2x+2=4\) und \(x+1=2\) sind äquivalent (siehe Äquivalenzumformung).

- Die Aussagen \(x+1=42\) und \(x+2=2\) sind nicht äquivalent, da einige algebraische Umformungen zu dem Widerspruch \(1=42\) führen.

5. Operatorrangfolge

Bei der Verwendung mehrerer Operatoren in einem Ausdruck muss eindeutig entscheidbar sein, welche Bestandteile zuerst evaluiert werden. Eine der ersten Rechenregeln, die man in der Grundschule lernt, lautet „Punktrechnung vor Strichrechnung“. Hierbei handelt es sich um die Festlegung einer Operatorrangfolge, nach welcher der Operator \(\cdot\) stärker bindet als \(+\) oder \(-\). Möchte man hingegen \((40+41)\cdot 42\) ausrechnen, würde man zunächst die Summe \(40+41\) berechnen und anschließend mit \(42\) multiplizieren, was daran liegt, dass Klammern wiederum stärker als der Operator \(\cdot\) binden. Ist man sich bezüglich der Bindungsstärken unsicher, ist es nicht verkehrt durch Klammern klar zu machen, was man meint. Möchte man \(40+41\cdot 42\) ausrechnen, so sind die Klammern \(40+(41\cdot 42)\) zwar überflüssig, aber nicht falsch.

Auch in der Aussagenlogik unterliegen die Operatoren unterschiedlichen Bindungsstärken. Wir einigen uns auf folgende Operatorrangfolge:

- \(\neg\) bindet stärker als \(\wedge\).
- \(\wedge\) bindet stärker als \(\vee\).
- \(\vee\) bindet stärker als \(\Longrightarrow\).
- \(\Longrightarrow\) bindet stärker als \(\Longleftrightarrow\).

6. Äquivalenzregeln der Aussagenlogik

Es gibt eine Vielzahl an logischen Äquivalenzregeln, die einem die Arbeit mit Aussagen erleichtern. Die für unseren Fall wichtigen sind im Folgenden aufgeführt: $$ \begin{array}{|c|c|c|}\hline \text{Formel}&\text{logisch äquivalent zu}&\text{Bezeichnung der Regel} \\\hline A\wedge B&B\wedge A&\text{Kommutativgesetz} \\\hline A\vee B&B\vee A&\text{Kommutativgesetz} \\\hline \neg\neg A&A&\text{Doppelte Negation} \\\hline A\wedge(B\wedge C)&(A\wedge B)\wedge C&\text{Assoziativgesetz} \\\hline A\vee(B\vee C)&(A\vee B)\vee C&\text{Assoziativgesetz} \\\hline A\wedge(B\vee C)&(A\wedge B)\vee(A\wedge C)&\text{Distributivgesetz} \\\hline A\vee(B\wedge C)&(A\vee B)\wedge(A\vee C)&\text{Distributivgesetz} \\\hline \neg(A\wedge B)&\neg A\vee\neg B&\text{De Morgan'sche Regel} \\\hline \neg(A\vee B)&\neg A\wedge\neg B&\text{De Morgan'sche Regel} \\\hline A\Longrightarrow B&\neg A\vee B&\text{Disjunktive Implikation} \\\hline \end{array} $$

7. Ableitungsregeln der Aussagenlogik

Die folgende Übersicht listet Schlussfolgerungen auf, die man aus einfachen Formeln ziehen kann. Diese nutzt Shinichi, um Herrn Kirigaya als Täter zu entlarven. $$ \begin{array}{|c|c|c|}\hline\text{Formel} & \text{Ableitung} & \text{Bezeichnung der Schlussregel}\\\hline A & A\wedge B & \text{Ausdehnung}\\\hline A\text{ und }B & A\wedge B & \text{Konjunktion}\\\hline A\text{ und }A\Longrightarrow B & B & \text{Modus Ponens}\\\hline A\Longrightarrow B\text{ und }\neg B & \neg A & \text{Modus Tollens}\\\hline \end{array} $$ 

Beispiel (Modus Ponens):

„Wenn Herr Kirigaya kein Alibi hat \((A)\), dann ist er der Täter \((B)\).“
Herr Kirigaya hat kein Alibi \((A)\), alsoist er der Täter \((B)\).

Beispiel (Modus Tollens):

Wenn Herr Kirigaya kein Alibi hat \((A)\), dann ist er der Täter \((B)\).“
Herr Kirigaya ist nicht der Täter \((\neg B)\), also hat er ein Alibi \((\neg A)\).

8. Beweisfolgen

Die bisherigen Erkenntnisse zu den Äquivalenz- und Ableitungsregeln der Aussagenlogik werden nun dazu genutzt, um Beweisfolgen zu erzeugen. Doch was sind Beweisfolgen? Hierauf gibt uns die folgende Definition eine Antwort: 

Definition: Beweisfolgen

Sei \((A_1,A_2,...,A_n)\) eine Folge von aussagenlogischen Formeln \(A_i\) mit \(1\leq i\in\leq \mathbb{N}\leq n\). Wir nennen \((A_1,A_2,...,A_n)\) eine Beweisfolge, wenn für alle \(A_i\) gilt: Entweder ist \(A_i\) eine Prämisse oder Ergebnis einer Äquivalenz- oder Ableitungsregeln. \(\diamond\)

Eine Beweisfolge, bei der wir zeigen wollen, dass \(B\) aus einer Reihe von Prämissen \(A_1,A_2,...,A_j\) folgt, besitzt die allgemeine Gestalt: $$\begin{matrix} A_1\\ A_2\\ \vdots\\ A_j\\ \text{Ableitung}_1\\ \text{Ableitung}_2\\ \vdots\\ \text{Ableitung}_k\\ B \end{matrix}$$ Wir zeigen durch diese Art von Beweisfolgen die Gültigkeit der Implikation der allgemeinen Form $$A_1\wedge A_2\wedge ...\wedge A_j\Longrightarrow B$$ D.h.: Wenn Prämisse 1 gilt und Prämisse 2 gilt und ... und Prämisse j gilt, dann folgt daraus, dass \(B\) gilt. Ist eine der Prämissen nicht erfüllt, dann ist die Schlussfolgerung \(B\) nicht zwangsläufig korrekt.

Zum Aufstellen einer Beweisfolge bietet sich folgende Vorgehensweise an:

1. Prämissen identifizieren und notieren.

2. Ableitungen auf der Basis der Ableitungsregeln der Aussagenlogik durchführen.

9. Und so löst man den Fall

Aus der Fallbeschreibung können folgende Aussagen herausgelesen werden:

- \(A:=\) „Herr Kirigaya ist der Täter.“

- \(B:=\) „Der Mordfall ereignete sich 5km von Herrn Kirigayas Wohnung entfernt.“

- \(C:=\) „Frau Takahashi hat die Schreie des Opfers gehört.“

- \(D:=\) „Herr Kirigaya hat sich vor der Tatzeit in einem Love Hotel befunden.“

- \(E:=\) „Die Halskette des Opfers wurde gestohlen.“

Aus den Ausführungen von Shinichi setzen wir die Prämissen zusammen:

1. „Wenn Herr Kirigaya nicht der Täter ist, dann ereignete sich der Mordfall 5km von Herrn Kirigayas Wohnung entfernt.“ \(\neg A\Longrightarrow B\)

2. „Entweder hat der Mordfall nicht 5km von Herrn Kirigayas Wohnung stattgefunden oder Frau Takahashi hat die Schreie des Opfers gehört.“ \(\neg B\vee C\)

3. „Wenn sich Herr Kirigaya vor der Tatzeit nicht in einem Love Hotel aufgehalten hat, dann hat Frau Takahashi die Schreie des Opfers nicht gehört.“ \(\neg D\Longrightarrow \neg C\)

4. Wenn Herr Kirigaya sich vor der Tatzeit in dem Love Hotel befunden hat, dann ereignete sich der Mord auch 5km von seiner Wohnung entfernt und der Täter hätte die Halskette des Opfers gestohlen.“ \(D\Longrightarrow (B\wedge E)\)

5. „Aber, wie Sie sehen, wurde die Halskette nicht gestohlen! Das Opfer trägt Sie immer noch.“ \(\neg E\)

Um nachzuweisen, dass Shinichi mit seinen Schlussfolgerungen richtig liegt, müssen wir zeigen, dass \(A\) aus den Prämissen 1 bis 5 folgt. Es ist also die Gültigkeit der Formel $$(\neg A\Longrightarrow B)\wedge (\neg B\vee C)\wedge (\neg D\Longrightarrow \neg C)\wedge (D\Longrightarrow (B\wedge E))\wedge \neg E\Longrightarrow A$$ nachzuweisen. Dies werden wir im Folgenden durch schrittweise Anwendung der logischen Äquivalenz- und Ableitungsregeln erreichen. Mit anderen Worten: wir erzeugen eine Beweiskette:

6. Mit Prämisse 5 und der Ausdehnung folgt: \(\neg E\vee \neg B\)

7. Mit Schlussfolgerung 6 und den Kommutativgesetzen folgt: \(\neg B\vee \neg E\)

8. Mit Schlussfolgerung 7 und den De Morgan'schen Regeln folgt: \(\neg (B\wedge E)\)

9. Mit Prämisse 4, Schlussfolgerung 8 und dem Modus Tollens folgt: \(\neg D\)

10. Mit Prämisse 3, Schlussfolgerung 9 und dem Modus Ponens folgt: \(\neg C\)

11. Mit Prämisse 2 und den Kommutativgesetzen folgt: \(C\vee \neg B\)

12. Mit Schlussfolgerung 11 und der disjunktiven Implikation folgt: \(\neg C\Longrightarrow \neg B\)

13. Mit den Schlussfolgerungen 10, 12 und dem Modus Ponens folgt: \(\neg B\)

14. Mit Prämisse 1, Schlussfolgerung 13 und dem Modus Tollens folgt: \(\neg \neg A\)

15. Mit Schlussfolgerung 14 und der doppelten Negation folgt: \(A\)

Wir haben nun aus den Prämissen unter Anwendung der logischen Äquivalenz- und Schlussregeln schrittweise hergeleitet, dass \(A:=\) „Herr Kirigaya ist der Täter.“ aus den Prämissen folgt. Shinichi hat also Recht und Herr Kirigaya ist als Täter überführt!

 

Community Artikel, geschrieben vor 3 Wochen, 6 Tage
andré dalwigk, verified
Student, Punkte: 4206
 
Kommentar schreiben Diesen Artikel melden
0 Antworten