Проверяющие и диагностические тесты для конъюнкторов, дизъюнкторов и инверторов

Рассматриваются задачи проверки исправности и диагностики состояний $N$ функциональных элементов, которые реализуют в исправном состоянии заданную булеву функцию $f\in\{x_1\&\ldots\&x_n, x_1\vee\ldots\vee x_n, \overline{x_1}\}$ и среди которых не более чем $k$ неисправных, путем составления из них схем с одним выходом и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности на выходах элементов. Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех элементов. В работе получены нижние оценки вида $ck(\log_2 N-\log_2 k)$ для числа указанных схем.