Disjunktive Normalformen aussagenlogischer Formeln

Eine Formel der Aussagenlogik ist in disjunktiver Normalform (DNF), wenn sie eine Disjunktion von Konjunktionstermen ist. Ein Konjunktionsterm wird ausschließlich durch die konjunktive Verknüpfung von Literalen gebildet. Literale sind dabei nichtnegierte oder negierte Variablen. Eine Formel in DNF hat also die Form

Der logische Ausdruck in disjunktiver Normalform besteht auf der obersten Ebene ausschließlich aus ODER-Verknüpfungen.

Beispiel: $A\or B \or C \or D$

Dabei können die einzelnen Elemente der ODER-Verknüpfung ($A$, $B$, $C$, $D$) Variablen, ihre Negation oder durch eine UND-Verknüpfung (Konjunktion) von ihnen erhaltene Ausdrücke sein.

Beispiel: $(a\and b)\or (a\and \not b\and c)\or \not a$

In einer verkürzenden Schreibweise, lässt man $\and$ und die Klammern weg. Außerdem schreibt man die Negatation durch einen Überstrich $\ovl x$ für $\not x$. Beispiel: $\bar{a}\bar{a}\bar{c}\vee \bar{a}c\bar{c}\vee ab\bar{c}\vee \bar{a}\bar{b}c\vee \bar{a}bc\vee abc$

Jede Formel der Aussagenlogik lässt sich in die disjunktive Normalform umwandeln, da sich auch jede boolesche Funktion mit einer DNF darstellen lässt. Dazu geht man von ihrer Wahrheitstabelle aus. Für jede Zeile, die als Resultat eine 1 liefert, wird eine Konjunktion gebildet, die alle Variablen der Funktion (der Zeile) verknüpft. Variablen, die in der Zeile mit 1 belegt sind, werden dabei nicht negiert und Variablen, die mit 0 belegt sind, werden negiert. Diese Terme werden auch Minterme genannt. Durch disjunktive Verknüpfung der Minterme erhält man schließlich die disjunktive Normalform.

In der folgenden Wahrheitswertetabelle seien nur die Zeilen angegeben, bei denen unsere Funktion den Wert $1$ annimmt.

$a$	$b$	$c$
0	0	1
1	0	0
1	0	1

Wir können die DNF sofort "ablesen":

Bei dieser Methode wird der Ausdruck um so länger, je mehr Zeilen der Wahrheitswertetabelle den Wert $1$ liefern. Dies bedeutet aber nicht notwendigerweise, dass die Funktionen mit den meisten Einsen, die längsten DNF liefern. Z.B. lliefert die DNF $a\ovl b\ovl c\or \ovl b c$ die gleiche boolesche Funktion wie (1)

Im Allgemeinen verwendet man zum Ermitteln einer minimalen Formel (mit möglichst wenigen Termen) Karnaugh-Veitch-Diagramme oder das Quine-McCluskey-Verfahren.

Eine kanonische disjunktive Normalform (KDNF), auch vollständige disjunktive Normalform genannt, ist eine DNF, die nur Minterme enthält, in denen alle Variablen vorhanden sind, jede Variable genau einmal vorkommt und deren Minterme alle voneinander verschieden sind. Jede Boolesche Funktion besitzt genau eine KDNF.

In der KDNF sind diejenigen Variablenbelegungen, für die die Funktion den Wert 1 annimmt, durch Minterme ausgedrückt, (1) ist also kanonisch.