RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2022 Number 56, Pages 104–112 (Mi pdm771)

This article is cited in 2 papers

Mathematical Backgrounds of Computer and Control System Reliability

Short complete diagnostic tests for circuits with one additional input in the standard basis

K. A. Popkov

Keldysh Institute of Applied Mathematics, Moscow, Russia

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.

Keywords: logic circuit, stuck-at fault, complete diagnostic test, Boolean function.

UDC: 519.718.7

DOI: 10.17223/20710410/56/6



© Steklov Math. Inst. of RAS, 2025