|
Сколько функций от переменных $$x_1,x_2, ... , x_n$$ содержит множество $$(L-T_0) ∪ S$$ Фактически, нужно определить мощность множества (L-T_0) ∪ S. Пользуясь формулой включений-исключений получаем: $$|(L-T_0) ∪ S|=|L-T_0|+|S|-|(L-T_0)S|$$ Известно, что: $$|S(n)|=2^{2^{n-1}}$$ $$|T_0(n)|=2^{2^{n}-1}$$ $$|L(n)|=2^{n+1}$$ задан 18 Май '14 3:29 
ssh |
|
Количество самодвойственных функций известно, поэтому надо подсчитать количество остальных, то есть линейных, которые не принадлежат ни $%T_0$%, ни $%S$%. Рассмотрим общий вид линейной функции: $%f(x_1,\ldots,x_n)=a_0+a_1x_1+\cdots+a_nx_n$%. Ясно, что $%f\in T_0 \Leftrightarrow a_0=0$%, то есть нас интересует случай $%a_0=1$%. Далее, подставим вместо переменных их отрицания: $%f(x_1+1,\ldots,x_n+1)=a_0+a_1(x_1+1)+\cdots+a_n(x_n+1)=f(x_1,\ldots,x_n)+a_1+\cdots+a_n$%. Самодвойственность функции равносильна условию $%a_1+\cdots+a_n=1$%. Значит, нас интересует условие $%a_1+\cdots+a_n=0$%. При $%n\ge1$% таких наборов ровно $%2^{n-1}$%, так как все коэффициенты кроме последнего выбираются произвольно, а последний -- однозначно, из условия $%a_n=a_1+\cdots+a_{n-1}$%. Таким образом, при $%n\ge1$% ответом будет число $%2^{2^{n-1}}+2^{n-1}$%. Можно ещё рассмотреть отдельно случай $%n=0$%, когда имеются всего две константы. Они обе линейны, но не самодвойственны. Нам из них подходит одна функция $%1$%. отвечен 18 Май '14 4:13 
falcao |