Аннотация:
Пусть $S$ есть перестановка множества всех $(0,1)$-векторов длины $n$,
а $P^{-1}$ – ей обратная. Показано,что минимально-возможная глубина схемы
из функциональных элементов в базисе $\{\&,\vee,^-\}$, реализующей систему булевых
функций, определяемую перестановкой $P$, может отличаться от минимально-
возможной глубины схемы, реализующей систему булевых функций, определяемую
перестановкой $P^{-1}$, не менее чем на $2\log_2n-3$, а для почти всех
рассматриваемых перестановок эта разница не превышает 4.
Библиогр. 11