|
Дискретная математика, 1989, том 1, выпуск 2, страницы 129–136
(Mi dm915)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 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$ переменных с соответствующими свойствами.
Статья поступила: 15.11.1988
Образец цитирования:
В. Б. Алексеев, “О числе семейств подмножеств, замкнутых относительно пересечения”, Дискрет. матем., 1:2 (1989), 129–136
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm915 https://www.mathnet.ru/rus/dm/v1/i2/p129
|
Статистика просмотров: |
Страница аннотации: | 687 | PDF полного текста: | 341 | Первая страница: | 3 |
|