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

Рассматривается задача реализации булевых функций самокорректирующимися схемами из ненадёжных функциональных элементов в различных полных базисах. Заранее задаётся множество допустимых неисправностей каждого элемента, на которое не накладывается никаких ограничений за исключением того, что оно должно быть непустым. Доказаны следующие утверждения:

1) для любого целого \(m\geqslant 3\) существует базис, состоящий из одной булевой функции от \(m\) переменных, в котором любую булеву функцию можно реализовать схемой из ненадёжных функциональных элементов, самокорректирующейся относительно некоторых неисправностей произвольного числа элементов;

2) для любого натурального \(k\) любую булеву функцию можно реализовать схемой из ненадёжных функциональных элементов в любом из базисов \(\{x\,|\,y\}\), \(\{x\&y, \overline x\}\), самокорректирующейся относительно некоторых неисправностей не более \(k\) элементов;

3) почти никакую булеву функцию нельзя реализовать схемой из ненадёжных функциональных элементов в базисе \(\{x\&\overline y,1\}\) и схожих базисах, самокорректирующейся относительно хотя бы каких-нибудь неисправностей не более чем одного элемента.