Sum of products

Sum of products

Als disjunktive Normalform (kurz DNF) wird in der Booleschen Algebra eine in besonderer Weise normierte Funktionsdarstellung Boolescher Funktionen bezeichnet.

Inhaltsverzeichnis

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

\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 ODER B ODER C ODER D; A∨B∨C∨D

Dabei können die einzelnen Elemente der ODER-Verknüpfung (A, B, C, D) komplexere 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

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

Beispiel:  
\bar{A}\bar{B}\bar{C}\vee
\bar{A}B\bar{C}\vee
AB\bar{C}\vee
\bar{A}\bar{B}C\vee
\bar{A}BC\vee
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 anders herum: 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. 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 Klauseln 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 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:

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

Anmerkung: Die einzelnen Klauseln 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} \vee \bar{x_2}x_1x_0 \vee x_2\bar{x_1}x_0 \vee x_2x_1x_0

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

e = ((\bar{x_2}) \wedge x_1) \vee (x_2 \wedge x_0)

Üblicherweise werden die inneren \wedge-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:

e = \bar{x_2}x_1 + x_2x_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), auch vollständige disjunktive Normalform genannt, 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.

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

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

  1. In manchen Quellen (z. B. Obershelp W., Vossen G., Rechneraufbau und Rechnerstrukturen) versteht man unter DNF genau diese kanonische DNF. S. auch: Kanonische Normalform.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sum Elai-Mang — (Hindko:هندکو) or Sum is a village/state in Sirran Valley,Mansehra District, North West Frontier Province, Pakistan.It was ruled by Haroon Khan Badshah who was known as “Badshah Khan”. Sum is blessed with a lot of natural beauty which comprises… …   Wikipedia

  • Sum-product number — A sum product number is an integer that in a given base is equal to the sum of its digits times the product of its digits. Or, to put it algebraically, given an integer n that is l digits long in base b (with d x representing the x th digit), ifn …   Wikipedia

  • Lerche–Newberger sum rule — The Lerche–Newberger, or Newberger, sum rule, discovered by B. S. Newberger in 1982,[1][2][3] finds the sum of certain infinite series involving Bessel functions Jα of the first kind. It states that if μ is any non integer complex… …   Wikipedia

  • Power sum symmetric polynomial — In mathematics, specifically in commutative algebra, the power sum symmetric polynomials are a type of basic building block for symmetric polynomials, in the sense that every symmetric polynomial with rational coefficients can be expressed as a… …   Wikipedia

  • Annuity (US financial products) — In the U.S. an annuity contract is created when an individual gives a life insurance company money which may grow on a tax deferred basis and then can be distributed back to the owner in several ways. The defining characteristic of all annuity… …   Wikipedia

  • Divergence of the sum of the reciprocals of the primes — The sum of the reciprocals of all prime numbers diverges, that is: This was proved by Leonhard Euler in 1737, and strengthens Euclid s 3rd century BC result that there are infinitely many prime numbers. There is a variety of proofs of Euler s… …   Wikipedia

  • Direct sum of modules — For the broader use of the term in mathematics, see Direct sum. In abstract algebra, the direct sum is a construction which combines several modules into a new, larger module. The result of the direct summation of modules is the smallest general… …   Wikipedia

  • Empty sum — Not to be confused with Zero sum. In mathematics, an empty sum, or nullary sum, is a summation involving no terms at all. The value of any empty sum of numbers is conventionally taken to be zero. For summations defined in terms of addition of… …   Wikipedia

  • con|sum´er|ist — con|sum|er|ism «kuhn SOO muh rihz uhm», noun. 1. a movement to protect the consumer from unsafe or defectively manufactured products, from misleading labeling, packaging, or promotion practices, and to protect the environment from undue harm:… …   Useful english dictionary

  • con|sum|er|ism — «kuhn SOO muh rihz uhm», noun. 1. a movement to protect the consumer from unsafe or defectively manufactured products, from misleading labeling, packaging, or promotion practices, and to protect the environment from undue harm: »“Consumerism”… …   Useful english dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”