Статья в сборнике "Математические вопросы кибернетики" №16, Москва, 2007
Авторы:Коршунов А.Д.
Нижние оценки числа (k, r)-неразделенных семейств
подмножеств n-элементного множества ((k, r)-неразделенных булевых функций). Случай k≥3 и r≥1
Аннотация:
Семейство F подмножеств n-элементного множества S (булева функция от n переменных) называется (k,r)-неразделенным, если в пересечении любых k членов из F содержится не менее r элементов из S (любые k наборов, на которых функция равна 1, имеют r общих единиц). Найдены нижние оценки числа (k,r)-неразделенных булевых функций от n переменных при любых фиксированных k≥3, r≥1 и n→ ∞.
Ключевые слова:
Булевы функции и конечные множества, неразделенные булевы функции и неразделенные конечные множества, нижние оценки
