Abstract:
We consider realization of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis $B \subseteq B_3$ ($B_3$ is the set of all Boolean functions of three variables $x_1, x_2, x_3$). We assume that all elements are subjected independently of each other to inverse failures at the output with the probability $\epsilon$ ($\epsilon \in (0,1/2)$). In this article we found bases, in which almost all boolean functions is possible to realize by asymptotically optimal on reliability circuits with unreliability equal $5\epsilon$ with $\epsilon \rightarrow 0$. We proved that there are not other bases where it's possible to realize almost all boolean functions by asymptotically optimal on reliability circuits with unreliability $5\epsilon$.
Keywords:unreliable functional elements, circuits asymptotically optimal with respect to reliability, inverse failures on outputs of elements, synthesis of circuits composed of unreliable elements.