Дискретная математика

[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)|$ вам известно или здесь тоже нужна подсказка?
Попробуйте найти условия, при которых линейная функция является самодвойственной.(запишите общий вид линейной функции $f(x) = \bigoplus\limits_{i=1}^n \alpha_i x_i \oplus \alpha_0$ и подставьте его в определение самодвойственности)

[Jnrty]

Jnrty:

ozhigin, приведите в порядок формулы. Знаки доллара должны стоять в начале и в конце формулы, а не в середине. И не надо включать текст в тег [mаth] (лучше вообще не употребляйте этот тег без крайней нужды, он сам вставится, куда надо). Иначе тема отправится в "Карантин".

[ozhigin]

Jnrty
вроде поправил!

Добавлено спустя 1 минуту 50 секунд:

Xaositect
с линейными ясно, когда представление в ПЖ без конъюнкций!
итого
$|L| =2^{n+1}$

[AD]

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

с линейными ясно, когда представление в ПЖ без конъюнкций!

Ну и с остальными всё ясно, надо лишь с правильной стороны посмотреть. В случае $T_0$ надо просто посчитать, сколько у них бывает таблиц истинности. В случае $S$ - тоже придумать альтернативное наглядное описание в терминах таблицы истинности (ну помните - перевёртывается там), и всё станет понятно.

[ozhigin]

я знаю по методичке, что мощность множества|S(n)|= $2^{2^{n-1}}$
но я не очень понимаю почему так.
самодвойственные функции в таблице принимают на противоположных наборах разное значение...помогите ещё)

Добавлено спустя 1 минуту 1 секунду:

AD
не очень понмю

[AD]

Ну то есть необходимо и достаточно задать самодвойственную функцию произвольным образом на ровно одном из любой пары противоположных наборов.

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

[ozhigin]

ага, понял функция полностью определена на половине строк, а как тогда перечения найти $|LS|$ и $|LT_0\overline S|$

[AD]

Понимаете, с линейными функциями всё вообще слишком просто. Смотрите внимательно на полином Жегалкина - и всё становится ясно.

Ну то есть проверяем, когда линейный многочлен самодвойственный: тупо выписываем, что такое самодвойственность, и смотрим, что выходит; потом тупо выписываем, что такое $T_0$, и смотрим, что происходит.

[Jnrty]

Jnrty:

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

вроде поправил!

Не вижу изменений в лучшую сторону.

Как обещал - в "Карантин" до исправления.

Правила записи формул можно найти в темах "Первые шаги в наборе формул" и "Краткий ФАК по тегу [math]."
Обязательно запишите свои формулы как положено, а также сообщите свои соображения о способах вычисления Ваших интегралов.
Когда исправите, напишите об этом в теме "Сообщение в карантине исправлено". Кто-нибудь из модераторов перенесёт Вашу тему в раздел "Помогите решить / разобраться (М)".

[PAV]

Тема возвращена