Logik:Klausuren/20.02.2002/B.7 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung[Bearbeiten]
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[Bearbeiten]
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.
