Negationsnormalform
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
In klassischer Logik kann jede Formel in diese Form gebracht werden, indem man wie folgt vorgeht:
- Man löst die in ihr vorkommenden materialen
Implikationen und Bikonditionale
mittels der für diese geltenden Äquivalenzgesetze auf. Beispiele sind (Siehe
dazu auch: Implikation):
- Man verschiebt mittels der De Morganschen Gesetze die Negationen nach innen und beseitigt dabei zugleich gegebenenfalls auftretende doppelte Negationen
Beispiel
Gegeben sei die folgende Formel:
Die Formel ist nicht in NNF, weil Negationen vor nichtatomaren Teilformeln
auftreten. Dies ist sowohl vor der äußeren Klammer als auch innerhalb (vor )
der Fall. Daher zieht man die Negation nach innen und formt um:
Da auch in dieser Formel noch komplexe Formeln verneint sind, wird weiter
umgeformt:
Nun ist noch die hierbei aufgetretene doppelte Negation zu
beseitigen:
Damit ist die NNF erreicht, weil nur noch vor atomaren Teilformeln (d.h. Variablen) auftritt.
Basierend auf einem Artikel in: Wikipedia.de Seite zurück© biancahoegel.de
Datum der letzten Änderung: Jena, den: 05.11. 2020