Übungsblatt 2 (Mathematische Logik) (Grädel)
Aus Infostudium Wiki
| Damit das Wiki keine Schwierigkeiten bekommt, bittet es euch, keine direkten Lösungen zu posten. Bitte erklärt euer Vorgehen bei der Bearbeitung der Aufgaben so, dass es andere verstehen und nachvollziehen können. So kann jeder das Ergebnis bestätigen oder gegebenenfalls auf Fehler hinweisen. |
Inhaltsverzeichnis |
Aufgabe 1
a)
In dieser Aufgabe wird vorausgesetzt, dass die Horn-Formeln ein Modell haben. Da eine Horn-Formel eine Konjunktion von Klauseln ist, müssen alle Klauseln ein Modell besitzen. Folglich haben die Klauseln, die nach dem Durchschnitt noch übrig sind, ebenfalls ein Modell.
Würde nach dem Durchschnitt nur die leere Menge übrig bleiben, so ist die Aussage ebenfalls korrekt, da die leere Menge erfüllbar ist und somit ein Modell besitzt.
Ansatz: Damit die Formel 
erfüllt ist, muss jede Unterformel erfüllt sein. Dann eine Art Induktion über die Formeltypen der Horn-Formel.
b)
Eine Horn-Formel kann
- erfüllbar (Tautologie) sein
- nicht erfüllbar sein
Wichtig ist, dass bei einer Horn-Formel nur maximal ein Literal erfüllbar sein darf. Sonst dürfen die Formeln alles sein.
Aufgabe 2
Aufgabe 3
Aufgabe 4
Aufgabe 5
Bilder
Zur Zeit noch ein Test
