Том 3, номер 1, 1996 г., Стр. 3-8

УДК 519.6
М. И. Гринчук
О сложности реализации булевых функций в трех классах схем в базисе, состоящем из всех симметрических функций

Аннотация:
Изучается сложность реализации произвольных булевых функций схемами в бесконечном базисе, состоящем из всех симметрических функций, причем вес симметрической функции считается равным числу ее аргументов. Рассмотрены три модели схем: произвольные схемы из функциональных элементов, схемы без ветвления выходов (формулы) и схемы, состоящие только из одного элемента (в этом случае реализация булевых функций осуществляется отождествлением аргументов симметрической функции). Для каждого из трех случаев получена асимптотика соответствующей функции Шеннона. Для третьей модели найдены булевы функции, имеющие максимально возможный порядок сложности. 
Ил. 1, библиогр. 2.

Гринчук М. И. ¹
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия

Статья поступила 20 ноября 1995 г.