О полных диагностических тестах для контактных схем при обрывах и/или замыканиях контактов

Актуальность и цели. Изучаются возможности построения (двухполюсных) контактных схем, реализующих булевы функции от $n$ переменных и допускающих короткие полные диагностические тесты относительно обрывов и/или замыканий контактов. Исследуемая тема относится к проблеме синтеза легкотестируемых схем, поставленной С. В. Яблонским и И. А. Чегис в 50-х годах прошлого века и к настоящему времени достаточно хорошо изученной. Материалы и методы. Нижние оценки длин тестов доказываются путем подбора неисправностей контактов, при которых получающиеся функции неисправности произвольной контактной схемы, реализующей заданную булеву функцию, отличаются друг от друга не более чем на двух наборах. При этом некоторые классы «самых трудных» для тестирования булевых функций с точки зрения длин минимальных полных диагностических тестов хорошо описываются с помощью понятий максимального независимого множества в графе булева куба, а также двоичного блокового кода, исправляющего одну ошибку. Для доказательства верхних оценок длин тестов используются контактные схемы, моделирующие представления булевых функций дизъюнктивными либо конъюнктивными нормальными формами. Результаты. Доказано, что любую булеву функцию от $n$ переменных можно реализовать контактной схемой, допускающей полный диагностический тест длины не более $2^{n-1}$ относительно обрывов контактов; верен также аналогичный факт относительно замыканий контактов. В трех случаях: при обрывах и замыканиях контактов, только при их обрывах или только при их замыканиях, найдены достаточно обширные классы булевых функций от $n$ переменных, для каждой из которых длина минимального полного диагностического теста при реализации ее контактными схемами является максимально возможной среди всех булевых функций от $n$ переменных и равна $2^{n}$, $2^{n-1}$, $2^{n-1}$ соответственно. Получены сверхэкспоненциальные нижние оценки числа булевых функций в каждом из этих классов. Выводы. Улучшены верхние оценки длин минимальных полных диагностических тестов размыкания и замыкания для произвольной булевой функции при реализации ее контактными схемами. Описаны некоторые классы «самых трудных» для тестирования функций.