Python-based RPN Evaluator

This program evaluates logic expressions out of a textfile with Reveresed Polish Notation (RPN) syntax.

Example world file:
wind
/sun
/rain
red

wind and red have the value of 1, sun and rain 0 since they are prefixed by "/".
Here's the syntax to run the program: "python log.py myworld.world".
It quits when an empty expression occurs.

Example usage:
C:\Python26>python log.py myworld.world
Logical Expression: rain sun &
0
Logical Expression: sun red |
1
Logical Expression: sun wind ^
True
Logical Expression: winter sun &
*** Error while evaluating: Bad name: 'winter'.
Logical Expression: sun red
*** Error while evaluating: Unbalanced expression: 'sun red'.
Logical Expression: sun red red |
*** Error while evaluating: Unbalanced expression: 'sun red red |'.
Logical Expression:

C:\Python26>



Find the source code here.

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.

Aussagenlogik (Teil 1)

Zunächst ein bisschen Humor, man wird ihn brauchen. Sei kein Pinguin - lern Logik:

Die Aussagenlogik überprüft eine atomare Aussage auf ihren Wahrheitsgehalt. Eine atomare Aussage ist eine strukturlose, abstrakte Elementaraussage, wie unten beschrieben. Eine Aussage kann wahr oder falsch sein - binär gesprochen 1 oder 0. Man merkt schon, dass die Aussagenlogik nicht den Anspruch erhebt natürlichsprachige Phänomene völlig abzudecken. Abstufungen werden nicht berücksichtigt, dafür gibt es die Fuzzy Logic. Wofür ist also Logik gut? Dafür:

Es handelt sich eherum ein Formalismus, der zur semantischen Wahrheitswertzuweisung dient und uns, durch die Abstraktion, abhalten soll die Aussagen weiter zu zerlegen und zu interpretieren. Nehmen wir zwei Sätze:

(α) Der Mond dreht sich um die Erde.
(β) Die Erde ist eine Scheibe.

Durch unsere Allgemeinbildung wissen wir, dass A wahr und B falsch ist. Daraus ergibt sich folgende Funktion:

g: {A1, A2, A3, ... } → { 0, 1 }

Natürlich könnten wir beide Aussagen mit einer Konjunktion (z.B. und bzw. oder) verbinden. In der Aussagenlogik gibt es auch solche Konjunktionen, sie heißen Junktoren und verbinden atomare Aussagen:

¬ (Negation, sprich: nicht)

∧ (Konjunktion, sprich: und)

∨ (Disjunktion, sprich: oder)

⇒ (Implikation, sprich: wenn, dann)

⇔ (Äquijunktion, sprich: genau dann, wenn)

Im übrigen lassen sich alle Junktoren mittels ¬ und ∨ ausdrücken. Implikation und Äquijunktion sind einfach nur abgekürzte Schreibweisen, auf deren Herleitung ich nicht besonders eingehen will. Beschäftigen wir uns zunächst mit der Negation. Eine Aussage kann wahr sein, dann muss die Negation dieser Aussage falsch sein und umgekehrt, daraus lässt sich folgende Wahrheitstabelle erstellen, welche alle Möglichkeiten aufzeigt:

α	¬α
wahr	falsch
falsch	wahr

Konkret auf α und β bezogen:

(α) Der Mond dreht sich um die Erde = 1, also (¬α) Der Mond dreht sich nicht um die Erde = 0
(β) Die Erde ist eine Scheibe = 0, also (¬β) Die Erde ist keine Scheibe = 1

Die allgemeingültige Formel dafür ist:

I (¬φ) = 1, falls I (φ) = 0, sonst I (¬φ) = 0

I ist die Interpretationsfunktion für die gilt:

I (A_i) = g (A_i)

Dabei steht φ für die ein atomares Element der Funktion und ψ für ein anderes, unterschiedliches, Element der Funktion. Hier einmal die allgemeingültigen Regeln, welche wir später einzeln abhandeln wollen:

1. I (¬φ) = 1, falls I (φ) = 0, sonst I (¬φ) = 0

2. I ((φ ∧ ψ)) = 1, falls I (φ) = 1 und I (ψ) = 1, sonst I ((φ ∧ ψ)) = 0

3. I ((φ ∨ ψ)) = 1, falls I (φ) = 1 oder I (ψ) = 1, sonst I ((φ ∨ ψ)) = 0

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

5. I ((φ ⇔ ψ)) = 1, falls I (φ) = (ψ), sonst I ((φ ⇔ ψ)) = 0

Konkretisieren wir das, ab Punkt 2, mit den obigen Beispielen:

(α) Der Mond dreht sich um die Erde.
(β) Die Erde ist eine Scheibe.


2. Konjunktion: Der Mond dreht sich um die Erde und sie ist eine Scheibe. Diese Aussage ist falsch und das obwohl der erste Teil stimmt, aber der zweite Teil der Aussage ist falsch und somit auch die Gesamtaussage. Es müssen beim Junktor ∧ also alle Teilaussagen wahr sein. Daraus ergibt sich folgende Wahrheitswerttabelle:

α	β	α ∧ β
wahr	wahr	wahr
falsch	wahr	falsch
wahr	falsch	falsch
falsch	falsch	falsch

Oder eben folgende allgemeingültige Formel:

I ((φ ∧ ψ)) = 1, falls I (φ) = 1 und I (ψ) = 1, sonst I ((φ ∧ ψ)) = 0

3. Disjunktion: Der Mond dreht sich um die Erde oder die Erde ist eine Scheibe. Diese Gesamtaussage ist wahr, wenn mindestens eine Teilaussage wahr ist. Beachte, es handelt sich um ein nichtausschließendes Oder. Hier die Wahrheitswerttabelle:

α	β	α ∨ β
wahr	wahr	wahr
falsch	wahr	wahr
wahr	falsch	wahr
falsch	falsch	falsch

Führt zu folgender Formel:

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

4. Implikation: Hier stoßen wir auf ein natürlichsprachliches Problem. Lasset das allmächtige Wikipedia sprechen:

Die Lesart „wenn … dann“ ist insofern problematisch, als mit dem natürlichsprachlichen „wenn … dann“ vor allem inhaltliche Zusammenhänge wie Kausalität oder zeitliche Nähe ausgedrückt werden. All das macht die materiale Implikation nicht, sie nennt nur den formalen Zusammenhang: „Dass es regnet, ist eine hinreichende Bedingung dafür, dass die Straße nass ist“. Zur Frage, warum das eine hinreichende Bedingung ist – ob auf Grund eines kausalen Zusammenhangs oder auch nur rein zufällig –, nimmt die materiale Implikation nicht Stellung

Mit unseren obigen Aussagen mag das vielleicht ein Problem sein, deswegen bedienen wir uns den Beispielen von Wikipedia:

(γ) Es regnet.
(δ) Die Straße ist nass.

Beginnen wir diesmal mit der Wahrheitswerttabelle für die Formel:

I ((φ ⇒ ψ)) = 1, falls I (φ) = 0 oder I (ψ) = 1, sonst I ((φ ⇒ ψ)) = 0, daraus folgt für unsere Beispiele:

γ	δ	γ ⇒ δ
wahr	wahr	wahr
falsch	wahr	wahr
wahr	falsch	falsch
falsch	falsch	wahr

Das heißt für uns, wenn es regnet, ist die Straße nass und wenn die Straße nicht nass ist, regnet es nicht. Falsch wäre zu sagen, weil es nicht regnete, kann die Straße nicht nass sein.


5. Äquijunktion: Aussage A trifft genau dann zu wenn Aussage B zutrifft, dabei ist der allfällige Inhalt der Aussage wurscht, wie Wikipedia es so schön formuliert. Nehmen wir die zwei Aussagen:

(ε) Heute ist Dienstag.
(ζ) Morgen ist Mittwoch.

Daraus folgt, dass heute genau Dienstag ist, wenn morgen Mittwoch ist. Wenn morgen nicht Mittwoch ist, ist heute auch nicht Dienstag, ergo:

ε	ζ	ε ⇔ ζ
wahr	wahr	wahr
falsch	wahr	falsch
wahr	falsch	falsch
falsch	falsch	wahr

Abgeleitet zur Formel:

I ((φ ⇔ ψ)) = 1, falls I (φ) = (ψ), sonst I ((φ ⇔ ψ)) = 0

Abschließend möchte ich noch sagen, dass dieser Post auf Klabunde et al. und dem Wikipedia-Artikel Aussagenlogik basiert. Für eine Vertiefung empfehle ich Marcus Spies. Einführung in die Logik. Spektrum. 2004. Hoffentlich habe ich das Buch richtig gelesen, denn es kann natürlich sein, dass ich logische Fehler reingebracht habe. ;-)
Bald gehts weiter mit: