Об эффективных методах синтеза булевых формул и схем из функциональных элементов

Целью данной работы является уточнение верхних оценок сложности симметрических булевых функций из стандартного и Жегалкина базисов, а также разработка алгоритмов для автоматизации синтеза дискретных устройств обработки информации. Предлагается конструктивный метод синтеза формул и схем на основе рекуррентных соотношений (функциональных уравнений) [9], сопровождаемый получением заранее аналитически верхних оценок различных показателей сложности (по числу букв; числу подформул; по числу функциональных элементов), в том числе и для схем минимальной сложности.

булевы функции, синтез формул и схем, функционал, декомпозиция, сложность, минимизация, функциональные уравнения, симметрические функции, 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.