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

Установлено, что любую булеву функцию от n переменных можно реализовать контактной схемой, допускающей полный диагностический тест длины не более \(2^{n-1}\) относительно обрывов контактов; верен также аналогичный факт относительно замыканий контактов. В трех случаях: при обрывах и замыканиях контактов, только при их обрывах или только при их замыканиях, найдены достаточно обширные классы булевых функций от \(n\) переменных, для каждой из которых длина минимального полного диагностического теста при реализации ее контактными схемами является максимально возможной среди всех булевых функций от n переменных и равна \(2^n, 2^{n-1}, 2^{n-1}\) соответственно. Получены сверхэкспоненциальные нижние оценки числа булевых функций из каждого из этих классов.