Точное значение немонотонной сложности булевых функций

Исследуется задача о сложности реализации булевых функций схемами в бесконечных полных базисах, содержащих все монотонные функции, имеющие при этом нулевой вес (стоимость использования) и конечное число немонотонных функций единичного веса. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А. А. Марковым: минимальное число отрицаний, достаточное для реализации произвольной булевой функции $f$ (инверсионная сложность функции $f$), равно $\lceil\log_{2}(d(f)+1)\rceil$, где $d(f)$ – максимальное (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции с 1 на 0. В данной работе этот результат обобщен на случай вычисления булевых функций над произвольным базисом $B$ указанного вида. Установлено, что минимальное число немонотонных функций, достаточное для вычисления произвольной булевой функции $f$, равно $\lceil\log_{2}(d(f)/D(B)+1)\rceil$, где $D(B)=\max d(\omega)$; максимум берется по всем немонотонным функциям $\omega$ базиса $B$.
Библиография: 15 названий.