Abstract:
The problem of synthesizing asymptotically optimal schemes implementing Boolean functions with inverse faults at the outputs of elements in the basis $\{x\&y, x\vee y, \overline{x}\}$ is considered. It is proved that almost all Boolean functions can be implemented with asymptotically optimal reliability schemes that function with an unreliability asymptotically equal to $3\epsilon$ at $\epsilon\to 0$, where $\epsilon$ is the probability of an inverse malfunction at the output of the base element. The complexity of the proposed schemes exceeds the complexity of the minimum schemes built only from reliable elements by no more than 3 times.