УДК 519.95

О сложности самокорректирующихся схем для одной последовательности булевых функций / В. М. Краснов. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. ? 5. С. 55-57.

Рассматриваются k-самокорректирующиеся схемы из функциональных элементов в базисе \{x_1\& x_2,\bar x\}. Предполагается, что константные неисправности на выходах элементов однотипные. Инверторы предполагаются надежными. Вес каждого инвертора равен 1. Конъюнкторы могут быть надежными и ненадежными. Каждый надежный конъюнктор реализует конъюнкцию двух переменных и имеет вес p>k+2. Каждый ненадежный конъюнктор в исправном состоянии реализует конъюнкцию, а в неисправном — булеву константу \delta (\delta\in\{0,1\}). Вес каждого ненадежного конъюнктора равен 1. Установлено, что сложность реализации такими схемами монотонных пороговых симметрических функций f_2^n(x_1,\dots,x_n)=\bigvee\limits_{\scriptscriptstyle 1\leq i < j \leq n}x_ix_j, n=3,4,\ldots, асимптотически равна (k+3)n.

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

Библиогр. 4.