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

Максимальное число $l(f)$ конъюнкций в тупиковой дизъюнктивной нормальной форме (д.н.ф.) булевой функции $f$ и число $\tau(f)$ тупиковых д.н.ф. являются важными параметрами, характеризующими сложность алгоритмов нахождения минимальных д.н.ф. Показано, что у почти всех булевых функций $l(f)\sim2^{n-1}$, $\log_2\tau(f)\sim2^{n-1}\log_2n\log_2\log_2n$ ($n\to\infty$). Библ. 5 назв.