9
Автоматизация задачи определения сложности булевой функции
Automation of the problem of determining the complexity
of a Boolean function
© A.A. Gurchenkov
1
, E.K. Egorova
2
1
Bauman Moscow State Technical University, Moscow 105005, Russia
2
Dorodnicyn Computing Centre of the Russian Academy of Sciences, Moscow, 119991,
Russia
The main task of the theory of decomposing Boolean functions is the development and
research of expansion of an arbitrary Boolean function, which is dependent on large
number of variables, to a system of functionally related Boolean functions, each of which
depends on fewer variables. The decomposition task is closely related to the minimization
of Boolean functions, i.e. the problem of finding such an analytical representation of
the function in which the number of letters in it is minimal. We examined the problem
of synthesis of discrete control systems based on formulas and developed the method of
synthesis of Boolean formulas designed for efficient schemes of functional elements,
including schemes for minimum complexity. The resulting algorithm may be implemented
by a parallel programming.
Keywords
: Boolean functions, formulas, Zhegalkin basis, complexity measures,
minimization, decomposition, synthesis, functional equations, schemes.
REFERENCES
[1] Zhuravlev Yu.I. Teoretiko-mnozhestvennye metody v algebre logiki [Set-theoretic
methods in the algebra of logic.].
Problemy kibernetiki — Problems of cybernetics,
1962, no. 8, pp. 5–44.
[2] Kudryavtsev V.B., Gasanov E.E., Podkolzin A.S.
Vvedenie v teoriyu
intellektual’nykh sistem
[Introduction to the theory of intelligent systems]. Moscow,
MSU Publ., 2006, 208 p.
[3] Lupanov O.B.
Problemy kibernetiki — Problems of cybernetics,
1960, iss. 3,
pp. 61–80.
[4] Yablonskiy S.V.
Problemy kibernetiki — Problems of cybernetics,
1959, no. 2,
pp. 75–121.
[5] Pospelov D.A.
Logicheskie metody analiza i sinteza skhem
[Logical methods of
analysis and synthesis of circuits]. Moscow, Energiya Publ., 1974, 342 p.
[6] Egorova E.K., Cheburakhin I.F.
Izvestiya RAN. Teoriia i sistemy upravleniya —
Proceedings of the Russian Academy of Sciences. Control Theory and Systems,
2013, no.3, pp. 121–129.
[7] Tsurkov V.I.
Dekompozitsiya v zadachakh bol’shoi razmernosti
[Decomposition in
large-scale problems]. Moscow, Nauka Publ., 1981, 324 p.
[8] Gurchenkov A.A., Nosov M.V., Ivanov I.M. Optimal’noe upravlenie dvizheniem
volchka s zhidkim napolneniem [Optimal control of movement of the liquid-filled
top].
XVII Vserossiyskaya konferentsiya “Teoreticheskie osnovy i konstruirovanie
chislennykh algoritmov i reshenie zadach matematicheskoi fiziki”
[XVII
National Conference «Theoretical Foundations and construction of numerical
