Associative and commutative tree representations for Boolean functions

Abstract

Since the 90's, several authors have studied a probability distribution on the set of Boolean functions on $n$ variables induced by some probability distributions on formulas built upon the connectors $And$ and $Or$ and the literals $\{x_1,{\bar{x}}_1,\dots ,x_n,{\bar{x}}_n\}$. These formulas rely on plane binary labelled trees, known as Catalan trees. We extend all the results, in particular the relation between the probability and the complexity of a Boolean function, to other models of formulas: non-binary or non-plane labelled trees (i.e. Polya trees). This includes the natural tree class where associativity and commutativity of the connectors $And$ and $Or$ are realised.

arXiv comment36 pages, 9 figures

Cited by in corpus (1)

• 2-Xor revisited: satisfiability and probabilities of functions