minimale Modell

Rapha
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 6. Sep 2009 17:45

minimale Modell

Beitrag von Rapha » 9. Sep 2010 20:35

wir haben uns grade die klausur von ss07 angeschaut und hängen schon an aufgabe 2c) fest

kann uns jemand erklären, wie wir das minimale modell aus der hornformel herausbekommen?

aus der tabelle von der übung wurden wir nicht so recht schlau...

Benutzeravatar
John
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 167
Registriert: 12. Dez 2008 17:41
Wohnort: E-Pool

Re: minimale Modell

Beitrag von John » 9. Sep 2010 21:02

Wie man einfach auf die Modelle in der Tabelle kommt, weiß ich auch nicht. Mit dem Horn-Erfüllbarkeitstest kannst du aber schnell ermitteln, was das minimale Modell ist.

Voraussetzung ist eine Menge nicht-negativer Hornklauseln (also mindestens ein positives Literal pro Klausel), nennen wir die Menge X. Ergebnis ist eine Menge, nennen wir sie M, die dein minimales Modell ist. In der Menge befinden sich die Literale, die 1 sein müssen. Nun iterierst du wiederholt über die Klauselmenge X, bis deine Ergebnismenge M sich nicht mehr ändert, und in jeder Iteration machst du folgendes:

Für jede Klausel \(C \in X\) prüfst du, was du am aktuellen Modell M verändern musst, um die Klausel zu erfüllen. Sei \(C = \{\neg q_1, ..., \neg q_r, q\}\). Falls eine der negativen Literale noch nicht in M ist, ist die Klausel bereits erfüllt. Dann weiter. Ansonsten, also wenn \(q_1, ... q_r\) bereits alle in M sind, nimmst du auch q in M auf.

Das erste Literal, was du also in dein Modell M aufnimmst, ist am Anfang immer eins aus einer positiven Hornklausel der Form \(\{q\}\). Denn für solche Klauseln muss q wahr sein. Jetzt wo q = 1 ist, schaust du also, ob es eine (oder mehrere) Klausel(n) der Form \(\{\neg q, p\}\) gibt, dann musst du hier auch p in dein Modell M aufnehmen, um diese Klausel(n) wahrzumachen. Usw. Das ganze terminiert recht schnell spätestens nach n-1 Iterationen bei n Variablen.

EDIT:
Wenn du erstmal das minimale Modell hast, kannst du von dort aus auch effizienter alle anderen erfüllende Belegungen ermitteln. Dazu nimmst du weiterhin alle Variablen im minimalen Modell als 1 an, denn diese müssen ja wahr sein. Mit den verbleibenden Variablen bildest du alle möglichen Kombinationen von wahr/falsch und schaust, ob die Belegung ebenfalls ein Modell ist.
DON'T PANIC

Antworten

Zurück zu „Archiv“