Оценки длин проверяющих и диагностических тестов для функциональных элементов

Рассматриваются задачи проверки исправности и диагностики состояний $N$ функциональных элементов, в исправном состоянии реализующих заданную булеву функцию $f(x_1,\ldots,x_n)$, путём составления из них схем с одним выходом и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности на выходах функциональных элементов; при этом предполагается, что не более $k$ элементов неисправны, где $k$ – заданное натуральное число, не превосходящее $N$. Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех элементов. Показано, что для любых $f,N$ и $k$ необходимо не менее $k$ схем. Для функций $f$ специального вида получены необходимые и достаточные условия того, что для проверки исправности и определения состояний всех элементов достаточно $k$ схем. Ил. 3, библиогр. 2.