On the exact value of the length of the minimal single diagnostic test for a particular class of circuits

Resumo

Under consideration is the problem of synthesis of irredundant logic circuits in the basis {&, ∨, ¬} which implement Boolean functions of n variables and allow some short single diagnostic tests regarding uniform constant faults at outputs of gates. For each Boolean function permitting implementation by an irredundant circuit, the minimal possible length value of such a test is found. In particular, we prove that this value is at most 2.