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

Aus VoWi
Zur Navigation springen Zur Suche springen

Beweistechniken[Bearbeiten | Quelltext bearbeiten]

[...]

Beweissammlung[Bearbeiten | Quelltext bearbeiten]

Deduction theorem[Bearbeiten | Quelltext bearbeiten]

if and only if

  • Wir beweisen zuerst :

Angenommen es gilt , dann existiert eine Interpretation also und (nach der Semantik von , da die Implikation nur falsch ist, wenn die linke Seite der Implikation wahr ist und die rechte falsch.).

Dann ist aber , und somit gilt . Daher gilt

  • Nun beweisen wir

Angenommen es gilt , dann gilt, nach Definition von : und es existiert eine Interpretation mit und . Deswegen gilt , aber . Daher gilt .

Contraposition theorem[Bearbeiten | Quelltext bearbeiten]

iff

Damit aus , folgt, gibt es drei Möglichkeiten:

  1. I() = t und I() = t , d.h. I() = f
  2. I() = f und I() = t , d.h. I() = f
  3. I() = f und I() = f , d.h. I() = t


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

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

ad 3: I() = t und I() = f, d.h. I() = 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[Bearbeiten | Quelltext bearbeiten]

is unsatisfiable (i.e. a contradiction) iff

contradiction theorem

Equivalent replacement lemma[Bearbeiten | Quelltext bearbeiten]

Let

  • be an Interpretation
  • a variable assigment and

then

TODO

Links[Bearbeiten | Quelltext bearbeiten]

Equivalent replacement theorem[Bearbeiten | Quelltext bearbeiten]

Let then

TODO


Diverses[Bearbeiten | Quelltext bearbeiten]

Prüfung 2012-11-12 Beispiel 1. c) 2.[Bearbeiten | Quelltext bearbeiten]

iff is unsatisfiable.

Premisses:

  1. holds iff is valid.
  2. A formula is valid iff is unsatisifiable.
  3. By semantics of ,


holds

  • iff is valid (1.)
  • iff is valid (3.)
  • iff is unsatisifiable (2.)
  • iff is unsatisfiable (De Morgan)

Kommentare[Bearbeiten | Quelltext bearbeiten]

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)