RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Поволжский регион. Физико-математические науки // Архив

Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2010, выпуск 4, страницы 26–38 (Mi ivpnz652)

Математика

О надежности неветвящихся программ в базисе, содержащем функцию вида $x_1^{\alpha_1} \vee x_2^{\alpha_2}$

С. М. Грабовская

Пензенский государственный университет, Пенза

Аннотация: Рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки в полном конечном базисе $B$, содержащем некоторую функцию вида $x_1^{\alpha_1} \vee x_2^{\alpha_2}$, $\alpha_1, \alpha_2 \in \{0,1\}$. Предполагается, что функциональные операторы с вероятностью $\epsilon$ ($\epsilon \in (0,1/2)$) подвержены инверсным неисправностям на выходах, а операторы условной остановки абсолютно надежны. Доказано, что любую булеву функцию можно реализовать неветвящейся программой, функционирующей с ненадежностью не больше $\epsilon+81\epsilon^2$ при $\epsilon \in (0,1/960]$.

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

УДК: 519.718



© МИАН, 2024