Article collection "Mathematical Problems of Cybernetics" №16, Moscow, 2007
Lower bounds for the number of (k,r)-nonseparated families of subsets of an n-element set (of (k,r)-nonseparated Boolean functions). The case k≥3 and r≥1
A family F of subsets of an n-element set S (a Boolean function f(x ,…,x )) is called (k,r)-nonseparated if the intersection of any members from F contains at least r elements of S) any k tuples, on which f(x ,…,x ) equals to 1, contains at least r ones). Lower bounds for the number of (k,r)-nonseparated Boolean functions of n variables for fixed k≥3, r≥1 and n→ ∞ are established.
Boolean functions and finite sets, nonseparated Boolean functions and nonseparated finite sets, lower bounds
Publication language:russian, pages:12 (p. 31-42)
Mathematical problems and theory of numerical methods