Дедекиндово число

Шаблон:Не путать <imagemap> Файл:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right|Свободные дистрибутивные решётки монотонных булевых функций от 0, 1, 2 и 3 аргументов с 2, 3, 6 и 20 элементами соответственно (наведите мышь на правую диаграмму, чтобы видеть описание) circle 659 623 30 circle 658 552 35 circle 587 480 35 circle 659 481 35 circle 729 481 35 circle 588 410 35 circle 658 410 35 circle 729 410 35 circle 548 339 30 circle 604 339 30 circle 758 339 30 circle 661 339 35 circle 588 268 35 circle 659 267 35 circle 729 268 35 circle 588 197 35 circle 658 197 35 circle 729 197 35 circle 658 126 35 circle 659 56 30 desc bottom-left </imagemap> Дедекиндово число — число $M(n)$, равное количеству монотонных булевых функций от $n$ переменных. Эквивалентные определения: число антицепей подмножеств $n$-элементного множества; число элементов в Шаблон:Не переведено 5 с $n$ производящими; число Шаблон:Не переведено 5 с $n$ элементами.

Последовательность $(M(n))$ — быстрорастущая, и хотя известны асимптотические оценки $M(n)$Шаблон:SfnШаблон:SfnШаблон:Sfn и точное выражение в виде суммыШаблон:Sfn, но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию Шаблон:На точные значения известны для $n⩽9$:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366.

Шаблон:ЯкорьЧисла от $M(0)$ до $M(4)$ вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число $M(5)$ вычислил Чёрч в 1940 годуШаблон:Sfn, результат опроверг гипотезу Биркгофа, что $M(n)$ всегда делится на $(2n-1)(2n-2)$Шаблон:Sfn. Числа $M(6)$, $M(7)$, $M(8)$, $M(9)$ были вычислены соответственно в 1946Шаблон:Sfn, 1965Шаблон:SfnШаблон:Sfn, 1991Шаблон:Sfn и 2023 годах.

Для нахождения $M(8)$ использовался суперкомпьютер Шаблон:Iw. Число $M(9)$ было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС Шаблон:Iw 10 GX под управлением суперкомпьютера Noctua 2, занявших около трёх месяцев. Обе группы получили одинаковый результат вычислений числа $M(9)$, Якель опубликовал препринт на три дня раньше бельгийских коллег.

Если $n$ чётно, то $M(n)$ также должно быть чётнымШаблон:Sfn.

Точная формула для вычисления дедекиндовых чисел на основе логического определения антицепей была выведена в 1988 годуШаблон:Sfn:

$M(n)=\sum _{k=1}^{2^{2^n}}\prod _{j=1}^{2^n-1}\prod _{i=0}^{j-1}(1-b_i^k{b}_j^k\prod _{m=0}^{{\log }_{2}i}(1-b_m^i+b_m^i{b}_m^j))$,

где $b_i^k$ является $i$-м битом числа $k$, который может быть записан с помощью округления вниз:

$b_i^k=\lfloor \frac{k}{2^i}\rfloor -2\lfloor \frac{k}{2^{i+1}}\rfloor$,

однако она бесполезна для практического вычисления значений $M(n)$ для больших $n$ ввиду большого числа членов суммирования.

В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа:

$M(n+2)=\sum _{\alpha ,\beta \in M_n}(|[\mathrm{\perp },\alpha ]|2^{C_{\alpha },\beta }|[\beta ,\mathrm{\top }]|)$

Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности.

Логарифм дедекиндова числа можно оценить с помощью границ:

$(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })⩽{\log }_{2}M(n)⩽(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })(1+O\left(\frac{\log n}{n}\right))$,

где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности $\lfloor n/2\rfloor$ элементов; правая часть неравенства установлена в 1975 годуШаблон:Sfn.

В 1981 годуШаблон:Sfn были даны более точные оценкиШаблон:Sfn:

$M(n)=(1+o(1))2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}\exp a(n)$

для чётных $n$ и:

$M(n)=(1+o(1))2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor +1})}\exp (b(n)+c(n))$

для нечётных $n$, где

$a(n)=(\genfrac{}{}{0ex}{}{n}{n/2-1})(2^{-n/2}+n^2{2}^{-n-5}-n{2}^{-n-4})$,

$b(n)=(\genfrac{}{}{0ex}{}{n}{(n-3)/2})(2^{-(n+3)/2}+n^2{2}^{-n-6}-n{2}^{-n-3})$,

$c(n)=(\genfrac{}{}{0ex}{}{n}{(n-1)/2})(2^{-(n+1)/2}+n^2{2}^{-n-4})$.

Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к $n/2$Шаблон:Sfn. Для $n=2,4,6,8$ формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и −3,3 % соответственноШаблон:R.

Пример

Для $n=2$ существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества $\{x,y\}$:

• функция $f(x,y)=\mathrm{\perp }$, игнорирующая входные значения и всегда возвращающая $\mathrm{\perp }$, соответствует пустой антицепи $\varnothing$;
• логическая конъюнкция $f(x,y)=x\wedge y$ соответствует антицепи $\{\{x,y\}\}$, содержащей единственное множество $\{x,y\}$;
• функция $f(x,y)=x$, игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи $\{\{x\}\}$, содержащей единственное множество $\{x\}$;
• функция $f(x,y)=y$, игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи $\{\{y\}\}$, содержащей единственное множество $\{y\}$;
• логическая дизъюнкция $f(x,y)=x\vee y$ соответствует антицепи $\{\{x\},\{y\}\}$, содержащей два множества $\{x\}$ и $\{y\}$;
• функция $f(x,y)=\mathrm{\top }$, игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи $\{\varnothing \}$, содержащей только пустое множество.

Литература

• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья. Как процитировано Видерманом (Шаблон:Harvtxt).
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Книга