Ringsummennormalform

Ringsummennormalform

Die Ringsummennormalform (kurz RSNF) (auch: Reed-Muller-Entwicklung, Ringsummenexpansion oder Schegalkinsches Polynom) ist eine Darstellungsform einer Booleschen Funktion. Diese Normalform verwendet ausschließlich die Operatoren XODER (Kontravalenz) und UND (Konjunktion).

Inhaltsverzeichnis

Definition

Die beiden Operatoren Kontravalenz und Konjunktion \{\oplus,\wedge\} bilden eine vollständig Basis der booleschen Funktionen. Damit wird die folgende Definition möglich.

Eine Formel ist in Ringsummennormalform, wenn sie eine Kontravalenz (\oplus) von Konjunktionen (\wedge) der Eingabevariablen x1,...,xn und der Konstanten 0,1 ist. Eine Formel in RSNF hat folgende Form:

\bigoplus_{T\subseteq\{1,...,n\}} ( a_T \wedge \bigwedge_{i\in T} x_i ), wobei a_T\in\{0,1\} für jede Teilmenge T ist.

Berechnung der RSNF

Man geht von einer orthogonalen disjunktiven Normalform (also einer disjunktiven Normalform, deren Konjunktionen alle gegenseitig disjunkt sind, d.h. 0 ergeben) aus. Das kann z. B. auch die kanonisch disjunktive Normalform sein. In dieser ersetzt man den Disjunktionsoperator durch den Antivalenzoperator (Ringsumme), was aufgrund der Orthogonalität möglich ist. Danach schreibt man die Negationen in die (geklammerte) Antivalenz mit 1 um. Anschließend „multipliziert“ man unter besonderer Beachtung der Rechenregel für die Antivalenz x \oplus x = 0 aus.

Beispiel

Die disjunktive Normalform AB \vee \bar{A} \bar{B} \vee A \bar{C} kann wie folgt in ihre RSNF umgeformt werden:

Orthogonalisierung (z. B. mit Hilfe eines Karnaugh-Planes): AB \vee \bar{A} \bar{B} \vee A \bar{B}\bar{C}

Ersetzen der Disjunktion durch die Antivalenz: AB \oplus \bar{A} \bar{B} \oplus A \bar{B}\bar{C}

Umschreiben der Negation: AB \oplus (A \oplus 1) (B \oplus 1) \oplus A (B \oplus 1) (C \oplus 1)

Ausmultiplizieren: AB \oplus AB \oplus A \oplus B \oplus 1 \oplus ABC \oplus AC \oplus AB \oplus A

Durch „Wegstreichen“ von jeweils zwei gleichen Termen erhält man nach dem Umsortieren schließlich:

1 \oplus B \oplus A B \oplus A C \oplus A B C

Folgerungen

  • Jede beliebige boolesche Funktion kann in Ringsummennormalform überführt werden.
  • Die Ringsummennormalform einer booleschen Funktion ist eindeutig.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Ringsummen-Normalform — Die Ringsummennormalform (kurz RSNF) (auch: Reed Muller Entwicklung oder Ringsummenexpansion) ist eine Darstellungsform einer Booleschen Funktion. Diese Normalform verwendet ausschließlich die Operatoren XODER (Kontravalenz) und UND (Konjunktion) …   Deutsch Wikipedia

  • Boole'sche Funktion — Eine Boolesche Funktion (auch logische Funktion) ist eine mathematische Funktion der Form (teilweise auch allgemeiner ). B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, wird für Boolesche Funktionen im Allgemeinen groß… …   Deutsch Wikipedia

  • Kanonische Form — Unter einer Normalform versteht man eine Darstellung, die bestimmte vorgegebene Eigenschaften hat. Insbesondere bezeichnet Normalform in der Mathematik eine Darstellung eines Objektes, die bestimmte vorgegebene Eigenschaften hat und für alle… …   Deutsch Wikipedia

  • Logische Funktion — Eine Boolesche Funktion (auch logische Funktion) ist eine mathematische Funktion der Form (teilweise auch allgemeiner ). B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, wird für Boolesche Funktionen im Allgemeinen groß… …   Deutsch Wikipedia

  • Schaltfunktion — Eine Boolesche Funktion (auch logische Funktion) ist eine mathematische Funktion der Form (teilweise auch allgemeiner ). B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, wird für Boolesche Funktionen im Allgemeinen groß… …   Deutsch Wikipedia

  • Verknüpfungsbasis — Eine Boolesche Funktion (auch logische Funktion) ist eine mathematische Funktion der Form (teilweise auch allgemeiner ). B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, wird für Boolesche Funktionen im Allgemeinen groß… …   Deutsch Wikipedia

  • Boolesche Funktion — Eine Boolesche Funktion (auch logische Funktion) ist eine mathematische Funktion der Form (teilweise auch allgemeiner ). B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, wird für Boolesche Funktionen im Allgemeinen groß… …   Deutsch Wikipedia

  • Kanonische Normalform — Eine aussagenlogische Formel ist die kanonische Normalform (KNF; engl.: canonical normal form) zu einer weiteren aussagenlogischen Formel, wenn sie eine Normalform dieser aussagenlogischen Formel ist, d.h. eine zu dieser Formel äquivalente… …   Deutsch Wikipedia

  • Karnaugh-Veitch-Diagramm — Bild 1 1: Karnaugh Veitch Diagramm: ¬AB¬C¬D ∨ A¬B¬C¬D ∨ A¬B¬CD ∨ A¬BC¬D ∨ A¬BCD ∨ AB¬C¬D ∨ ABC¬D ∨ ABCD = AC ∨ B¬C¬D ∨ A¬B …   Deutsch Wikipedia

  • Normalform — Unter einer Normalform (auch kanonische Form) versteht man eine Darstellung mit bestimmten vorgegebenen Eigenschaften. Mitunter ist die Darstellung eindeutig. Formal ist eine Normalform ein letztes Element in einer Kette von einer wohlfundierten… …   Deutsch Wikipedia

Share the article and excerpts

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