О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами | Прикладная дискретная математика. 2015. № 4(30).

Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. А. Марковым в 1957 г. показано, что минимальное число немонотонных элементов, достаточное для реализации функции f, равно \log ₂(d(f) + 1)], где d(f) - максимальное число переключений значений функции f с 1 на 0 (максимум берётся по всем возрастающим цепям наборов значений переменных). В работе установлено, что в общем случае сложность реализации булевой функции f равна P\log2(d(f ) + 1)] - 0(1), где р - минимальный вес немонотонных элементов базиса. Получено также аналогичное обобщение классического результата А. А. Маркова о сложности реализации систем булевых функций.