RUS  ENG
Full version
JOURNALS // University proceedings. Volga region. Physical and mathematical sciences // Archive

University proceedings. Volga region. Physical and mathematical sciences, 2009 Issue 1, Pages 3–10 (Mi ivpnz666)

Mathematics

On asymptotically optimal schemes in the basis $\{x|y, x\downarrow y, x\&y, x\vee y, \bar{x}\}$

A. V. Vasin

Penza State University, Penza

Abstract: Circuits of unreliable functional elements are considered in basis $\{x | y, x \downarrow y, x \& y, x \vee y, \bar{x} \}$. It's possible to realize all boolean functions by asymptotically optimal reliable circuits. Unreliability of these circuits is asymptotically equal 3$\epsilon$ for almost all boolean functions with $\epsilon \rightarrow 0$ ($\epsilon$ is the probability of inverse failure at the output of the base element).

Keywords: reliable circuits, unreliable elements, inverse failure, synthesis of circuits, boolean functions.

UDC: 519.9



© Steklov Math. Inst. of RAS, 2025