KNF in 3-KNF überführen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:32 Mi 15.11.2006 | | Autor: | AGO |
| Aufgabe | Zwei Formeln heißen erfüllbarkeits¨aquivalent, wenn entweder beide erfüllbar oder beide unerf
üllbar sind. (Erfüllbarkeits¨aquivalente Formeln wie etwa X und ¬X müssen natürlich nicht
unbedingt ¨aquivalent sein.)
Eine KNF-Formel ist in m-KNF, wenn sie eine Konjunktion von Disjunktionsklauseln mit je
höchstens m Literalen ist, d.h. wenn sie die Form Vi(Yi1 _ · · · _ Yiki) mit ki < m hat.
Zeigen Sie, dass man zu jeder KNF-Formel in Polynomialzeit eine erfüllbarkeits¨aquivalente
Formel in 3-KNF konstruieren kann. |
Guten morgen erstmal,
also mein Lösungsansatz war die gegebene KNF Termweise zu betrachten, und dann für jeden Termzu entscheiden ob er lösbar unlösbar oder eine Tautologie ist. Das könnte ich dann in meine neue Formel entsprechend durch andere Variablen übertragen.
Allerdings führte das bisher alles nicht zum Erfolg, daher wäre ich für einen Gedankenansporn recht dankbar.
Grüße,
AGo
# Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Fr 17.11.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
