Composition of Post classes and normal forms of Boolean functions

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