Sufficient conditions for realizability of Boolean functions by asymptotically optimal circuits with the unreliability 2ɛ
M. A. Alyokhina, А. В. Васин · Russian Mathematics · 2010
We consider realizations of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis B. We assume that all elements independently of each other with the probability ɛ (ɛ ∈ (0; 1/2)) are subjected to inverse failures at the output. We construct Boolean functions φ(x 1, x 2, x 3) such that the presence of at least one of them in the considered basis B guarantees the realizability of all three Boolean functions by circuits whose reliability does not exceed 2ɛ + 144ɛ 2 with ɛ ≤ 1/960. In addition, if B ⊂ B 3 | G (B 3 is the set of all Boolean functions of three variables x 1, x 2, x 3, and G is the set of Boolean functions such that each one of them is congruent either to x 1 1 x 2 2 ∨ x 1 1 x 3 3 ∨ x 2 2 x 3 3 , or to x 1 1 x 2 2 ⊕ x 3 3 , or to x 1 1 $$ x_2^{\bar \sigma _2 } $$ ∨ x 2/σ 2 x 3 3 (σ 1, σ 2, σ 3 ∈ “0, 1”)), then the presence of at least one of functions φ(x 1, x 2, x 3) guarantees the realizability of almost all Boolean functions by asymptotically optimal (with respect to the reliability) circuits, whose unreliability equals 2ɛ as ɛ → 0.