Сколько существует монотонных булевых функций, зависящих от 4 переменных x1, x2, x3, x4?

задан 19 Июн 11:02

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

Вопрос о нахождении числа монотонных булевых функциях в общем виде достаточно сложный (проблема Дедекинда). Для небольших значений n это число можно найти при помощи аккуратного ручного перебора. Надо при этом сделать так, чтобы он был более "прозрачным" и менее трудоёмким.

Обозначим через f(n) число интересующих нас функций от n переменных. Ясно, что f(0)=2 (обе константы), f(1)=3 (те же плюс тождественная функция).

Найдём f(2). Две константы уже имеются. Пусть g(x,y) -- монотонная функция, отличная от константы. Тогда g(0,0)=0, g(1,1)=1, а на остальных наборах значение g можно задать произвольно. Получается ещё 4 функции, итого f(2)=6. Их можно частично упорядочить, полагая g1<=g2, если g1(x,y)<=g2(x,y) для любых x,y. Здесь все шесть функций известны нам "персонально", и их можно перечислить:

0 <= xy <= x, y <= xVy <= 1.

Теперь пусть n=3. Монотонная функция g(x,y,z) определяется двумя монотонными функциями g1(x,y)=g(x,y,0) и g2(x,y)=g(x,y,1), причём g1<=g2. Для каждой из 6 функций списка легко указать, сколько функций находятся "выше" неё в смысле отношения <=, включая саму эту функцию. Получатся следующие числа: 6, 5, 3, 3, 2, 1. Это значит, что если g1(x,y)=0, то g2 можно выбрать 6 способами; при g1(x,y)=xy выбор g2 делается 5 способами, и так далее. Поэтому, перебирая все варианты выбора g1, мы имеем в итоге f(3)=6+5+3+3+2+1=20.

Для нашего случая n=4 можно было бы нарисовать упорядоченное множество из 20 функций и далее для него поступить аналогичным способом, но это будет довольно долго. Поступим иначе. Для монотонной функции g от 4 переменных рассмотрим функции g1(x,y)=g(x,y,0,0), g2(x,y)=g(x,y,0,1), g3(x,y)=g(x,y,1,0) и g4(x,y)=g(x,y,1,1). Легко понять, что g1<=g2,g3<=g4, то есть g2,g3 находятся между g1 и g4 в смысле <=. Выбрать функции g1<=g4 из имеющего у нас списка можно 20 способами, и для каждого их них нужно рассмотреть число "промежуточных" между ними функций (включая сами эти функции). Если таких функций имеется k, то как g2, так и g3 выбирается k способами, и для выбора пары их получается k^2. Например, при g1=0, g2=1 получается k=6. Этих случаев не так много, с учётом возникающей симметрии, то есть в итоге нам надо будет просуммировать несколько квадратов.

Переобозначим наши функции в виде a<=b<=c,d<=B,A, и укажем значение k для всех случаев пар g1<=g4 в символической форме.

aA (это значит, что g1=a, g4=A): k=6

aB или bA: k=5

ac ad, cA, DA: k=3

ab, BA: k=2

aa, AA: k=1

Это были случаи, когда одна из "крайних" функций a или A входила в состав g1, g4. Теперь перебираем оставшиеся случаи для системы b<=c,d<=B:

bB: k=4

bc,bd,cB,dB: k=2

bb, cc, dd, BB: k=1

Это все случаи: пару из c,d брать нельзя, так как эти функции не сравнимы.

Осталось просуммировать квадраты (x далее выступает как знак умножения), получая f(4)=6^2+2x5^2+4x3^2+2x2^2+2x1^2+4^2+4x2^2+4x1^2=36+50+36+8+2+16+16+4=168.

ссылка

отвечен 19 Июн 18:50

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

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

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

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

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

отмечен:

×1,469
×886
×160
×56

задан
19 Июн 11:02

показан
83 раза

обновлен
19 Июн 18:50

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

по почте:

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

по RSS:

Ответы

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

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