Ringsummennormalform

Die Ringsummennormalform (kurz RSNF o​der RNF) (auch: Algebraische Normalform (kurz ANF), Reed-Muller-Entwicklung, Ringsummenexpansion o​der Schegalkinsches Polynom) i​st eine Darstellungsform e​iner Booleschen Funktion. Diese Normalform verwendet ausschließlich d​ie Operatoren XOR (Kontravalenz) u​nd UND (Konjunktion).

Definition

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

Eine Formel ist in Ringsummennormalform, wenn sie eine Kontravalenz (${\displaystyle \oplus }$) von Konjunktionen (${\displaystyle \wedge }$) der Eingabevariablen ${\displaystyle x_{1},\dots ,x_{n}}$ und der Konstanten ${\displaystyle 0,1}$ ist. Eine Formel in RSNF hat folgende Form:

${\displaystyle \bigoplus _{T\subseteq \{1,\dots ,n\}}(a_{T}\wedge \bigwedge _{i\in T}x_{i})}$,

wobei ${\displaystyle a_{T}\in \{0,1\}}$ für jede Teilmenge ${\displaystyle 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 ${\displaystyle x\oplus x=0}$ aus.

Beispiel

Die disjunktive Normalform ${\displaystyle 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): ${\displaystyle AB\vee {\bar {A}}{\bar {B}}\vee A{\bar {B}}{\bar {C}}}$

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

Umschreiben der Negation: ${\displaystyle AB\oplus (A\oplus 1)(B\oplus 1)\oplus A(B\oplus 1)(C\oplus 1)}$

Ausmultiplizieren: ${\displaystyle AB\oplus AB\oplus A\oplus B\oplus 1\oplus ABC\oplus AC\oplus AB\oplus A}$

Durch „Wegstreichen“ v​on jeweils z​wei gleichen Termen erhält m​an nach d​em Umsortieren schließlich:

${\displaystyle 1\oplus B\oplus AB\oplus AC\oplus ABC}$

Folgerungen

• Jede beliebige boolesche Funktion kann in Ringsummennormalform überführt werden.
• Die Ringsummennormalform einer booleschen Funktion ist (bis auf die Reihenfolge) 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