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

Доказано, что каждую из булевых функций \(x_1\oplus\ldots\oplus x_n\), \(x_1\oplus\ldots\oplus x_n\oplus 1\) можно реализовать схемой из функциональных элементов в каждом из базисов \(\{x\oplus y,1\}\), \(\{x\&\overline y,x\vee y,\overline x\}\), \(\{x\&y,x\vee y,\overline x\}\), допускающей полный диагностический тест длины не более \(\lceil\log_2(n+1)\rceil\) (для первых двух базисов) либо не более \(n\) (для третьего базиса) относительно однотипных константных неисправностей на выходах элементов. Установлено также, что каждую из функций \(x_1\oplus\ldots\oplus x_n\), \(x_1\oplus\ldots\oplus x_n\oplus 1\) можно реализовать схемой из функциональных элементов в базисе \(\{x\oplus y,1\}\), допускающей полный диагностический тест длины не более \(\lceil\log_2(n+1)\rceil+1\) относительно произвольных константных неисправностей на выходах элементов.

https://doi.org/10.4213/mzm13639