Языки и исчисления

При некотором сложность большинства булевых -местных функций:

(Отметьте один правильный вариант ответа.)

Варианты ответа

не меньше

не больше

не меньше $C{\raise0.7ex\hbox{${2^n }$} \!\mathord{\left/ {\vphantom {{2^n } n}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$n$}}$ (Верный ответ)

Похожие вопросы

Количество всех

-местных булевых функций равно:

Сложность большинства булевой

-местной функций при наибольшем размере

их схем:

Сложность любой булевой

-местной функций при наибольшем размере

их схем:

Количество всех различных

-местных схем размера

оценивается:

Контрпример к секвенции $A \mapsto B$ будет контрпримером к формуле ( $\wedge A$ - конъюнкция, $\vee A$ - дизъюнкция формул из А)

Вычитание двух

-разрядных двоичных чисел по модулю 2^n

выполнима схема:

Верно утверждение для любой булевой функции

от

аргументов:

Если

- минимальная глубина схемы, вычисляющая функцию

, то:

Фильтр на S со свойством $A \in F$ или $S\backslash A \in F\forall A \subset S$ называется:

Для сложения двух

-разрядных двоичных чисел: