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

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