Disjunktive Normalform

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 entweder nichtnegierte oder negierte Variablen. Eine Formel in DNF hat also die Form

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

Erläuterung

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}\ \mathrm {oder} \ {B}\ \mathrm {oder} \ {C}\ \mathrm {oder} \ {D}$

als formale Schreibweise:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {A}\lor {B}\lor {C}\lor {D}}

Dabei können die einzelnen Elemente der ODER-Verknüpfung (A, B, C, D) komplexere Ausdrücke sein, die dann auch eine oder mehrere UND-Verknüpfungen (Konjunktion) enthalten können.

Beispiel

$({A}\ \mathrm {und} \ {B})\ \mathrm {oder} \ ({A}\ \mathrm {und} \ {B}\ \mathrm {und} \ {C})\ \mathrm {oder} \ ({B}\ \mathrm {und} \ {C})\ \mathrm {oder} \ {D}$

als formale Schreibweise:

$({A}\land {B})\lor ({A}\land {B}\land {C})\lor ({B}\land {C})\lor {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

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {A}{B}\lor {A}{B}{C}\lor {B}{C}\lor {D}}

Auch der NICHT-Operator kann in solchen Ausdrücken auftreten:

Beispiel

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\bar {A}}{\bar {B}}{\bar {C}}\lor {\bar {A}}B{\bar {C}}\lor AB{\bar {C}}\lor {\bar {A}}{\bar {B}}C\lor {\bar {A}}BC\lor ABC}

Zusätzlich zu der bereits oben erwähnten Forderung, dass der logische Ausdruck in der obersten Ebene ausschließlich aus ODER-Verknüpfungen besteht (ODER-Ebene), darf es keine weiteren ODER-Verknüpfungen in tiefer geklammerten Ebenen geben. Nur zwei Ebenen sind 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 andersherum: eine UND-Verknüpfung von ODER-Aussagen und Einzelaussagen. Das ist 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 in die DNF umgewandelt. Dabei wird der logische Ausdruck in der Regel noch länger. In einem weiteren Schritt erfolgt eine Vereinfachung des logischen Ausdrucks mittels Karnaugh-Veitch-Diagramm oder dem Quine-McCluskey-Verfahren. Dabei werden logische 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 Terme werden auch Minterme genannt. Durch disjunktive Verknüpfung der Minterme erhält man schließlich die disjunktive Normalform.

Auf diese Weise erhält man allerdings in der Regel keine minimale Formel, das heißt eine Formel mit möglichst wenig Termen. Will man eine minimale Formel bilden, so kann man dies mit Hilfe von Karnaugh-Veitch-Diagrammen oder mithilfe des Quine-McCluskey-Verfahrens tun.

Beispiel für die Bildung der DNF

Gesucht ist eine Formel in disjunktiver Normalform für die Boolesche Funktion mit drei Variablen $A$, $B$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} , die genau dann den Wahrheitswert 1 annimmt, wenn die Dualzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [ABC]_2} eine Primzahl ist.

Die Wahrheitstafel für diese Funktion hat folgende Gestalt:

Wahrheitstafel sowie disjunktive und konjunktive Normalform für die Funktion, die genau dann wahr ist, wenn [ABC]_2 eine Primzahl ist

Für jede Kombination der Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} , für die sich der Funktionswert 1 ergibt, wird eine Konjunktion gebildet. Die Variablen, die den Wert 0 haben, werden negiert. Im Beispiel oben sind das die Konjunktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lnot A \land B \land \lnot C} und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \lnot A\land B\land C} und $A\land \lnot B\land C$ und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle A\land B\land C} . Schließlich werden diese Minterme mit Disjunktionen verknüpft. Daraus ergibt sich die disjunktive Normalform:

$(\lnot A\land B\land \lnot C)\lor (\lnot A\land B\land C)\lor (A\land \lnot B\land C)\lor (A\land B\land C)$

Anmerkung: Die einzelnen Terme sind als Minterme notiert. Außerdem kann man gut sehen, dass jede DNF eine äquivalente KNF besitzt.

Die in DNF dargestellte Funktion

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

kann auch als vollständig geklammerter Boolescher Ausdruck dargestellt werden:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle e=(({\bar {x_{2}}})\land x_{1})\lor (x_{2}\land x_{0})}

Üblicherweise werden die inneren $\land$-Verknüpfungen analog zu den Multiplikations-Operatoren gesehen und können deshalb weggelassen werden. So ergibt sich eine noch kompaktere Schreibweise, welche man auch Produktterm nennt:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle e={\bar {x_{2}}}x_{1}+x_{2}x_{0}}

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 paarweise voneinander unterschiedliche Minterme enthält, in denen jede Variable genau ein Mal vorkommt. Sie wird auch vollständige disjunktive Normalform genannt. Jede Boolesche Funktion besitzt genau eine KDNF (bis auf Anordnung der Minterme).

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

Orthogonale disjunktive Normalform

Unter einer orthogonalen disjunktiven Normalform (ODNF) versteht man eine DNF, deren Konjunktionen jeweils paarweise disjunkt sind, d. h. Null ergeben. Um aus einer nichtorthogonalen disjunktiven Normalform eine ODNF zu machen, gibt es verschiedene Orthogonalisierungsverfahren. Man erhält beispielsweise eine ODNF, wenn man aus einem Karnaugh-Veitch-Diagramm nur nichtüberlappende Blöcke ausliest. Im Allgemeinen gibt es zu jeder booleschen Funktion mehrere ODNF. Die kanonische disjunktive Normalform ist „von Hause aus“ orthogonal und eindeutig. ODNF sind aufgrund ihrer Orthogonalität algorithmisch einfacher zu verarbeiten und werden deshalb oft im maschinellen Logikentwurf benutzt. Beispielsweise lässt sich eine ODNF einfach in eine antivalente Normalform umrechnen, indem man alle Disjunktionsoperatoren durch Antivalenzoperatoren ersetzt und anschließend vereinfacht.

Weitere Normalformen

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

Disjunktive Minimalform

Eine disjunktive Normalform heißt disjunktive Minimalform oder minimale disjunktive Normalform, wenn

• jede äquivalente Darstellung derselben Ausgabefunktion mindestens genauso viele Produktterme besitzt
• bei jeder äquivalenten Darstellung derselben Ausgabefunktion mit gleich vielen Produkttermen die Anzahl der Eingänge in die Produktterme mindestens genauso groß ist, wie die Anzahl der Eingänge in die Produktterme von f.

Weblinks

• Webformular zur Bildung der disjunktiven und konjunktiven Normalform