Сколько функций от переменных $$x_{1} , x_{2} ,..., x_{n}$$ содержит множество $$( L \cup T_{0} ) - S$$ Нужно определить мощность множества. Упрощаем. $$( L \cup T_{0} ) - S = ( L \cup T_{0} )\bar{S} = L \bar{S} \cup T_{0} \bar{S}$$ и пользуясь формулой включений-исключений получаем: $$ \mid L \bar{S} \cup T_{0} \bar{S} \mid = \mid L \bar{S} \mid + \mid T_{0} \bar{S} \mid - \mid LT_{0}\bar{S} \mid $$ А как дальше считать? Линейная и не самодвойственная; сохраняющая на нулевом наборе ноль и не самодвойственная; линейная и сохраняющая на нулевом значении ноль и не самодвойственная, сколько таких функций от n переменных ? L -класс линейные функции; S -класс самодвойственные функции; Т_0 - класс функция сохраняющие на нулевом наборе ноль. известно, что : $$ \mid T_{0} (n) \mid = 2^{ 2^{n} - 1 } $$ $$ \mid S (n) \mid = 2^{ 2^{n-1} } $$ $$ \mid L (n) \mid = 2^{ n +1 } $$

задан 23 Май '16 15:55

изменен 23 Май '16 19:32

Что эти множества обозначают?

(23 Май '16 15:59) pavel1076

Замкнутые классы булевых функций

(23 Май '16 16:23) Andre452
10|600 символов нужно символов осталось
0

В принципе, как-то так и надо делать. Подсчёты здесь несложные. Надо только исправить формулу для числа самодвойственных функций: там должно быть $%2^{2^{n-1}}$%.

Общий вид линейной функции нам известен: $%f(x_1,...,x_n)=a+a_1x_1+\cdots+a_nx_n$%. При замене каждой из переменных на её отрицание, должно получаться отрицание функции. Это равносильно тому, что $%a_1+\cdots+a_n=1$%. Такое возможно при $%n\ge1$%, и ровно в половине случаев значение этой суммы равно 1, а в половине оно равно 0. Значит, $%L\bar{S}$% даёт $%2^n$% функций при $%n\ge1$%. Сразу же отметим, что половина только что учтённых функций принадлежит $%T_0$%, а половина нет. Поэтому учёт $%LT_0\bar{S}$% даёт нам $%2^n-2^{n-1}=2^{n-1}$%.

Осталось найти число функций из $%T_0$%, не являющихся самодвойственными. Общее число мы знаем, и вычесть нужно число самодвойственных из $%T_0$%. При $%n\ge1$% все такие функции задаются произвольным образом на верхней половине таблицы, кроме набора из нулей. Это значит, что они определяются $%2^{n-1}-1$% свободными переменными, то есть их будет $%2^{2^{n-1}-1}$%. Это то, что надо вычесть из количества функций в $%T_0$%.

Итоговый ответ: $%2^{2^n-1}-2^{2^{n-1}-1}+2^{n-1}$% (при $%n\ge1$%). При $%n=0$% получится одна функция (константа 0).

ссылка

отвечен 23 Май '16 17:38

Ошибку исправил. Спасибо за ответ!

(23 Май '16 19:34) Andre452
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,250
×212
×146
×80

задан
23 Май '16 15:55

показан
1692 раза

обновлен
23 Май '16 19:34

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

по почте:

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

по RSS:

Ответы

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

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