Logik:Klausuren/28.02.2003/2.4 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
a) Der Algorithmus zur Transformation einer prädikatenlogischen Formel in Pränexnor- malform soll dahingehend erweitert werden, dass auch Formeln, die den binären Junktor ! enthalten, transformiert werden können. Ergänzen Sie dazu die Regel- fragmente in der letzten Zeile derart, dass die transformierten Formeln jeweils mit einem Quantor beginnen.
$ \frac{ \neg ( \forall \ X)F}{(\exists X) \neg F}\qquad \frac{\neg (\exists X)F}{(\forall X) \neg F}\qquad \frac{((Q X)F \wedge G)}{(Q X)(F \wedge G)}\qquad \frac{(F \wedge (Q X)G}{(Q X)(F \wedge G)}\qquad \frac{((Q X)F \vee G)}{(Q X)(F \vee G)}\qquad \frac{(F \wedge (Q X)G)}{(Q X)(F \vee G)} $
$ \frac{((\exists X)F \rightarrow G)}{}\qquad \frac{((\forall X)F \rightarrow G)}{}\qquad \frac{(F \rightarrow(\exists X)G)}{}\qquad \frac{F \rightarrow(\forall X)G)}{} $
b) Transformieren Sie die prädikatenlogische Formel
$ \neg ((\forall X)q(X) \rightarrow (\exists X)(\forall Y )\neg (p(Y ) \wedge (\neg p(X) \vee \neg q(X)))) $
unter Verwendung der von Ihnen in (a) aufgestellten Regeln in Pränexnormalform.
