Nondisjoint decomposition of monotone Boolean functions

Jan C. Bioch

Erasmus University Rotterdam


We discuss nondisjoint decompositions of a monotone Boolean function f of

the form f =F(A,B,g(B,C)), where A,B and C are disjoint sets of variables. If B

is the empty set then the theory of decompositions, studied in game theory,

reliability theory etc. is well understood. However, in the general case little or

nothing is known. We present some results on the lattice of components g of f

for a fixed partition A,B and C, as well as on the properties of the so-called

modular(bound) sets of f.