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

Доказаны следующие утверждения: для любого натурального k существует базис, состоящий из булевых функций от не более чем 2k+2 переменных (от не более чем 4k+2 переменных), в котором любую булеву функцию, кроме константы 1, можно реализовать схемой из функциональных элементов, неизбыточной и допускающей проверяющий тест длины не более 3 (соответственно, диагностический тест длины не более 4) относительно не более k произвольных константных неисправностей на входах и выходах элементов. Показано, что при рассмотрении только произвольных константных неисправностей на входах элементов указанные оценки длин тестов можно понизить до 2.

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