Composition of Post classes and normal forms of Boolean functions

The class composition C∘KC∘K of Boolean clones, being the set of composite functions f(g1,…,gn)f(g1,…,gn) with f∈Cf∈C, g1,…,gn∈Kg1,…,gn∈K, is investigated. This composition C∘KC∘K is either the join C∨KC∨K in the Post Lattice or it is not a clone, and all pairs of clones C,KC,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.