Hausaufgabe 1.4 - minimale Belegung

[dripper]

Hallo,
Wo steht eigentlich der Algorithmus für die Bestimmung der minimale Belegenung eines Hornklausels und was bedeutet eine minimale Belegung?
Ich kann leider das in den Folien nicht finde.

[olg]

Fgdi2-Folien, Seite 42ff. ist der Algorithmus angegeben

Unter http://de.wikipedia.org/wiki/Markierungsalgorithmus gibt es den Algorithmus in einer etwas praktischeren Form angegeben.

[dripper]

Danke für den Link, aber leider kann ich noch nicht den Algorithmus verstehen.
Kannst du mir vielleicht eines Beispiel geben wie man nach diesem Algorithmus rechnet?

[Der_olle_Schwoebel]

Das hier ist ein praktisches Beispiel und ziemlich gut erklärt meiner Meinung nach:
http://www.onli-blogging.de/index.php?/ ... thmus.html

[kutschke]

Hi!
Der Algorithmus steht auch im Skript, und zwar kommt der im Beweis des Satzes vor, wo es darum geht, dass es diesen Algorithmus gibt. Der Prof hat ihn nicht auf den Power-Point-Folien gehabt, hat es aber "per Hand" auf Overhead-Folien gemacht. Naja, wie auch immer, im Skript gibts den jedenfalls.

[Puppetmaster]

Kann mir mal wer erklären, was die letzten beiden Zeilen bei der Lösung zu bedeuten haben?

[s4lph0r]

So wie ich mir das aus der Vorlesung übernommen habe, müsste der Algorithmus zur Findung der minimalen Belegung in etwa so Ablaufen:

Ich nutze als Beispiel das, was auch unter dem Link von Der_olle_Schwoebel bearbeitet wird.

Dort ist folgende Menge von Hornklauseln gegeben: {a,¬c}, {c}, {¬a, b, ¬c}, {¬b, ¬c, a, ¬d}

Zunächst ist es meistens so, dass man in dieser Menge eine einstellige Klausel mit einer nicht-negierten Variable hat, das ist in diesem Fall {c}.

Somit weist man zunächst c den Wert 1 zu.
In Folge dessen streicht man nun das ¬c aus allen Klauseln, in denen es Vorkommt. Die Klauseln in denen c unnegiert vorkommt, werden komplett gestrichen, da sie nun automatisch wahr werden. ( Weil die Variablen quasi alle durch ein "oder" verbunden sind. )

Somit erhält man die Klauselmenge {a}, {¬a, b}, {¬b, a, ¬d}

Hier wird schnell ersichtlich, dass das ganze nun nochmal auf a angewandt wird.
Also wird a auch auf 1 gesetzt.

Somit bleibt nur noch die Klauselmenge {b} übrig.

Setzt man b jetzt auch noch auf 1 bleibt keine Klausel mehr übrig, folglich ist es egal, welchen Wert d bekommt.
Also bekommt d einfach den Wert 0.

Und so haben wir auch schon die selbe Belegung wie unter dem Link vorgestellt: a=b=c=1 und d=0.

Insgesamt hat die Klauselmenge 2 erfüllende Belegungen, da sie auch für d=1 erfüllt ist.


Ich hoffe mal das meine Beschreibung für den Algorithmus verständlich und vor allem auch korrekt ist.
Ein Punkt, für den ich noch keinen Richtigen Rat wüsste ist, wie man vorzgehen hat, wenn zu Beginn keine einstellige Klausel mit einem nicht-negierten Wert vorhanden ist.

Für Tipps und Kritik bin ich natürlich dankbar!

[Puppetmaster]

Dann ist es unerfüllbar.

Meine Frage nach den letzten beiden Zeilen wurde damit aber leider nicht beantwortet.

[mister_tt]

Mit dem Algorithmus willst du ja eine minimale erfüllende Belegung für deine Hornklausel-Menge finden. Und die letzten beiden Zeilen besagen, dass diese Belegung wie folgt aussieht:
q = r = s = t = 1
p = u = v = 0

Dort wird es halt nur offiziell mit einer Belegungsfunktion J ausgedrückt...