KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №19, Moscow, 2019
Authors: Akulov Y.V.
On classes of Boolean functions expressible in terms of extended superposition
Abstract:
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.
Keywords:
Boolean function, extended superposition, closed class, completeness criterion
Publication language: russian,  страниц: 76 (p. 123-198)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text: