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

задан 8 Май '15 23:01

изменен 9 Май '15 9:31

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


9917

Как это понять? Нулевая функция -- это тождественный ноль, она всего одна.

Может, имелось в виду "булевых"?

(8 Май '15 23:15) falcao

@falcao конечно, булевых, все автоисправление портит

(8 Май '15 23:48) sleepless_study

@sleepless_study, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

(9 Май '15 9:32) Виталина
10|600 символов нужно символов осталось
1

Симметрическая булева функция полностью определяется своими значениями на наборах, у которых сначала идут нули, а потом единицы. Таких наборов ровно 16. Чтобы функция была монотонна, необходимо и достаточно, чтобы при увеличении числа единиц значение функции не убывало. Это значит, что если упорядочить рассматриваемые наборы следующим образом: $%(0,\ldots,0)$%, $%(0,\ldots,0,1)$%, $%(0,\ldots,1,1)$%, $%(0,1,\ldots,1)$%, $%(1,\ldots,1)$%, то для получения монотонной функции надо назначить значение 0 для первых $%k\ge0$% наборов списка, и 1 для $%16-k$% остальных. Это можно сделать 17 способами, и столько же будет искомых функций.

Для функций от $%n$% переменных ответом будет $%n+2$%. Скажем, для $%n=2$% условию удовлетворяют 4 функции: константы 0, 1, конъюнкция и дизъюнкция.

ссылка

отвечен 8 Май '15 23:59

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

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

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

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

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

отмечен:

×1,866
×176

задан
8 Май '15 23:01

показан
1588 раз

обновлен
9 Май '15 9:32

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

по почте:

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

по RSS:

Ответы

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

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