Сколько всего попарно неконгруэнтных самодвойственных монотонных функций зависящих от четырех переменных?

задан 10 Мар 16:44

@Santiago: надо дать определение того, что понимается под "конгруэнтными" функциями.

(10 Мар 17:41) falcao

@falcao: Функции f и g называются конгруэнтными, если отличаются только именами переменных, то есть осуществляют одинаковое отображение. Например, х и у конгруэнтные функции, хy и yz тоже, а xz и yy таковыми не являются

(10 Мар 21:45) Santiago
10|600 символов нужно символов осталось
1

Пусть функция f равна 1 на наборе с одной единицей и остальными нулями. С точностью до перестановки переменных, f(1,0,0,0)=1. Тогда f(1,a,b,c)=1 для всех a,b,c ввиду монотонности. На противоположных наборах получится f(0,y,z,t)=0 для любых y,z,t. Это значит, что такая функция равна значению одной их переменных, то есть f(x)=x (тождественная функция).

Теперь пусть f равна нулю на наборе с одной единицей. Получается, что если единиц в наборе 0 или 1, то функция равна 0. Если единиц 3 или 4, значение функции равно 1. На наборах, в которых две единицы и два нуля (назовём их нейтральными), любой выбор значений приводит к монотонной функции. Всего нейтральных наборов 6, их можно представлять как рёбра тетраэдра. Чтобы функция была самодвойственной, надо из каждой пары противоположных рёбер выделить ровно одно ребро, для которого функция равна 1.

Одно ребро рисуем произвольно. Второе не противоположно первому, то есть имеет общую вершину. Третье либо образует треугольник с этими двумя, либо все рёбра исходят из одной вершины.

Получается ещё две функции. В одном случае одна из переменных фиктивна, а на трёх других имеем функцию голосования. Здесь три существенных переменных. Во втором случае одна переменная выделена. Если она равна 1 вместе с какой-то другой переменной, значение функции равно 1. Если она равна 0, то для значения функции 1 нужно, чтобы три остальные переменные были равны 1. Формула такова: f(x,y,z,t)=x(y V z V t) V yzt. Такая функция подходит, существенных переменных у неё 4. Она не конгруэнтна предыдущей.

Итого 3 функции с точностью до конгруэнтности (без такого ограничения было бы 12 функций).

ссылка

отвечен 11 Мар 14:37

@falcao: Спасибо!

(11 Мар 17:08) Santiago
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×72
×14

задан
10 Мар 16:44

показан
49 раз

обновлен
11 Мар 17:08

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

по почте:

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

по RSS:

Ответы

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

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