Abstract:
We prove that each Boolean function can be modeled by a logic circuit with one additional input in a basis consisting of conjunctions of an arbitrary number of variables, two-input disjunction and negation, allowing a complete diagnostic test with the length no more than $n+1$ relative to constant faults of type $1$ at outputs of logic gates.