Circuits for disjunction admitting short unitary diagnostic tests

S. R. Bedzhanova


Abstract: 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\ge3$ 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.

UDC: 519.7

Received: 15.04.2010

DOI: 10.4213/dm1118

 English version: Discrete Mathematics and Applications, 2010, 20:5-6, 643–654

Bibliographic databases:

• 
• 
•