DNF vs KNF
-
zwei gleiche meine ich.
-
Seh ich genauso. Jede Variable höchstens einmal pro Konjunktionsterm, sonst ist es keine DNF.
-
Eine solche Definition von DNF war mir nicht bekannt. Mit dieser Definition macht Bashars Aussage dann natürlich wesentlich mehr Sinn ;).
-
life schrieb:
Eine solche Definition von DNF war mir nicht bekannt. Mit dieser Definition macht Bashars Aussage dann natürlich wesentlich mehr Sinn ;).
Sonst könnte man eine DNF beliebig aufblähen und keine obere Schranke für die Länge für Formeln in DNF angeben. Egal. Es gibt Formeln, deren kleinste DNF nach obiger Definition die Länge O(2^n) haben. Checken ist also linear, aber die Konstruktion dieser DNF braucht natürlich im Worst-Case O(2^n).
-
Eine DNF ist es ja immer noch, egal wie oft die Literale in einem Monom vorkommen. Wenn man das exakt einmalige Vorkommen jedes Literals fordert heißt das ganze kanonische DNF
