Zerlegung einer Booleschen Funktionf : {0, 1}ⁿ → {0,1} in der Form \begin{align} & f(x_{1},\ldots,x_{n})=g(\alpha(x_{i_{1}},\ldots,x_{i_{p}}),\beta(x_{i_{p+1}},\ldots,x_{i_{n}})). \end{align} Hierbei ist {{x_i1, …,x_ip},{x_ip+1, …, x_in}} eine Partition der Menge der Booleschen Variablen von f mit 1 ≤ p ≤ n − 1, α : {0, 1}^p → {0, 1}^r, β : {0, 1}^n−p → {0, 1}^s und g : {0,1}^r+s → {0, 1}. Die Booleschen Funktionen α und β heißen Zerlegungsfunktionen, die Boolesche Funktion g Zusammensetzungsfunktion der Zerlegung.

Ist r + s< n, so wird die Zerlegung nichttriviale funktionale Dekomposition genannt. Ist entweder α oder β die identische Abbildung, so heißt die Zerlegung einseitige funktionale Zerlegung.

Funktionale Dekompositionen Boolescher Funktionen werden im Rahmen der Logiksynthese kombinatorischer logischer Schaltkreise eingesetzt.

Können in jedem Schritt nichttriviale Zerlegungen berechnet werden, so kann das entsprechende Verfahren rekursiv auf die jeweiligen Zerlegungs- und Zusammensetzungsfunktionen angewendet werden, um so eine Realisierung über einer gegebenen vollständigen Bausteinbibliothek zu erhalten.

[1] Molitor, P.; Scholl, Chr.: Datenstrukturen und Effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen. B.G. Teubner Stuttgart-Leipzig, 1999.