Сколько существенных переменных может быть у самодвойственной функции?

задан 25 Сен '17 18:09

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

Любое число, кроме 0 и 2.

При n=0 есть только константы, и они двойственны друг другу.

При n=1 подходит тождественная функция x, а также отрицание not(x).

При n=2 имеется ровно 4 самодвойственных функции, так как значения задаются произвольно на верхней половине таблицы, а на нижнюю однозначно продолжаются. Но 4 самодвойственные функции -- это x1, not(x1), x2, not(x2). Других нет, а у этих только одна переменная существенная.

При n=3 укажем такие функции как f(x,y,z)=x+y+z, а также функция голосования h(x,y,z)=xy+xz+yz. Из них построим пример для n=4. Самодвойственные функции образуют замкнутый класс, и их можно подставлять друг в друга. Рассмотрим функцию f(h(x,y,z),z,t)=xy+xz+yz+z+t. Она самодвойственна, и все переменные существенны, так как они явно входят в полином Жегалкина.

Далее идёт индукция: при нечётном n берём пример для n=3, и парами добавляем новые переменные в виде слагаемых. При чётном n>=4 берём пример для n=4 и новые переменные прибавляем парами.

ссылка

отвечен 25 Сен '17 22:56

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

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

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

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

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

отмечен:

×86

задан
25 Сен '17 18:09

показан
969 раз

обновлен
25 Сен '17 22:56

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

по почте:

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

по RSS:

Ответы

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

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