Функции без коротких имплицент. Часть I: нижние оценки весов

В статье рассматриваются булевы функции от $n$ переменных, не имеющие имплицент от $k$, $1\le k<n$, переменных. Получены оценки минимально возможного веса $w(n,\;k)$ таких функций. Показано, что $w(n,\;1) = 2$, $n = 2,3,\dots$, и $w(n,\;2)\sim \log _2n$ при $n \to \infty$, а для $k > 2$ существует такое ${n_0}$, что $w(n,\;k) > {2^{k - 2}} \cdot \log _2n$ при всех $n > {n_0}$.