| Haevelin |
Zur Erfüllbarkeit einer aussagenlogische Formel
Erfüllbarkeit kann man wie folgt prüfen. Wenn die Formel nicht unerfüllbar ist, dann ist sie erfüllbar.
Ich erhalte folgende Äquivalenz:
Formel F ist unerfüllbar <==>
1. Überführe die Formel in disjunktive Normalform
2. Die Modelle der Formel erhält man durch die einzelnen Konjunkte. Die Formel ist unerfüllbar, wenn in jedem Konjunkt eine Aussagenvariable sowohl negiert als auch nicht-negiert auftritt.
Zum Beweis:
<== ist trivial, weil durch ein solches Auftreten der Aussagenvariabel die disjunktive Normalform FALSCH ist, und die Formel daher unerfüllbar ist.
==> aus der Unerfüllbarkeit folgt, dass alle Disjunktionsglieder der DNF falsch sind. Sind dann notwendigerweise in jedem Disjunkt eine Aussagenvariable negiert als auch nicht negiert? Sicherlich wenn dies der Fall ist, dann sind alle Disjunktionsglieder falsch. Aber können diese auch alle falsch sein, wenn nicht ein Aussagenglied positiv und negiert vorkommt? Jede Variablenbelegung, die in Konjunktion steht kann erfüllt werden, falls nicht eine Aussagenvariable sowohl positiv als auch negiert vorkommt. |
