УДК 519.714 Автоматизация задачи определения сложности булевой функции © А. <...> А.А. Дородницына РАН, Москва, 119991, Россия Основной задачей теории декомпозиции булевых функций являются разработка и исследование методов разложения произвольной булевой функции, зависящей от большого числа переменных, на систему функционально связанных булевых функций, каждая из которых зависит от меньшего числа переменных. <...> С задачей декомпозиции тесно связана задача минимизации булевых функций, т. е. задача о нахождении такого аналитического представления функции, при котором число букв в нем минимально. <...> Рассмотрена задача синтеза дискретных управляющих систем на основе формул. <...> Разработан метод синтеза булевых формул, предназначенный для эффективного построения схем из функциональных элементов, в том числе и для схем минимальной сложности. <...> Полученный алгоритм может быть реализован с помощью параллельного программирования. <...> В данной работе изучаются задачи минимальной по различным показателям сложности реализации булевых функций (БФ) в базисе Жегалкина (в классах формул или схем из функциональных элементов (ФЭ)), находящие многочисленные приложения в информационной индустрии. <...> Проводимые исследования в области математической кибернетики и дискретной математики показывают, что получение требуемого минимального решения по определенным показателям сложности неизбежно предполагает использование алгоритмов переборного характера. <...> Для этого требуется разработка новых подходов постановки задачи и ее решения, заметно отличающихся по трудоемкости от переборных алгоритмов [1–4]. <...> В ряде работ созданы теория локальных алгоритмов оптимизации, алгоритмов вычисления оценок, алгебраическая теория алгоритмов и показано, что можно даже в явном виде строить экстремальные по качеству алгоритмы для решения очень широких классов трудно формализуемых задач, а также разрабатываются математические и прикладные аспекты <...>