Асимптотически оптимальные по надежности схемы в базисе Россера - Туркетта в $P_4$

Актуальность и цели. Многозначная логика предоставляет широкие возможности для разработки различных алгоритмов во многих областях. Она позволяет уменьшить как вычислительную сложность, так и размеры, число соединений в различных арифметико-логических устройствах, повысить плотность размещения элементов на схемах, найти альтернативные методы решения задач. Уже сейчас многозначная логика с успехом применяется при решении многих задач и во множестве технических разработок. Среди них различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработки сложных цифровых сигналов и т.д. Определенный интерес представляет задача исследования надежности функционирования схем в полном конечном базисе из $k$-значных функций ($k \geq 3$). Задача построения надежных схем в произвольном полном базисе из трехзначных функций (т.е. при $k=3$) решена в диссертации О. Ю. Барсуковой. Цель работы - построить асимптотически оптимальные по надежности схемы в базисе Россера - Туркетта при $k=4$. Результаты. Найдена схема, которую можно использовать для повышения надежности исходных схем, получено рекуррентное соотношение для ненадежностей исходной схемы и предлагаемой схемы. Описан метод синтеза надежных схем, получена верхняя оценка ненадежности схем. Описан класс функций $K$, содержащий почти все четырехзначные функции, и доказана нижняя оценка ненадежности схем, реализующих функции из этого класса. Для функции из класса $K$ построена схема, верхняя и нижняя оценки ненадежности которой асимптотически равны. Выводы. Почти любую функцию четырехзначной логики можно реализовать асимптотически оптимальной по надежности схемой.