Установлено, что почти любую булеву функцию от n переменных можно реализовать схемой из функциональных элементов в базисе {x&y,x∨y,x⊕y,1}, допускающей полный проверяющий тест длины не более 4 относительно произвольных константных неисправностей на выходах элементов. Доказаны также следующие утверждения: любую булеву функцию от n переменных можно реализовать схемой из функциональных элементов в базисе {x&y,x∨y,x⊕y,1} (в базисе {x&y,x∨y,x∨y¯,x⊕y}), содержащей не более одной фиктивной входной переменной и допускающей полный проверяющий тест длины не более 5 (соответственно, не более 4) относительно неисправностей такого же типа.

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

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

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