- 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 bilden eine vollständig Basis der booleschen Funktionen. Damit wird die folgende Definition möglich.
Eine Formel ist in Ringsummennormalform, wenn sie eine Kontravalenz () von Konjunktionen () der Eingabevariablen x1,...,xn und der Konstanten 0,1 ist. Eine Formel in RSNF hat folgende Form:
, wobei 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 aus.
Beispiel
Die disjunktive Normalform kann wie folgt in ihre RSNF umgeformt werden:
Orthogonalisierung (z. B. mit Hilfe eines Karnaugh-Planes):
Ersetzen der Disjunktion durch die Antivalenz:
Umschreiben der Negation:
Ausmultiplizieren:
Durch „Wegstreichen“ von jeweils zwei gleichen Termen erhält man nach dem Umsortieren schließlich:
Folgerungen
- Jede beliebige boolesche Funktion kann in Ringsummennormalform überführt werden.
- Die Ringsummennormalform einer booleschen Funktion ist eindeutig.
Literatur
- Ingo Wegener: The complexity of Boolean functions. Wiley-Teubner, 1987, ISBN 3-519-02107-2, S. 6 (Online-Ausgabe)
- Präsentation der Uni Duisburg
-
Wikimedia Foundation.