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

Beweistechniken

[...]

Beweissammlung

Deduction theorem

$\phi \models \psi$ if and only if $\models \phi \to \psi$

• Wir beweisen zuerst $\phi \models \psi ⟹\models \phi \to \psi$:

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

Dann ist aber $I\in Mod(\phi )$, $I\notin Mod(\psi )$ und somit gilt $Mod(\phi )⊈Mod(\psi )$. Daher gilt $\phi ⊭\psi$

• Nun beweisen wir $\phi \models \psi ⟸\models \phi \to \psi$

Angenommen es gilt $\phi ⊭\psi$, dann gilt, nach Definition von $\models$: $Mod(\phi )⊈Mod(\psi )$ und es existiert eine Interpretation $I$ mit $I\in Mod(\phi )$ und $I\notin Mod(\psi )$. Deswegen gilt $I\models \phi$, aber $I⊭\psi$. Daher gilt $I⊭\phi \to \psi$.

Contraposition theorem

$W\cup \{\varphi \}\models \mathrm{\neg }\psi$ iff $W\cup \{\psi \}\models \mathrm{\neg }\varphi$

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

1. I($\psi$) = t und I($\mathrm{\neg }\varphi$) = t , d.h. I($\varphi$) = f
2. I($\psi$) = f und I($\mathrm{\neg }\varphi$) = t , d.h. I($\varphi$) = f
3. I($\psi$) = f und I($\mathrm{\neg }\varphi$) = f , d.h. I($\varphi$) = t

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

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

ad 3: I($\varphi$) = t und I($\psi$) = f, d.h. I($\mathrm{\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 \{\varphi \}$ is unsatisfiable (i.e. a contradiction) iff $W\models \mathrm{\neg }\varphi$

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 \varphi [{\psi }_1]\leftrightarrow \varphi [{\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 $\varphi [{\psi }_1]\equiv \varphi [{\psi }_2]$

TODO

Diverses

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

$\models \varphi \to \psi$ iff $\varphi \wedge \mathrm{\neg }\psi$ is unsatisfiable.

Premisses:

1. $\models \phi$ holds iff $\phi$ is valid.
2. A formula $\phi$ is valid iff $\mathrm{\neg }\phi$ is unsatisifiable.
3. By semantics of $\to$, $p\to q\equiv \mathrm{\neg }p\vee q$

$\models \varphi \to \psi$ holds

• iff $\varphi \to \psi$ is valid (1.)
• iff $\mathrm{\neg }\varphi \vee \psi$ is valid (3.)
• iff $\mathrm{\neg }(\mathrm{\neg }\varphi \vee \psi )$ is unsatisifiable (2.)
• iff $\varphi \wedge \mathrm{\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)