RUS  ENG
Полная версия
ЖУРНАЛЫ // Препринты Института прикладной математики им. М. В. Келдыша РАН // Архив

Препринты ИПМ им. М. В. Келдыша, 2021, 049, 18 стр. (Mi ipmp2966)

Эта публикация цитируется в 1 статье

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

К. А. Попков


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

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

DOI: 10.20948/prepr-2021-49



© МИАН, 2024