Теоретическая кибернетика

Доказано, что при \(n\geqslant 2\) любую булеву функцию от n переменных можно реализовать двухполюсной контактной схемой, неизбыточной и допускающей диагностический тест, длина которого не превосходит \(n+k(n-2)\), относительно размыканий не более \(k\) контактов. Установлено, что при \(k=k(n)\leqslant 2^{n-4}\) для почти всех булевых функций от \(n\) переменных наименьшая возможная длина указанного теста не превосходит \(2k+2\).