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

Article collection "Mathematical Problems of Cybernetics" №19, Moscow, 2019
Authors: Akulov Y.V.
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.
Boolean function, extended superposition, closed class, completeness criterion
Publication language: russian,  pages: 76 (p. 123-198)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Akulov Yaroslav Viktorovich,  ,  МГУ им. М. В. Ломоносова, механико-математический факультет