Single fault detection tests for logic networks of AND, NOT gates | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 38. DOI: 10.17223/20710410/38/5

Let Di(/) (Do(/)) be the least length of a fault detection test for irredundant logic networks consisting of logic gates in the basis {&, -}, implementing a given Boolean function /(x₁,...,x_n), and having at most one stuck-at-1 (stuck-at-0 respectively) fault on outputs of the logic gates. Let /₁ = xp, /₂ = 0, Xi, or ж//&x_i2 ... ; /₃ = = Xi1 &Xi2&x_ig& ... &x_ik or (... ((x/¹ &x_i2)^/2&x_ig)^/3& ... &x_ik)^/k; /₄ = x/¹ & ... Ax//; k-i /5 = (... ((x/_i¹ &x/2 )^¹ &x/3 )^² & ... &x/k )^^k-1, where 2 @ k @ n for /2, /3, and /5; k-i 1 @ k @ n for /4; ai,...,ak,5i,...,5k-i G {0,1}; i,ii,...,ik G {1,...,n}; indices i]_,... ,i_k are pairwise different; for /₃, at least one of numbers a₂,... ,a_k equals 0 and if k = 2, then assume x_i3& ... &x_ik = 1; for /₅, at least one of numbers 6_i,..., 5_k-i equals 0. It is proved that, for each Boolean function f {x\,... ,x_n) ф 1, 0, iff the function f is representable in the form of f₁, Di(/) = 1, iff the function f is representable in the form of /₂, 2, iff the function f is representable in the form of f₃, 3 otherwise. If f ф 1 then the value D₁(f) is undefined. Also, it is proved that, for each Boolean function f (x₁,..., x_n) which is different from constants, 0, iff the function f is representable in the form of f1 , Do(f) = 1, iff the function f is representable in the form of f₄ but not of f₁, 2, iff the function f is representable in the form of f₅, 3 otherwise. If f ф 1 or f ф 0 then the value D₀(f) is undefined.