Сапоженко А.А. Проблема Дедекинда и метод граничных функционалов

М.: Физматлит, 2009. — 152 с.В книге излагается асимптотическое решение известной проблемы Дедекинда о числе монотонных булевых функций, а также метод граничных функционалов, предназначенный для решения задач подобного типа. Проблема имеет более чем вековую историю, начавшуюся с работы Р. Дедекинда 1897 г., в которой было найдено число элементов дистрибутивной свободной структуры с четырьмя образующими, или, что то же самое, число монотонных булевых функций, зависящих от четырех переменных. С начала 1950-х годов проблема привлекла большой интерес специалистов в области алгебры логики и кибернетики и способствовала развитию методов решения перечислительных задач.Введение
Основные понятия
Метод граничных функционалов
Асимптотики для S(B)
Оценки сумм S(B) для ординарных функциональных пар
Связные множества и покрытия
Примеры ординарных функциональных пар
Оценки числа связных подмножеств с заданной мощностью границы в двудольных графах
Оценки числа антицепей в двухслойных ЧУМ
Оценки числа антицепей в трехслойных ранжированных множествах
Оценки числа антицепей в многослойных ранжированных множествах
Асимптотика числа монотонных булевых функций
Коды с расстоянием 2
Двудольные графы
Независимые множества в графах
Расшифровка монотонных функций
Поиск верхнего нуля
Антицепи в ранжированных множествах
Список литературы