![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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.
Монотонной назовём булеву функцию, значение которой не убывает при росте значения аргументов. Интересуют нетривиальные функции, то есть реально зависящие от аргументов. Варианты, отличающиеся перестановкой аргументов, считаем за один.
Для двух аргументов имеем всего две монотонные функции:
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.
no subject
Date: 2016-08-12 02:18 (UTC)http://oeis.org/A006602
Ищется по 1,2,5,20,180
no subject
Date: 2016-08-12 03:25 (UTC)Прямо энциклопедия натуральных чисел. :)
Пошёл гуглить ссылки, попал на статью "Identification of control targets in Boolean molecular network models via computational algebra". То есть народ такими методами реверс-инжинирит цепочки управления в живых клетках и организмах.
no subject
Date: 2016-08-12 05:20 (UTC)no subject
Date: 2016-08-12 05:31 (UTC)Я уже попадал на этот сайт неоднократно, а в этот раз почему-то не додумался.
see also
Date: 2016-08-12 02:36 (UTC)Re: see also
Date: 2016-08-12 02:38 (UTC)no subject
Date: 2016-08-12 03:47 (UTC)На самом деле Дедекинд даёт завышенные значения, так как не учитывает перестановку аргументов.
Правильная статья вот эта: https://en.wikipedia.org/wiki/Abstract_simplicial_complex
no subject
Date: 2016-08-12 07:41 (UTC)no subject
Date: 2016-08-12 08:09 (UTC)CMOS
Date: 2016-08-12 09:51 (UTC)