Рассматривается задача синтеза неизбыточных схем из функциональных элементов, реализующих булевы функции от n переменных и допускающих короткие единичные тесты относительно произвольных константных неисправностей на выходах элементов. Доказано, что любую неконстантную булеву функцию можно реализовать схемой в базисе 'конъюнкция, отрицание, сумма по модулю 2 трех переменных', допускающей единичный проверяющий тест длины не более 2, а также схемой в базисе, состоящем из одной конкретной булевой функции от шести переменных, допускающей единичный диагностический тест длины не более 3.

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

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

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