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 k ≤ n 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 t ≤ s 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
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
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 j ≠ i 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
Dies ergibt die sog. Lupanowsche (k, s)-Darstellung
[1] Wegener, I.: The Complexity of Boolean Functions. B.G. Teubner Stuttgart and John Wiley & Sons Chichester, New York, Brisbane, Toronto, Singapore, 1987.
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.