О тестах замыкания для контактных схем

Рассматривается задача синтеза двухполюсных контактных схем, реализующих булевы функции от $n$ переменных и допускающих короткие проверяющие и диагностические тесты относительно замыканий контактов. Установлено, что почти все булевы функции от $n$ переменных реализуемы неизбыточными двухполюсными контактными схемами, допускающими единичные проверяющие, полные проверяющие и единичные диагностические тесты константной длины. Доказано также, что: 1) любую булеву функцию $f(x_1,\ldots,x_n)$ можно реализовать неизбыточной двухполюсной контактной схемой, содержащей не более одной входной переменной, отличной от переменных $x_1,\ldots,x_n$, и допускающей единичный и полный проверяющий тесты длины не более $2n$; 2) любую булеву функцию $f(x_1,\ldots,x_n)$ можно реализовать неизбыточной двухполюсной контактной схемой, содержащей не более двух входных переменных, отличных от переменных $x_1,\ldots,x_n$, и допускающей единичный диагностический тест длины не более $4n$. Работа выполнена при поддержке РФФИ, проект № 14-01-00598 (“Вопросы синтеза, сложности и контроля управляющих систем”) и программы фундаментальных исследований ОМН РАН “Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения”(проект “Задачи оптимального синтеза управляющих систем”).