Найти число самодвойственных симметрических булевых функций.

задан 8 Июн '15 16:03

изменен 8 Июн '15 19:44

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Симметрическая б.ф. от $%n$% переменных однозначно задаётся своими значениями на наборах вида $%a_k=(0,...,0,1,...,1)$%, где количество нулей равно $%0\le k\le n$%, а количество единиц равно $%n-k$%. Общее количество таких функций равно $%2^{n+1}$%, поскольку наборов рассматривается $%n+1$%.

Теперь посмотрим, какое количество таких функций самодвойственно. Это те функции, которые на противоположных наборах принимают противоположные значения. Ясно, что набору $%a_0$% противоположен набор $%a_n$%, набору $%a_1$% -- набор $%a_{n-1}$% с точностью до перестановки, и так далее. Поэтому значения функции мы можем свободно выбирать на первой половине наборов, а далее они однозначно определяются. Надо также иметь в виду, что если среди наборов есть "средний", где число нулей равно числу единиц, то он оказывается противоположен сам себе, и функцию задать вообще нельзя.

Из сказанного следует, что при чётном $%n$% функций будет $%0$%, а при нечётном $%n$% их будет $%2^{(n+1)/2}$%.

ссылка

отвечен 8 Июн '15 16:39

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

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

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

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

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

отмечен:

×130

задан
8 Июн '15 16:03

показан
352 раза

обновлен
8 Июн '15 16:39

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

по почте:

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

по RSS:

Ответы

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

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