Probabilities of Boolean Functions given by Random Implicational Formulas

  • Antoine Genitrini
  • Bernhard Gittenberger
  • Veronika Kraus
  • Cécile Mailler
Keywords: Boolean functions, Boolean formulas, Implication, Analytic combinatorics, Complexity, Shannon effect, Logic


We study the asymptotic relation between the probability and the complexity of Boolean functions in the implicational fragment which are generated by large random Boolean expressions involving variables and implication, as the number of variables tends to infinity. In contrast to models studied in the literature so far, we consider two expressions to be equal if they differ only in the order of the premises. A precise asymptotic formula is derived for functions of low complexity. Furthermore, we show that this model does not exhibit the Shannon effect.

An erratum was added to this paper on Feb 20, 2014.

Article Number