All round normal form

The circular sum normal form (RSNF or RNF for short) (also: algebraic normal form (ANF for short), Reed-Muller expansion , ring sum expansion or Schegalkin polynomial) is a form of representation of a Boolean function . This normal form only uses the operators XOR (contravalence) and AND (conjunction) .

definition

The two operators contravalence and conjunction form a complete basis for the Boolean functions . This enables the following definition. ${\displaystyle \{\oplus ,\wedge ,1\}}$

A formula is in circular sum normal form if it is a contravalence ( ) of conjunctions ( ) of the input variables and the constants . A formula in RSNF has the following form: ${\displaystyle \oplus }$ ${\displaystyle \wedge }$ ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle 0,1}$

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

where for each subset is. ${\displaystyle a_{T}\in \{0,1\}}$ ${\displaystyle T}$

Calculating the RSNF

One starts from an orthogonal disjunctive normal form ( i.e. a disjunctive normal form whose conjunctions are all mutually disjunctive, i.e. result in 0). This can e.g. B. also be the canonically disjunctive normal form . In this one replaces the disjunction operator with the non- equivalence operator (ring sum), which is possible due to the orthogonality. Then you rewrite the negations in the (bracketed) antivalence with 1. Then “multiply”, paying special attention to the calculation rule for the antivalence . ${\displaystyle x\oplus x=0}$

example

The disjunctive normal form can be transformed into its RSNF as follows: ${\displaystyle AB\vee {\bar {A}}{\bar {B}}\vee A{\bar {C}}}$

Orthogonalization (e.g. with the help of a Karnaugh plan ): ${\displaystyle AB\vee {\bar {A}}{\bar {B}}\vee A{\bar {B}}{\bar {C}}}$

Replacing the disjunction with the antivalence: ${\displaystyle AB\oplus {\bar {A}}{\bar {B}}\oplus A{\bar {B}}{\bar {C}}}$

Rewriting the negation: ${\displaystyle AB\oplus (A\oplus 1)(B\oplus 1)\oplus A(B\oplus 1)(C\oplus 1)}$

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

By "deleting" two identical terms each time you finally get:

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

Inferences

• Any Boolean function can be converted to normal form of the total sum.
• The normal form of a Boolean function is unique (except for the sequence).

literature

• Ingo Wegener: The complexity of Boolean functions. Wiley-Teubner, 1987, ISBN 3-519-02107-2 , p. 6 ( online edition )
• Presentation of the University of Duisburg