Reference : Composition of Post classes and normal forms of Boolean functions
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Composition of Post classes and normal forms of Boolean functions
Couceiro, Miguel mailto [University of Tampere, Finland]
Foldes, Stephan mailto [Tampere University of Technology, Finland]
Lehtonen, Erkko mailto [Tampere University of Technology, Finland]
Discrete Mathematics
Yes (verified by ORBilu)
[en] function class composition ; clones ; Boolean functions ; Post classes ; class factorization ; normal forms ; DNF ; CNF ; Zhegalkin polynomial ; Reed–Muller polynomial ; formulas ; efficient representations ; complexity ; median ; ternary majority
[en] The class composition CK of Boolean clones, being the set of composite functions f(g1,...,gn) with f∈C, g1,...,gn∈K, is investigated. This composition CK 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 Boolean functions as a composition of minimal clones are described and seen to correspond to normal form representations of Boolean functions. The median normal form, 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 normal form representation.

File(s) associated to this reference

Fulltext file(s):

Limited access
CPCNFBF.pdfAuthor postprint445.7 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.