Modular Decomposition of Boolean Functions

Modular decomposition is a thoroughly investigated topic in many areas such as switching theory, reliability theory, game theory and graph theory. Most appli- cations can be formulated in the framework of Boolean functions. In this paper we give a uni_ed treatment of modular decomposition of Boolean functions based on the idea of generalized Shannon decomposition. Furthermore, we discuss some new results on the complexity of modular decomposition. We propose an O(mn)- algorithm for the recognition of a modular set of a monotone Boolean function f with m prime implicants and n variables. Using this result we show that the the computation of the modular closure of a set can be done in time O(mn2). On the other hand, we prove that the recognition problem for general Boolean functions is coNP-complete.