Composition of Post classes and normal forms of Boolean functions
Couceiro, Miguel; Foldes, Stephan; Lehtonen, Erkko
Discrete Math., 306 (2006), 3223-3243
http://dx.doi.org/10.1016/j.disc.2006.06.014
The class composition $C \circ K$ of Boolean clones, being the set of composite functions $f(g_1, \dots, g_n)$ with $f \in C$, $g_1, \dots, g_n \in K$, is investigated. This composition $C \circ K$ is either the join $C \vee 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 $\Omega$ 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 $\Omega$ 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.
|
