  We present here a new and universal approach for the study of random and/or
trees, unifying in one framework many different models, including some novel
ones not yet understood in the literature. An and/or tree is a Boolean
expression represented in (one of) its tree shapes. Fix an integer $k$, take a
sequence of random (rooted) trees of increasing size, say $(t_n)_{n\ge 1}$, and
label each of these random trees uniformly at random in order to get a random
Boolean expression on $k$ variables.
  We prove that, under rather weak local conditions on the sequence of random
trees $(t_n)_{n\ge 1}$, the distribution induced on Boolean functions by this
procedure converges as $n$ tends to infinity. In particular, we characterise
two different behaviours of this limit distribution depending on the shape of
the local limit of $(t_n)_{n\ge 1}$: a degenerate case when the local limit has
no leaves; and a non-degenerate case, which we are able to describe in more
details under stronger conditions. In this latter case, we provide a
relationship between the probability of a given Boolean function and its
complexity.
  The examples covered by this unified framework include trees that interpolate
between models with logarithmic typical distances (such as random binary search
trees) and other ones with square root typical distances (such as conditioned
Galton--Watson trees).
