А) Найти число булевых функций степени 5 от n => 5 переменных Б) Сколько из них являются симметрическими?

задан 2 Июн '19 15:41

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

О "степени" булевой функции можно говорить лишь условно, имея в виду степень её полинома Жегалкина.

Количество одночленов Жегалкина от $%n$% переменных, имеющих степень $%0\le k\le n$%, равно $%C_n^k$%. Поэтому количество многочленов степени не выше $%k$% равно $%2^{C_n^0+C_n^1+\cdots+C_n^k}$%. Обозначим эту величину через $%s_{nk}$%. Тогда для степени ровно $%5$% мы получим значение $%s_{n5}-s_{n4}$%.

Симметрический многочлен данной степени $%k$% имеется ровно один -- это сумма произведений всех одночленов степени $%k$%. В ней ровно $%C_n^k$% слагаемых. Соответственно, симметрических многочленов степени не выше $%k$% получается $%2^{k+1}$%, а степени ровно $%k$% их будет $%2^{k+1}-2^k=2^k$%. В данной задаче их будет $%32$% при любом $%n\ge5$%.

ссылка

отвечен 2 Июн '19 18:39

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

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

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

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

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

отмечен:

×158
×87

задан
2 Июн '19 15:41

показан
273 раза

обновлен
2 Июн '19 18:39

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

по почте:

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

по RSS:

Ответы

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

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