Automation of the problem of determining the complexity of a Boolean function
Published: 20.11.2014
Authors: Gurchenkov A.A., Egorova E.K.
Published in issue: #5(29)/2014
DOI: 10.18698/2308-6033-2014-5-1324
Category: Basic science | Chapter: Mathematics
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.
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 algorithms and solution of problems of mathematical physics."]. Abrau-Dyurso, 15-21 September, 2008, pp. 143-144.
[9] Gurchenkov A.A., Esenkov A.S., Tsurkov V.I. Izvestiya RAN. Teoriya i sistemy upravleniya - Proceedings of the Russian Academy of Sciences. Control Theory and Systems, 2006, no. 1, pp. 135-142.
[10] Gurchenkov A.A., Esenkov A.S., Tsurkov V.I. Izvestiya RAN. Teoriya i sistemy upravleniya - Proceedings of the Russian Academy of Sciences. Control Theory and Systems, 2006, no. 3, pp. 82-89.
[11] Gurchenkov A.A., Esenkov A.S., Tsurkov V.I. Avtomatika i telemekhanika - Automatics and Telemechanics, 2007, no. 2, pp. 81-94.
[12] Gurchenkov A.A., Eleonskiy V.M., Kulagin N.E. O sopostavlenii bifurkatsiy v klassicheskoi i kvantovoi mekhanike. Sluchai integriruemykh sistem. [On comparing the bifurcations in classical and quantum mechanics. Case of integrable systems]. Moscow, Comp. Center RAS Publ., 2009, 84 p.
[13] Gurchenkov A.A., Yalamov Y.I. Prikladnaya mekhanika i tekhnicheskayafizika - Applied Mechanics and Technical Physics, 1980, no. 4, p. 66.
[14] Gurchenkov A.A., Esenkov A.S., Tsurkov V.I. Izvestiia RAN. Teoriia i sistemy upravleniia - Proceedings of the Russian Academy of Sciences. Control theory and systems, 2006, no.1, pp. 141-148.
[15] Gurchenkov A.A. Izv. vuzov. Ser. Priborostroenie - University Proced. Ser. Instrument Engineering, 2001, vol. 44, no. 2, p. 44.
[16] Gurchenkov A.A. Inzhenerno-fizicheskii zhurnal - Journal of Engineering Physics, 2002, vol. 75, no. 3, pp. 28-32.
[17] Gurchenkov A.A. J. of Engineering Physics and Thermo Physics, 2002, vol. 75, no. 3, p. 554.
[18] Gurchenkov A.A. Prikladnaya mekhanika i tekhnicheskaya fizika - Applied Mechanics and Technical Physics, 2001, vol. 42, no. 4, pp. 48-51.
[19] Gurchenkov A.A., Korneev V.V., Nosov M.V. Prikladnaya matematika i mekhanika - Applied Mathematics and Mechanics, 2008, vol. 72, no. 6, pp. 904-911.
[20] Gurchenkov A.A. Dokl. Akademii nauk - Acad. Sci. Reports, 2002, vol. 382, no. 4, p. 476.
[21] Gurchenkov A.A., Nosov M.V, Tsurkov V.I. Control of Fluid-Containing Rotating Rigid Bodies. CRS Press, 2013, 147 p.
[22] Gurchenkov A.A. Prikladnaya matematika i mekhanika - Applied Mathematics and Mechanics, 2002, vol. 66, iss. 2, pp. 251-255.
[23] Gurchenkov A.A., Eleonskiy V.M., Kulagin N.E. Sloistye struktury v nelineinykh vektornykh polyakh [Layered structures in nonlinear vector fields]. Moscow, Comp. Center RAS Publ., 2007, 177 p.
[24] Gurchenkov A.A., Kulagin N.E. Ob uzorakh simmetrii v prostykh modelyakh nelineinogo skaliarnogo polya [Patterns of symmetry in simple models of nonlinear scalar field]. Moscow, Comp. Center RAS, 2004, 84 p.
[25] Gurchenkov A.A., Moroz I.I., Popov N.N.Inzhenernyizhurnal: naukai innovatsii - Engineering Journal: Science and Innovation, 2013, iss. 9. Available at: http://engjournal.ru/catalog/appmath/hidden/1166.html
[26] Gurchenkov A.A., Romanenkov A.M. Inzhenernyi zhurnal: nauka i innovatsii - Engineering Journal: Science and Innovation, 2013, iss. 2. Available at: http://engjournal.ru/catalog/appmath/hidden/613.html
[27] Gurchenkov A.A., Egorova E.K. Inzhenernyi zhurnal: nauka i innovatsii - Engineering Journal: Science and Innovation, 2013, iss. 12. Available at: http://engjournal.ru/catalog/appmath/hidden/1167.html
[28] Gurchenkov A.A. Inzhenernyi zhurnal: nauka i innovatsii - Engineering Journal: Science and Innovation, 2013, iss. 2. Available at: http://engjournal.ru/catalog/appmath/hidden/603.html
[29] Gurchenkov A.A. Inzhenernyi zhurnal: nauka i innovatsii - Engineering Journal: Science and Innovation, 2012, iss. no. 7. Available at: http://engjournal.ru/articles/297/297.pdf
[30] Gurchenkov A.A., Nosov M.V., Tsurkov V.I. Upravlenie vrashchaiushchimisia tverdymi telami s zhidkost’iu [Control of rotating solids with the fluid]. Moscow, Fizmatlit Publ., 2011, 202 p.