Сколько функций от переменных x1, x2, . . . , xn содержит множество L ∩ (T0 ∪ S)? Преобразования привели к тому, что надо посчитать вот такое выражение: |L∩0| + |L∩S| - |LST0|, а вот как посчитать это, разобрать уже не могу. Знаю, что L: 2^(n+1), T0: 2^(2^n - 1), S: 2^(2^(n-1)), но не могу применить

задан 22 Апр '19 17:53

Ошибочка, |L∩T0| вместо |L∩0|

(22 Апр '19 17:54) LaCost765
10|600 символов нужно символов осталось
0

Линейная функция имеет вид $%f=a+a_1x_1+\cdots+a_nx_n$%. Их $%2^{n+1}$%. Функция принадлежит $%T_0$%, если $%a=0$%, и самодвойственна, если $%a_1+\cdots+a_n=1$%. Все такие функции подходят, а не подходят функции со свойством $%a=1$%, $%a_1+\cdots+a_n=0$%. Таких функций $%2^{n-1}$% при $%n\ge1$%, так как первые $%n-1$% переменных суммы выбираются свободно. Их количество надо вычесть, и получится $%2^{n+1}-2^{n-1}=3\cdot2^{n-1}$%.

При $%n=0$% получается особый случай: предыдущая формула неприменима, и достаточно заметить, что из двух констант подходит одна: $%0$%.

Здесь задача касается только линейных функций, а они устроены просто, и всё легко анализируется.

ссылка

отвечен 22 Апр '19 19:13

А почему она самодвойственна, если a1+⋯+an=1?

(22 Апр '19 21:01) LaCost765

@LaCost765: это сразу следует из определения: противоположный набор имеет вид x1+1, ... , xn+1. На нём значение функции отличается от значения на наборе x1, ... , xn на величину a1+...+an. Значение на противоположном наборе должно быть противоположным, что и означает a1+...+an=1.

Для ясности: функции x, x+1, x+y+z, x+y+z+1 самодвойственны; x+y и x+y+1 нет.

(22 Апр '19 22:04) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,357
×575
×81

задан
22 Апр '19 17:53

показан
158 раз

обновлен
22 Апр '19 22:04

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

по почте:

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

по RSS:

Ответы

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

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