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

К. А. Попков


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

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

DOI: 10.20948/prepr-2018-197

Реферативные базы данных:

•