Logik

Bevor wir nach Athen aufbrechen, hier ein Satz von der Art, wie man ihn in den Nachrichten hören kann. Ein Politiker erklärt:

„Es gilt die Unschuldsvermutung. Für einen gewöhnlichen Bürger ist sie heilig und unantastbar. Für einen Politiker gilt jedoch die Schuldvermutung.“

Ist das eine einzige Aussage? Welche Teile sind Behauptungen, über deren Wahrheit man entscheiden kann, und welche drücken nur eine Wertung aus oder erteilen einen Befehl?

Schon das Wort Logik kommt vom griechischen logos – Wort, Rede, Vernunft, Rechnung. Die Logik begann also als Regeln für die Rede. Das ist der erste Hinweis darauf, warum später Sprachwissenschaftler in ihre Geschichte eintreten.

Das ganze Kapitel in einem Satz: Die Logik begann als Regeln richtigen Redens, die Stoiker machten daraus ein Rechnen mit der Wahrheit, Boole machte aus der Wahrheit die Zahl 1 und aus der Falschheit die 0, und Shannon baute daraus Schaltungen. An jeder Station siehst du, wo du der Idee heute im Code begegnest.

„Im Gegenteil“, fuhr Dideldei fort, „wenn es so war, könnte es sein; und wenn es so wäre, würde es sein; aber da es nicht so ist, ist es nicht. Das ist Logik.“— Lewis Carroll, Alice hinter den Spiegeln, 1871

Wie erkennt man, dass ein Schluss wirklich folgt und nicht bloß überzeugend klingt?

Im Athen des 5. und 4. Jahrhunderts v. Chr. entschied über alles die Rede: in der Volksversammlung, vor Gericht, wo man sich selbst verteidigte, und auf der Agora. Die Sophisten lehrten gegen Geld, wie man einen Streit gewinnt, nicht, wie man recht hat. Platon warf ihnen das vor, und sein Schüler Aristoteles stellte eine genauere Frage: Gibt es Regeln, nach denen man mechanisch erkennen kann, dass ein Argument gültig ist, unabhängig davon, wer es vorbringt und wie schön?

Aristoteles (384–322 v. Chr.) schrieb seine Antwort in Werken nieder, die seine Schüler später Organon nannten – „das Werkzeug“. Die Logik war für ihn keine Wissenschaft über die Welt, sondern ein Werkzeug für alle anderen Wissenschaften. Genau so benutzt sie heute ein Programmierer.

Die Entdeckung des Aristoteles: Ob ein Argument gültig ist, hängt nicht davon ab, worüber wir sprechen, sondern von seiner Form. Deshalb begann er statt Wörtern Buchstaben zu schreiben – die allererste Verwendung von Variablen in der Geschichte der Logik, zweitausend Jahre vor der Algebra.

// erste Prämisse: die Regel
  if (human(x)) mortal(x) = true;
  // zweite Prämisse: die Daten
  human("Socrates") == true;
  // Schluss
  mortal("Socrates") == true;

Die fliegende Katze: Wahrheit ist nicht dasselbe wie Gültigkeit

Alle Katzen können fliegen. Felix ist eine Katze. ⟹ Felix kann fliegen. Prämisse und Schluss sind Unsinn, und trotzdem ist das Argument logisch gültig: Seine Form ist dieselbe wie bei Sokrates. Würden die Prämissen gelten, müsste auch der Schluss gelten. Die Logik prüft nicht, ob die eingegebenen Wörter wahr sind, sondern ob die innere logische Struktur funktioniert.

Garbage in, garbage out: Ein korrektes Programm mit schlechten Daten liefert ein schlechtes Ergebnis. Und umgekehrt bedeutet ein richtiges Ergebnis noch nicht, dass das Programm korrekt ist:

Die Gesetze, die Aristoteles für die festesten hielt

In der Metaphysik (Buch IV) begründet Aristoteles, dass das sicherste aller Prinzipien der Satz vom Widerspruch ist: Nichts kann im selben Sinn zugleich sein und nicht sein. Gleich daneben formuliert er den Satz vom ausgeschlossenen Dritten: Von jedem Ding muss man etwas entweder bejahen oder verneinen; dazwischen gibt es nichts. Diese beiden Gesetze sind die Wurzel der zweiwertigen Logik – und damit auch des Typs boolean, der genau zwei Werte hat und nichts dazwischen.

Eine Kuriosität: In der Lehre vom Satz zögerte Aristoteles selbst, ob der Satz vom ausgeschlossenen Dritten auch für die Zukunft gilt. Ist die Aussage „Morgen wird eine Seeschlacht stattfinden“ schon heute wahr oder falsch?

„Es regnet.“ – „Regnet es?“ – „Möge es regnen!“ Drei Sätze über dieselbe Sache. Bei welchem von ihnen ist es sinnvoll zu fragen, ob er gilt?

Aristoteles arbeitete mit Begriffen (Menschen, Sterbliche). Die Stoiker im 3. Jahrhundert v. Chr., allen voran Chrysipp von Soloi (um 279–206 v. Chr.), begannen mit ganzen Sätzen zu arbeiten. Sie führten den Begriff axíōma ein, der unserer „Aussage“ entspricht, und definierten ihn genau über die Wahrheit: Eine Aussage ist etwas, das entweder wahr oder falsch ist.

Die Stoiker untersuchten auch, wie die Wahrheit eines zusammengesetzten Satzes von der Wahrheit seiner Teile abhängt: „und“, „oder“, „wenn… dann“. Über die Implikation stritten sie so heftig, dass der Dichter Kallimachos geschrieben haben soll, sogar die Raben auf den Dächern krächzten darüber, welche Implikation die richtige sei. Gesiegt hat die Definition von Philon von Megara: Der Satz „wenn A, dann B“ ist nur dann falsch, wenn A gilt und B nicht. Das ist genau die dritte Spalte der heutigen Tafel, 2200 Jahre älter als die Tafel selbst.

Die Bemerkung über die Raben des Kallimachos kennen wir nur von späteren Autoren (Sextus Empiricus). Die logischen Schriften der Stoiker sind nicht erhalten; über Chrysipp wissen wir vor allem aus Diogenes Laertios (Leben und Meinungen berühmter Philosophen, Buch VII).

Chrysipp stellte auch fünf grundlegende Schlussregeln auf. Die berühmteste von ihnen kennen wir heute als Modus ponens: Wenn A, dann B. A gilt. ⟹ B gilt.

Das Lügner-Paradox: wenn eine Aussage keinen Wahrheitswert hat

Schon im 4. Jahrhundert v. Chr. wurde Eubulides von Milet das Paradox „Diese Aussage ist falsch“ zugeschrieben. Ist sie wahr, ist sie falsch; ist sie falsch, ist sie wahr. Chrysipp soll darüber mehrere Schriften verfasst haben. Das Paradox zeigt die Grenze der Definition einer Aussage: Nicht jeder Aussagesatz ist eine Aussage.

function liar() {
    if (halts(liar)) while (true) {}  // soll ich enden? dann ende ich nicht
    else return;                      // soll ich nicht enden? dann ende ich
  }

Lassen sich die Gesetze des richtigen Denkens als Algebra aufschreiben?

Gottfried Wilhelm Leibniz (1646–1716) träumte von einer characteristica universalis, einer Sprache, in der Begriffe als Zeichen geschrieben würden, und von einem calculus ratiocinator, einem Kalkül des Denkens. Streitigkeiten würden dann nicht mehr durch Zank entschieden: Zwei Gelehrte würden sich hinsetzen und sagen Calculemus! – „Lasst uns rechnen!“. Leibniz beschrieb auch ausführlich das Dualsystem (1703) mit seinen zwei Ziffern 0 und 1. Logik und Dualsystem verband er aber noch nicht. Das tat anderthalb Jahrhunderte später ein Autodidakt aus Lincoln.

George Boole (1815–1864) war der Sohn eines Schuhmachers aus Lincoln; Mathematik brachte er sich selbst bei, und ab seinem 16. Lebensjahr arbeitete er als Lehrer, um seine Familie zu ernähren. Ohne Universitätsabschluss wurde er Professor in Cork in Irland. 1847 veröffentlichte er ein schmales Buch, The Mathematical Analysis of Logic, und 1854 sein Hauptwerk, An Investigation of the Laws of Thought. Daher das Jahr 1854 für dieses Kapitel.

Booles Ziel war nicht, einen Computer zu bauen. Er wollte beschreiben, wie Menschen denken, und zwar so genau, wie Newton die Bewegung beschrieben hatte. Er fand heraus, dass man Argumente wie Gleichungen aufschreiben und umformen kann.

George Boole 1815–1864, Lincoln – Cork

1. 1815Geboren in Lincoln in einer Schuhmacherfamilie.
2. 1831Mit 16 Jahren beginnt er zu unterrichten, um seine Familie zu ernähren.
3. 1847The Mathematical Analysis of Logic.
4. 1849Professor für Mathematik am Queen's College in Cork.
5. 1854An Investigation of the Laws of Thought.
6. 1864Stirbt im Alter von 49 Jahren an einer Lungenentzündung.

Neben Boole wirkte Augustus De Morgan (1806–1871), nach dem die Gesetze ¬(A ∧ B) ⇔ (¬A ∨ ¬B) und ¬(A ∨ B) ⇔ (¬A ∧ ¬B) benannt sind – die, die ein Programmierer jedes Mal benutzt, wenn er !(a && b) in !a || !b umschreibt.

Boole dachte nicht über Aussagen nach, sondern über Klassen von Dingen. Bei ihm konnte der Buchstabe x „weiße Dinge“ bedeuten, y „Schafe“. Das Produkt xy war dann der Durchschnitt: „weiße Schafe“. 1 war das ganze Diskursuniversum, alles, worüber wir sprechen, und 0 die leere Klasse, nichts.

Dann bemerkte er etwas Seltsames. Weiße weiße Dinge sind immer noch nur weiße Dinge, also xx = x, das heißt

x² = x.

In der gewöhnlichen Algebra hat diese Gleichung nur zwei Lösungen: x = 0 und x = 1. Daraus zog Boole einen Schluss, der die Geschichte veränderte: Die Algebra des Denkens ist die gewöhnliche Algebra, beschränkt auf die Zahlen 0 und 1. In seinem zweiten Buch deutete er dann 1 als „immer“, also Wahrheit, und 0 als „nie“, also Falschheit.

Aus derselben Gleichung leitete Boole auch den Satz vom Widerspruch des Aristoteles her: x − x² = 0, also x(1 − x) = 0. In Worten: Nichts kann die Eigenschaft x zugleich haben und nicht haben (1 − x). Das älteste Gesetz der Logik fiel als Nebenprodukt aus der Algebra heraus.

Wenn die Wahrheit 1 ist und die Falschheit 0, kann man dann die Tafeln für „nicht“, „und“, „oder“ und „wenn“ ausrechnen, statt sie auswendig zu lernen?

Boole zeichnete keine Tafeln; er rechnete mit Gleichungen. Die Tafel als Methode kam erst einige Jahrzehnte später.

• Gottlob Frege (1879, Begriffsschrift) beschrieb genau, wann eine Implikation wahr ist, indem er alle vier Fälle aufzählte – noch in Worten.
• Charles S. Peirce zeichnete um 1893 in einem unveröffentlichten Manuskript eine Matrix, die der heutigen Wahrheitstafel der Implikation entspricht. Sie tauchte erst nach seinem Tod in seinem Nachlass auf.
• Ludwig Wittgenstein (Tractatus, 1921) und unabhängig von ihm Emil Post (1921) veröffentlichten die Tafeln und zeigten, dass man mit ihnen bei jeder aussagenlogischen Formel entscheiden kann, ob sie eine Tautologie ist. Wittgenstein definierte eine Tautologie im Grunde als Formel, in deren Ergebnisspalte lauter Wahrheiten stehen.

Frege misstraute der natürlichen Sprache: Er hielt sie für ungenau und mehrdeutig und schuf deshalb eine eigene Sprache. Wie es mit Logik und Sprache weiterging, erzählt die eigene Seite Sprache und Logik.

Sobald die Wahrheit 1 und die Falschheit 0 ist, können wir Junktoren als Rechenoperationen betrachten: Wir geben zwei Zahlen ein, 0 oder 1, und erhalten 0 oder 1 zurück. Die Aufgabe: eine Formel finden, die genau in den Zeilen 1 ergibt, in denen die zusammengesetzte Aussage wahr ist. Schritt für Schritt:

1. Negation. Wir brauchen eine Operation, die 1 in 0 und 0 in 1 verwandelt. Das leistet die Subtraktion von eins: 1 − 1 = 0 und 1 − 0 = 1. Also ¬p = 1 − p.
2. Konjunktion „p und q“. Sie soll nur gelten, wenn beide Teile gelten. Probieren wir das Produkt: 1 · 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 · 0 = 0. Eine einzige Null macht das ganze Produkt zunichte, so wie ein einziger falscher Teil das ganze „und“ zu Fall bringt. Also p ∧ q = p · q.
3. Disjunktion „p oder q“. Sie soll gelten, wenn mindestens ein Teil gilt. Die erste Idee ist die Summe p + q. Sie funktioniert in drei Zeilen, aber für p = q = 1 ergibt sie 2, und eine 2 gibt es in unserer Welt nicht. Wir beheben das, indem wir den gemeinsamen Teil einmal abziehen: p + q − pq. (Boole selbst schrieb nur x + y und meinte das ausschließende „oder“; für die einschließende Variante setzte sich vor allem W. S. Jevons ein.)
4. Implikation „wenn p, dann q“. Nach Philon ist sie in einem einzigen Fall falsch: p = 1 und q = 0. Diesen „verbotenen“ Fall schreiben wir als Produkt p(1 − q), das nur dann 1 ist, wenn p = 1 und zugleich q = 0. Die Implikation gilt, wenn der verbotene Fall nicht eingetreten ist, also verneinen wir ihn: p ⇒ q = 1 − p(1 − q).
5. Äquivalenz „p genau dann, wenn q“. Sie soll gelten, wenn p und q denselben Wert haben. Die Differenz p − q ist 0, wenn sie übereinstimmen, und +1 oder −1, wenn nicht. Das Quadrieren beseitigt das Vorzeichen: (p − q)² ist 0, wenn sie übereinstimmen, und 1, wenn nicht. Bleibt nur, das Ergebnis umzudrehen: p ⇔ q = 1 − (p − q)².

Heraus kommt genau die bekannte Wahrheitstafel, diesmal nicht gelernt, sondern ausgerechnet. Die Tafel ist also ein Algorithmus: Geh alle 2ⁿ Kombinationen durch und schau nach. Es ist das erste Entscheidungsverfahren der Logik – und Brute Force in reinster Form.

Achtzig Jahre lang war die Boolesche Algebra eine Kuriosität für Philosophen. Kann man daraus eine Maschine bauen?

1937 schrieb der einundzwanzigjährige Claude Shannon am MIT seine Masterarbeit A Symbolic Analysis of Relay and Switching Circuits. Er zeigte, dass sich in Reihe geschaltete Schalter wie ∧ verhalten und parallel geschaltete wie ∨. Ein = 1, aus = 0. Von diesem Moment an ließ sich jedes logische Argument aus Drähten bauen. Jeder Prozessor ist ein Haufen Boolescher Gleichungen.