Рассматривается задача синтеза двухполюсных контактных схем, реализующих булевы функции от n переменных и допускающих короткие проверяющие и диагностические тесты относительно замыканий контактов. Установлено, что почти все булевы функции от n переменных реализуемы неизбыточными двухполюсными контактными схемами, допускающими единичные проверяющие, полные проверяющие и единичные диагностические тесты замыкания константной длины. Доказаны также следующие факты: 1) любую булеву функцию f(x₁,…,x_n) можно реализовать неизбыточной двухполюсной контактной схемой, содержащей не более одной входной переменной, отличной от переменных x₁,…,x_n, и допускающей единичный и полный проверяющий тесты замыкания длины не более 2n; 2) любую булеву функцию f(x₁,…,x_n) можно реализовать неизбыточной двухполюсной контактной схемой, содержащей не более двух входных переменных, отличных от переменных x₁,…,x_n, и допускающей единичный диагностический тест замыкания длины не более 4n.

контактная схема, замыкание контакта, единичный проверяющий тест, полный проверяющий тест, единичный диагностический тест

Математическое моделирование в актуальных проблемах науки и техники

Попков Кирилл Андреевич,  ,  orcid.org/0000-0003-3763-4050,  ИПМ им. М.В. Келдыша РАН