A method of synthesis of irredundant circuits admitting single fault detection tests of constant length

A constructive proof is given that in each of the bases $B'=\{ x\mathbin{\&} y, x\oplus y, x\sim y\}$, $B_1=\{ x\mathbin{\&} y, x\oplus y, 1\}$ any $n$-place Boolean function may be implemented: a) by an irredundant combinational circuit with $n$ inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates) a single fault detection test of length at most 16, b) by an irredundant combinational circuit with $n$ inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most $2n-2\log_2 n+O(1)$; besides, there exists an $n$-place function that cannot be implemented by an irredundant circuit admitting a detecting test whose length is smaller than $2n-2\log_2 n-\Omega(1)$, c) by an irredundant combinational circuit with $n$ inputs and three outputs admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most 17.