Diagnosis of Retaining Faults in Circuits

In this chapter, retaining faults of circuits are considered. We prove that, for iteration-free circuits, there exist decision trees, which solve the problem of circuit diagnosis relative retaining faults and whose depth is bounded from above by a linear function on the number of gates in circuits. For each closed class of Boolean functions, we find a basis, which is optimal from the point of view of complexity of diagnosis of formula-like circuits over this basis (during the procedure of diagnosis each formula-like circuit is transformed into an iteration-free circuit). We also study relationships between two types of Shannon functions. A function of the first type characterizes the complexity of diagnosis of formula-like circuits implementing Boolean functions from a closed class. A function of the second type characterizes the complexity of formulas implementing Boolean functions from a closed class. The obtained relationships allow us to transfer some known results for Shannon functions of the second type to the case of Shannon functions of the first type.