Здравствуйте! $%f(x_1, x_2, x_3, x_4) \in M \cap S$%, $%f(1, 0, 0, 1) = 0$%. Найти $%f$%. И ещё у меня вопрос - есть понятие сравнимого и несравнимого набора. Как мы определяем, что наборы сравнимы? Ну, в принципе, если друг под другом записать по принципу половинок, то видно, какие сравнимые, а какие - нет.

задан 14 Окт '15 19:46

изменен 14 Окт '15 22:26

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

Для двух наборов $%a=(a_1,...,a_n)$% и $%b=(b_1,...,b_n)$% одинаковой длины полагаем $%a\preceq b$%, если или $%a_i\le b_i$% для всех $%1\le i\le n$%, или $%b_i\le a_i$% для всех $%1\le i\le n$%. Говорят, что наборы $%a$% и $%b$% сравнимы, если $%a\preceq b$% или $%b\preceq a$%. В противном случае наборы называются несравнимыми.

Для несравнимых наборов всегда можно указать две координаты, которые равны 0 и 1 для одного набора, и 1 и 0 соответственно для другого.

Функций, удовлетворяющих условию задачи, имеется шесть. Сначала укажем четыре из них. Это переменные $%x_2$% и $%x_3$%, а также "функции голосования" по трём переменным, включая $%x_2$% и $%x_3$%, то есть $%{\rm maj}(x_1,x_2,x_3)=x_1x_2+x_1x_3+x_2x_3$%, и $%{\rm maj}(x_2,x_3,x_4)=x_2x_3+x_2x_4+x_3x_4$%. Очевидно, что все они монотонны, самодвойственны, а также удовлетворяют условию $%f(1,0,0,1)=0$%. Докажем, что других функций нет, кроме ещё двух, которые будут указаны в конце.

Рассмотрим значение $%f$% на наборе $%(0,0,1,0)$%. Предположим, что оно равно $%1$%. Тогда в силу монотонности, наличие $%1$% в третьей позиции достаточно, чтобы функция была равна $%1$%. Поскольку функция самодвойственна, то на противоположных наборах она принимает значение $%0$%, а это наборы с нулевой третьей координатой. Из описания понятно, что это функция $%x_3$%.

Аналогично, если $%f(0,1,0,0)=1$%, то это функция $%x_2$%.

Осталось рассмотреть случай $%f(0,0,1,0)=f(0,1,0,0)=0$%. Из самодвойственности вытекает, что $%f(1,1,0,1)=f(1,0,1,1)=1$%. Перечисленные условия однозначно задают значения $%f$% на 12 наборах из 16. То, что осталось, можно выписать (в упрощённом виде): 0011, 0101, 1010, 1100. Поскольку здесь у нас имеются две пары противоположных наборов, то возникает не более четырёх случаев.

Сразу можно заметить, что двум функциям голосования соответствуют случаи, когда значения на указанных наборах (в порядке их следования) либо 0, 0, 1, 1, либо 1, 1, 0, 0. Осталось исследовать два варианта, когда значения равны 0, 1, 0, 1 или же 1, 0, 1, 0. Нетрудно заметить, что эти функции получаются друг из друга заменой порядка следования переменных на обратный, и достаточно исследовать первый из вариантов, а ко второму прийти из соображений симметрии.

Итак, пусть $%f(0,0,1,1)=f(1,0,1,0)=0$% и $%f(0,1,0,1)=f(1,1,0,0)=1$%. Можно заполнить таблицу для такого случая; там получится вектор-столбец 0000011100011111. При этом становится ясно, что функция самодвойственна (первые восемь символов противоположны вторым восьми, прочитанным в обратном порядке). Зададим функцию формулой, чтобы убедиться в её монотонности (хотя это можно сделать и так, используя описанный ранее тест разбиений на "половинки".

Что здесь нам гарантирует $%1$% в качестве значения функции? Нетрудно убедиться, что это $%x_1x_2$% (последние 4 единицы), или $%x_2x_3$%, или $%x_2x_4$%, плюс ещё один вариант $%x_1x_3x_4$%. Нетрудно проверить непосредственно, что $%f$% здесь задаётся формулой $%x_1x_2\lor x_2x_3\lor x_2x_4\lor x_1x_3x_4$%. Из такого представления хорошо видно, что функция монотонна, а самодвойственность мы уже проверили. При желании, можно выписать для этой функции полином Жегалкина, но он имеет довольно сложный вид (7 одночленов), и мало о чём говорит.

Осталось выписать последний вариант, симметричный предыдущему относительно замены $%x_1$% на $%x_4$%, а $%x_2$% на $%x_3$%. Это будет $%x_1x_3\lor x_2x_3\lor x_3x_4\lor x_1x_2x_4$%.

ссылка

отвечен 15 Окт '15 0:03

На самом деле, пока ждала ответ, я как-то решила и тоже получила 6 наборов, значит, у меня таки правильно.

(15 Окт '15 19:32) Math_2012

@Math_2012: эта задача сравнительно трудная. Конечно, она решается по таблице прямым перебором, но две функции здесь как бы несколько "неожиданные".

(15 Окт '15 20:20) falcao

@falcao: Вот я и перебрала...

(15 Окт '15 20:45) Math_2012
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,293
×150

задан
14 Окт '15 19:46

показан
1276 раз

обновлен
15 Окт '15 21:44

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

по почте:

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

по RSS:

Ответы

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

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