Subsumieren von Klauseln

Question

Aufgabe:

Wir sollen folgendes Begründen:

Enthält eine Menge M von Klauseln zwei Klauseln K1 und K2 von denen die eine, K1, die andere, K2, subsumiert, so kann man K2 aus M entfernen, ohne die Erfüllbarkeit von M zu verändern.

Ansatz:

Ich weiß das eine Klausel K1 eine andere Klausel K2 subsumiert, falls K1 auch in K2 vorkommt.

Also z.B:  A2 ∨ ¬A4 subsumiert ¬A1 ∨ ¬A4 ∨ A5 ∨ A2.

Ich weiß aber nicht, wie ich das auf die Aufgabe anwenden soll.

Answer 1

Antwort mit KI erzeugt

Subsumierung von Klauseln

Bevor wir direkt auf deine Aufgabe eingehen, erläutern wir zunächst, was Subsumierung im Kontext der logischen Klauseln bedeutet. Eine Klausel \(K_1\) subsumiert eine Klausel \(K_2\), wenn jedes Literal (jede Variable oder ihre Negation) in \(K_1\) auch in \(K_2\) vorkommt. Das bedeutet, jede Interpretation, die \(K_1\) wahr macht, macht auch \(K_2\) wahr.

Gegeben sind zwei Klauseln \(K_1\) und \(K_2\) innerhalb einer Menge von Klauseln \(M\), wobei \(K_1\) die Klausel \(K_2\) subsumiert. Das Ziel ist es zu begründen, dass das Entfernen von \(K_2\) aus der Menge \(M\) die Erfüllbarkeit der Menge \(M\) nicht verändert.

Begründung:

Gegeben sind die Klauseln \(K_1\) und \(K_2\) mit der Eigenschaft, dass \(K_1\) die Klausel \(K_2\) subsumiert. Das heißt implizit, dass \(K_2\) mindestens alle Literale von \(K_1\) plus möglicherweise weitere Literale enthält.

Die Subsumierung bedeutet, dass jede Belegung der Literale, die \(K_1\) wahr macht, automatisch \(K_2\) wahr machen muss, da \(K_2\) alle Literale von \(K_1\) enthält und möglicherweise zusätzlich weitere, die in der Wahrheitsfindung irrelevant sind, solange \(K_1\) wahr ist. Das bedeutet, dass \(K_1\) eine "strengere" Bedingung stellt als \(K_2\).

Wenn eine Belegung der Literale existiert, die \(M\) wahr macht, dann wird diese Belegung auch \(K_1\) wahr machen. Da \(K_1\) \(K_2\) subsumiert, macht dieselbe Belegung auch \(K_2\) wahr. Somit ist das Vorhandensein von \(K_2\) in der Menge \(M\) redundant, da jede Lösung, die \(K_1\) erfüllt, automatisch \(K_2\) erfüllt.

Umgekehrt, wenn \(K_2\) entfernt wird, bleibt die Bedingung \(K_1\) in \(M\) erhalten. Da \(K_1\) die strengere Bedingung ist, wird die Erfüllbarkeit von \(M\) nicht verändert durch das Entfernen von \(K_2\).

Schlussfolgerung:

Das Entfernen von \(K_2\) aus der Menge \(M\) verändert die Erfüllbarkeit von \(M\) nicht, weil jede Lösung, die \(M\) erfüllt, bereits durch die Erfüllung von \(K_1\) sichergestellt ist. \(K_2\) ist in Gegenwart von \(K_1\) redundant, da \(K_1\) durch die Subsumierung die selben oder strikteren Anforderungen an die Lösungen stellt als \(K_2\). Somit ist die Entfernung von \(K_2\) in Hinblick auf die Erfüllbarkeit von \(M\) ohne Einfluss.