About One Efficient Method of Synthesis of Boolean Formulas and Circuits of Functional Elements

Currently relevance of modeling problems of analysis and synthesis of mathematical models of discrete logic control and computing devices persists. Particularly important is fhe task of estimating fhe oufpuf of difficulty in presenting a Boolean function (BF) in fhe classes of formulas and schemes of functional elements (FE). This problem is sfill relevant today. Because of ongoing research in fhe field of mathematical cybernetics and discrete mathematics should be fhaf obtaining fhe required minimum solutions using dimensions of complexify inevitably involves fhe use of nature exhaustive search algorithms. The re-sulf is a greafer complexify (including compufafional complexify and labor inpuf) obfaining such a decision has fhe funcfions of small dimension. This required fhe development of new approaches formulation of fhe problem and ifs solutions, significantly differ in fhe complexify of exhaustive search [1-3]. So, fhe problem of fhe realization of Boolean functions in fhe class of formulas and - circuits made of functional elements in different bases. Obtained in this scheme are applied in discrete logic devices, and managemenf informafion processing, fhe complexify (qualify) of fhe main characferisfics of which depend on com-pufing and confrol engineering. And if nofed fhaf fhe symmefric Boolean funcfions are increasingly being used in fhe design of computing devices due fo fheir specific properties [7-8].The purpose of this paper is fo clarify fhe upper bounds for fhe complexify of symmetric BF in sfandarf and Zhegalkin bases, as well as fhe development of algorithms fo automate fhe synthesis of discrefe informafion processing devices. An efficienf consfrucfive mefhod synfesis of digifal circuifs and formulas is offered. This mefhod is based on recurrence relafions (funcfional equafions - FE [9]) and is accompanied by a receipf in advance analyfically upper esfimafes of various indicafors of complexify (fhe number of leffers, number of subformulas; according fo fhe number of functional elements), including schemes for minimum complexify. In this paper we consider some classes of func-fions, which are accurafe upper bounds for fhe complexify mefrics. To aufomafe fhe process and expanding fhe sfudy of individual cases fhe algorithm implemented structural and functional decomposition [2] is used. A convenient model for fhe rep-resenfafion of a Zhegalkin polynomial form fhaf used in fhe algorifhm fhe mafrix represenfafion has been designed. The resulfs are applicable as in fhe synthesis device (af fhe logical design) in multiprocessor computing and control systems, and fhe de-velopmenf of algorifhms for fhe effecfive operafion of fhese sysfems.

булевы функции, синтез формул и схем, функционал, декомпозиция, сложность, минимизация, функциональные уравнения, симметрические функции, boolean function, syntheses formula and circuit, decomposition, difficulty, minimization, functional of fhe equafion, symmefric funcfions

1. Журавлев Ю. И. Теоретико-множественные методы в алгебре логики // Проблемы кибернетики. 1962. № 8.

2. Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960.

3. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. 1959. № 2.

4. Теряев Е. Д., Петрин К. В., Филимонов Н. Б., Филимонов А. Б. Агентные технологии в автоматизированных информационно-управляющих системах. Часть 1. Основы агентного подхода // Мехатроника, автоматизация, управление. 2010. № 7. С. 11-21.

5. Теряев Е. Д., Петрин К. В., Филимонов Н. Б., Филимонов А. Б. Агентные технологии в автоматизированных информационно-управляющих системах. Часть II. Агентные решения в задачах контроля и управления // Мехатроника, автоматизация, управление. 2010. № 10. С. 11-21.

6. Вагин В. Н., Головина Е. Ю., Загорянская А. А. и др. Достоверный и правдоподобный вывод в интеллектуальных системах. М.: Физматлит, 2004.

7. Чебурахин И. Ф. Алгоритмизация представления булевых функций, минимальной сложностью, в базисе Жегалкина в классах формул и схем // Мехатроника, автоматизация, управление. 2012. № 12. С. 7-14.

8. Чебурахин И. Ф. Математические модели для минимизации и автоматизации синтеза дискретных управляющих систем // Мехатроника, автоматизация, управление. 2012. № 4. С. 5-13.

9. Чебурахин И. Ф. Сложность булевых функций для интеллектуальных систем синтеза цифровых ИС // Изв. РАН. ТиСУ. 2006. № 3. С. 150-165.

10. Чебурахин И. Ф. Показатели сложности симметрических полиномов Жегалкина. Тез. докл. XV Международной конф. "Проблемы теоретической кибернетики" (Казань, 2-7 июня 2008 г.). Казань, 2008. С. 123.

11. Чебурахин И. Ф. Сложность симметрических полиномов Жегалкина // XVII Международная школа-семинар "Синтез и сложность управляющих систем" имени академика О. Б. Лупанова (27.10-1.11.2008. Новосибирск), 2008. С. 180-185.

12. Чебурахин И. Ф., Цурков В. И. Модели для оптимизации и автоматизации синтеза дискретных устройств обработки информации в мехатронных системах // 3-я Российская мульти-конференция по проблемам управления. Материалы 7-й научно-технической конференции " Мехатроника, автоматизация, управление МАУ-2010". 12-14 октября 2010. С. 420-423.