The realization of monotone boolean functions (preliminary version)

Abstract

In this paper we study the complexity of realizing a monotone but otherwise arbitrary Boolean function. We consider realizations by means of networks and formulae. In both cases the possibility exists that although a monotone function can always be realized in terms of monotone basis functions, a more economical realization may be possible if basis functions that are not themselves monotone are used. Thus, we have four cases, namely:1. The cost of realizing a monotone function with a network over a 2. The cost of realizing with a network over a 3. The cost of realizing with a formula over a 4. The cost of realizing with a formula over a universal basis. a monotone function monotone basis. a monotone function universal basis. a monotone function monotone basis. For the first case, we obtain a complete solution to the problem. For the other three cases, we obtain improvements over previous results and come within a logarithmic factor or two of a complete solution.