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

Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2012, выпуск 1, страницы 57–65 (Mi ivpnz508)

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

Математика

О надежности схем, реализующих функции из $P_3$

М. А. Алехина, О. Ю. Барсукова

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

Аннотация: Рассматривается реализация функций трехзначной логики схемами из ненадежных функциональных элементов в базисе Россера - Туркетта. Предполагается, что вероятность появления одного неверного значения на выходе любого базисного элемента на каждом входном наборе равна $\epsilon$, а следовательно, вероятность ошибки равна $2\epsilon$. Доказано, что любую функцию трехзначной логики $f(x_1,...x_n)$ можно реализовать схемой, ненадежность которой при всех $\epsilon \in (0,1/8*3^n*(2n+1)(13^n*4(2n+1)))$ не превосходит $6\epsilon + 420\epsilon^2$.

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

УДК: 519.718



© МИАН, 2024