Аннотация:Исследуется задача о сложности реализации булевых функций
схемами в бесконечных полных базисах, содержащих все монотонные функции,
имеющие при этом нулевой вес (стоимость использования) и конечное число немонотонных функций единичного веса. Для сложности реализации
булевых функций в случае, когда единственным немонотонным элементом базиса является
отрицание, исчерпывающее описание было получено А.\,А.~Марковым: минимальное число отрицаний, достаточное для реализации произвольной булевой функции~$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$.