Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов - Попков, К.А. (Препринты ИПМ им. М.В.Келдыша, 2018)
Установлено, что почти любую булеву функцию от 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) относительно неисправностей такого же типа.
Keywords: схема из функциональных элементов; произвольная константная неисправность; полный проверяющий тест