Теоретическая кибернетика

Установлено, что почти любую булеву функцию от 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) относительно неисправностей такого же типа.

http://keldysh.ru/papers/2018/prep2018_197.pdf