TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Beweissammlung

Beweistechniken

[...]

Beweissammlung

Deduction theorem

$\varphi \models \psi$ if and only if $\models \varphi \rightarrow \psi$

• Wir beweisen zuerst $\varphi \models \psi \,\Longrightarrow \,\models \varphi \rightarrow \psi$:

Angenommen es gilt $\nvDash \varphi \rightarrow \psi$, dann existiert eine Interpretation $I\nvDash \varphi \rightarrow \psi$ also $I\models \varphi$ und $I\nvDash \psi$ (nach der Semantik von $\rightarrow$, da die Implikation nur falsch ist, wenn die linke Seite der Implikation wahr ist und die rechte falsch.).

Dann ist aber $I\in Mod(\varphi )$, $I\notin Mod(\psi )$ und somit gilt $Mod(\varphi )\nsubseteq Mod(\psi )$. Daher gilt $\varphi \nvDash \psi$

• Nun beweisen wir $\varphi \models \psi \,\Longleftarrow \,\models \varphi \rightarrow \psi$

Angenommen es gilt $\varphi \nvDash \psi$, dann gilt, nach Definition von $\models$: $Mod(\varphi )\nsubseteq Mod(\psi )$ und es existiert eine Interpretation $I$ mit $I\in Mod(\varphi )$ und $I\notin Mod(\psi )$. Deswegen gilt $I\models \varphi$, aber $I\nvDash \psi$. Daher gilt $I\nvDash \varphi \rightarrow \psi$.

Contraposition theorem

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

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 lgosiche Konsequenz erfüllt ist, gilt das Contraposition Theorem.

Contradiction theorem

$W\cup \{\phi \}$ is unsatisfiable (i.e. a contradiction) iff $W\models \neg \phi$

contradiction theorem

Equivalent replacement lemma

Let

• $I$ be an Interpretation
• $\alpha$ a variable assigment and
• $I_{\alpha }\models \psi _{1}\leftrightarrow \psi _{2}$

then $I_{\alpha }\models \phi [\psi _{1}]\leftrightarrow \phi [\psi _{2}]$

TODO

Links

• https://web.archive.org/web/20180801000604/https://math.stackexchange.com/questions/126600/structural-induction-logic
• Formale Methoden Musterlösung

Equivalent replacement theorem

Let $\psi _{1}\equiv \psi _{2}$ then $\phi [\psi _{1}]\equiv \phi [\psi _{2}]$

TODO

Diverses

Prüfung 2012-11-12 Beispiel 1. c) 2.

$\models \phi \rightarrow \psi$ iff $\phi \land \neg \psi$ is unsatisfiable.

Premisses:

1. $\models \varphi$ holds iff $\varphi$ is valid.
2. A formula $\varphi$ is valid iff $\neg \varphi$ is unsatisifiable.
3. By semantics of $\rightarrow$, $p\rightarrow q\equiv \neg p\lor q$

$\models \phi \rightarrow \psi$ holds

• iff $\phi \rightarrow \psi$ is valid (1.)
• iff $\neg \phi \lor \psi$ is valid (3.)
• iff $\neg (\neg \phi \lor \psi )$ is unsatisifiable (2.)
• iff $\phi \land \neg \psi$ is unsatisfiable (De Morgan)

Kommentare

Kann mir vorstellen, dass 1. (Semantik vom Entailment) noch explizit zu beweisen ist damit's bei der Prüfung durchgeht --Thrau (Diskussion) 22:35, 11. Dez. 2012 (CET)