ein spezieller Boolescher Ausdruck, der eine gegebene Boolesche Funktion f beschreibt.

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

Die Zeilen werden nun in \(p=\lceil \frac{{2}^{k}}{s}\rceil \) Blöcke A₁,…, A_p 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 f_i : {0, 1}ⁿ → {0, 1} mit i ∈ {1, …, p}, die für alle α = (α₁, …, α_n) ∈ {0, 1}ⁿ 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 = f₁ ∨ …∨ f_p.

Die Booleschen Funktionen f₁,…,f_p werden nun weiter zerlegt. Um die Boolesche Funktion f_i zu zerlegen, wird für jedes w ∈ {0,1}^s (ist i = p, so für jedes w ∈ {0, 1}^t) die Menge B_i,w der Spalten betrachtet, die im Block A_i mit w übereinstimmen. Für die Booleschen Funktionen f_i,w : {0,1}ⁿ → {0, 1}, die für alle α = (α₁,…, α_n) ∈ {0, 1}ⁿ 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 f_i,w (i ∈ {1,…, t}) wird nun nochmals zerlegt. Diese Zerlegung ist sehr einfach, da f_i,w eine sehr einfache Form hat: In allen Blöcken A_j mit j ≠ i ist f_i,w gleich Null. Im Block A_i hat die Funktionsmatrix höchstens zwei verschiedene Spalten, solche, die nur aus Nullen bestehen, und w-Spalten.

Die Gleichung f_i,w(α₁,…, α_n) = 1 gilt also genau dann, wenn es ein j mit w_j = 1 gibt, so daß (α₁,…, α_k) die j-te Zeile von A_i ist und (x_k+1,…,x_n) ∈ B_i,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 α = (α₁,…, α_n) ∈ {0, 1}ⁿ \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.