imported>Neutronstar2 am 28. Juni 2023 um 14:10 Uhr

2023-06-28T14:10:46Z

Neue Seite

{{Belege}}
Eine [[Logik|logische]] Formel ist in '''Negationsnormalform''' (NNF), falls die [[Negation]]soperatoren in ihr nur direkt über atomaren Aussagen vorkommen.

Eine Formel in Negationsnormalform kann in die [[konjunktive Normalform|konjunktive]] (KNF) oder [[disjunktive Normalform]] (DNF) gebracht werden, indem man die [[Distributivgesetz]]e 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 [[Klassische Logik|klassischer Logik]] kann jede Formel in diese Form gebracht werden, indem man wie folgt vorgeht:
* Man löst die in ihr vorkommenden [[Implikation#Wahrheitsfunktionale Implikation|materialen Implikationen]] und [[Bikonditional]]e mittels der für diese geltenden Äquivalenzgesetze auf. Beispiele sind (Siehe dazu auch: [[Implikation#Eigenschaften_und_logische_Gesetze|Implikation]]):
**<math>P \rightarrow Q \equiv \neg P \lor Q</math>
**<math>\neg(P \rightarrow Q) \equiv P \land \neg Q</math>
**<math>P \leftrightarrow Q \equiv (P \land Q) \lor (\neg P \land \neg Q)</math>
* Man verschiebt mittels der [[De Morgansche Gesetze|De Morganschen Gesetze]] die Negationen nach innen und beseitigt dabei zugleich gegebenenfalls auftretende doppelte Negationen

== Beispiel ==
Gegeben sei die folgende Formel:<br />
<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:<br />
<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:<br />
<math>(A \wedge (\neg B \vee \neg \neg (C \vee D)))</math>

Nun ist noch die hierbei aufgetretene doppelte Negation zu beseitigen:<br />
<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.

[[Kategorie:Mathematische Logik]]
[[Kategorie:Normalform]]

Negationsnormalform - Versionsgeschichte

imported>Neutronstar2 am 28. Juni 2023 um 14:10 Uhr