• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Математические заметки. 2019. Т. 105. № 1. С. 32-41.

Исследуется задача о сложности реализации булевых функций схемами в бесконечных полных базисах, содержащих все монотонные функции, имеющие при этом нулевой вес (стоимость использования) и конечное число немонотонных функций единичного веса. Для сложности реализации булевых функций в случае, когда  единственным немонотонным элементом базиса является отрицание, исчерпывающее описание  было получено А.А. Марковым: минимальное число отрицаний, достаточное для реализации произвольной булевой функции f (инверсионная сложность функции f), равно ]log2(d(f)+1)[, где d(f) — максимальное  (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции с 1 на 0.

В данной работе этот результат обобщен на случай вычисления булевых функций над произвольным базисом B указанного вида. Установлено, что минимальное число немонотонных функций, достаточное для вычисления произвольной булевой функциии f, равно  ]log2(d(f)/D(B)+1)[, где D(B) = max d(ω), максимум берется по всем немонотонным функциям ω базиса B.