Generalised and quotient models for random and/or trees and application to satisfiability

This article is motivated by the following satisfiability question: pick uniformly at random an (Formula presented.) Boolean expression of length n, built on a set of (Formula presented.) Boolean variables. What is the probability that this expression is satisfiable? asymptotically when n tends to infinity? The model of random Boolean expressions developed in the present paper is the model of Boolean Catalan trees, already extensively studied in the literature for a constant sequence (Formula presented.). The fundamental breakthrough of this paper is to generalise the previous results for any (reasonable) sequence of integers (Formula presented.), which enables us, in particular, to solve the above satisfiability question. We also analyse the effect of introducing a natural equivalence relation on the set of Boolean expressions. This new quotient model happens to exhibit a very interesting threshold (or saturation) phenomena at (Formula presented.).