УДК 511

Инверсионная сложность самокорректирующихся схем для одной последовательности булевых функций / Т. И. Краснова. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2012. № 3. С. 58-61.

Для последовательности булевых функций ƒn2(x1,...,xn)=∨(1≤i<jn)xixj при любых фиксированных k, p ≥ 1 и растущем n установлена асимптотика Lk-n2)∼n min{k+1, p}, где Lk-n2) - инверсионная сложность реализации функции ƒn2 k-самокорректирующимися схемами из функциональных элементов в базисе B={&,-}, p - вес надежного инвертора.

Ключевые слова: схемы из функциональных элементов, монотонные симметрические булевы функции, инверсионная сложность, самокорректирующаяся схема.

Библиогр. 6.

К оглавлению номера  Go!