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

задан 14 Янв '18 17:14

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

В отличие от других предполных классов, для количества монотонных функций от n переменных, хорошей общей формулы не имеется. Поэтому считать придётся вручную. Способов можно предложить несколько. Один из них такой: сразу учтём 2 константы. Остальные монотонные функции представляются в виде дизъюнкции элементарных конъюнкций. При этом более "слабые" члены не учитываются, что гарантирует единственность. Это означает, что если одна конъюнкция "содержит" другую -- в том смысле, как xz "содержит" и x, и z, то x V xz равно x. Поэтому наличие члена xz исключает наличие более "слабых" членов x и z.

Тогда, если есть xyz, то больше ничего нет. Предположим, что члена 3-й степени нет, а члены 2-й степени есть. Если их три, то получается функция голосования xy V xz V yz. Других членов нет. Если их два, то это функция xy V xz, или симметричная ей. Всего таких 3 штуки. Других членов снова нет. Если есть только один член -- скажем, xy, то он идёт или сам по себе, или вместе с z, то есть функция равна xy V z. С учётом симметрии, это ещё 6 случаев. Наконец, если члены имеют только первую степень, то функций будет 2^3-1=7 по числу непустых подмножеств в {x,y,z}.

Теперь аккуратно всё складываем: 2+1+1+3+6+7=20. Это ответ.

Вот ещё один способ. От двух переменных имеется ровно 6 монотонных функций: две константы, две переменные, конъюнкция и дизъюнкция. Это легко проверяется. В виде векторов их легко выписать (в лексикографическом порядке): 0000, 0001, 0011, 0101, 0111, 1111. Теперь заметим, что при фиксации значения одной переменной у монотонной функции, это свойство сохраняется. Если для функции f(x,y,z) мы фиксируем x=0, то получим один из этих 6 наборов. Если фиксируем x=1, то снова получается набор из списка, который покоординатно не меньше предыдущего. Поэтому остаётся для каждого набора списка подсчитать число покоординатно не меньших, и всё сложить. Это даёт 6+5+3+3+2+1=20. Ответ тот же.

ссылка

отвечен 14 Янв '18 17:52

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

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

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

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

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

отмечен:

×784
×149

задан
14 Янв '18 17:14

показан
1004 раза

обновлен
14 Янв '18 17:52

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

по почте:

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

по RSS:

Ответы

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

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