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

Булева функция — это функция, которая принимает в качестве входа n булевских переменных (то есть значений, которые могут быть либо false (ложь), либо true (истина), или, эквивалентно, бинарными значениями, которые могут быть либо 0, либо 1), и даёт в качестве выхода другую булевскую переменную. Функция монотонна, если для любой комбинации входа изменение одной входной переменной с false на true может привести только к изменению выхода с false на true, но не с true на false. Число Дедекинда M(n) — число различных монотонных булевых функций от n переменных.

Антицепь множеств (известная также как семейство Спенсера) — это семейство множеств, ни одно из которых не содержится в любом другом множестве. Если V является множеством n булевых переменных, антицепь A подмножеств V определяет монотонную булеву функцию f, когда значение f равно true для данного множества входов, если некоторое подмножество true входов функции f принадлежит A и false в другом случае. Обратно, любая монотонная булева функция определяет таким образом антицепь, минимальных подмножеств булевских переменных, которые вынуждают функцию дать значение true. Поэтому число Дедекинда M(n) равно числу различных антицепей подмножеств n-элементного множества[3].

Третий эквивалентный способ описания того же класса использует теорию решёток. Из двух монотонных булевых функций f и g мы можем найти две другие монотонные булевы функции ${\displaystyle f\wedge g}$ и ${\displaystyle f\vee g}$, их логическую конъюнкцию и логическую дизъюнкцию соответственно. Семейство всех монотонных булевых функций от n входов вместе с этими двумя операциями образует дистрибутивную решётку, задаваемую теоремой Биркгофа о представлении из частично упорядоченного множества подмножеств n переменных с частичным порядком включения множеств. Это построение даёт свободную дистрибутивную решётку с n генераторами[6]. Таким образом, числа Дедекинда подсчитывают число элементов в свободных дистрибутивных решётках[7][8] [9].

Числа Дедекинда подсчитывают также (на единицу больше) число абстрактных симплициальных комплексов на n элементах, семейства множеств со свойством, что любое подмножество множества в семействе также принадлежит семейству. Любая антицепь определяет симплициальный комплекс, семейство подмножеств членов антицепей, и обратно, максимальные симплексы в комплексах образуют антицепь[4].

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

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

Точные значения чисел Дедекинда известны для ${\displaystyle 0\leqslant n\leqslant 8}$:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 последовательность A000372 в OEIS.

Первые шесть этих чисел дал Чёрч[7]. M(6) вычислил Уорд[10], M(7) вычислили Чёрч[8] Берман и Кёлер[11], а M(8) вычислил Видерман[5].

Если n чётно, то M(n) также должно быть чётным[12]. Вычисление пятого числа Дедекинда ${\displaystyle M(5)=7581}$ опровергает гипотезу Гаррета Биркгофа, что M(n) всегда делится на ${\displaystyle (2n-1)(2n-2)}$[7].

Киселевич[4] переписал логическое определение антицепей в следующую арифметическую формулу для чисел Дедекинда:

${\displaystyle M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{j}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right),}$

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

${\displaystyle b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor .}$

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

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

${\displaystyle {n \choose \lfloor n/2\rfloor }\leqslant \log _{2}M(n)\leqslant {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).}$

Здесь неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности ${\displaystyle \lfloor n/2\rfloor }$ элементов, а правое неравенство доказали Кляйтман и Марковский[1].

Коршунов[2] дал даже более точные оценки[9]

${\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)}$

для чётных n, и

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

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

${\displaystyle a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),}$

${\displaystyle b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3}),}$

и

${\displaystyle c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).}$

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