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