Дано вот такое множество : ( L - T0 ) U T1

Вот мои попытки решения : Для начала разберемся с операциями, операция '-' - означает, что нужно найти такие элементы, которые есть только в L и только в T0... Запишем линейное представление функции : a0 + a1x1 + a2x2 + ... + anxn Теперь разберемся с T0 в этой функции, для этого просто подставим заместо x - нули, и приравняем наше L к 0. Т.е имеем : a0 + a1 * 0 + a2 * 0 + ... + an * 0 = 0 => a0 = 0, а все остальное комбинируем как хотим -> получаем что мощность вот таких функций = 2 ^ n( ну т.е линейных, где фиксировано a0 )... Но вот вопрос, что делать дальше ?

задан 30 Май '14 16:25

Что у Вас обозначает знак "минус"? Я бы скорее подумал на теоретико-множественную разность. Подсчёт тут в любом случае можно произвести, но нужно точно знать, какая именно операция осуществляется над классами.

(30 Май '14 16:32) falcao

Ведь по сути, a0 + a1 * 0 + a2 * 0 + ... + an * 0 = 0 - пересечение множеств L и T0, т.е при a0 = 1, мы получаем вычитание ( не симметричное которое ) из L - пересечения L и T0, а еще надо тогда найти вычитание из T0 пересечения L и T0 ...Я в общем то запутался :D

(30 Май '14 16:34) DaHood

Falcao - я как раз вас и ждал, знак минус - симметрическая разность :)

(30 Май '14 16:35) DaHood

Если симметрическая разность, то всё понятно. Решение я сейчас напишу. Только её не надо обозначать знаком "минус", так как он как раз обычно несимметричен. Чаще всего используют символ $%\Delta$% для обозначения симметрической разности. Встречается также $%\oplus$%, или знак минус, но с "точечкой" сверху.

(30 Май '14 17:09) falcao

окей, буду разбирать, надеюсь на ваше решение :]

(30 Май '14 17:18) DaHood
10|600 символов нужно символов осталось
0

Итак, требуется подсчитать количество булевых функций от $%n$% переменных, принадлежащих множеству $%(L\mathop{\Delta}T_0)\cup T_1$%. Сразу же отделим функции из $%T_1$%: их имеется половина от общего количества, то есть $%2^{2^n-1}$%. Подсчитаем, сколько ещё в наш класс входит функций, которые не принадлежат $%T_1$%.

В соответствии с определением симметрической разности, у нас возникает два случая: $%L\cap\overline{T_0}$% и $%\overline{L}\cap T_0$%. Нас интересуют классы $%L\cap\overline{T_0}\cap\overline{T_1}$% и $%\overline{L}\cap T_0\cap\overline{T_1}$%; они не пересекаются.

Функции из первого множества охарактеризовать просто: они линейны, то есть имеют вид $%a_0+a_1x_1+\cdots+a_nx_n$%. Принадлежность $%T_0$% равносильна $%a_0=0$%, поэтому у нас $%a_0=1$%. Принадлежность $%T_1$% означала бы, что $%1+a_1+\cdots+a_n=1$%, а у нас это не так, то есть $%a_1+\cdots+a_n=1$%. При $%n\ge1$% таких наборов в точности $%2^{n-1}$%; это то, что добавляется к предыдущему количеству.

Теперь осталось подсчитать количество функций из второго множества. Для этого надо сначала взять класс $%T_0\cap\overline{T_1}$%, в котором ровно $%2^{2^n-2}$% функций (на наборе из нулей значение 0, на наборе из единиц -- тоже 0, на остальных $%2^n-2$% наборах значение выбирается одним из двух способов). Теперь надо вычесть количество линейных функций, попавших в этот класс, то есть функций из $%L\cap T_0\cap\overline{T_1}$%. Здесь также всё легко подсчитывается: представляя функцию в виде $%b_0+b_1x_1+\cdots+b_nx_n$%, мы замечаем, что $%b_0=0$%, и $%b_1+\cdots+b_n=0$%, и таких наборов $%2^{n-1}$%. Это количество надо вычесть, и оно сократится с тем, что мы выше прибавляли.

В итоге получится $%2^{2^n-1}+2^{2^n-2}=3\cdot2^{2^n-2}$% при $%n\ge1$%. Случай $%n=0$% можно охарактеризовать отдельно: там из двух констант только $%1$% попадёт в рассматриваемый класс.

ссылка

отвечен 30 Май '14 17:29

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

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

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

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

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

отмечен:

×1,699

задан
30 Май '14 16:25

показан
4296 раз

обновлен
30 Май '14 17:29

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

по почте:

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

по RSS:

Ответы

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

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