Irreducible Boolean Functions

MaRDI QIDQ6208154zbMATH OpenFDO

Authors Moncef Bouaziz, Miguel Couceiro, Maurice Pouzet

Publication date 18 January 2008

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Triple systems (05B07) Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07) Boolean functions (06E30)

Abstract: This paper is a contribution to the study of a quasi-order on the set $Omega$ of Boolean functions, the emph{simple minor} quasi-order. We look at the join-irreducible members of the resulting poset $ildeOmega$. Using a two-way correspondence between Boolean functions and hypergraphs, join-irreducibility translates into a combinatorial property of hypergraphs. We observe that among Steiner systems, those which yield join-irreducible members of $ildeOmega$ are the -2-monomorphic Steiner systems. We also describe the graphs which correspond to join-irreducible members of $ildeOmega$.

This page was built for publication: Irreducible Boolean Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6208154)