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

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

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

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