Аннотация:
Показано, как для произвольной булевой функции $n$ переменных построить формулы сложности $O(2^{n/2})$ в базисах
$$
\{x-y,xy,|x|\} \cup [0,1],\qquad \{x-y,x*y,2x,|x|\} \cup [0,1],
$$
где ${x*y=\max(-1,\min(1,x))\max(-1,\min(1,y))}$. Данные оценки, вообще говоря, по порядку неулучшаемы.
Библиография: 3 названия.