Negationsnormalform

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine logische Formel ist in Negationsnormalform (NNF), falls die Negationsoperatoren in ihr nur direkt über atomaren Aussagen vorkommen.

Eine Formel in Negationsnormalform kann in die konjunktive (KNF) oder disjunktive Normalform (DNF) gebracht werden, indem man die Distributivgesetze anwendet.

Im Allgemeinen gibt es für jede aussagenlogische Formel mehr als eine Negationsnormalform. Das kann man sich veranschaulichen, indem man sich vor Augen führt, dass jede konjunktive und jede disjunktive Normalform zugleich auch eine Negationsnormalform ist.

Vorgehensweise[Bearbeiten | Quelltext bearbeiten]

In klassischer Logik kann jede Formel in diese Form gebracht werden, indem man wie folgt vorgeht:

Beispiel[Bearbeiten | Quelltext bearbeiten]

Gegeben sei die folgende Formel:
\neg(A \rightarrow (B \wedge \neg (C \vee D)))

Die Formel ist nicht in NNF, weil Negationen vor nichtatomaren Teilformeln auftreten. Dies ist sowohl vor der äußeren Klammer als auch innerhalb (vor (C \vee D)) der Fall. Daher zieht man die Negation nach innen und formt um:
\neg(A \rightarrow (B \wedge \neg (C \vee D))) \equiv  (A \wedge \neg (B \wedge \neg (C \vee D)))

Da auch in dieser Formel noch komplexe Formeln verneint sind, wird weiter umgeformt:
(A \wedge (\neg B \vee \neg \neg (C \vee D)))

Nun ist noch die hierbei aufgetretene doppelte Negation zu beseitigen:
(A \wedge (\neg B \vee (C \vee D)))

Damit ist die NNF erreicht, weil \neg nur noch vor atomaren Teilformeln (d.h. Variablen) auftritt.

Anmerkungen[Bearbeiten | Quelltext bearbeiten]