Als disjunktive Normalform (kurz DNF) wird in der Booleschen Algebra eine in besonderer Weise normierte Funktionsdarstellung Boolescher Funktionen bezeichnet.
Definition
Eine Formel der Aussagenlogik ist in disjunktiver Normalform, 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
Eine DNF besteht aus Mintermen, die miteinander disjunktiv verknüpft sind. Diejenigen Variablenbelegungen, für die die Funktion den Wert 1 annimmt, werden durch Minterme ausgedrückt. Diese Minterme werden disjunktiv verknüpft.
Einfache Erklärung für Mathematiklaien
Bei der disjunktiven Normalform handelt es sich um einen logischen Ausdruck, der aus ODER-Verknüpfungen (Disjunktion - nicht ausschließendes ODER) besteht. Der logische Ausdruck besteht in der obersten Ebene ausschließlich aus ODER-Verknüpfungen.
Beispiel: A ODER B ODER C ODER D; A∨B∨C∨D
Dabei können die einzelnen Elemente der ODER-Verknüpfung (A, B, C, D) kompliziertere Ausdrücke sein, die dann auch eine UND-Verknüpfung (Konjunktion) enthalten können.
Beispiel: (A UND B) ODER (A UND B UND C) ODER (B UND C) ODER D; (A∧B)∨(A∧B∧C)∨(B∧C)∨D
Hier handelt es sich um eine Disjunktion (ODER-Verknüpfung) von drei Konjunktionen (UND-Verknüpfungen) und der Aussage D - genau das ist die disjunktive Normalform.
Vereinbarungsgemäß werden die Klammern und die Zeichen (Operatoren) für die UND-Verknüpfung nicht mitgeschrieben.
Beispiel: AB∨ABC∨BC∨D
Das ganze ist häufig auch noch mit dem NICHT-Operator kombiniert.
Beispiel:
Zusätzlich zu der bereits oben erwähnten Forderung, dass der logische Ausdruck in der obersten Ebene außschließlich aus ODER-Verknüpfungen besteht (ODER-Ebene), darf es keine weiteren ODER-Verknüpfungen in tiefer geklammerten Ebenen geben. Eigentlich sind nur zwei Ebenen zulässig: die obere Ebene der ODER-Verknüpfungen (ODER-Ebene) und die untere Ebene der UND-Verknüpfungen (UND-Ebene). Eine tiefere Verschachtelung gibt es nicht. Lediglich die Negation darf für die Elemente der UND-Ebene noch verwendet werden.
Das Ganze geht auch anders herum: eine UND-Verknüpfung von ODER-Aussagen und Einzelaussagen. Das ist dann aber die konjunktive Normalform (KNF) - das Gegenstück zur disjunktiven Normalform (DNF).
Praktischen Nutzen bringen solche Normalformen bei großen Aussagensystemen - beispielsweise bei der logischen Beschreibung der Flugzeugelektrik mit 50 Eingabeparametern und Hunderten von Kombinationsmöglichkeiten. Das System wird erst einmal von der wörtlichen Beschreibung in logische Formeln umgewandelt - z.B. "wenn der Fahrwerksensor die Landung meldet, darf die Schubumkehr aktiviert werden". Diese Ansammlung von logischen Ausdrücken wird dann einheitlich in die DNF umgewandelt. Dabei wird der logische Ausdruck noch länger. In einem weiteren Schritt erfolgt dann eine Vereinfachung des logischen Ausdrucks mittels Karnaugh-Veitch-Diagramm (dabei werden logischen Doppelungen entfernt und Überschneidungen berücksichtigt). Der letztendlich errechnete logische Ausdruck wird dann in die Steuersoftware integriert bzw. hardwaremäßig in der Steuerelektronik umgesetzt.
Bildung
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 genügt es, die Zeilen ihrer Wahrheitstabelle abzulesen. 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 Klauseln werden auch Minterme genannt. Durch disjunktive Verknüpfung der Minterme erhält man schließlich die dijunktive Normalform.
Auf diese Weise erhält man allerdings in der Regel keine minimale Formel, das heißt eine Formel mit möglichst wenig Klauseln. Will man eine minimale Formel bilden, so kann man dies etwa mit Hilfe von Karnaugh-Veitch-Diagrammen (kurz KV-Diagrammen) tun.
Beispiel für die Bildung der DNF
Gesucht sei eine Formel in DNF für die boolesche Funktion mit drei Variablen x2, x1 und x0, die genau dann den Wahrheitswert 1 (wahr) annimmt, wenn die Dualzahl [x2x1x0]2 eine Primzahl ist.
Die Wahrheitstafel für diese Funktion hat folgende Gestalt:
| x2 | x1 | x0 | Ergebnis | Monome* |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | - |
| 0 | 0 | 1 | 0 | - |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | - |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | - |
| 1 | 1 | 1 | 1 |
Daraus ergibt sich die Funktion
oder als vollständig geklammerten Booleschen Ausdruck:
ist das gleiche wie
Die inneren -Verknüpfungen werden analog zu Multiplikations-Operatoren gesehen und können deshalb weggelassen werden. Sie werden auch als Produktterm bezeichnet.
Die Bestimmung des Wahrheitswertes eines Produktterms erfolgt wie in der Mathematik durch Multiplikation der Werte der logischen Variablen. Ist eine der beteiligten Variablen Null, so ist der Wert des gesamten Produktterms Null, der Produktterm nimmt den Wert Eins genau dann an, wenn alle Variablen in ihm den Wert Eins haben.
CPLDs verwenden disjunktiv (ODER) verknüpfte Produktterme, um ihre Funktion zu definieren.
Kanonische disjunktive Normalform
Eine kanonische disjunktive Normalform (KDNF) ist eine DNF, die nur Minterme enthält, in denen alle Variablen vorhanden sind, jede Variable genau einmal vorkommt und deren Minterme alle von einander verschieden sind.[1] Jede Boolesche Funktion besitzt genau eine KDNF.
Weitere Normalformen
Neben der disjunktiven Normalform gibt es in der Aussagenlogik weitere Normalformen, etwa die konjunktive Normalform und die Negationsnormalform.
Siehe auch
Bemerkungen
- ↑ In manchen Quellen (z.B. Obershelp W., Vossen G., Rechneraufbau und Rechnerstruckturen) versteht man unter DNF genau diese kanonische DNF. S. auch: Kanonische Normalform.