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

Глава

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

С. 56-58.

Доказано, что сложность реализации произвольной симметрической булевой функции f от n переменных для f не равной тождественно единице при реализации схемами в базисе антицепных функций, т.е. функций, принимающих значение 1 лишь на попарно несравнимых наборах, равна min(k(f),n-k(f)+2), где k(f) - количество слоев, на которых функция f равна 1.