Composition of Post classes and normal forms of Boolean functions
From the introduction: ``The plan of the paper is as follows. In Section 2 we restate a lemma on the associativity of function class composition, and state and prove a general sufficient condition for the composition of clones to be a clone. In Section 3 we completely classify those pairs of Boolean clones whose class composition is a clone (Section 3.1), and those pairs whose composition is not a clone (Section 3.2), and we summarize this classification in the two theorems of Section 3.3 -- from the direct point of view of compositions in Theorem 2 and from the reverse point of view of decompositions or factorizations of a given clone in Theorem 3. In Section 4 we consider certain factorizations of the clone \(\Omega\) of all Boolean functions which correspond to normal form representations of functions such as disjunctive normal form (DNF), conjunctive normal form (CNF), and Zhegalkin or Reed-Muller polynomial representations. We conclude by showing that the representation using the ternary median (majority) function, based on the factorization of \(\Omega\) with the clone \(SM\) of self-dual monotone functions as the leftmost factor, is asymptotically more efficient than the more classical DNF, CNF and polynomial representations which use Boolean lattice or Boolean ring operations.''
scientific article; zbMATH DE number 5080066
scientific article