Random Boolean functions induced by random Boolean expressions

Abstract

We consider a set of Boolean expressions with a probability measure on it and call this our model. This model induces a probability measure on the Boolean functions. The induced probability depends strongly on the underlying Boolean expressions, so we consider several different sets of Boolean expressions, i.e. different models, distinguished by the connectors they are built with and/or by the structure of the expressions. We examine the relation between the underlying class of Boolean expressions and the induced probability and investigate the shape and its properties. We study the question if this probability measure has a limit when the size of the underlying Boolean expressions tends to infinity. The aim of this thesis is to give a broad overview of several different set-ups for such models considered in the literature with a slight focus on models that allow interesting conclusions regarding the number of satisfiable assignments of read-one expressions.