Negationsnormalform - LinkFang.de





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):
    • [math]P \rightarrow Q \equiv \neg P \or Q[/math]
    • [math]\neg(P \rightarrow Q) \equiv P \and \neg Q[/math]
    • [math]P \leftrightarrow Q \equiv (P \and Q) \or (\neg P \and \neg Q)[/math]
  • 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:
[math]\neg(A \rightarrow (B \wedge \neg (C \vee D)))[/math]

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

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

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

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

Anmerkungen


Kategorien: Mathematische Logik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Negationsnormalform (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.