Мощность класса функций (линейные, самодвойственные...)

[ozhigin]

необходимо найти мощность $|(L-S)\cup T_0|$ , где $L$ - линейные лог.ф-ии, $S$ - самодвойственные, $T_0$ -функции,сохраняющие константу 0

вопрос частично решен , хотя может я и ошибаюсь!

1) Распишем по формуле включений и исключений
$|(L\cap\overline S)\cup T_0| = |L\overline S| + |T_0| - |LT_0\overline S|$

2) Мощность |$T_0$(n)| известна
$|T_0(n)| =2^{2^n-1}$

3) Мощность пересечения линейных и несамодвойственных представляем таким образом
$|L\overline S| = |L|-|LS|$

[Xaositect]

Было же уже.
Какие затруднения у Вас возникли?

Приведу рассуждение, которое наверняка есть в учебнике:
$|L(n)| = 2^{n+1}$
Действительно, линейная функция, зависящая от не более чем $n$ переменных $x_1,x_2,\dots,x_n$ может быть однозначно представлена в виде
$f(x) = \bigoplus\limits_{i=1}^n \alpha_i x_i \oplus \alpha_0$
Т.е. линейных функций ровно столько, сколько наборов коэффициентов $(\alpha_0,\alpha_1,\dots,\alpha_n)$ -- $2^{n+1}$

[ozhigin]

затруднение возникли в $|LS|$ и в $|LT_0\overline S|$ вообще не понимаю, а завтра надо контрольную отдать!

[Xaositect]

Какие линейные функции будут самодвойственными?
Здесь нужно просто скомбинировать определения линейной(ту форму, которую я выше выписал) и самодвойственной функций.

Сколько линейных функций сохраняют нуль?
Тут можно действовать так же, как и в прошлом случае.
А можно просто показать, что $f \in T_0 \Leftrightarrow f\oplus 1\notin T_0$, а значит, их ровно половина.
В первом вопросе, кстати, тоже можно действовать аналогично. Только прибавлять не единицу.

[ozhigin]

т.е $|LS|= 2^{(n-2)}$ и $|LT_0\overline S|=2^{(n+1)}$
можно ответ?

[Xaositect]

$|L\bar{S}(n)| = 2^n$(половина)
$|LT_0\bar{S}(n)| = 2^{n-1}$(половина от половины)

У Вас получилось доказать утверждение о том, какие линейные функции являются самодвойственными?

[ozhigin]

Спасибо.
Нет, мы должны взглянуть на полином Жегалкина понятно, что мощность линейных распишется так - коэффициенты $n+1$ штука и каждый может принимать значение либо 0 , либо 1
а пересечение не ясно

[Xaositect]

ozhigin в сообщении #210997 писал(а):

а пересечение не ясно

Хмм.
Ну вот у нас есть функция $f(x) = \bigoplus \alpha_i x_i \oplus \alpha_0$
В каком случае она будет самодвойственной?
Если она подходит под определение самодвойственности, т.е.
$\overline{f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})} = f(x_1,x_2,\dots,x_n)$
Распишем левую часть:
$\overline{\bigoplus \alpha_i \overline{x_i} \oplus \alpha_0} = \bigoplus \alpha_i (x_i\oplus 1) \oplus \alpha_0 \oplus 1 = \bigoplus \alpha_i x_i \oplus \alpha_0 \oplus\bigoplus \alpha_i \oplus 1$
Это равно $f$, если $\bigoplus \alpha_i = 1$, т.е. у нас есть нечетное число существенных переменных!
Все просто.

[ozhigin]

ну да в комбинаторику надо въехать, а Вы сказали ,что в учебнике такое объяснение, не подскажите учебник?

[Xaositect]

Я, честно говоря, не помню уже, может быть, в учебнике этого нет, а было на лекциях.

А учился я по следующим книгам:
Лекции: Алексеев В.Б. — Дискретная математика
Учебник: Яблонский С.В. — Введение в дискретную математику
Задачник: Гаврилов Г.П., Сапоженко А.А. — Задачи и упражнения по дискретной математике