ich versuche gerade das beispiel im skript nachzuvollziehen. mit der wahrheitstablle… es wird angenommen das die formel falsch ist…. ich verstehe die darstellung im skript noch nich ganz, mit den unterstrichenen Nullen und Einsen
vieleicht könnte mal jemnd, der das beispiel im skrpt kennt, es in worte fassen? als ergänzung zur tabelle?
Etwas spät zwar, aber trotzdem noch die Erklärung des Beispiels aus dem Skript:
Reductio ad absurdum ist zurzeit in Folie
3. Aussagenlogik Semantik [28] ff. zu finden.
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe07/Semantik_1.pdfWichtige Eigenschaft dieses (Widerspruchs-)Beweisverfahrens:
Die zu beweisende Aussage wird nicht direkt hergeleitet, sondern ihr kontradiktorisches Gegenteil wird widerlegt.
Hier ist das Beispiel aus dem Skript:
Beispiel | A | B || ¬A | (¬A v B) | (A => B) | (¬A v B) <=> (A => B)
-----------+---+---++----+----------+----------+----------------------
1. Annahme | | || | | | 0
-----------+---+---++----+----------+----------+----------------------
2a. | | || | 1 | 0 | 0
3a. | 1 | 0 || | 1 | 0 | 0
-----------+---+---++----+----------+----------+----------------------
2b. | | || | 0 | 1 | 0
3b. | | 0 || 0 | 0 | 1 | 0
4b. | 1 | 0 || 0 | 0 | 1 | 0
-----------+---+---++----+----------+----------+----------------------
5. Test | 1 | 0 || 0 | 0 | 0 | 1
Bei obiger Wahrheitstabelle wird versucht, durch Rückschlüsse eine zwingend falsifizierende Belegung für die Formel (¬A v B) <=> (A => B) zu ermitteln. Dann wird diese Belegung getestet und widerlegt. Damit ist dann letztlich bewiesen, dass die Formel allgemeingültig ist.
So geht es schrittweise:Am Anfang steht eine leere Wahrheitstabelle.
In der
1. Annahme, wird zunächst behauptet, die Formel sei falsch.
Da eine Biimplikation nur falsch sein kann, wenn eine Seite wahr und die andere falsch ist …
A | B || A <=> B
--+---++--------
1 | 1 || 1
1 | 0 || 0
0 | 1 || 0
0 | 0 || 1 … ergeben sich daraus zwei mögliche Fälle
a. und
b., d. h für die beiden Teilformeln muss | 1 | 0 | (
2a.) oder | 0 | 1 | (
2b. ) gelten. Das wird also ebenfalls angenommen und in die Tabelle eingetragen. (Daher die Unterstreichungen im Skript).
Zuerst führen wir Fall
2a. mit der rechten Teilformel A => B als Falsch-Annahme fort. (Dieser ist leichter zu untersuchen, weil für die Falsch-Belegung nur ein möglicher Fall zu untersuchen ist, denn es gilt …
A | B || A => B
--+---++-------
1 | 1 || 1
1 | 0 || 0
0 | 1 || 1
0 | 0 || 1 Als Konsequenz ist also die Annahme nur dann möglich, wenn A = 1 und B = 0 ist. Das wird in die Tabelle (
3a.) eingetragen, die Konsequenzen unterstrichen. Ich bevorzuge allerdings Pfeile, die verdeutlichen, woher ich die Konsequenz gezogen habe.
(Anmerkung: Aus der anderen Teilformel ¬A v B ergibt sich diese Konsequenz nicht zwingend. Es genügt aber, eindeutig zwingende Konsequenzen zu betrachten.) Wir merken uns für den
a.-Fall -
A muss wahr und B muss falsch sein.
Jetzt muss auch Fall
2b. untersucht werden. Denn erst durch die Betrachtung beider zusammengehörig zwingend notwendigen Konsequenzen aus der Annahme können wir die Annahme widerlegen. In diesem Fall mussten ja die Teilformeln ¬A v B falsch und A => B wahr sein.
Aus "Teilformel ¬A v B ist falsch" ergibt sich, dass ¬A falsch sein muss und B ebenfalls. (Damit lässt sich Zeile
3b. vervollständigen.) Aus dieser Konsequenz bildet sich ebenfalls Zeile
4b. -
A muss wahr und B muss falsch sein.
(Anmerkung: Würde man jetzt die Konsequenz der Implikation A => B mit den oben gezogenen Konsequenzen aus "Teilformel ¬A v B ist falsch" vergleichen, wäre das schon ein Widerspruch zu der Annahme ¬A = 0 und damit zum ganzen
b.-Fall. Um aber die Belegung der gesamten Formel mit falsifizierendem Ergebnis zu widerlegen wird diese Konsequenz nicht betrachtet, sondern stattdessen eine andere, ebenfalls zwingende Konsequenz, nämlich dass sich aus "Teilformel A => B ist falsch" ebenfalls "
A muss wahr sein und B falsch" ergibt. Was sich mit Zeile
4b. deckt.
Die für eine falsifizierendes Ergebnis der Gesamtformel notwendige Belegung A = 1 und B = 0 wird nun in die Tabelle eingesetzt und ausgerechnet. Die Zeile
5. Test zeigt das Ergebnis: Wenn A wahr und B falsch ist, kommt eben nicht heraus, was angenommen wurde, sondern mit dieser Belegung ist die Formel insgesamt wahr. Damit haben wir die Annahme zum Widerspruch geführt und die einzig denkbare Belegung, die Gesamtformel falsch zu machen, widerlegt.
Würde dieses Verfahren auf Formeln angewendet, die falsifizierbar sind, wäre es leichter, unter der Annahme konsequent zwingend eindeutige Belegungen für die atomaren Formelteile zu ermitteln. Der Negativ-Test würde aber erfolglos verlaufen. Letzlich ließe sich dann die Annahme nicht widerlegen.
Selbst für eine so kleine Formel ist dieses Beweisverfahren schon hilfreich. Es bietet zudem aber die Möglichkeit, automatisiert auf riesige Formeln angewendet zu werden. Teilweise sogar auf unendliche, wenn man bereits mit endlichen Teilformeln zu einem eindeutigen Ergebnis kommt.
