Том 3, номер 2, 1996 г., Стр. 62-79

УДК 519.6
Н. П. Редькин
Асимптотически минимальные самокорректирующиеся схемы для одной последовательности булевых функций

Аннотация:
Рассматриваются схемы из надежных и ненадежных функциональных элементов. Схема $S$, реализующая в исправном состоянии булеву функцию $f$, называется $k$-самокорректирующейся, если любая схема, в которую преобразуется схема $S$ в результате перехода в неисправное состояние не более $k$ ненадежных элементов, реализует $f$. Каждый надежный элемент имеет вес $p>0$ и всегда реализует предписанную ему функцию. Ненадежные элементы имеют вес 1 и в неисправном состоянии реализует булеву константу $\delta$ ($\delta=0$, или $\delta=1$). Под сложностью схемы понимается сумма весов всех ее элементов, а через $L_k(f)$ понимается наименьшая из сложностей $k$-самокорректирующихся схем, реализующих функцию $f$. В работе устанавливаются асимптотические формулы для величины $L_k(f)$, когда $f$ является булевой функцией от $n$ переменных, принимающей значение 1 только на тех наборах, в которых содержится не менее чем две единицы, а схемы строятся над базисами $\{\&,\vee,^-\}$ и $\{\&,\vee\}$.
Табл. 1, библиогр 6.

Редькин Н. П. ¹
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия

Статья поступила 2 апреля 1996 г.