And/or tree probabilities of Boolean functions
Danièle Gardy, Alan Woods
Abstract
We consider two probability distributions on Boolean functions defined in terms of their representations by and/or trees (or formulas). The relationships between them, and connections with the complexity of the function, are studied. New and improved bounds on these probabilities are given for a wide class of functions, with special attention being paid to the constant function True and read-once functions in a fixed number of variables.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page