Jürgen Dix, Frieder Stolzenburg * Institut für Informatik * Universität Koblenz
Übung zu Logik für Informatiker * Blatt 5 * Abgabe bis 16.5.2000, 16.00 Uhr

Aufgabe 5.1 (3 Punkte)
Geben Sie für die folgenden Formeln jeweils eine äquivalente Formel in (a) konjunktiver bzw. (b) disjunktiver Normalform an!

  1. $((A \to B) \vee C) \to ((A \leftrightarrow B) \wedge C)$
  2. $A \to (B \to (C \to A))$
Erzeugen Sie außerdem (c) konjunktive Normalformen mit Hilfe von OTTER oder PL2TME.

Aufgabe 5.2 (2 Punkte)
Betrachten Sie die Formelmenge $M = \big\{ \neg (A \wedge B), (\neg B) \to A \big\}$.

  1. Bestimmen Sie alle Modelle von $M$!
  2. Gilt $M \models (A \wedge \neg B)$?

Aufgabe 5.3 (2 Punkte)
Sei $M$ eine Formelmenge und $F$ eine Formel. Man beweise:

$M \models F$ genau dann, wenn $M \cup \{\neg F\}$ unerfüllbar ist.

Aufgabe 5.4 (3 Punkte)
Geben Sie $Res^n(M)$ für alle $n \ge 0$ sowie $Res^*(M)$ für die folgenden Klauselmengen an! Welche Formeln sind erfüllbar bzw. welche sind unerfüllbar?

  1. $\{\{A,\neg B\},\{A,B\},\{\neg A\}\}$
  2. $\{\{A,B,C\},\{\neg B,\neg C\},\{\neg A,C\}\}$
  3. $\{\{\neg A,\neg B\},\{B,C\},\{\neg C,A\}\}$