Probabilities of Boolean Functions given by Random Implicational Formulas

摘要

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.