The realization of monotone Boolean functions (Preliminary Version)
Nicholas J. Pippenger · 1976
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: