TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Übungen WS12/Blatt 1 - Beispiel 2

Show the contraposition theorem directly from the definition of $\models$ :

$W\cup \{\phi \}\models \neg \psi$ iff $W\cup \{\psi \}\models \neg \phi$

Lösungsvorschlag von Steve92

Damit aus $W\cup \{\psi \}$, $\neg \phi$ folgt, gibt es drei Möglichkeiten:

1. I($\psi$) = t und I($\neg \phi$) = t , d.h. I($\phi$) = f
2. I($\psi$) = f und I($\neg \phi$) = t , d.h. I($\phi$) = f
3. I($\psi$) = f und I($\neg \phi$) = f , d.h. I($\phi$) = t

Wenn man nun die Wissensbasis hernimmt und sie mit $\phi$ vereinigt, passiert folgendes:

ad 1 und 2: Da I($\phi$) = f ist, wird der ganze linke Teil der logischen Konsequenz falsch und aus Falschem lässt sich ja bekanntlich alles ableiten.

ad 3: I($\phi$) = t und I($\psi$) = f, d.h. I($\neg \psi$) = t - hier gilt die logische Konsequenz auch, weil aus Wahrem Wahres folgt.

Da für alle Fälle die logsiche Konsequenz erfüllt ist, gilt das Contraposition Theorem.

Lösungsvorschlag von Enrimilan

Bei "iff" geht man so vor, dass man immer 2 Implikationen zeigen muss, nämlich: $W\cup \{\phi \}\models \neg \psi \Rightarrow W\cup \{\psi \}\models \neg \phi$ und $W\cup \{\psi \}\models \neg \phi \Rightarrow W\cup \{\phi \}\models \neg \psi$

$\Rightarrow$ Angenommen $W\cup \{\phi \}\models \neg \psi$ ist gültig. Wir wählen eine beliebige Interpretation I mit $I\models W\cup \{\psi \}$, also gilt auch $I\models W$ und $I\models \psi$.

Jetzt müssen wir 2 Fälle unterscheiden:

1) $I\models W\cup \{\phi \}$ Aus unserer Annahme, dass $W\cup \{\phi \}\models \neg \psi$ folgt also dass $I\models \neg \psi$ Das ist aber ein Widerspruch zu unserer gewählten Interpretation, weil $I\models \psi$

2) $I\not \models W\cup \{\phi \}$ Für unsere gewählte Interpretation muss aber auch gelten, dass $I\models W$. Damit gilt $I\not \models W\cup \{\phi \}$ nur, wenn $I\not \models \phi$ was dasselbe ist wie $I\models \neg \phi$. Also gilt jetzt $I\models W\cup \{\psi \}$ und $I\models \neg \phi$. Also ist $W\cup \{\psi \}\models \neg \phi$ gültig ( das was wir zeigen wollten).

Wir haben also für den ersten Fall einen Widerspruch, für den zweiten haben wir die Formel bewiesen. Bei solchen Beweisen ist das so, dass für alle Fälle für die wir keinen Widerspruch bekommen, wir immer dieselbe Formel bekommen müssen. Kriegen wir einen Widerspruch, dann kann man aus diesem Widerspruch sowieso alles herleiten. Damit wäre der erste Teil der Formel bewiesen.

$\Leftarrow$ Analog wie oben, also man muss zeigen dass $W\cup \{\psi \}\models \neg \phi \Rightarrow W\cup \{\phi \}\models \neg \psi$