Оценки высокой степени точности для сложности булевых формул в некоторых базисах из элементов с прямыми и итеративными входами

Актуальность и цели. В математической кибернетике одной из основных задач является задача синтеза управляющих систем, заключающаяся в построении схемы из заданного класса, которая реализует заданную функцию алгебры логики. При решении этой задачи часто требуется учитывать различного рода ограничения на структуру и параметры управляющих систем. Такие ограничения часто более точно описывают реальные вычисления, а исследование сложности функций в моделях с ограничениями представляет большой теоретический интерес. Рассматриваемое в данной работе ограничение относится к способам соединения элементов в схеме. Входы элементов схем делятся на два типа - прямые и итеративные. Итеративные входы служат для присоединения к ним выходов других элементов, а прямые входы являются входами схем. Задача синтеза в этой модели рассматривается для случая формул, т.е. схем без ветвлений выходов элементов. Целью данной работы является получение оценок функции Шеннона высокой степени точности для сложности формул в некоторых полных базисах указанного типа, т.е. оценок, в которых устанавливается асимптотика второго члена асимптотического разложения этой функции. Ранее была получена только асимптотика функции Шеннона для базисов, итеративное замыкание которых содержит класс монотонных функций, оценки высокой степени точности для широких классов базисов в этой модели известны не были. Материалы и методы. В работе, в частности, приводится модификация известного ранее оптимального метода синтеза формул с использованием техники моделирования функций алгебры логики переменными на компонентах специальных разбиений множества наборов булева куба. В основе конструкции лежит построение специальных формул, которые реализуют функции, имеющие селекторные разбиения множества своих переменных с константной энтропией. Результаты. Получены оценки высокой степени точности функции Шеннона для сложности формул алгебры логики в некоторых полных базисах с прямыми и итеративными переменными, итеративное замыкание которых содержит класс монотонных функций. Выводы. Впервые в классе формул в базисах с прямыми и итеративными входами выделен достаточно широкий подкласс, в котором получены оценки высокой степени точности функции Шеннона для их сложности.