Übungsblatt 4 (Mathematische Logik) (Grädel)
Aus Infostudium Wiki
Inhaltsverzeichnis |
Aufgabe 1
Welche der folgenden Sequenzen sind gültig? Beweisen Sie Ihre Antworten semantisch, d. h. mit Hilfe von Interpretationen, und nicht durch Ableitungen im Sequenzenkalkül.
Aufgabe 2
Konstruieren Sie für die folgenden Sequenzen Beweise im Sequenzenkalkül oder falsifizierende Interpretationen:
Aufgabe 3
Weisen Sie die Korrektheit der folgenden Schlussregeln nach, oder geben Sie ein Gegenbeispiel an.
Aufgabe 4
Zwei Formeln heißen erfüllbarkeitsäquivalent, wenn entweder beide erfüllbar oder beide unerfüllbar sind. (Erüllbarkeitsäquivalente Formeln wie etwa X und 
müssen natürlich nicht unbedingt äquivalent sein.)
Eine KNF-Formel ist in m-KNF, wenn sie eine Konjunktion von Disjunktionsklauseln mit je höchstens m Literalen ist, d.h. wenn sie die Form 
mit 
hat.
Zeigen Sie, dass man zu jeder KNF-Formel in Polynomialzeit eine erfüllbarkeitsäquivalente
Formel in 3-KNF konstruieren kann.
