посчитать число функций

[chencho]

$|T_0\cap L|$ и $|T_0\cap S|$
Как посчитать число вот таких функций?
В первом случае вроде бы нужно записать полином Жегалкина от некой функции и приравнять его к такой функции, которая сохраняет 0...

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

[zhoraster]

Сообщение перемещено из раздела "Помогите решить / разобраться (М)" в карантин. Почему это произошло, можно понять, прочитав тему
Что такое карантин и что нужно делать, чтобы там оказаться
Там же описано, как исправлять ситуацию.

Четко сформулируйте свой вопрос, используя ТеХ.

[AKM]

Возвращаю.

[cyb12]

Пусть $f(x_1,\ldots,x_n)\in T_0\cap L,$ тогда ее можно представить полиномом, поскольку она линейна, и $f(0,\ldots,0)=0.$ Тогда $f=a_1x_1\oplus\ldots\oplus a_nx_n.$ Каждый $a_i$ можно выбрать двумя способами - 0 или 1, а представление вида $a_1x_1\oplus\ldots\oplus a_nx_n$ задает однозначно функцию из рассматриваемого класса. Вот и получаем, что всего таких представлений $2^n.$

Пусть $f(x_1,\ldots,x_n)\in T_0\cap S,$ $f$-- самодвойственная, а потому на любых двух противоположных наборах она принимает противоположные значения. То есть столбец значений такой функции однозначно определяется значением на $2^{n-1}$ наборах (то есть по одной половине другая однозначно восстанавливается). Но значение на наборе из нулей известно - 0, так как функция из $T_0.$ Поэтому столбец значений функции определяется ее значением на $2^{n-1}-1$ наборах, то есть $|T_0\cap S|=$ числу слов длины $2^{n-1}-1$ в алфавите из двух символов =...

Есть разобранные некоторые задачи в книжке Г.П.Гаврилова, А.А.Сапоженко ("Задачи и упражнения по дискретной математике"), но там много опечаток.
Общего алгоритма вроде нет, но нужно просто основываться на определениях и порешать задачки.

[Xaositect]

chencho в сообщении #346093 писал(а):

Если знаете какую-нибудь литературу, где разобраны подобные задачи то подскажите...

В Гаврилове-Сапоженко примеры вроде есть.

chencho в сообщении #346093 писал(а):

Насколько я понял относительно операций объединения и разности никаких хитростей в отличае от пересечения нет или я ошибаюсь?

Не уверен, что понял Вас, но в таких задачах часто удобно объединение и разность сводить к пересечению: $|A\cup B| = |A| + |B| - |A\cap B|$, $|A\setminus B| = |A| - |A\cap B|$

В общем, большинство этих задач из начального курса ДМ легко решаются либо с помощью утверждения о том, что число двоичных наборов длины $m$ равно $2^m$, либо исходя из деления на равные части.

Примеры, сначала на первый прием, потом на второй:
$|T_0 \cup T_1 |$: любая функция от $n$ переменных из $T_0\cup T_1$ может быть представлена вектором из $2^n-2$ бит: всего $2^n$ наборов, выкидываем $\tilde{0}$, где значение ф-и равно 0 и $\tilde{1}$, где оно равно 1. И обратно, любой вектор длины $2^n-2$ задает функцию. Значит функций в $T_0\cup T_1(n)$ столько же, сколько и векторов длины $2^n-2$, т.е. $2^{2^n-2}$.

$|L\cup S|$: рассмотрим произвольную линейную функцию $l(x_1,\dots,x_n)$ из $L(n)$. Если $l$ самодвойственная, то $l\oplus x_1$ - несамодвойственная, и наоборот. Это значит, что в $L(n)$ самодвойственных и несамодвойственных функций поровну, т.е. по $2^n$.

Кстати, первый пример тоже можно решить таким способом: все функции из $P_2(n)$ разбиваются на 4 класса : $T_0\cup T_1$, $T_0\setminus T_1$, $T_1\setminus T_0$, $\bar{T_0}\cup \bar{T_1}$. Легко видеть, что все они одинаковы по размеру (но это надо строго написать, задать взаимно-однозначные соответствия), значит каждый занимает ровно четверть из всех $2^{2^n}$ функций, т.е. $2^{2^n-2}$.

[chencho]

Спасибо. Разобрался!