Logik:Klausuren/20.02.2002/B.7 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
Zu den Regeln des Algorithmus zur Transformation einer aussagenlogischen Formel in konjunktive Normalform fügen wir die folgende Regel hinzu:
$ \frac{((G_1 \and G_2 ) \or G_1 )}{G_1} $
a) Ist der Algorithmus mit dieser zusätzlichen Regel noch korrekt?
$ ja \ \ \Box \qquad \qquad nein \ \ \Box $
Beweisen Sie Ihre Antwort.
b) Ist der Algorithmus mit dieser zusätzlichen Regel noch vollständig, d.h. kann immer
noch jede aussagenlogische Formel in konjunktive Normalform transformiert werden?
$ ja \ \ \Box \qquad \qquad nein \ \ \Box $
Beweisen Sie Ihre Antwort.
2. Lösung
a) Ja. Absorptionsregel (siehe Satz 3.17)
b) Ja. Der Algorithmus war vorher vollständig, also auch nach der Hinzunahme einer neuen Regel immer noch vollständig, da man die neue Regel ignorieren kann.
