RSE, spezieller Boolescher Ausdruck.

Die Ring-Summen-Expansion einer Booleschen Funktion f : {0, 1}ⁿ → {0, 1} ist ein spezieller Boolescher Ω-Ausdruck (Boolescher Ausdruck) w mit Ω = {∧, ⊕} der Form \begin{eqnarray}w={m}_{1}\oplus \ldots \oplus {m}_{s},\end{eqnarray} der f beschreibt, wobei m_i (∀1 ≤ i ≤ s) ein Boolesches Monom ist, das nur aus positiven Booleschen Literalen besteht, m_i ≠ m_j für i = j ist, und ⊕ die EXOR-Funktion darstellt. Die Ring-SummenExpansion ist eine kanonische Darstellung Boolescher Funktionen.

Sei beispielsweise f : {0, 1}³ → {0, 1} definiert durch \begin{eqnarray}f(\alpha )=1\iff \alpha \in \{(1, 1,0),(1, 1,1),(0, 1,1)\}.\end{eqnarray} Dann kann die Ring-Summen-Darstellung von f wie folgt konstruiert werden: \begin{eqnarray}\begin{array}{ll}f({x}_{1},{x}_{2},{x}_{3})\\ = ({x}_{1}\wedge {x}_{2}\wedge \overline{{x}_{3}})\vee ({x}_{1}\wedge {x}_{2}\wedge {x}_{3})\vee ({\overline{x}}_{1}\wedge {x}_{2}\wedge {x}_{3})\\ = ({x}_{1}\wedge {x}_{2}\wedge \overline{{x}_{3}})\oplus ({x}_{1}\wedge {x}_{2}\wedge {x}_{3})\oplus ({\overline{x}}_{1}\wedge {x}_{2}\wedge {x}_{3})\\ = ({x}_{1}\wedge {x}_{2}\wedge (1\oplus {x}_{3}))\oplus ({\overline{x}}_{1}\wedge {x}_{2}\wedge {x}_{3})\\ \oplus ((1\oplus {x}_{1})\wedge 1\oplus {x}_{3})\\ = ({x}_{1}\wedge {x}_{2})\oplus ({x}_{1}\wedge {x}_{2}\wedge {x}_{3})\oplus ({x}_{1}\wedge {x}_{2}\wedge {x}_{3})\\ \oplus ({x}_{2}\wedge {x}_{3})\oplus ({x}_{1}\wedge {x}_{2}\wedge {x}_{3})\\ = ({x}_{1}\wedge {x}_{2})\oplus ({x}_{1}\wedge {x}_{2}\wedge {x}_{3})\oplus ({x}_{2}\wedge {x}_{3})\end{array}\end{eqnarray}