Синтез асимптотически оптимальных по надежности неветвящихся программ в базисе $\{x_1\vee x_2, x_1 \& x_2, \bar{x}_1, stop\}$

Рассматривается задача синтеза асимптотически оптимальных по надежности неветвящихся программ с условной остановкой, реализующих булевы функции, при инверсных неисправностях на выходах операторов в базисе $\{x_1\vee x_2, x_1 \& x_2, \bar{x}_1, stop\}$. Доказано, что в рассматриваемом базисе все булевы функции $f(x_1,x_2,...,x_n)$ можно реализовать асимптотически оптимальными по надежности программами с условной остановкой, причем для функций $x_i$ ($i \in \{1, 2, ..., n\}$) эти программы являются абсолютно надежными (не содержат операторов), а для остальных функций эти программы функционируют с ненадежностью, асимптотически равной $\epsilon$ при $\epsilon \to 0$ ($\epsilon$ - вероятность инверсной неисправности на выходе оператора).