Том 21, номер 4, 2014 г., Стр. 12-24

УДК 519.718
Алехина М. А., Барсукова О. Ю.
О надёжности схем, реализующих функции трёхзначной логики

Аннотация:
Рассматривается реализация функций трёхзначной логики схемами из ненадёжных функциональных элементов в произвольном полном конечном базисе. Предполагается, что элементы схемы переходят в неисправные состояния независимо друг от друга, а сами неисправности могут быть произвольными (например, инверсными или константными).
В работе описан класс G функций трёхзначной логики, схемы которых можно использовать для повышения надёжности исходных схем. При инверсных неисправностях на выходах базисных элементов с использованием функций класса G конструктивно доказано, что функцию, отличную от любой из переменных, можно реализовать надёжной схемой (напомним, что функцию, равную одной из переменных, можно реализовать абсолютно надёжно, не используя функциональных элементов). В частности, если рассматриваемый базис содержит хотя бы одну из функций класса G, то предлагаемые схемы являются не просто надёжными, а асимптотически оптимальными по надёжности для всех функций, отличных от любой из переменных.
Ил. 2, библиогр. 13.

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

Алехина Марина Анатольевна ¹
Барсукова Оксана Юрьевна ¹
1. Пензенский гос. университет,
ул. Красная, 40, 440026 Пенза, Россия
е-mail: ama@sura.ru, kuzya_7@mail.ru

Статья поступила 11 ноября 2013 г.
Исправленный вариант — 21 февраля 2014 г.

Литература

[1] Аксенов C. И. О надёжности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Изв. вузов. Поволжский регион. Естеств. науки. - № 6. - Пенза: ИИЦ ПГУ, 2005. - С. 42–55.

[2] Алехина М. А. О надёжности и сложности схем в базисе {x|y} при инверсных неисправностях на выходах элементов // Дискрет. анализ и исслед. операций. Сер. 1. - 2005. - Т. 12, №2. - С. 3–11.

[3] Алехина М. А., Аксенов С. И., Васин А. В. О функциях и схемах, применяемых для повышения надёжности схем // Изв. вузов. Поволжский регион. Физ.-мат. науки. - №3. - Пенза: ИИЦ ПГУ, 2008. - С. 30–38.

[4] Алехина М. А., Барсукова О. Ю. О надёжности схем, реализующих функции из P₃ // Изв. вузов. Поволжский регион. Физ.-мат. науки. - Пенза: ИИЦ ПГУ, 2012. –– № 1. - С. 57–65.

[5] Алехина М. А., Барсукова О. Ю. Верхняя оценка ненадёжности схем в базисе, состоящем из функции Вебба // Мат. IX междунар. молодёж. школы по дискретной математике и её приложениям (Москва, 16–21 сентября 2013 г.). –– М.: Изд-во Ин-та прикл. математики им. М. В. Келдыша
РАН, 2013. - С. 9–12.

[6] Алехина М. А., Васин А. В. О надёжности схем в базисах, содержащих функции не более чем трех переменных // Уч. зап. Казанск. гос. ун-та. Сер. Физ.-мат. науки. - 2009. - Т. 151, кн. 2. - С. 25–35.

[7] Барсукова О. Ю. О возможности применения одного метода повышения надёжности к схемам, реализующим функции из P₃ // Мат. междунар. научно-практ. конф. .Молодежь и наука: модернизация и инновационное развитие страны. (Пенза, 15–16 сентября 2011 г.). 1 ч. - Пенза:
Изд-во ПГУ, 2011. - С. 110–112.

[8] Виноградов Ю. А. О синтезе трёхзначных схем // Мат. вопросы кибернетики. Вып. 3. - М.: Наука, 1991. - С. 187–198.

[9] Виноградов Ю. А., Иорданский М. А. Машинный анализ схем ЭВМ // Пробл. кибернетики. Вып. 24. - М.: Наука, 1972. - С. 147–160.

[10] Ларионов В. Б. Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций: Дис. . . . канд. физ.-мат. наук: 01.01.09 - М., 2010. - 158 с.

[11] Моделирующие системы с многозначными гибридным кодированием. - Киев: Наук. думка, 1980. - 192 с.

[12] Alekhina М. А. Synthesis and complexity of asymptotically optimal circuits with unreliable gates // Fundam. Informaticae. - 2010. - Vol. 104, N3. - P. 219–225.

[13] Von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata Studies. - Princeton: Princeton Univ. Press, 1956. - P. 43–98.