RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1989, том 1, выпуск 2, страницы 129–136 (Mi dm915)

Эта публикация цитируется в 2 статьях

О числе семейств подмножеств, замкнутых относительно пересечения

В. Б. Алексеев


Аннотация: Пусть $\alpha(n)$ – число семейств подмножеств $n$-элементного множества, обладающих свойством: для любых двух подмножеств, входящих в семейство, их пересечение (также входит в семейство. В статье доказано, что $\log_2\alpha(n)\sim C_n^{[n/2]}$ при $n\to\infty$. Отсюда вытекает, что такой же результат справедлив и для некоторых других структур, в частности для числа всех возможных операций замыкания на $n$-элементном множестве. Эти результаты получены как следствие аналогичного результата при $n\to\infty$ и $k=o(\sqrt n/\log_2^2n)$ для числа семейств подмножеств $n$-элементного множества, удовлетворяющих условию: если $k$ одноэлементных расширений подмножества $A$ входят в семейство, то и $A$ входит в семейство. Поскольку имеется соответствие между семействами подмножеств и функциями алгебры логики, то эти результаты устанавливают также асимптотику логарифма для числа функций алгебры логики от $n$ переменных с соответствующими свойствами.

УДК: 510.716

Статья поступила: 15.11.1988



Реферативные базы данных:


© МИАН, 2024