Circuits for disjunction admitting short unitary diagnostic tests

摘要

We study tests for circuits realising disjunction. In a circuit, the inversion fault is allowed at the output of precisely one functional element. For any functionally complete basis B it is found that for any n 3 the disjunction of n variables can be realised by a circuit over B which admits a unitary diagnostic test consisting of at most two tuples. It is proved that this result cannot be improved in the general case.