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

Рассматривается задача реализации булевых функций двухполюсными контактными схемами, неизбыточными и допускающими короткие проверяющие или диагностические тесты относительно замыканий не более \(k\) контактов при заданном натуральном \(k\). Доказаны следующие утверждения: для почти любой булевой функции от \(n\) переменных минимальная длина проверяющего (диагностического) теста равна 2 (соответственно, не превосходит \(2k+2\)).