Premium
The fraction of large random trees representing a given Boolean function in implicational logic
Author(s) -
Fournier Hervé,
Gardy Danièle,
Genitrini Antoine
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20379
Subject(s) - mathematics , boolean function , branching process , discrete mathematics , boolean model , boolean expression , simple (philosophy) , probability generating function , function (biology) , infinity , tree diagram , random variable , product term , probability mass function , combinatorics , two element boolean algebra , algebra over a field , pure mathematics , statistics , philosophy , epistemology , evolutionary biology , biology , mathematical analysis , bayesian probability , posterior probability , filtered algebra
We consider the logical system of Boolean expressions built on the single connector of implication and on positive literals. Assuming all expressions of a given size to be equally likely, we prove that we can define a probability distribution on the set of Boolean functions expressible in this system. Then we show how to approximate the probability of a function f when the number of variables grows to infinity, and that this asymptotic probability has a simple expression in terms of the complexity of f . We also prove that most expressions computing any given function in this system are “simple”, in a sense that we make precise. The probability of all read‐once functions of a given complexity is also evaluated in this model. At last, using the same techniques, the relation between the probability of a function and its complexity is also obtained when random expressions are drawn according to a critical branching process. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011