Aussagenlogik (Teil 2)

In Teil 1 wurde die Terminologie und die Syntax der Aussagenlogik besprochen. Um das ganze abzurunden beschäftigen wir uns nun mit dem letzten Teil der Aussagenlogik, der Semantik und dem Tableaux als Beweisverfahren.

In den vorherigen Gesetzen ist eine Formel als φ definiert und die aussagenlogische Belegung als g. Nun gibt es Belegungen die allgemeingültig oder gar unerfüllbar sind. Ersteres nennt man Tautologie (gr. τὸ αὐτό "dasselbe" und λόγος "Wort", "Rede", "Sinn"). "Sinnlos", aber nicht "unsinnig" seien die Tautologien, welche "nichts" bedeuten, schreibt Wittgenstein in seinem Tractatus¹. Als Formel wird eine Tautologie folgendermaßen ausgedrückt:

⊨φ

Eine Tautologie ist also unabhängig der Wahrheitswerte ihrer Elemente wahr. Das einfachste Beispiel ist (A ∨ ¬A); Es ist also wahr oder nicht wahr. Das einfachste Beispiel eines Widerspruchs wäre im Umkehrschluss (¬A ∧ A). Shakespeare lässt seinen Hamlet ganz treffend sagen: "Sein oder nicht sein"² - wobei er wohl noch keine Bekanntschaft mit Schrödingers Katze gemacht hat, denn die kann bekanntlicherweise lebendig und tot zugleich sein³.

Damit wäre nun die Semantik abgeschlossen. Werfen wir noch ein paar Definitionen in den Raum bevor wir überhaupt zu einem anspruchsvollen Beweisverfahren kommen.
Wenn man eine Menge von Formeln hat, definiert als Φ, dann folgt aus dieser Menge eine Formel ψ, wenn die Formel ψ die gleichen Belegungen erfüllt wie die Menge Φ:
Man schreibt dafür Φ ⊨ ψ und nennt die Elemente von Φ die Prämissen und ψ die Konklusion.⁴ Zum Beispiel ist (A ∧ B) ⊨ (A ∨ B), denn jede Belegung die den ersten Teil der Formel erfüllt, macht auch den zweiten Teil wahr. Sind zwei Formeln gleichwertig, dann spricht man von Äquivalenz. Die einfachste Äquivalenz wäre:

¬¬φ ≡ φ

In Teil 1 haben wir Gebrauch von Tabellen gemacht um die Wahrheitswerte herauszufinden, das ist allerdings zu aufwendig, denn je mehr Elemente eine Formel hat, desto größer (2ⁿ um genau zu sein; n = Anzahl der Elemente) wird unsere Tabelle und platzt schließlich aus allen Nähten. Deshalb wurde die Tableaux-Methode entwickelt um in einem Widerlegungsverfahren die Erfüllbarkeit von Formeln der Aussagenlogik zu (be-) widerlegen. Ich verwende hierfür das Beispiel aus Klabunde (et al.).⁵
Die Frage ist, wie man beweisen kann, dass A ⇒ (B ⇒ A) eine Tautologie ist. Wir wissen, dass eine Formel genau dann allgemeingültig ist, wenn die Negation dieser Formel unerfüllbar ist. Wir benutzen also ein Hintertürchen und beweisen die Unerfüllbarkeit:

¬(A ⇒ (B ⇒ A))

Um diese Aussage also wahr zu machen, muss A ⇒ (B ⇒ A) falsch gemacht werden. Vergegenwärtigen wir uns noch einmal die allgemeine Regel:

I ((φ ⇒ ψ)) = 1, falls I (φ) = 0 oder I (ψ) = 1, sonst I ((φ ⇒ ψ)) = 0

Es muss (B ⇒ A) = 0 (d.h. ¬(B ⇒ A) = 1) und A = 1 sein. Im Tableaux wird es folgendermaßen dargestellt:

1. ¬(A ⇒ (B ⇒ A))
2. A
3. ¬(B ⇒ A)

Zeile 2 kann nicht weiter zerlegt werden, aber Zeile 3 können wir zerlegen in:

4. B
5. ¬A

Oder anders: Damit ¬(B ⇒ A) wahr wird muss B (siehe Zeile 4) wahr und A (siehe Zeile 5) falsch sein. Nun steht in Zeile 2 aber dass A = 1 sein muss und in Zeile 5 steht, dass A = 0 sein muss. Dieser Widerspruch schließt das Tableaux und wir haben bewiesen, dass ¬(A ⇒ (B ⇒ A)) nicht zu erfüllen und damit (A ⇒ (B ⇒ A)) eine Tautologie ist. Die Reihenfolge der Expansionen ist dabei fakultativ. Ein Tableaux ist dann geschlossen, wenn φ als auch ¬φ darin vorkommen. Beweisbar ist eine Formel, wenn ¬φ in ein geschlossenes Tableaux übergeht. Man spricht formal von einem Theorem:

⊦φ

Um eine Tautologie handelt es sich:

wenn ⊦φ dann ⊨ φ

Auch für das Tableaux gibt es allgemeingültige Regeln, so haben wir in Zeile 3 folgendes Schema angewandt:

F→: ¬(φ ⇒ ψ)
________
φ
¬ψ

Diese Regel wird Expansionsregel genannt. Daraus lassen sich natürlich auch andere Expansionsregeln wie:

W_∧: (φ ∧ ψ)
______
φ
ψ

erstellen. Mit dem Problem, dass (φ ∨ ψ) wahr ist, wenn das erste oder das zweite Element wahr ist muss man umgehen indem man im Tableaux eine Verzweigung in der betreffenden Zeile erstellt.

Dass die Möglichkeiten der Aussagenlogik begrenzt ist, habe ich schon Anfangs erwähnt. So ist es zum Beispiel nicht möglich über die Eigenschaften der Objekte zu sprechen. Dies ist das Gebiet der Prädikatenlogik, mit der ich mich demnächst beschäftigen werden. Ein anderes Thema, welches für mich im Moment relevant ist, ist MathML und LaTeX bzw. TeX um mathematische Formeln dazustellen. HTML alleine ist dazu kaum in der Lage.


_

¹ Wittgenstein, Ludwig. Tractatus Logico-Philosophicus. These 6.11.
² Shakespeare, William. Hamlet. 3. Aufzug, 1. Szene.
³ Schrödinger, Erwin. Naturwissenschaften, 48, 807; 49, 823; 50, 844.
⁴ Klabunde, Ralf (et al.). Computerlinguistik und Sprachtechnologie. 36.
⁵ Klabunde, Ralf (et al.). Computerlinguistik und Sprachtechnologie. 38ff.