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 P₂ 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.

Boolean function, extended superposition, closed class, completeness criterion

Mathematical problems and theory of numerical methods