Direkt zum Inhalt

Lexikon der Mathematik: Ring-Summen-Expansion

RSE, spezieller Boolescher Ausdruck.

Die Ring-Summen-Expansion einer Booleschen Funktion f : {0, 1}n → {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 mi (∀1 ≤ is) ein Boolesches Monom ist, das nur aus positiven Booleschen Literalen besteht, mimj für i = j ist, und ⊕ die EXOR-Funktion darstellt. Die Ring-SummenExpansion ist eine kanonische Darstellung Boolescher Funktionen.

Sei beispielsweise f : {0, 1}3 → {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}

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos