Introduction

The basic step in functional decomposition of a Boolean function f : {0, 1}n ↦ {0, 1} with input variables N = {x1, x2, … xn} is essentially the partitioning of the set N into two disjoint sets A = {x1, x2, …, xp} (the “modular set”) and B = {xp+1, …, xn} (the “free set”), such that f = F(g(xA), xB). The function g is called a component (subfunction) of f, and F is called a composition (quotient) function of f. The idea here is that F computes f based on the intermediate result computed by g and the variables in the free set. More complex (Ashenhurst) decompositions of a function f can be obtained by recursive application of the basic decomposition step to a component function or to a quotient function of f.

Functional decomposition for general Boolean functions has been introduced in switching theory in the late 1950s and early 1960s by Ashenhurst, Curtis, and Karp [1, 2, 20, 23, 24]. More or less independent from these developments, decomposition of positive functions has been initiated by Shapley [36], Billera [5, 4], and Birnbaum and Esary [12] in several contexts such as voting theory (simple games), clutters, and reliability theory. However, the results in these areas are mainly formulated in terms of set systems and set operations.