Composition of Post classes and normal forms of Boolean functions
Lehtonen, Erkko; Foldes, Stephan; Couceiro, Miguel (2006), Composition of Post classes and normal forms of Boolean functions, Discrete Mathematics, 306, 24, p. 3223-3243. http://dx.doi.org/10.1016/j.disc.2006.06.014
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Mathematics
MetadataShow full item record
Abstract (EN)The classcompositionC∘K of Boolean clones, being the set of composite functionsf(g1,…,gn) with f∈C, g1,…,gn∈K, is investigated. This compositionC∘K is either the join C∨K in the Post Lattice or it is not a clone, and all pairs of clones C,K are classified accordingly. Factorizations of the clone Ω of all Booleanfunctions as a composition of minimal clones are described and seen to correspond to normalform representations of Booleanfunctions. The median normalform, arising from the factorization of Ω with the clone SM of self-dual monotone functions as the leftmost composition factor, is compared in terms of complexity with the well-known DNF, CNF, and Zhegalkin (Reed–Muller) polynomial representations, and it is shown to provide a more efficient normalform representation.
Subjects / KeywordsTernary majority; Median; Complexity; Efficient representations; Formulas; Reed–Muller polynomial; Zhegalkin polynomial; CNF; DNF; Normal forms; Class factorization; Post classes; Boolean functions; Clones; Function class composition
Showing items related by title and author.