Кратчайшие и минимальные дизъюнктивные нормальные формы полных функций

Почти всем булевым функциям от $n$ переменных, число нулей $k$ которых не превышает $\log_2n-\log_2\log_2n+1$, может быть сопоставлена некоторая булева функция от $2^{k-1}-1$ переменой с $k$ нулями (полная функция) так, что сложность реализации исходной функции в классе дизъюнктивных нормальных форм определяется исключительно сложностью реализации полной функции. В работе установлена асимптотически точная граница для минимального возможного числа литералов, содержащихся в дизъюнктивных нормальных формах полной функции. Библ. 14. Фиг. 1.