Оценки ненадежности схем в базисе Россера - Туркетта

Актуальность и цель. В современной математике и технике теория синтеза схем из ненадежных функциональных элементов занимает важное место. Стоит отметить, что до сих пор рассматривались задачи построения надежных схем, реализующих только булевые функции. В данной работе предложена математическая модель построения асимптотически оптимальных по надежности схем, реализующих функции трехзначной логики. Исследуется задача реализации функций трехзначной логики схемами из ненадежных функциональных элементов в базисе Россера - Туркетта. Предполагается, что все базисные элементы независимо друг от друга переходят в неисправные состояния и любой базисный элемент на любом входном наборе (с вероятностью $1 - 2\epsilon$) выдает правильное значение и с вероятностью, равной $\epsilon$, может выдать любое из двух неправильных. Целью данной работы является получение нижних и верхних оценок ненадежности схем и построение асимптотически оптимальных по надежности схем.
Результаты. В результате исследования полученные ранее верхние оценки ненадежности удалось доказать, существенно ослабив ограничения на (ранее эта вероятность зависела от n - числа переменных функции, а в этой работе ее удалось заменить константой). Доказана асимптотическая точность верхних оценок, т.е. в базисе Россера - Туркетта найден класс K функций трехзначной логики такой, что при реализации любой функции из этого класса любой схемой нижняя оценка ненадежности этой схемы будет асимптотически равна верхней оценке ненадежности. Класс описан в явном виде, а также найдена оценка для количества функций, входящих в данный класс.
Выводы. Установлено, что любую функцию трехзначной логики можно реализовать схемой, функционирующей с ненадежностью, асимптотически (при $\epsilon \rightarrow 0$) не больше $6\epsilon$. Доказано, что функции класса K (содержащего почти все функции трехзначной логики) нельзя реализовать схемами с ненадежностью, асимптотически (при $\epsilon \rightarrow 0$) меньше $6\epsilon$. Таким образом, почти все функции трехзначной логики можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически $6\epsilon$ равной при $\epsilon\to 0$.