Том 5, серия 1, номер 3, 1998 г., Стр. 44-63

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

Аннотация:
Рассматриваются схемы из надежных и ненадежных функциональных элементов, в которых выход каждого элемента можно соединять только с одним входом какого-нибудь одного элемента схемы. Каждый надежный элемент имеет вес $P\geqslant 3$ и всегда реализует приписанную ему функцию из базиса $\textrm Б$. Каждый ненадежный элемент имеет вес 1 и в исправном состоянии реализует приписанную ему функцию из базиса $\textrm Б$, а в неисправном состоянии – булеву константу $\delta$. Схема считается 1-самокорректирующейся, если при переходе в неисправное состояние любого одного ненадежного элемента она реализует ту же самую функцию, что и при исправном состоянии всех ее элементов. Под сложностью схемы понимается сумма весов всех ее элементов, а через $L_1(f)$ обозначается наименьшая из сложностей самокорректирующихся схем, реализующих булеву $f$. Пусть $p_1=x_1y_1$, а $p_n=x_ny_n\vee(x_n\vee y_n)p_{n-1}$, где $n=2,3,\dots$. Для последовательности булевых функций $p_n$ и базиса $\textrm Б=\{\&,\vee\}$ (а также и для $\textrm Б=\{\&,\vee,\overline{\phantom a}\}$) при любом фиксированном $\delta$ и $n>1$ установлено, что $L_1(p_n)=8n-6+P$.
Библиогр. 5.

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

Статья поступила 5 февраля 1998 г.