Функции без коротких имплицент. Часть II: методы построения

Статья является продолжением работы "Функции без коротких имплицент. Часть I: нижние оценки весов". Во второй части предложены различные методы построения булевых функций от $n$ переменных, не имеющих имплицент от $k$ переменных. Первый из предложенных методов базируется на градиентном алгоритме, второй и третий методы используют определенное комбинаторное правило построения, четвертый метод основан на случайном выборе элементов носителя функции. В зависимости от значения $k$ методы имеют различную эффективность. Выводятся верхние оценки минимального значения $w\left( {n,\;k} \right)$ весов построенных функций. Вместе с нижними оценками величины $w\left( {n,\;k} \right)$ из первой части статьи это позволяет получить асимптотически точную оценку вида $w\left( {n,\;k} \right) = \Theta \left( {\ln n} \right)$ при $n \to \infty$ .