Сколько существует монотонных булевых функций с 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.

Монотонной назовём булеву функцию, значение которой не убывает при росте значения аргументов. Интересуют нетривиальные функции, то есть реально зависящие от аргументов. Варианты, отличающиеся перестановкой аргументов, считаем за один.
Для двух аргументов имеем всего две монотонные функции:
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.
