Bibliographic Metadata

Random Boolean functions induced by random Boolean expressions / durch Clemens Haim
AuthorHaim, Clemens
CensorGittenberger, Bernhard
PublishedWien, 2016
Descriptionx, 119 Seiten : Diagramme
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2016
Zusammenfassung in deutscher Sprache
Document typeThesis (Diplom)
Keywords (EN)random Boolen functions / random Boolean expression / Shannon effect
URNurn:nbn:at:at-ubtuw:1-89312 Persistent Identifier (URN)
 The work is publicly available
Random Boolean functions induced by random Boolean expressions [1.23 mb]
Abstract (English)

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.