Сколько функций от переменных $$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

изменен 18 Май '14 23:02

10|600 символов нужно символов осталось
1

Количество самодвойственных функций известно, поэтому надо подсчитать количество остальных, то есть линейных, которые не принадлежат ни $%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

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,699
×273

задан
18 Май '14 3:29

показан
2373 раза

обновлен
18 Май '14 23:02

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

по почте:

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

по RSS:

Ответы

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

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