03 Aussagenlogik

Normalformen

Literal

Ein Literal ist eine Formel (oder die negation einer Formel).

CNF und DNF

CNF: Konjunktion von Disjunktionen von Literalen $F=(A\vee B)\wedge (C\vee \neg D)$ DNF: Disjunktion von Konjunktionen von Literalen $F=(A\wedge B)\vee (C\wedge \neg D)$

Beispiel

• $A\wedge \neg B\wedge \neg C$ ist sowohl in CNF (jede Klausel besteht aus einem Literal) und DNF (alles ist eine Klausel)
• $A\vee (B\vee C)$ ist sowohl in CNF und in DNF, da $A\vee (B\vee C)\equiv A\vee B\vee C$