Disjunktive Normalform

Aufbau und Bedeutung der DNF

Die disjunktive Normalform (DNF) ist eine normierte Darstellung Boolescher Funktionen in der Aussagenlogik und Booleschen Algebra. Eine Formel ist genau dann in DNF, wenn sie aus einer Disjunktion, also einer ODER-Verknüpfung, von Konjunktionstermen besteht.

Ein Konjunktionsterm ist eine UND-Verknüpfung von Literalen. Ein Literal ist entweder eine nichtnegierte Variable, etwa A, oder eine negierte Variable, etwa ¬A. Allgemein hat eine DNF die Form ∨ᵢ ∧ⱼ (¬)xᵢⱼ.

Auf der obersten Ebene dürfen ausschließlich ODER-Verknüpfungen vorkommen. Darunter liegen die UND-Verknüpfungen der Literale. Weitere ODER-Verknüpfungen in tiefer geklammerten Ebenen sind nicht erlaubt; die DNF besitzt somit höchstens diese zwei logischen Ebenen. Die Negation darf nur auf einzelne Literale angewendet werden. Üblicherweise werden Klammern und die Zeichen für die UND-Verknüpfung weggelassen, sodass beispielsweise (A ∧ B) ∨ (A ∧ B ∧ C) ∨ (B ∧ C) ∨ D als AB ∨ ABC ∨ BC ∨ D geschrieben wird.

DNF ist besonders bei großen Aussagensystemen nützlich. Im Artikel wird als Beispiel die logische Beschreibung einer Flugzeugelektrik mit 50 Eingabeparametern und Hunderten von Kombinationsmöglichkeiten genannt. Eine sprachlich formulierte Bedingung wie „wenn der Fahrwerksensor die Landung meldet, darf die Schubumkehr aktiviert werden“ wird zunächst in eine logische Formel und anschließend in DNF überführt. Die Formel kann dadurch zunächst länger werden. Danach lassen sich logische Doppelungen und Überschneidungen mit einem Karnaugh-Veitch-Diagramm oder dem Quine-McCluskey-Verfahren beseitigen. Das Ergebnis kann in Steuersoftware oder in der Hardware einer Steuerelektronik umgesetzt werden. Das Gegenstück zur DNF ist die konjunktive Normalform (KNF), eine UND-Verknüpfung von ODER-Aussagen und Einzelaussagen.

Bildung aus der Wahrheitstabelle

Jede Formel der Aussagenlogik und jede Boolesche Funktion lässt sich in eine DNF umwandeln. Dazu liest man die Wahrheitstabelle zeilenweise aus. Für jede Zeile mit dem Funktionswert 1 wird ein Konjunktionsterm gebildet, der alle Variablen der Funktion enthält:

• Eine Variable mit dem Wert 1 wird nicht negiert.
• Eine Variable mit dem Wert 0 wird negiert.

Diese vollständigen Konjunktionsterme heißen Minterme. Verknüpft man alle zu den 1-Zeilen gehörenden Minterme durch ODER, erhält man die DNF der Funktion. Dieses Verfahren liefert im Allgemeinen keine minimale Formel, also keine Darstellung mit der kleinstmöglichen Zahl von Termen. Zur Minimierung dienen insbesondere Karnaugh-Veitch-Diagramme und das Quine-McCluskey-Verfahren.

In der Schreibweise Boolescher Schaltungen werden UND-verknüpfte Variablen oft wie Faktoren einer Multiplikation behandelt. Deshalb können die UND-Zeichen entfallen; ein solcher Ausdruck wird auch Produktterm genannt. Für den Produktterm gilt: Ist eine beteiligte Variable 0, ist der gesamte Produktterm 0. Er hat genau dann den Wert 1, wenn alle in ihm vorkommenden Variablen den Wert 1 haben. CPLDs verwenden disjunktiv, also durch ODER, verknüpfte Produktterme zur Definition ihrer Funktion.

Beispiel mit drei Variablen

Gesucht ist eine DNF für eine Boolesche Funktion mit den drei Variablen A, B und C, die genau dann den Wahrheitswert 1 annimmt, wenn die Dualzahl [ABC]₂ eine Primzahl ist.

Für jede passende Belegung werden die Variablen entsprechend der Wahrheitstabelle zu einem Minterm verbunden. Im Beispiel entstehen die vier Minterme ¬A ∧ B ∧ ¬C, ¬A ∧ B ∧ C, A ∧ ¬B ∧ C und A ∧ B ∧ C. Ihre Disjunktion ergibt die kanonische DNF:

(¬A ∧ B ∧ ¬C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C).

Eine in DNF dargestellte Funktion kann auch kompakter geschrieben werden. Der Ausdruck y = x̄₂x₁x̄₀ ∨ x̄₂x₁x₀ ∨ x₂x̄₁x₀ ∨ x₂x₁x₀ lässt sich als vollständig geklammerter Boolescher Ausdruck e = ((x̄₂) ∧ x₁) ∨ (x₂ ∧ x₀) und anschließend als Produktterm-Darstellung e = x̄₂x₁ + x₂x₀ schreiben. Die einzelnen Schreibweisen stellen dieselbe Funktion dar. Jede DNF besitzt außerdem eine äquivalente KNF.

Kanonische und orthogonale Formen

Die kanonische disjunktive Normalform (KDNF), auch vollständige DNF genannt, ist eine DNF mit paarweise verschiedenen Mintermen, in denen jede Variable genau einmal vorkommt. Sie beschreibt genau diejenigen Variablenbelegungen durch Minterme, für die die Funktion den Wert 1 annimmt. Jede Boolesche Funktion besitzt genau eine KDNF, abgesehen von der Reihenfolge ihrer Minterme.

Eine orthogonale disjunktive Normalform (ODNF) ist eine DNF, deren Konjunktionen paarweise disjunkt sind, also nicht gleichzeitig den Wert 1 annehmen und daher 0 ergeben, wenn sie miteinander verknüpft werden. Eine ODNF kann durch Orthogonalisierungsverfahren aus einer nichtorthogonalen DNF gewonnen werden. Auch das Auslesen ausschließlich nichtüberlappender Blöcke aus einem Karnaugh-Veitch-Diagramm führt zu einer ODNF.

Im Allgemeinen gibt es für eine Boolesche Funktion mehrere ODNF. Die KDNF ist dagegen grundsätzlich orthogonal und eindeutig. ODNF lassen sich wegen ihrer Orthogonalität algorithmisch einfacher verarbeiten und werden deshalb häufig im maschinellen Logikentwurf eingesetzt. Beispielsweise kann eine ODNF in eine antivalente Normalform umgerechnet werden, indem man alle Disjunktionsoperatoren durch Antivalenzoperatoren ersetzt und den Ausdruck anschließend vereinfacht.

Minimierung und weitere Normalformen

Eine disjunktive Normalform heißt disjunktive Minimalform oder minimale disjunktive Normalform, wenn keine äquivalente Darstellung derselben Ausgabefunktion mit weniger Produkttermen existiert. Haben zwei äquivalente Darstellungen gleich viele Produktterme, muss die minimale Form zusätzlich so gewählt sein, dass die Anzahl der Eingänge in die Produktterme nicht größer ist als in jeder anderen solchen Darstellung.

Die Minimierung ist von der zunächst aus der Wahrheitstabelle gewonnenen DNF zu unterscheiden: Die Wahrheitstabelle liefert eine vollständige Darstellung, aber nicht notwendig die kürzeste. Für die praktische Vereinfachung werden insbesondere Karnaugh-Veitch-Diagramme und das Quine-McCluskey-Verfahren verwendet.

Neben DNF und KNF gibt es in der Aussagenlogik weitere Normalformen, insbesondere die Negationsnormalform. Die DNF bleibt dabei durch ihre charakteristische Struktur aus ODER-verknüpften UND-Terms mit einzelnen, möglicherweise negierten Variablen gekennzeichnet.