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

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

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

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