Authors: Danièle Gardy ¹; Alan Woods ²

• 1 Parallélisme, Réseaux, Systèmes, Modélisation
• 2 School of Mathematics and Statistics [Crawley, Perth]

We consider two probability distributions on Boolean functions defined in terms of their representations by $\texttt{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 $\textit{True}$ and read-once functions in a fixed number of variables.