Abstract:
Let $D^P_1(n)$ ($D^P_0(n)$, $D^P_{0,1}(n)$) be the least length of a complete diagnostic test for the primary inputs of logical circuits implementing Boolean functions in $n$ variables and having constant faults of type $1$ (respectively $0$, both $0$ and $1$) on these inputs, $D^O_{B;\,1}(n)$ ($D^O_{B;\,0}(n)$, $D^O_{B;\,0,1}(n)$) be the least length of a complete diagnostic test for logical circuits consisting of logical gates in a basis $B$, implementing Boolean functions in $n$ variables, and having constant faults of type $1$ (respectively $0$, both $0$ and $1$) on outputs of the logical gates, and $B_2=\{x|y\}$, $B^*_2=\{x\uparrow y\}$, $B_3=\{x\&y,\overline x\}$, $B^*_3=\{x\vee y,\overline x\}$.
It is shown that the functions $D^P_1(n)$, $D^P_0(n)$, $D^O_{B_2;\,1}(n)$, $D^O_{B^*_2;\,0}(n)$, $D^O_{B_3;\,0,1}(n)$, $D^O_{B^*_3;\,0,1}(n)$ are not less than $\dfrac{2^{{n}/2}\cdot\sqrt[4]n}{2\sqrt{n+(\log_2 n)/2+2}}$ and
$
D^P_{0,1}(n)$ is not less than $2^{{n}/2}$ if $n$ is even, and is not less than
$\left\lfloor\dfrac{2\sqrt 2}3\cdot 2^{{n}/2}\right\rfloor$ if $n$ is odd.
Keywords:logic circuit, fault, complete diagnostic test, test for inputs of circuits.