Disjunktive Normalform (dnf)

Definition - Was bedeutet Disjunctive Normal Form (DNF)?

Disjunktive Normalform (DNF) ist die Normalisierung einer logischen Formel in der Booleschen Mathematik. Mit anderen Worten, eine logische Formel wird als disjunktive Normalform bezeichnet, wenn es sich um eine Disjunktion von Konjunktionen mit jeder Variablen handelt und ihre Negation einmal in jeder Konjunktion vorhanden ist. Alle disjunktiven Normalformen sind nicht eindeutig, da alle disjunktiven Normalformen für denselben Satz einander äquivalent sind.

Disjunktive Normalform wird häufig in Bereichen wie der automatisierten Theoremprüfung verwendet.

Technische.me erklärt die disjunktive Normalform (DNF)

Eine logische Formel liegt genau dann in disjunktiver Normalform vor, wenn eine oder mehrere Konjunktionen eines oder mehrerer Literale abwechseln. Eine Formel gilt als vollständig disjunktive Normalform, wenn alle beteiligten Variablen in jeder Klausel nur einmal dargestellt werden. Ähnlich wie bei der konjunktiven Normalform sind die Satzoperatoren in disjunktiver Normalform dieselben: AND, OR und NOT.

Alle logischen Formeln können in eine äquivalente disjunktive Normalform umgewandelt werden. In einigen Fällen ist jedoch eine exponentielle Explosion der logischen Funktion aufgrund der Umwandlung in eine disjunktive Normalform möglich. Ein weiterer hervorstechender Punkt ist, dass jede eindeutige Boolesche Funktion nur durch eine und eine eindeutige vollständig disjunktive Normalform dargestellt werden kann. Mit Hilfe von Techniken wie der Wahrheitstabellenmethode, Wahrheitsbäumen oder einer Tabelle logischer Äquivalenzen kann eine disjunktive Normalform für logische Formeln erzeugt werden. K-DNF, eine Variation der disjunktiven Normalform, ist weit verbreitet und beliebt bei der Untersuchung der Komplexität von Berechnungen.