On asymptotically minimal self-correcting schemes for a sequence of Boolean functions (Q1382560)

The author investigates schemes of functional elements over the basis \(\{x\& y, x\vee y,\bar x\}\) constructed of reliable and nonreliable elements. Let every nonreliable element have the weight \(p\) \((p > 0)\), \(\delta\) \((\delta\in\{0,1\})\) be a Boolean constant. The realization complexity of the Boolean function \(f^n_2(x_1,\dots,x_n) = \bigvee\limits_{1\leq i< j\leq n} x_ix_j\) is denoted by \(L_1(f^n_2)\). The author proves that \(L_1(f^n_2)\sim 3n\) for \(p\geq 2\), \(\delta = 0\); \(L_1(f^n_2)\geq L_1(f^{n-1}_2)+3\) for \(n\geq 3\), and for the Shannon function \(L_1'(f^n_2)\) it holds that \(L_1'(f^n_2)\sim n\cdot\min(3,2p)\), \(p > 0\).