On complete diagnostic tests for contact diagrams during opening and/or closing of contacts

Background. We study the possibility of constructing of (two-pole) contact circuits which implement Boolean functions on $n$ variables and allow short complete diagnostic tests regarding contact breaks and/or closures. The topic under study relates to the problem of synthesis of easily testable circuits, set by S. V. Yablonskiy and I. A. Chegis in the 50s of the last century and well studied by now. Materials and methods. We prove lower estimates of test lengths by selecting of contact faults, under which the resulting fault functions of an arbitrary contact circuit implementing a given Boolean function differ from each other on no more than two vectors. At that, some classes of “the most difficult” Boolean functions for testing in terms of the lengths of minimal complete diagnostic tests are well described using the concepts of maximal independent set in the Boolean cube graph, as well as binary block code correcting one error. We use contact circuits modeling representations of Boolean functions by disjunctive or conjunctive normal forms to prove the upper bounds of the test lengths. Results. We prove that any Boolean function on $n$ variables can be implemented by a contact circuit allowing a complete diagnostic test with length not more than $2^{n-1}$ regarding contact breaks; the same fact is also true regarding contact closures. In three cases: under contact breaks and closures, only under their breaks or only under their closures, we find rather extensive classes of Boolean functions on $n$ variables, for each of which the length of the minimal complete diagnostic test at its implementation by contact circuits is the maximal possible among all Boolean functions on $n$ variables and equals $2^{n}$, $2^{n-1}$, $2^{n-1}$, respectively. We obtain overexponential lower bounds on the number of Boolean functions from each of these classes. Conclusions. The upper bounds on the lengths of the minimal complete diagnostic tests of contact break and contact closure for an arbitrary Boolean function at its implementation by contact circuits are improved. Some classes of “the most difficult” functions for testing are described.