Part 3. Mathematical models

The growing lower bound for the Shannon function of the detection test set cardinality with respect to single stuck-at faults at the outputs of gates in formulas over bases close to the standard one

Zh. Cui, D. S. Romanov

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Abstract: Lower bounds asymptotically equal to the number of variables are established for Shannon functions of the cardinality of single fault detection test set with respect to stuck-at faults at outputs of gates in Boolean formulas over bases $\{x\mathbin{\&}y,\,x\vee y,\,\bar x\}$, $\{x\mathbin{\&}y,\,\bar x\}$, $\{x\vee y,\,\bar x\}$, $\{x\mathbin{\&}{\bar y},\,\bar x\}$, $\{x\vee {\bar y},\,\bar x\}$.

Keywords: fault detection test set, stuck-at faults, Boolean formula