Русская Википедия:Дедекиндово число

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Не путать <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 A и B и C circle 587 480 35 A и B circle 659 481 35 A и C circle 729 481 35 B и C circle 588 410 35 (A и B) или (A и C) circle 658 410 35 (A и B) или (B и C) circle 729 410 35 (A и C) или (B и C) circle 548 339 30 A circle 604 339 30 B circle 758 339 30 C circle 661 339 35 (A или B) и (A или C) и (B или C) <====> (A и B) или (A и C) или (B и C) circle 588 268 35 (A или B) и (A или C) circle 659 267 35 (A или B) и (B или C) circle 729 268 35 (A или C) и (B или C) circle 588 197 35 A или B circle 658 197 35 A или C circle 729 197 35 B или C circle 658 126 35 A или B или C circle 659 56 30 тавтология desc bottom-left </imagemap> Дедекиндово число — число <math>M(n)</math>, равное количеству монотонных булевых функций от <math>n</math> переменных. Эквивалентные определения: число антицепей подмножеств <math>n</math>-элементного множества; число элементов в Шаблон:Не переведено 5 с <math>n</math> производящими; число Шаблон:Не переведено 5 с <math>n</math> элементами.

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

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

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

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

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

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

<math>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)</math>,

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

<math>b_i^k=\left\lfloor\frac{k}{2^i}\right\rfloor - 2\left\lfloor\frac{k}{2^{i+1}}\right\rfloor</math>,

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

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

<math>M(n+2)=\sum_{\alpha,\beta\in M_n} \left(|[\bot,\alpha]|2^{C_\alpha,\beta}|[\beta,\top]|\right)</math>

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

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

<math>{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)</math>,

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

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

<math>M(n)=(1+o(1)) 2^{n\choose \lfloor n/2\rfloor}\exp a(n)</math>

для чётных <math>n</math> и:

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

для нечётных <math>n</math>, где

<math>a(n)={n\choose n/2-1}(2^{-n/2} + n^2 2^{-n-5} - n2^{-n-4})</math>,

<math>b(n)={n\choose (n-3)/2}(2^{-(n+3)/2} + n^2 2^{-n-6} - n2^{-n-3})</math>,

<math>c(n)={n\choose (n-1)/2}(2^{-(n+1)/2} + n^2 2^{-n-4})</math>.

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

Пример

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

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

Литература

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