[Back]

A. Genitrini, B. Gittenberger, V. Kraus, C. Mailler:
"Erratum to: Probabilities of Boolean functions given by random implicational formulas";
Electronic Journal of Combinatorics, 19 (2) (2014), 6.

Probabilities of Boolean Functions given by Random Implicational Formulas

Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus, Cécile Mailler







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.



Keywords

Boolean functions; Boolean formulas; Implication; Analytic combinatorics; Complexity; Shannon effect; Logic