EN|RU

Том 19, номер 1, 2012 г., Стр. 33-40

УДК 519.718
Грабовская С. М. 
О надёжности неветвящихся программ в базисе, содержащем обобщённую конъюнкцию

Аннотация:
Рассматривается реализация булевых функций неветвящимися программами с операторами условной остановки в полном конечном базисе, содержащем хотя бы одну из функций $x_1\cdot x_2$, $\overline x_1\cdot x_2$, $\overline x_1\cdot\overline x_2$. Предполагается, что функциональные операторы с вероятностью $\varepsilon\in(0,1/2)$ подвержены инверсным неисправностям на выходах, а операторы условной остановки абсолютно надёжны. Доказано, что в таких базисах любую булеву функцию можно реализовать неветвящейся программой, функционирующей с ненадёжностью не больше $\varepsilon+59\varepsilon^2$ при $\varepsilon\in(0,1/960]$.
Ил. 1, библиогр. 4.

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

Грабовская Светлана Михайловна 1
1. Пензенский гос. университет,
ул. Красная, 40, 440026 Пенза, Россия
е-mail: swetazin@mail.ru

Статья поступила 16 ноября 2010 г.
Исправленный вариант — 14 октября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015