imported>Serols: Änderungen von 87.130.119.194 (Diskussion) rückgängig gemacht (HG) (3.4.10)

2023-02-08T14:08:34Z

Änderungen von 87.130.119.194 (Diskussion) rückgängig gemacht (HG) (3.4.10)

Neue Seite

Als '''disjunktive Normalform''' (kurz DNF) wird in der [[Boolesche Algebra|Booleschen Algebra]] eine in besonderer Weise normierte Funktionsdarstellung [[Boolesche Funktion|Boolescher Funktionen]] bezeichnet.

== Definition ==
Eine Formel der Aussagenlogik ist in disjunktiver Normalform, wenn sie eine [[Disjunktion]] von [[Konjunktionsterm]]en ist. Ein Konjunktionsterm wird ausschließlich durch die [[Konjunktion (Logik)|konjunktive]] Verknüpfung von Literalen gebildet. Literale sind dabei entweder nichtnegierte oder negierte Variablen. Eine Formel in DNF hat also die Form
<div class="center"><math>\bigvee_i \bigwedge_j (\neg)x_{ij}.</math> </div>

== 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'''

:<math>{A}\ \mathrm{oder}\ {B}\ \mathrm{oder}\ {C}\ \mathrm{oder}\ {D}</math>

als formale Schreibweise:

:<math>{A}\lor{B}\lor{C}\lor{D}</math>

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 (Logik)|Konjunktion]]) enthalten können.

'''Beispiel'''

:<math>({A}\ \mathrm{und}\ {B})\ \mathrm{oder}\ ({A}\ \mathrm{und}\ {B}\ \mathrm{und}\ {C})\ \mathrm{oder}\ ({B}\ \mathrm{und}\ {C})\ \mathrm{oder}\ {D}</math>

als formale Schreibweise:

:<math>({A}\land{B})\lor({A}\land{B}\land{C})\lor({B}\land{C})\lor{D}</math>

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'''

:<math>{A}{B}\lor{A}{B}{C}\lor{B}{C}\lor{D}</math>

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

'''Beispiel'''

:<math>\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</math>

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 [[Verfahren nach Quine und McCluskey|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 [[Vollkonjunktion|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-Diagramm]]en oder mithilfe des [[Verfahren nach Quine und McCluskey|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 <math>A</math>, <math>B</math> und <math>C</math>, die genau dann den Wahrheitswert 1 annimmt, wenn die [[Dualzahl]] <math>[ABC]_2</math> eine [[Primzahl]] ist.

Die Wahrheitstafel für diese Funktion hat folgende Gestalt:

[[Datei:Knf+dnf.svg|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 <math>A</math>, <math>B</math> und <math>C</math>, für die sich der Funktionswert 1 ergibt, wird eine [[Konjunktion (Logik)|Konjunktion]] gebildet. Die Variablen, die den Wert 0 haben, werden negiert. Im Beispiel oben sind das die Konjunktionen <math>\lnot A \land B \land \lnot C</math> und <math>\lnot A \land B \land C</math> und <math>A \land \lnot B \land C</math> und <math>A \land B \land C</math>. Schließlich werden diese [[Minterm|Minterme]] mit [[Disjunktion|Disjunktionen]] verknüpft. Daraus ergibt sich die disjunktive Normalform:

:<math>(\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)</math>

'''Anmerkung:''' Die einzelnen Terme sind als [[Minterm]]e notiert. Außerdem kann man gut sehen, dass jede DNF eine äquivalente [[Konjunktive Normalform|KNF]] besitzt.

Die in DNF dargestellte Funktion

:<math>y = \bar{x_2} x_1\bar{x_0} \lor \bar{x_2}x_1x_0 \lor x_2\bar{x_1}x_0 \lor x_2x_1x_0</math>

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

:<math>e = ((\bar{x_2}) \land x_1) \lor (x_2 \land x_0)</math>

Üblicherweise werden die inneren <math>\land</math>-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:

:<math>e = \bar{x_2}x_1 + x_2x_0</math>

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.

[[CPLD]]s 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 [[Minterm]]e enthält, in denen jede Variable genau ein Mal vorkommt.<ref>In manchen Quellen (zum Beispiel: W. Oberschelp, G. Vossen: ''Rechneraufbau und Rechnerstrukturen.'') versteht man unter DNF genau die kanonische DNF. (Siehe auch: [[Kanonische Normalform]]).</ref> 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 [[Ringsummennormalform|antivalente Normalform]] umrechnen, indem man alle [[Disjunktion]]soperatoren durch [[Kontravalenz|Antivalenzoperatoren]] ersetzt und anschließend vereinfacht.<ref>{{Literatur |Autor=[[Dieter Bochmann]], [[Bernd Steinbach]] |Titel=Logikentwurf mit XBOOLE: Algorithmen und Programme |Verlag=Verlag Technik |Ort=Berlin |Datum=1991 |ISBN=3-341-01006-8}}</ref>

== Weitere Normalformen ==
Neben der disjunktiven Normalform gibt es in der Aussagenlogik weitere [[Normalform]]en, etwa die [[konjunktive Normalform]] und die [[Negationsnormalform]].

== Disjunktive Minimalform ==
Eine disjunktive Normalform heißt '''disjunktive Minimalform''' oder '''minimale disjunktive Normalform'''<ref>{{Literatur |Autor=[[Manfred Peschel]] |Titel=Moderne Anwendungen algebraischer Methoden |Verlag=Verlag Technik |Ort=Berlin |Datum=1971 |DNB=575635827}}</ref>, 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.

== Bemerkungen ==
<references />

== Weblinks ==
* [http://sven.killig.de/nf Webformular zur Bildung der disjunktiven und konjunktiven Normalform]

[[Kategorie:Mathematische Logik]]
[[Kategorie:Normalform]]

Disjunktive Normalform - Versionsgeschichte

imported>Serols: Änderungen von 87.130.119.194 (Diskussion) rückgängig gemacht (HG) (3.4.10)