Эта публикация цитируется в
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