2) Пусть A - множество функций из P2(X^n),существенно зависящая от n переменных |A| >= 1/2 * 2^2^n. Доказать что система A полна в P2, n>=2

задан 27 Май '16 16:02

изменен 27 Май '16 16:43

Имеется в виду множество функций, каждая из которых существенно зависит от всех n переменных?

(27 Май '16 19:09) falcao

@falcao да

(27 Май '16 23:27) PavLee
10|600 символов нужно символов осталось
0

Здесь достаточно применить критерий Поста, и из соображений мощности показать, что A не содержится целиком ни в одном из предполных классов.

Количество функций от $%n$% переменных в $%T_0$% равно половине числа всех функций от $%n$% переменных, то есть $%\frac122^{2^n}$%. Среди таких функций заведомо имеются те, у которых не все переменные существенны. Поэтому $%A\not\subseteq T_0$%. Аналогично для $%T_1$%.

Линейных функций от $%n$% переменных, которые существенно зависят от них, имеется всего две. Ясно, что при $%n\ge2$% мощность $%A$% не меньше восьми, откуда $%A\not\subseteq L$%.

Все монотонные функции помимо констант содержаться в пересечении $%T_0\cap T_1$%. Следовательно, $%A\not\subseteq M$%.

Наконец, $%A\not\subseteq S$%, поскольку $%|S|=2^{2^{n-1}} < |A|$%.

ссылка

отвечен 28 Май '16 11:17

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,074

задан
27 Май '16 16:02

показан
415 раз

обновлен
28 Май '16 11:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru