Disjunktive Normalform

Als Disjunktive Normalform (kurz DNF) wird in der Aussagenlogik eine bestimmt Form von Formeln bezeichnet.

Definition

Eine Formel der Aussagenlogik ist in disjunktiver Normalform wenn sie eine Disjunktion von konjunktiv verknüpften Literalen ist. Literale sind dabei nichtnegierte oder negierte Variablen. Eine Formel in DNF hat also die Form

$\bigvee _{i}\bigwedge _{j}(\neg )x_{ij}.$

Bildung

Jede Formel der Aussagenlogik lässt sich in disjunktive Normalform umwandeln, da sich auch jede boolsche Funktion mit einer DNF darstellen lässt. Dazu genügt es die Zeilen ihrer Wahrheitstabelle abzulesen. Für jede Zeile, die als Resultat eine 1 liefert wird eine Disjunktion gebildet, die alle Variablen der Funktion verknüpft. Variablen, die in der Zeile mit 1 belegt sind, werden dabei nicht negiert und Variablen, die mit 0 belegt sind, werden negiert.

Beispiel für die Bildung der DNF

Gesucht sei eine Formel in DNF für die boolesche Funktion mit drei Variablen x₂, x₁ und x₀, die genau dann den Wahrheitswert 1 (wahr) annimmt, wenn die Dualzahl [x₂x₁x₀]₂ eine Primzahl ist.

Die Wahrheitstafel für diese Funktion hat folgende Gestalt:

x2	x1	x0	Ergebnis	Klausel
0	0	0	0	-
0	0	1	0	-
0	1	0	1	${\bar {x_{2}}}\wedge x_{1}\wedge {\bar {x_{0}}}$
0	1	1	1	${\bar {x_{2}}}\wedge x_{1}\wedge x_{0}$
1	0	0	0	-
1	0	1	1	$x_{2}\wedge {\bar {x_{1}}}\wedge x_{0}$
1	1	0	0	-
1	1	1	1	$x_{2}\wedge x_{1}\wedge x_{0}$

Daraus ergibt sich die Funktion

$y={\bar {x_{2}}}x_{1}{\bar {x_{0}}}\vee {\bar {x_{2}}}x_{1}x_{0}\vee x_{2}{\bar {x_{1}}}x_{0}\vee x_{2}x_{1}x_{0}$

_{Die inneren $\wedge$-Verknüpfungen kann man, analog der Multiplikations-Operatoren als gegeben ansehen, und weglassen}

Weitere Normalformen

Neben der disjunktiven Normalform gibt es in der Aussagenlogik weitere Normalformen, etwa die konjunktive Normalform.

Siehe auch: Verfahren nach Quine und McCluskey, Konjunktive Normalform, Negationsnormalform