математическая-логика - Количество монотонных булевых функций

В отличие от других предполных классов, для количества монотонных функций от 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. Ответ тот же.