Lower bounds for lengths of complete diagnostic tests for circuits and inputs of circuits | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/5

Let Dp (n) (D₀ (n), DP ₁(n)) be the least length of a complete diagnostic test for the primary inputs of logical circuits implementing Boolean functions in n variables and having constant faults of type 1 (respectively 0, both 0 and 1) on these inputs, °; 1 (n) (Dg(n), DO _;01n)) be the least lengpg logical circuits consisting of logical gates in a basis B, implementing Boolean functions in n variables, and having constant faults of type 1 (respectively 0, both 0 and 1) on outputs of the logical gates, and B₂ = {x|y}, B| = {x t y}, B₃ = {x&y,x}, 3 = У- I Dfn) D°n^ °_2;1 (n), DO (n), 2™/2 · д/n Do_;0 1(n), D°»_{;0 1}(n) are not less than - = and D^n) is not less ; , 3; , 2\Jn + (log₂ n)/2 + 2 2^2 . 2™/2 if n is odd. than 2 if n is even, and is not less than