Abstract:
We prove that each monotone (antimonotone) Boolean function in n variables can be modeled by a logic circuit with one additional input in the basis “conjunction, disjunction, negation” allowing a complete diagnostic test with length no more than n+2 (no more than n+1, respectively) relative to constant faults of type 1 at outputs of logic gates.
Citation:
K. A. Popkov, “Short complete diagnostic tests for circuits with one additional input in the standard basis”, Prikl. Diskr. Mat., 2022, no. 56, 104–112