Direkt zum Inhalt

Lexikon der Mathematik: Lupanow-Darstellung

ein spezieller Boolescher Ausdruck, der eine gegebene Boolesche Funktionf beschreibt.

Um die Lupanowsche (k, s)-Darstellung einer Booleschen Funktion f : {0, 1}n → {0,1} mit kn und s ≤ 2k zu erhalten, wird die Funktionstafel von f als (2k × 2n−k)-Matrix dargestellt. Die Zeilen entsprechen dabei den 2k möglichen Belegungen von (x1, …, xk), und die Spalten den 2n−k möglichen Belegungen von (xk+1, …, xn). In der Matrix stehen die entsprechenden Funktionswerte.

Die Zeilen werden nun in \(p=\lceil \frac{{2}^{k}}{s}\rceil \) Blöcke A1,…, Ap so eingeteilt, daß die ersten p − 1 Blöcke genau s Zeilen und der letzte Block ts Zeilen enthält. Für die Booleschen Funktionen fi : {0, 1}n → {0, 1} mit i ∈ {1, …, p}, die für alle α = (α1, …, αn) ∈ {0, 1}n durch \begin{eqnarray}{f}_{i}(\alpha )=\left\{\begin{array}{ll}f(\alpha ), & \text{falls}\,({\alpha }_{1},\ldots,{\alpha }_{k})\in {A}_{i}\\ 0, & \text{sonst}\end{array}\right.\end{eqnarray} definiert sind, gilt f = f1 ∨ …∨ fp.

Die Booleschen Funktionen f1,…,fp werden nun weiter zerlegt. Um die Boolesche Funktion fi zu zerlegen, wird für jedes w ∈ {0,1}s (ist i = p, so für jedes w ∈ {0, 1}t) die Menge Bi,w der Spalten betrachtet, die im Block Ai mit w übereinstimmen. Für die Booleschen Funktionen fi,w : {0,1}n → {0, 1}, die für alle α = (α1,…, αn) ∈ {0, 1}n durch \begin{eqnarray}{f}_{i,w}(\alpha )=\left\{\begin{array}{ll}{f}_{i}(\alpha ), & \text{falls}\,({\alpha }_{k+1},\ldots,{\alpha }_{n})\in {B}_{i,w},\\ 0, & \text{sonst}\end{array}\right.\end{eqnarray} definiert sind, gilt dann \begin{eqnarray}{f}_{i}=\mathop{\bigvee }\limits_{w\in {\{0,1\}}^{s}}{f}_{i,w}\,\,\text{bzw}\text{.}\,\,\,{f}_{p}=\mathop{\bigvee }\limits_{w\in {\{0,1\}}^{t}}{f}_{p,w}.\end{eqnarray}

Jede Boolesche Funktion fi,w (i ∈ {1,…, t}) wird nun nochmals zerlegt. Diese Zerlegung ist sehr einfach, da fi,w eine sehr einfache Form hat: In allen Blöcken Aj mit ji ist fi,w gleich Null. Im Block Ai hat die Funktionsmatrix höchstens zwei verschiedene Spalten, solche, die nur aus Nullen bestehen, und w-Spalten.

Die Gleichung fi,w(α1,…, αn) = 1 gilt also genau dann, wenn es ein j mit wj = 1 gibt, so daß (α1,…, αk) die j-te Zeile von Ai ist und (xk+1,…,xn) ∈ Bi,w gilt. Wenn \({f}_{i,w}^{(1)}\) und \({f}_{i,w}^{(2)}\) die erste bzw. die zweite Bedingung überprüft, so gilt für alle α = (α1,…, αn) ∈ {0, 1}n\begin{eqnarray}{f}_{i,w}(\alpha )={f}_{i,w}^{(1)}({\alpha }_{1},\ldots,{\alpha }_{k})\wedge {f}_{i,w}^{(2)}({\alpha }_{k+1},\ldots,{\alpha }_{n}).\end{eqnarray}

Dies ergibt die sog. Lupanowsche (k, s)-Darstellung \begin{eqnarray}f(\alpha )=\underset{i=1}{\overset{p}{\bigvee }}\mathop{\bigvee }\limits_{w}{f}_{i,w}^{(1)}({\alpha }_{1},\ldots,{\alpha }_{k})\wedge {f}_{i,w}^{(2)}({\alpha }_{k+1},\ldots,{\alpha }_{n}).\end{eqnarray}

[1] Wegener, I.: The Complexity of Boolean Functions. B.G. Teubner Stuttgart and John Wiley & Sons Chichester, New York, Brisbane, Toronto, Singapore, 1987.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.