Asymptotics of the Shannon function for switching circuits in the ``Sheffer stroke'' basis with partial unreliability (Q1310741)

Using a switching circuit which realizes the function \(\overline {xy}\) in the basis \(f_{sh}\) (``Sheffer stroke'') -- with some upper bound of error probability --, the switching circuits realizing the functions \(\overline{x}\), \(xy\) and \(x\vee y\) are described and their complexities and upper bounds of error probability are deduced. Then, the circuit realizing any function of \(n\) variables in the basis \(f_{sh}\) is described and it is shown that for \(n\to\infty\) the upper bound of its error probability \(\varepsilon(n) \to 0\) and that the Shannon function of this circuit has an \(L(n, \varepsilon (n))\sim 2^ n/n\) order.