Article collection "Mathematical Problems of Cybernetics" №19, Moscow, 2019
On classes of Boolean functions expressible in terms of extended superposition
The present article considers the problem of implementing Boolean functions by formulas of a special type, where trivial formulas are taken to be functions from a certain set. For this implementation we introduce the notion of extended superposition operation. For this operation we obtain a criterion of Boolean function expressibility, also for all classes of Boolean functions closed under extended superposition we prove a criterion of decomposability into an intersection of other classes' extended closure, and finally a criterion of completeness of extended superposition for the class P2 and all precomplete classes of Boolean functions. The article also features a complete description of all extended closures of Boolean function classes which contain non-constant functions relatively to each other.