2016-08-11

vak: (Улыбка)
Сколько существует монотонных булевых функций с N аргументами?

Монотонной назовём булеву функцию, значение которой не убывает при росте значения аргументов. Интересуют нетривиальные функции, то есть реально зависящие от аргументов. Варианты, отличающиеся перестановкой аргументов, считаем за один.

Для двух аргументов имеем всего две монотонные функции:
    a | b
    ab

В случае трёх аргументов таких функций уже пять:
    a | b | c
    a | bc
    ab | ac
    ab | ac | bc
    abc

При N=4 получается двадцать функций:
    a | b | c | d
    a | b | cd
    a | bc | bd
    a | bc | bd | cd
    a | bcd
    ab | ac | ad
    ab | ac | ad | bc
    ab | ac | ad | bc | bd
    ab | ac | ad | bc | bd | cd
    ab | ac | ad | bcd
    ab | ac | bcd
    ab | acd
    ab | acd | bcd
    ab | bc | ad
    ab | cd
    abc | abd
    abc | abd | acd
    abc | abd | acd | bcd
    abcd
    ac | bc | ad | bd

Для пяти аргументов я насчитал 180 монотонных функций. Вычисление для шести аргументов всё еще идет и, надеюсь, закончится к утру. (Результат 16143 штук)

Монотонные функции играют важную роль в методике асинхронных цифровых схем. про это напишу позже.

Для наглядности булевы функции можно представлять как N-мерные кубики с углами, раскрашенными в два цвета. К примеру, так выглядит функция f(a, b, c, d) = ab | bc | ad.