The fraction of large random trees representing a given Boolean function in implicational logic

We consider the logical system of Boolean expressions built on the single connector of implication and on positive literals. Assuming all expressions of a given size to be equally likely, we prove that we can define a probability distribution on the set of Boolean functions expressible in this system. Then we show how to approximate the probability of a function f when the number of variables grows to infinity, and that this asymptotic probability has a simple expression in terms of the complexity of f . We also prove that most expressions computing any given function in this system are “simple”, in a sense that we make precise. The probability of all read‐once functions of a given complexity is also evaluated in this model. At last, using the same techniques, the relation between the probability of a function and its complexity is also obtained when random expressions are drawn according to a critical branching process. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011