· 

Denken wie Sherlock Holmes

1. Der Fall

Der selbsternannte Consulting Detective Sherlock Holmes hilft der Polizei (und insbesondere dem oft etwas unbeholfen wirkenden Inspector Lestrade) wieder einmal bei der Aufklärung eines schwierigen Mordfalls. Nachdem Sherlock 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 Hotel aufgehalten hat, dann hat Frau Takahashi die Schreie des Opfers nicht gehört. Wenn Herr Kirigaya sich vor der Tatzeit in dem 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 Sherlock auf diese Schlussfolgerung? Ist der Täter damit überführt?

2. Aussagenlogik

Um die einzelnen Schritte in Sherlocks 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.
Beispiel
  • \(A_1:=\) Mein Name ist Bond.
    Das ist eine Aussage, da man ihr auf sinnvolle Art und Weise einen Wahrheitswert zuordnen kann. Entweder ist sein oder ihr Name Bond oder nicht.
  • \(A_2:=\) Der Mord ereignete sich in Atlantis.
    Hierbei handelt es sich ebenfalls um eine Aussage, da sich der Mord tatsächlich in Atlantis ereignet hat oder nicht.
  • \(A_3:=1+1=42\)
    Das ist ebenfalls eine Aussage, nämlich eine falsche.
Es kommt nicht darauf an, ob die Aussage wahr oder falsch ist, sondern nur, ob es möglich ist, auf sinnvolle Art und Weise einen Wahrheitswert zuzuweisen.
Die folgenden Äußerungen sind keine Aussagen, da man ihnen keinen Wahrheitswert zuordnen kann.
  • \(A_4:=\) Magst Du Mathe auch so sehr wie ich?
    Eine Frage kann keine Aussage sein, auch wenn man sie mit "Ja" oder "Nein" beantworten kann. Immer dann, wenn am Ende eines sprachlichen Gebildes ein Fragezeichen kommt, liegt keine Aussage vor!
  • \(A_5:=\) Reiche mir das Wasser!
    Eine Aufforderung ist ebenfalls keine Aussage, da man ihr nicht auf sinnvolle Art und Weise einen Wahrheitswert zuordnen kann. Wenn am Ende eines sprachlichen Gebildes also ein Ausrufezeichen steht, dann liegt keine Aussage vor.
Definition: Prämisse und Schlussfolgerung

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.
Beispiel: Für \(A\Longrightarrow B\) ist \(A\) die Prämisse und \(B\) die Schlussfolgerung.

3. 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.
Mit einer sogenannten Wahrheitstafel kannst du die Negation (und andere logische Verknüpfungen) definieren und nachvollziehen. Das ist eine Tabelle, in der in der ersten Zeile die Aussage (bzw. Aussagen) und die Verknüpfungen, um die es geht, stehen. Darunter werden alle möglichen Kombinationen von \(0\) und \(1\) für die Aussagenspalten geschrieben. Da beim Begriff der Negation nur eine Aussage relevant ist, gibt es nur eine Spalte mit den Werten \(0\) und \(1\).
\begin{array}{|c|c|} \hline A & \neg A\\\hline 0 & 1\\\hline 1 & 0\\\hline \end{array}
Aus der \(0\) wird durch die Negation eine \(1\) und aus der \(1\) wird eine \(0\).
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.
Hier bilden jetzt zwei Aussagen die aussagenlogische Verknüpfung, nämlich \(A\) und \(B\). Die dazugehörige Wahrheitstabelle hat also \(3\) Spalten. In der Kopfzeile stehen neben den beiden Aussagen noch die Verknüpfung \(A\wedge B\), um die es geht. Auf wie viele Arten kann man die beiden Wahrheitswerte \(0\) und \(1\) kombinieren? Richtig, auf \(2^2=4\) Arten, nämlich durch \(00, 01, 10\) und \(11\). Allgemein gibt es für \(n\) Aussagen \(2^n\) mögliche Verknüpfungen für die Wahrheitswerte, aber dazu in einem anderen Artikel mehr.
\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.

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. Hierbei handelt es sich um ein entweder oder, d. h. \(A\) und \(B\) dürfen nicht beide wahr sein. Dann ist das Ergebnis \(0\). Das Zeichen für das XOR ist das für die Disjunktion mit einem Punkt oben drüber, also \(dot{\vee}\). Ü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.
Deshalb nutzt man für eine Äquivalenzumformung auch das Symbol \(\Longleftrightarrow\), weil es eine Kombination aus \(\Longleftarrow\) und \(\Longrightarrow\) 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.

4. Operratorrangfolge

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:
Bemerkung: Operatorrangfolge in der Aussagenlogik

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

5. Ä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}$$

6. Ableitungsregeln der Aussagenlogik

Die folgende Übersicht listet Schlussfolgerungen auf, die man aus einfachen Formeln ziehen kann. Diese nutzt Sherlock, 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)\), also ist 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)\).

7. 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.
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:
  • Prämissen identifizieren und notieren.
  • Ableitungen auf der Basis der Ableitungsregeln der Aussagenlogik durchführen.

8. 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 Hotel befunden.“
  • \(E:=\) „Die Halskette des Opfers wurde gestohlen.“
Aus den Ausführungen von Sherlock 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 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 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 Sherlock 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:
  1. Mit Prämisse 5 und der Ausdehnung folgt: \(\neg E\vee \neg B\)
  2. Mit Schlussfolgerung 6 und den Kommutativgesetzen folgt: \(\neg B\vee \neg E\)
  3. Mit Schlussfolgerung 7 und den De Morgan'schen Regeln folgt: \(\neg (B\wedge E)\)
  4. Mit Prämisse 4, Schlussfolgerung 8 und dem Modus Tollens folgt: \(\neg D\)
  5. Mit Prämisse 3, Schlussfolgerung 9 und dem Modus Ponens folgt: \(\neg C\)
  6. Mit Prämisse 2 und den Kommutativgesetzen folgt: \(C\vee \neg B\)
  7. Mit Schlussfolgerung 11 und der disjunktiven Implikation folgt: \(\neg C\Longrightarrow \neg B\)
  8. Mit den Schlussfolgerungen 10, 12 und dem Modus Ponens folgt: \(\neg B\)
  9. Mit Prämisse 1, Schlussfolgerung 13 und dem Modus Tollens folgt: \(\neg \neg A\)
  10. 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. Sherlock hat also (wie so oft) Recht und Herr Kirigaya ist als Täter überführt! Wie kommt man auf die einzelnen Schritte? Nun, das ist wie beim Beweisen: durch viel Übung und Spielen mit dem Problem.