Mathe-Artikel #001: Kombinieren wie ein Meisterdetektiv - Teil 2/2

Question

Vorheriger Teil: https://www.mathelounge.de/507798/mathe-artikel-001-kombinieren-wie-…

Im zweiten Teil geht es nun um Beweisfolgen und die Lösung des Falls. Zur Erinnerung hier noch einmal, um was es eigentlich geht:

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

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

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 lesen wir folgende Aussagen heraus:

$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 Herr Kirigaya sich 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!

André Dalwigk

Den Artikel gibt es auch auf: https://www.informatik.academy/aussagenlogik-kombinieren-wie-ein-mei… (inklusive PDF-Download).

Das Mitglied hat durch den Artikel 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.

Comments

Auch in toller Artikel!

Hier fehlt das "ist" wie im ersten Teil auch. Ein Schönheitsfehler ist, dass zwischen $A_i$ und "gilt" in 8.1 in der zweiten Zeile ein Leerzeichen fehlt. In der dritten Zeile des Abschnitts gehört das "n" bei "Ableitungsregeln" nicht hin. Nichts tragisches, aber mich würde es stören in meinem eigenen Artikel. Deswegen sei es mal erwähnt :)

In der ersten Zeile von 8.1 ein Tippfehler: $i \le n \in \mathbb{N}$ muss es heißen.

Dann noch eine Frage:
Müsste bei der Gestalt einer Beweisfolge nicht neben den "Ableitungen" noch "$\text{Äquivalenz}_1$",...,"$\text{Äquivalenz}_l$" hin oder so ähnlich?

Optisch hat es mich zunächst verwirrt, dass die Prämissen und Ableitungen so dicht beieinander stehen. Dachte zuerst, das gehört zusammen und aus all den Aussagen zusammen würde man dann B folgern.

Wie bereits im ersten Teil schon erwähnt, finde ich die Verknüpfung zu Detektiv Conan toll!:)

Ich denke, dass es damit vor allem zu Beginn des Studiums Leuten leichter fallen wird das Thema "Logik" besser nach zu vollziehen.

---

Hallo Bruce, 

vielen Dank für das positive Feedback :-)

Das "ist" ist in beiden Artikeln beim Kopieren von meiner Website verschluckt worden. Auch der zweite Schönheitsfehler ist dieser Problematik geschuldet (im Original passt alles;-)). Das $\leq$ hinter $\in$ muss weg (das ist tatsächlich schon vorher falsch gewesen).

Die Darstellung mit den Äquivalenzen hatte ich tatsächlich erst. Allerdings haben meine Studies gemeint, dass sie das eher verwirrend finden und so ist es bei der abgespeckten Version geblieben. Von den knapp $50$ Studies haben mir das mehr als die Hälfte erwähnt, weshalb ich es dann weggelassen habe. 

Ich würde einen Moderator bitten, die ersten drei Änderungen am Original vorzunehmen!

Nochmals vielen Dank für Dein ausführliches Feedback! Normalerweise kickt der Autismus bei Syntaxfehlern immer :-D

Ideen sind noch reichlich vorhanden (auch für andere Serien :-))

André

---

50 Bonuspunkte gutgeschrieben! Vielen Dank für den Artikel.