Normalformen (DNF, CNF)

Definitionen:

• Variable: v₁,...
• Literal: v oder ¬v
• DNF-Klausel: Konjunktion von Literalen
• DNF-Formel: Disjunktion von Klauseln
• CNF-Klausel: Disjunktion von Literalen
• CNF-Formel: Konjunktion von Klauseln

Def: Formeln F und G heißen äquivalent, wenn Mod(F) = Mod(G).

Satz: zu jeder Formel F existiert äquivalente Formel G in DNF und äquivalente Formel G' in DNF.