Direkt zum Inhalt

Lexikon der Mathematik: Würfeldarstellung einer Booleschen Funktion

Darstellung einer Booleschen Funktion \begin{eqnarray}f:{\{0,1\}}^{n}\to \{0,1\}\end{eqnarray}

durch einen markierten n-dimensionalen Würfel 𝔚(f).

Die Knoten des Würfels entsprechen den Elementen des Definitionsbereiches {0, 1}n von f und umgekehrt. Zwei Elemente \begin{eqnarray}({\alpha}_{1},\ldots, {\alpha}_{n}),({\beta}_{1},\ldots, {\beta}_{n})\in {\{0,1\}}^{n},\end{eqnarray}

die sich an genau einer Stelle unterscheiden, für die also mit einem i ∈ {1..., n} gilt, daß αiβi und αj = βjji ist, sind bezüglich der i-ten Dimension durch eine Kante benachbart.

Abbildung 1 zum Lexikonartikel Würfeldarstellung einer Booleschen Funktion
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Würfel der Dimension 4

Jeder Knoten vV, der einem Knoten aus der ON-Menge von f entspricht, wird markiert.

Die Würfeldarstellung wird als anschauliche Darstellung Boolescher Funktionen benutzt, um Minimalpolynome dieser Booleschen Funktionen zu berechnen.

Teilwürfel von 𝔚(f), die nur markierte Knoten enthalten, sind die Implikanten der Booleschen Funktion f. Ein solcher Teilwürfel heißt maximaler Teilwürfel von 𝔚(f), wenn kein Teilwürfel höherer Dimension, der ebenfalls nur markierte Knoten enthält, ihn umfaßt. Maximale Teilwürfel entsprechen den Primimplikanten von f.

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

Partnerinhalte