РУАЭСТ (RUAEST)
ОЦЕНКИ НЕНАДЕЖНОСТИ СХЕМ В БАЗИСЕ РОССЕРА – ТУРКЕТТА
Актуальность и цель. В современной математике и технике теория синтеза схем из ненадежных функциональных элементов занимает важное место. Стоит отметить, что до сих пор рассматривались задачи построения надежных схем, реализующих только булевые функции. В данной работе предложена математическая модель построения асимптотически оптимальных по надежности схем, реализующих функции трехзначной логики. Исследуется задача реализации функций трехзначной логики схемами из ненадежных функциональных элементов в базисе Россера – Туркетта. Предполагается, что все базисные элементы независимо друг от друга переходят в неисправные состояния и любой базисный элемент на любом входном наборе (с вероятностью 1 – 2ε) выдает правильное значение и с вероятностью, равной ε, может выдать любое из двух неправильных. Целью данной работы является получение нижних и верхних оценок ненадежности схем и построение асимптотически оптимальных по надежности схем. Результаты. В результате исследования полученные ранее верхние оценки ненадежности удалось доказать, существенно ослабив ограничения на ε (ранее эта вероятность зависела от n – числа переменных функции, а в этой работе ее удалось заменить константой). Доказана асимптотическая точность верхних оценок, т.е. в базисе Россера – Туркетта найден класс K функций трехзначной логики такой, что при реализации любой функции из этого класса любой схемой нижняя оценка ненадежности этой схемы будет асимптотически равна верхней оценке ненадежности. Класс K описан в явном виде, а также найдена оценка для количества функций, входящих в данный класс. Выводы. Установлено, что любую функцию трехзначной логики можно реализовать схемой, функционирующей с ненадежностью, асимптотически (при ε → 0) не больше 6ε. Доказано, что функции класса K (содержащего почти все функции трехзначной логики) нельзя реализовать схемами с ненадежностью, асимптотически (при ε → 0) меньше 6ε. Таким образом, почти все функции трехзначной логики можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически равной 6ε при ε→0 .