EN|RU

Том 4, серия 1, номер 3, 1997 г., Стр. 9-17

УДК 519.6
О. М. Касим-Заде
О минимальных покрытиях булева куба центрированными антицепями

Аннотация:
Изучаются покрытия булева $n$-куба $B^n=\{0,1\}^n$ центрированными антицепями, т. е. множествами, состоящими из попарно несравнимых наборов, имеющих общую единичную компоненту; к числу центрированных антицепей относится также одноэлементное множество $\{\widetilde0^n\}$. Установлено, что для всякого $n\geqslant 1$ минимальное число центрированных антицепей, объединение которых покрывает $n$-куб, равно $n[\log_2{n}]+2(n-2^{[\log_2{n}]})+2$. Дано явное описание минимальных покрытий.
Библиогр. б.

Касим-Заде О. М. 1
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия
е-mail: omkas@nw.math.msu.su

Статья поступила 28 апреля 1997 г.

 © Институт математики им. С. Л. Соболева, 2015