Пожалуйста, помогите, с данной темой возникли проблемы.

Imgur

задан 21 Июн '14 11:24

изменен 23 Июн '14 21:56

Deleted's gravatar image


126

@mds, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(23 Июн '14 21:56) Deleted
10|600 символов нужно символов осталось
2

$$|T_0\cap T_1\cup L\cap S|$$

Похожий вопрос был здесь; даю на него ссылку.

Класс $%T_0\cap T_1$% довольно большой: в него попадает $%2^{2^n-2}$% булевых функций от $%n$% переменных (при $%n\ge1$%). Это связано с тем, что $%f(0,...,0)=0$% и $%f(1,...,1)=1$%, а на остальных $%2^n-2$% двоичных векторах значение функции задаётся произвольно одним из двух способов.

Посмотрим, какое количество функций надо добавить. Прежде всего, класс $%L\cap S$% допускает простое описание. Оно имеется по ссылке. Это функции вида $%f(x_1,...,x_n)=a_0+a_1x_1+\cdots+a_nx_n$% с условием $%a_1+\cdots+a_n=1$%, и таких функций ровно $%2^n$%. Это все линейные самодвойственные функции. Но нам среди них нужны только те, которые не были учтены. Поэтому надо понять, сколько таких функций было уже учтено, то есть сколько их попадает в класс $%T_0\cap T_1$%.

Если $%f\in T_0$%, то $%a_0=0$%. При этом для нашего случая оказывается, что $%f(1,...,1)=a_1+\cdots+a_n=1$%, и $%f\in T_1$% автоматически. Значит, нами уже было учтено $%2^{n-1}$% функций из $%2^n$% (ровно половина), а вторую половину, то есть функции вида $%f(x_1,...,x_n)=1+a_1x_1+\cdots+a_nx_n$% с условием $%a_1+\cdots+a_n=1$%, надо добавить. Итого будет $%2^{2^n-2}+2^{n-1}$% функций при $%n\ge1$%.

Можно заметить, что при $%n=0$% рассматриваемый класс пуст (ни одна из двух констант ему не принадлежит).

ссылка

отвечен 21 Июн '14 17:30

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

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

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

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

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

отмечен:

×938

задан
21 Июн '14 11:24

показан
563 раза

обновлен
23 Июн '14 21:56

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

по почте:

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

по RSS:

Ответы

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

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