Синтез надежных схем, реализующих функции двухзначной и трехзначной логик

Барсукова, Оксана Юрьевна

Синтез надежных схем, реализующих функции двухзначной и трехзначной логик тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Барсукова, Оксана Юрьевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Пенза МЕСТО ЗАЩИТЫ

2014 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Синтез надежных схем, реализующих функции двухзначной и трехзначной логик»

Автореферат диссертации на тему "Синтез надежных схем, реализующих функции двухзначной и трехзначной логик"

На правах рукописи

Барсукова Оксана Юрьевна

СИНТЕЗ НАДЕЖНЫХ СХЕМ, РЕАЛИЗУЮЩИХ ФУНКЦИИ ДВУХЗНАЧНОЙ И ТРЕХЗНАЧНОЙ ЛОГИК

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

?2 та щ

Казань - 2014

005548441

Работа выполнена в ФГБОУ ВПО «Пензенский государственный университет» на кафедре «Дискретная математика».

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор ФГБОУ ВПО «Пензенский государственный университет» Алехина Марина Анатольевна

доктор физико-математических наук, профессор ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова» Редькин Николай Петрович;

кандидат физико-математических наук, доцент ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» Гайнутдинова Аида Фаритовна

ФГБОУ ВПО «Восточно-Сибирская государственная академия образования»

Защита состоится 6 июня 2014 г. в {6 ч 00 мин на заседании диссертационного совета Д 212.081.24 при ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, д. 35, конференц-зал научной библиотеки им. Н. И. Лобачевского.

С диссертацией можно ознакомиться в научной библиотеке ФГАОУ ВПО «Казанский (Приволжский) федеральный университет».

Автореферат разослан мая 2014 г.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории надежности управляющих систем.

В современной технике и математике в подавляющем большинстве случаев используется двузначная логика. Это исторически сложившееся положение предопределено ее сравнительной простотой и сделало ее применение предпочтительным (в сравнении с другими логическими системами) с технической и экономической точек зрения. Однако сложность решаемых задач, а следовательно, и технических устройств, постоянно возрастает. Уже подходят к своему пределу многие технологические возможности, такие как увеличение плотности элементов в схемах, повышение рабочей частоты. Применение многозначной логики является одним из путей решения названных проблем.

К многозначным логикам, к их математическому аппарату как к источнику математических моделей, обладающих большими потенциальными возможностями, обращались в книге под редакцией М. А. Ракова 1 и работе Ю. А. Виноградова и М. А. Иорданского2. Обзор работ по многозначной логике содержит работа В. Б. Ларионова 3. В работе Ю. А. Виноградова 4 на компромиссной основе согласованы математические и технические (МДП-техники - от словосочетания металл-диэлектрик-полупроводник) требования и интересы, построен функционально полный в Р3 базис и рассмотрены некоторые аспекты синтеза электронных схем в этом базисе.

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

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

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

3Ларионов В. Б. Замкнутые классы А>зпачной логики, содержащие классы монотонных или самодвойственных функций : дис. ... канд. физ.-мат. паук. - М., 2010. - 158 с.

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

Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман 5. Он предполагал, что элементы схемы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией <р в неисправном состоянии, в которое он переходит независимо от других элементов схемы с вероятностью е(е£ (0,1/2)), реализует функцию (р. Для повышения надежности исходных схем Дж. фон Нейман использовал схему, реализующую функцию голосования д{хх,х2,х3) = хгх2 V а^хз Уад (еще эту функцию называют медианой). С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию ¡(хи...,хп) (п £ ]Ч) можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом е е (0,1/6] (с- некоторая положительная константа).

Таким образом, ненадежность схемы: 1) сравнима с ненадежностью одного отдельно взятого элемента (такие схемы в теории надежности принято называть надежными); 2) не зависит от числа п переменных функции. Основной недостаток метода Дж. Фон Неймана в том, что повышение надежности схем сопровождается существенным (по крайней мере логарифмическим) увеличением сложности схем. Затем надежные схемы с инверсными неисправностями на выходах элементов исследовались в работах С. И. Ортюкова6, Д. Улига7 и некоторых других авторов, причем главное внимание уделялось именно сложности схем.

Задачу построения схем, надежность которых близка к максимально высокой надежности (такие схемы называют асимптотически оптимальными по надежности) решали: М. А. Алехина8 в случае однотипных константных неисправностей только на входах или только на выходах базисных элементов в

5 Von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata studies / edited by Shannon C., Mc. Carthy J. - Princeton : Princeton University Press, 1956 (Русский перевод: Автоматы. - M. : ИЛ, 1956. - С. 68-139.)

6Ортюков С. 11. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и се приложениям (г. Москва, 27-29 января 1987 г.). -М. : Изд-во Моск. ун-та, 1989. - С. 166-168.

7Uhlig D. Reliable networks from unreliable gates with almost minimal comlexity // Fundamentals of Computation Theory: Intern, conf. FCT'87 (Kazan, June 1987). - Berlin : Springer-Vcrl, 1987. - P. -162-4S9.

8 Алехина M. А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов : мопогр. - Пенза : Информационно-издательский центр ПГУ, 2006. - 156 с.

полных неприводимых базисах из двухвходовых элементов; В. В. Чугунова9 -в случае инверсных неисправностей на входах элементов в полных неприводимых базисах из двухвходовых элементов; А. В. Васин10 - в случае инверсных неисправностей на выходах элементов во всех полных базисах, содержащих функции не более, чем трех переменных.

В отличие от названных работ в этой диссертации впервые рассматривается задача построения надежных схем, реализующих функции трехзначной логики (1-я глава) и функции двухзначной логики (булевы функции) при неисправностях двух типов (2-я глава).

Поскольку до появления работ автора ни задача построения асимптотически оптимальных по надежности схем из ненадежных элементов, ни задача построения надежных схем, реализующих функции трехзначной логики, не исследовались, для их решения потребовалась разработка новых оригинальных методов. Все результаты 1-й главы являются новыми и получены впервые.

Во второй главе решается задача синтеза надежных схем, реализующих булевы функции, но предполагается, что базисные элементы подвержены сразу двум типам неисправностей: инверсным неисправностям на выходах с вероятностью е (е € (0,1/4)) и появлению неопределенности на выходе * (* ^ {0,1}) с вероятностью 6 (6 е (0,1/4)). Предполагается также, что: 1) в каждый такт работы любой элемент схемы подвержен только одной неисправности; 2) при появлении на выходе какого-либо элемента схемы неопределенности схема продолжает работать. Такие неисправности элементов рассматриваются впервые и ранее не исследовались.

Приведем известные и связанные с тематикой диссертации результаты о надежности схем из ненадежных функциональных элементов, реализующих булевы функции.

Пусть В - произвольный полный конечный базис в Р2. Пусть / - произвольная булева функция. Считаем, что схема 51 из ненадежных элементов реализует булеву функцию / в базисе В, если она реализует ее при отсутствии неисправностей. Предполагается, что все элементы схемы пере-

9Чугунова В. В. Синтез асимптотически оптимальных по надежности схем при инверсных неисправностях па входах элементов : дис. ... канд. физ.-мат. паук. - Пенза, 2007.

10Васин А. В. Асимптотически оптимальные по надежности схемы в полных базисах из трехиходовых элементов ■. дис. ... канд. физ.-мат. паук. - Пенза, 2010.

ходят в неисправные состояния независимо друг от друга. Обозначим через Peif) = inf Я(5), где инфимум берется по всем схемам S из ненадежных элементов, реализующих булеву функцию /. Схема А из ненадежных элементов, реализующая булеву функцию / в базисе В, называется асимптотически оптимальной (асимптотически наилучшей) по надежности, если Р(А) ~ Pe{f)

при е —> 0, т. е. lim = 1.

e^ü Р(Л)

М. А. Алехиной11 доказано, что в базисах {х1\х2} и {ii 4- х2} при инверсных неисправностях на выходах элементов с вероятностью е почти все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически равной Зе при е —» 0. Решенная в этой статье задача является частным случаем задачи, решенной во 2-й главе диссертации, если считать 6 = 0.

Пусть В3 - множество всех булевых функций, зависящих от трех переменных Х\, Х2, Хз.

А. В. Васин 12 решил задачу синтеза асимптотически оптимальных по надежности схем во всех полных базисах В С В3 при инверсных неисправностях на выходах элементов. Он доказал, что почти любую булеву функцию можно реализовать асимптотически оптимальной по надежности схемой, функционирующей с ненадежностью, асимптотически равной екв при е —» 0. Константа кв зависит от базиса В и кв € {1, 2, 3, 4, 5}.

Задачи синтеза надежных схем, на выходе которых могут быть три различных значения, рассмотрены в диссертационной работе.

Цель работы:

- решить задачу синтеза надежных схем, реализующих функции трехзначной логики, при инверсных неисправностях на выходах элементов;

- решить задачу синтеза надежных схем, реализующих булевы функции, в базисе, состоящем из антиконъюнкции, при неисправностях двух типов.

11 Алехина М. А. О надежности и сложности схем в базисе {х\у} при инверсных неисправностях элементов // Дискретный анализ и исследование операций : сб. ст. Апрель-июнь. - 2005. - Сер. 1. Том 12,- № 2 - С. 3-11.

12Васин А. В. Асимптотически оптимальные по надежности схемы в полных базисах из трехиходовых элементов : дис. ... капд. физ.-мат. наук. - Пенза, 2010.

Научная новизна. Основные результаты диссертации являются новыми. Укажем наиболее важные из них:

1. Разработаны методы синтеза асимптотически оптимальных по надежности схем, реализующих функции трехзначной логики, при инверсных неисправностях на выходах элементов в базисе Россера - Туркетта и надежных схем в базисе, состоящем из функции Вебба.

2. Получены верхние и нижние оценки ненадежности схем в названных базисах при инверсных неисправностях на выходах элементов, а также найдены и явно описаны классы функций, для которых справедливы полученные нижние оценки ненадежности схем.

3. Выявлены свойства функций трехзначной логики (обозначим их множество через G), схемы которых можно использовать для повышения надежности исходных схем при произвольных неисправностях элементов.

4. Разработан метод синтеза надежных схем, реализующих функции трехзначной логики, при инверсных неисправностях на выходах базисных элементов в произвольном полном конечном базисе.

5. В базисе, состоящем из булевой функции штрих Шеффера, при двух типах неисправностей построены надежные схемы, которые для почти всех булевых функций являются асимптотически оптимальными по надежности.

Методы исследований. В работе использованы методы дискретной математики и математической кибернетики, теории вероятностей и математического анализа. Разработаны новые методы синтеза надежных (а в некоторых частных базисах асимптотически оптимальных по надежности) схем.

Теоретическая и практическая значимость. Полученные в работе результаты носят теоретический характер. Они могут быть использованы в дальнейших исследованиях надежности схем из ненадежных функциональных элементов. Предложенные методы синтеза схем, асимптотически оптимальных по надежности, могут найти применение при проектировании технических систем для повышения их надежности.

Апробация работы. Результаты диссертации докладывались на международных и российских конференциях и семинарах, среди которых: VIII молодежная научная школа по дискретной математике и ее приложениям (г. Москва, 2011 г.); Международная конференция «Проблемы автоматиза-

ции и управления в технических системах» (г. Пенза, 2013 г.); Региональный международный форум «Открытые инновации - вклад молодежи в развитие региона» (г. Пенза, 2013 г.); IX молодежная научная школа по дискретной математике и ее приложениям (г. Москва, 2013 г.); семинар «Надежность управляющих систем» под руководством профессора Н. П. Редькина (МГУ им. М. В. Ломоносова, ноябрь 2013 г.; март 2014 г.); научный семинар кафедры теоретической кибернетики (г. Казань, Казанский (Приволжский) федеральный университет, февраль 2014 г.).

Публикации. Результаты диссертации опубликованы в 12 работах автора, список которых приведен в конце автореферата; среди них 3 опубликованы в журналах, рекомендованных ВАК для публикации результатов диссертаций. Семь работ из 12 написаны в соавторстве с научным руководителем М. А. Алехиной (опубликованные результаты являются собственными, М. А. Алехиной принадлежит постановка задачи).

Структура диссертации и объем. Диссертация состоит из введения, двух глав, заключения и списка литературы. Объем диссертации составляет 87 страниц, включая 4 таблицы и 17 рисунков. Список литературы содержит 29 источников.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обзор результатов, связанных с темой диссертации, постановка задачи, дается характеристика работы, вводятся вспомогательные понятия и обозначения, необходимые для формулировки результатов диссертационной работы, формулируются полученные результаты.

В первой главе диссертации рассматривается реализация функций трехзначной логики схемами из ненадежных функциональных элементов.

В разделе 1.1 вводятся вспомогательные понятия и определения, необходимые для формулировки результатов.

Пусть п € N, а Р3(п) - множество функций трехзначной логики, каждая из которых зависит от переменных xi,...,xn, т.е. функций f(xi,...,xn) : {0,1,2}" -у {0,1,2}. Обозначим через Рл множество всех функций трехзначной логики.

Рассмотрим реализацию функций из множества Рл схемами из ненадежных функциональных элементов в произвольном полном конечном базисе В. Предполагается, что элементы схемы переходят в неисправные состояния независимо друг от друга.

Пусть f(x 1, ...,хп) - произвольная функция трехзначной логики, S- любая схема, ее реализующая. Обозначим через хп набор длины п с координатами из множества {0,1,2}, т.е. хп = (xi,...,xn).

Будем считать, что схема из ненадежных элементов реализует функцию f(xn), если при поступлении на входы схемы набора а" при отсутствии неисправностей в схеме на ее выходе появляется значение /(а"). Неисправности базисных элементов могут быть произвольными, но предполагается, что элементы переходят в неисправные состояния независимо друг от друга.

Пусть схема S реализует функцию f(x"). Обозначим через Pi(S,an) вероятность появления значения г (г <= {0,1,2}) на выходе схемы S при входном наборе ап, а через Р/{а")фт{3,ап) - вероятность появления ошибки на выходе схемы S при входном наборе а", на котором /(а") = т, т-е. РПа^т(3,ап) = PT+1(S,an) + PT+2(S,a'1). (В выражениях г + 1 и г + 2 сложение осуществляется по модулю 3.)

Например, если входной набор ап схемы S такой, что f(an) = 0 (т.е. при

отсутствии неисправностей в схеме S на ее выходе появляется значение 0), то вероятность ошибки на этом наборе равна Pf^")^o(S,än) = Pi(S,än) + +P2(S,än).

Ненадежностью схемы S будем называть число P(S) = max{Py(än)^T(S', än)}, где максимум берется по всем входным наборам än схемы S. Надеэюность схемы S равна 1 — P(S).

Далее в первой главе всюду, кроме раздела 1.4.1, предполагается, что базисные элементы с вероятностью е (е е (0,1/4)) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что элемент с функцией ip(xm) на любом входном наборе äm таком, что ip(äm) = т, с вероятностью 1 — 2е выдает значение т, с вероятностью е выдает значение т +1 (mod 3) и с вероятностью е выдает значение т + 2 (mod 3).

Очевидно, что ненадежность любого базисного элемента равна 2е.

Пусть P£(f) = inf P(S), где инфимум берется по всем схемам S из ненадежных элементов, реализующим функцию /. Схема А из ненадежных элементов, реализующая функцию /, называется асимптотически оптимальной по надежности, если Р(А) ~ P£(f) при £ —► 0, т.е. lim ^гщ = 1.

В разделе 1.2 решается задача построения асимптотически оптимальных по надежности схем в базисе Россера - Туркетта {0,1,2, Jq(xi), Ji{xi), Ji{x\), max{xi, x2}, min{a:i, x2}}.

В разделе 1.2.1 получена верхняя оценка ненадежности схем, а именно доказано (теорема 1.5), что любую функцию трехзначной логики можно реализовать такой схемой С, что Р[С) < бе + 126е2 при всех е б (0,1/1000]. Доказательство этой теоремы проводится с помощью теорем 1.3 и 1.4. Сначала (теорема 1.3) строим схему ip(S), которую в дальнейшем используем для повышения надежности исходной схемы S, и находим рекуррентное соотношение для ненадежностей схем ^(S) и S. Затем (теорема 1.4) индукцией по числу переменных функции доказываем, что произвольную функцию трехзначной логики можно реализовать схемой, ненадежность которой не больше 8е при Е 6 (0,1/1000]. Затем, дважды применяя теорему 1.3 к схеме из теоремы 1.4, получим утверждение теоремы 1.5.

Из теоремы 1.5 следует, что любую функцию из Рз можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше бе.

В разделе 1.2.2 получены нижние оценки ненадежности схем.

Пусть К\{п) - множество функций трехзначной логики, каждая из которых зависит от переменных х\,...,хп (п > 3), принимает все три значения 0,1,2 и не представима ни в виде Ж/„. V h(xn), ни в виде xkkh(xn) (к € {1,2,...,п}, h(xn) - произвольная функция трехзначной логики, x&¿y = mm{x,y},xV у = тах{х,у}). Нетрудно проверить (утверждение 1), что класс Kiin) содержит почти все функции из Рз{п). Пусть

оо

Кх = U Kiin).

п=3

В теореме 1.6 доказано, что для произвольной функции / G К\ любая схема S, реализующая /, при е G (0,1/1000] функционирует с ненадежностью PÍS) > бе — 16е2 + 12ея. Доказательство этой теоремы основано на следующей идее: в схеме S, реализующей функцию из выделяется подсхема из трех элементов и доказывается, что ненадежность всей схемы не меньше минимальной вероятности ошибки подсхемы на определенных наборах.

Из теоремы 1.6 следует, что любая схема, реализующая функцию / £ К\, функционирует с ненадежностью, которая асимптотически (при е —> 0) не меньше бе. Это означает, что для функции / € К\ схема, удовлетворяющая условиям теоремы 1.5, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной бе при е —» 0.

Таким образом, в базисе Россера - Туркетта: 1) любую функцию из Рл можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше бе; 2) для почти любой функции такая схема является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной бе при е —> 0.

В разделе 1.3 предложен метод построения надежных схем в полном базисе, состоящем из функции Вебба ^(11,12) = max(a;i,Х2) + 1 (mod 3).

В разделе 1.3.1 получена верхняя оценка ненадежности схем, а именно доказано (теорема 1.9), что любую функцию f € Рз можно реализовать такой схемой D, что PÍD) < 8е + 268е2 при всех е € (0,1/104]. Доказательство этой теоремы аналогично доказательству теоремы 1.5; но схема, повышающая надежность исходной схемы, другая.

Из теоремы 1.9 следует, что любую функцию из Р3 можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше 8е.

В разделе 1.3.2 получена нижняя оценка ненадежности схем.

Пусть К2(п) - множество функций трехзначной логики, каждая из которых зависит от переменных xi,...,xn (п > 3), принимает все три значения 0,1,2 и не представима в виде maxji/t, /i(ín)} + с (к € {1,2, ...,п}, с£ {0,1,2}, h(xn) - произвольная функция трехзначной логики). Нетрудно проверить (утверждение 2), что класс

оо

К^п) содержит почти все функции из Рз(п). Пусть К2 = [_J ^(п). В теоре-

п=3

ме 1.10 доказано, что для произвольной / G любая схема S, реализующая /, при е 6 (0,1/104] функционируете ненадежностью P(S) > бе ~ Юг2 + бе3. Доказательство этой теоремы аналогично доказательству теоремы 1.6.

Из теоремы 1.10 следует, что любая схема, реализующая функцию / 6 К2, функционирует с ненадежностью, которая асимптотически (при е —> 0) не меньше бе.

Таким образом, из теорем 1.9 и 1.10 получаем следующий результат: в базисе {Vy(xi, 2:2)} почти любую функцию трехзначной логики можно реализовать надежной схемой, функционирующей с ненадежностью, асимптотически не больше 8е и асимптотически не меньше бе при е —)■ 0.

В разделе 1.4 рассматривается реализация функций трехзначной логики схемами из ненадежных функциональных элементов в произвольном полном конечном базисе В.

В разделе 1.4.1 предполагается, что базисные элементы подвержены произвольным неисправностям и переходят в неисправные состояния независимо друг от друга.

Пусть &m,ßm - некоторые троичные наборы (тп > 3). Обозначим через p(äm,ß'n) число координат, в которых наборы á'n и ßm различаются.

Обозначим через Gm класс функций g(xm) 6 Р3, каждая из которых обладает следующими свойствами: существуют такие троичные наборы ám, ßm, 7m, что:

1) значения g{äm), g(ßm), g(jm) попарно различны;

2) для любого набора áf (p(äm,ä™) < 1) верно g{äf) = g{äm)\ для

любого набора /3J" (рф"\ ¡3[n) < 1) верно = дфт)\ для любого набора

7Í" {p{TñT) < 1) верно g{Yin) = <?(7m)-

Наборы am, ¡3™, 7m будем называть характеристическими наборами функции д(хт).

оо

Пусть G = (J Gm.

7/1=3

Схемы, реализующие функции из множества G, будем применять для повышения надежности исходных схем, используя следующую теорему (теорема 1.12): предположим, что любую функцию из Рз можно реализовать схемой с ненадежностью не больше р, и пусть схема Sn реализует функцию д{хш) £ G с ненадежностью P{Sg), причем v°,v*,v2 - вероятности ошибок схемы Sg на характеристических наборах ám (д(ат) = 0), ¡Зт {дфп) = 1), 7m (g(jm) = 2) соответственно; тогда произвольную функцию / можно реализовать такой схемой А, что Р(А) < maxl«0,«1,?;2} + mpP(Sg) + (2m — т — 1 )р2. Доказательство этой теоремы конструктивное и состоит в том, что для произвольной функции / £ Рз предъявляется схема А, реализующая функцию /, для ненадежности которой выполняется требуемое неравенство.

В разделе 1.4.2 предполагается, что базисные элементы с вероятностью е подвержены инверсным неисправностям на выходах.

Пусть Кз(п) — множество функций трехзначной логики, каждая из которых зависит от переменных xi,...,xn и отлична от функций xi,...,xn. Очевидно, что класс Кз(п) содержит почти все функции из Рз(м). Пусть

оо

К3 = Кз(п). Доказано (теорема 1.13), что в произвольном полном ко-

п=1

нечном базисе В для функции / £ Кз любая, реализующая ее схема S функционирует с ненадежностью P(S) > 2е.

В теореме 1.14 доказано, что в полном конечном базисе В любую функцию / £ Рз можно реализовать такой схемой А, что при всех е £ (0, l/(Áil04)] верно неравенство

Р(А) < 2Х2£ + к\£2,

где Ai - число элементов в схеме, реализующей функцию Вебба, Л2 - число элементов в схеме, реализующей функцию д(хт) £ G, к\ = 17mA2A2 +

+65(2"1 — т — l)Af. Доказательство проводится с помощью теорем 1.12 и 1.9.

Из теоремы 1.13 следует, что ненадежность схем, построенных при доказательстве теоремы 1.14 (и содержащих хотя бы один функциональный элемент), по порядку равна е. Таким образом, в произвольном полном конечном базисе любую функцию / £ K¿ можно реализовать надежной схемой (функцию f £ Кз можно реализовать абсолютно надежно, не используя функциональных элементов).

Однако при некоторых условиях на базис схемы из теоремы 1.14 для некоторых функций могут быть не просто надежными, а асимптотически оптимальными по надежности.

Доказано (следствие 1.2), что если конечный полный базис В содержит функцию д(хт) е G (при некотором (т > 3)), то любую функцию / е можно реализовать такой схемой А, что при всех е € (0, l/(Ail04)] верно неравенство

Р{А) < 2s + к2е1,

где Aj (как и в теореме 1.14) - число элементов в схеме, реализующей функцию Вебба, к2 = 17m\j + 65(2m - m - l)Af

Таким образом, из теоремы 1.13 и следствия 1.2 получаем следующий результат: если конечный полный базис В таков, что В П G ^ 0, то: 1) любую функцию из Рз можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше 2е; 2) для любой функции, отличной от переменной, такая схема является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 2е при е —> 0.

Во второй главе рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисе, состоящем из функции штрих Шеффера h{x\,x2) = Х\ ■ х2 (еще эту функцию называют антиконъюнкцией). Предполагается, что: 1) все элементы схемы независимо друг от друга переходят в неисправные состояния двух типов: инверсные неисправности на выходах элементов (когда в исправном состоянии элемент с булевой функцией Х\ ■ х2 в неисправном состоянии реализует булеву функцию Х\ • х2) и появление неопределенности *, * ^ {0,1}; 2) в каждый такт работы элемент подвержен либо только инверсной неисправности на выходе, либо только появлению неопределенности * на выходе, причем при появлении на

выходе какого-либо элемента схемы неопределенности она (схема) продолжает работать.

Пусть е (е € (0,1/4)) - вероятность появления инверсной неисправности на выходе элемента, 5 (<5 € (0,1/4)) - вероятность появления неопределенности на выходе элемента, т\ (т! € [0,1/4)) - вероятность появления 0 на выходе элемента при поступлении на его входы наборов (1,*), (*,1), (*,*); а то (т2 € [0,1/4)) - вероятность появления 1 на выходе элемента при поступлении на его входы наборов (1,*), (*Д), (*,*)■

В разделе 2.1 получена верхняя оценка ненадежности схем.

Доказано (теорема 2.3), что любую булеву функцию / можно реализовать такой схемой П, что Р(П) < Зе + 35 + 32 • (Зе2 + б2) + 2т2(48е2 + 175) при всех £, 6, Т\ и 7~2, удовлетворяющих условиям £ + 6 > 71 + Т2, < £ \л £ € (0,1/260], 5 е (0,1/260], т2 € (0,1/260]. Доказательство этой теоремы аналогично доказательству теоремы 1.5.

Из теоремы 2.3 следует, что любую булеву функцию можно реализовать схемой, функционирующей с ненадежностью, асимптотически не больше Зе + 35 при е 0, 5 -4 0.

Заметим, что из условий £ + 6 > 7~1 + т2, т\ < е при е —> 0 и 5 —> 0 следует —> 0 и т2 —>• 0.

В разделе 2.2 получена нижняя оценка ненадежности схем. Пусть К±(п) - множество булевых функций, каждая из которых зависит от переменных х\,...,хп (п > 3) и не представима в виде 1(х"))ь (г € {1,2, ...,п}, а, 6 € {0,1}, Н(хп) - произвольная булева функция). Нетрудно проверить (утверждение 4), что класс Кц{п) содержит почти все

оо

булевы функции, зависящие от переменных Х\,...,хп. Пусть = К^п).

п—3

Доказано (теорема 2.5), что для произвольной функции / € К^ любая схема 5, реализующая функцию /, функционирует с ненадежностью

Р(5) > 3е + 36 + <р(£,б,тит2),

где 1р(Е, 6, п, т2) = —13г5 — 5(52 — Не2 — 36т2 — 26тг — 2ет\ при всех е, 6, п, т2, удовлетворяющих условиям е 4- 6 < 1/8, £ + 5 > т\ + т2 и т\ < е. Доказательство основано на следующей идее: для функции / е К4 в любой схеме 5, реализующей функцию /, можно выделить такую подсхему из трех или

четырех элементов, что ненадежность схемы 5 не меньше минимальной вероятности ошибки подсхемы на определенных наборах (нулевых или единичных для рассматриваемой функции /).

Из теоремы 2.5 следует, что любая схема, реализующая функцию / £ К^, функционирует с ненадежностью, которая асимптотически не меньше Зе 4- 35 при £ —>■ 0, <5—^0. Это означает, что для функции / е Й~4 схема, удовлетворяющая условиям теоремы 2.3, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной Зе + 35 при е 0, <5->0.

Таким образом, при выполнении условий теорем 2.3 и 2.5 получаем следующие результаты: 1) любую булеву функцию можно реализовать схемой, ненадежность которой асимптотически не больше Зе + 35 при е —> 0, <5 —0; 2) для почти любой булевой функции такая схема является асимптотически оптимальной по надежности.

ЗАКЛЮЧЕНИЕ

В первой главе решена задача синтеза надежных схем, реализующих функции трехзначной логики, в произвольном полном конечном базисе и в некоторых частных полных базисах при инверсных неисправностях на выходах элементов. В базисе Россера -Туркетта и в базисе, содержащем функцию множества (7, предложенные схемы оказались не просто надежными, а асимптотически оптимальными по надежности для почти всех функций.

Во второй главе решена задача синтеза асимптотически оптимальных по надежности схем, реализующих булевы функции в базисе, состоящем из антиконъюнкции, при неисправностях двух типов.

Автор благодарит своего научного руководителя профессора М. А. Алехину за постоянное внимание к работе, поддержку и полезные советы, а также сотрудников и аспирантов кафедры дискретной математики МГУ им. М. В. Ломоносова за ценные замечания и советы.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Работы [1-3] опубликованы в журналах, рекомендованных ВАК для публикации результатов диссертаций.

1. Барсукова, О. Ю. О надежности схем, реализующих функции из Ра / М. А. Алехина, О. Ю. Барсукова // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2012. - № 1. -С. 57-65.

2. Барсукова, О. Ю. О ненадежности схем из функциональных элементов, подверженных двум типам неисправностей / М. А. Алехина, О. Ю. Барсукова // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2013. — № 3. — С. 33—50.

3. Барсукова, О. Ю. Оценки ненадежности схем в базисе Россера - Тур-кетта / М. А. Алехина, О. Ю. Барсукова // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2014. — N8 1(29). - С. 5 - 19.

4. Барсукова, О.Ю. О возможности применения одного метода повышения надежности к схемам, реализующим функции из Р3 / О. Ю. Барсукова // Материалы международной научно-практической конференции «Молодежь и наука: модернизация и инновационное развитие страны». - Пенза : Изд-во ПГУ, 2011. - Часть 1. - С. 110-112.

5. Барсукова, О.Ю. Об одном методе повышения надежности схем, реализующих функции из Р[\ / О. Ю. Барсукова // Материалы восьмой международной молодежной школы по дискретной математике и ее приложениям.-М. : Редакционно-издательская группа ИПМ им. М. В. Келдыша, 2011. - Часть 1. - С. 10-13.

6. Барсукова, О.Ю. О верхней оценке ненадежности схем, реализующих функции из Ря / О. Ю. Барсукова // Университетское образование (МКУО-2013) : сб. ст. XVII Междунар. науч.-метод. конф. - Пенза : Изд -во ПГУ, 2013. - С. 261-262.

7. Барсукова, О. Ю. Верхние оценки ненадежности схем в базисе «антиконъюнкция» при неисправностях двух типов / М. А. Алехина, О. Ю. Барсукова // Проблемы автоматизации и управления в техни-

ческих системах : сб. ст. Междунар. науч.-техн. конф. - Пенза : Изд-во ПГУ, 2013. - С. 71-73.

8. Барсукова, О. Ю. Верхняя оценка ненадежности схем в базисе, состоящем из функции Вебба / М. А. Алехина, О. Ю. Барсукова // Материалы девятой молодежной научной школы по дискретной математике и ее приложениям. - М. : Изд-во ИПМ РАН, 2013. - С. 9-12.

9. Барсукова, О. Ю. О надежности схем в базисе Россера - Туркетта / М. А. Алехина, О. Ю. Барсукова // Современные проблемы компьютерных наук (СПКН-2013) : сб. материалов I Междунар. науч.-практ. конф., посвященной 70-летию образования Пензенского государственного университета (г. Пенза, 29-30 октября 2013 г.). - Пенза : Изд-во ПГУ, 2013. -С. 96-98.

10. Барсукова, О. Ю. О нижних оценках ненадежности схем, реализующих функции из Рз / М. А. Алехина, О. Ю. Барсукова // Открытые инновации - вклад молодежи в развитие региона : сб. материалов рег. молодежного форума (Россия, г. Пенза, 22 ноября 2013 г.). - Пенза : Изд-во ПГУ, 2013. - С. 9-10.

11. Барсукова, О. Ю. О синтезе надежных схем, реализующих функции из Рз/ О. Ю. Барсукова // Университетское образование (МКУО-2014) : сб. ст. XVIII Междунар. науч.-метод. конф. - Пенза : Изд-во ПГУ, 2014. -С. 215-217.

12. Барсукова, О.Ю. О повышении надежности схем в Рз / О. Ю. Барсукова // Университетское образование (МКУО-2014) : сб. ст. XVIII Междунар. науч.-метод. конф. - Пенза : Изд-во ПГУ, 2014. - С. 217-218.

Научное издание

Барсукова Оксана Юрьевна

СИНТЕЗ НАДЕЖНЫХ СХЕМ, РЕАЛИЗУЮЩИХ ФУНКЦИИ ДВУХЗНАЧНОЙ И ТРЕХЗНАЧНОЙ ЛОГИК

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Редактор Т. В. Веденеева Компьютерная верстка О. Ю. Барсуковой

Подписано в печать 20.03.2014 г. Формат 60 х 84 1/1С. Усл. печ. л. 1,16.

_Заказ Na 008194. Тираж 120._

Издательство ПГУ 440026, Пенза, Красная, 40 Тел./факс: (8412) 56-47-33; e-mail: ¡ic@pnzgu.ru

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Барсукова, Оксана Юрьевна, Пенза

ФГБОУ ВПО «ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ«

На правах рукописи

¿а/ЭСу/Ю 04201459659 / /

Барсукова Оксана Юрьевна

Синтез надежных схем, реализующих функции двухзначной и

трехзначной логик

01.01.09 — дискретная математика и математическая

кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук,

Научный руководитель доктор физико-математических наук, профессор Алехина М.А.

Пенза - 2014

Оглавление

Введение 3 Глава 1. Ненадежность схем, реализующих функции трехзначной логики 13

1.1 Необходимые понятия и вспомогательные утверждения ... 13

1.2 Базис Россера - Туркетта........................................19

1.2.1 Верхние оценки ненадежности схем....................20

1.2.2 Нижние оценки ненадежности схем ....................30

1.2.3 Выводы....................................................35

1.3 Базис, состоящий из функции Вебба............................35

1.3.1 Верхние оценки ненадежности схем....................36

1.3.2 Нижние оценки ненадежности схем ....................50

1.3.3 Выводы....................................................53

1.4 Произвольный базис..............................................54

1.4.1 Произвольные неисправности............................54

1.4.2 Инверсные неисправности................................59

1.4.3 Выводы....................................................62

Глава 2. Ненадежность схем, реализующих булевы функции 64

2.1 Верхние оценки ненадежности схем............................66

2.2 Нижние оценки ненадежности схем............................73

2.3 Выводы............................................................81

Заключение 82

Литература 84

Введение

Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории надежности управляющих систем.

Задача синтеза управляющих систем является одной из основных задач дискретной математики и математической кибернетики. В современной технике и математике в подавляющем большинстве случаев используется двузначная логика. Это исторически сложившееся положение предопределено ее сравнительной простотой и сделало ее применение предпочтительным (в сравнении с другими логическими системами) с технической и экономической точек зрения. Однако сложность решаемых задач, а, следовательно, и технических устройств, постоянно возрастает. Уже подходят к своему пределу многие технологические возможности, такие как увеличение плотности элементов в схемах, повышение рабочей частоты. Применение многозначной логики является одним из путей решения названных проблем.

К многозначным логикам, к их математическому аппарату как к источнику математических моделей, обладающих большими потенциальными возможностями, обращались в [1,2]. Обзор работ по многозначной логике можно прочесть в [3]. В работе [4] на компромиссной основе согласованы математические и технические (МДП-техшгки - от словосочетания металл-диэлектрик-полупроводник) требования и интересы, построен функционально полный в Рз базис и рассмотрены некоторые аспекты синтеза электронных схем в этом базисе.

Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [5]. Он предполагал,

что элементы схемы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией ip в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью е {е € (0,1/2)), реализует функцию (р. Для повышения надежности исходных схем Дж. фон Нейман использовал схему, реализующую функцию голосования д(хi, х2, х*з) = х\х2У х\х^У х2х<^ (еще эту функцию называют медианой). С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию /(жi,..., хп) (п 6 N) можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом £ € (0,1/6] (с - некоторая положительная константа).

Таким образом, ненадежность схемы 1) сравнима с ненадежностью одного отдельно взятого элемента (такие схемы в теории надежности принято называть надежными); 2) не зависит от числа п переменных функции. Основной недостаток метода Дж. Фон Неймана в том, что повышение надежности схем сопровождается существенным (по крайней мере логарифмическим) увеличением сложности схем. Затем надежные схемы с инверсными неисправностями на выходах элементов исследовались в работах С. И. Ортюкова [6] , Д. Улига [7] и некоторых других авторов, причем главное внимание уделялось именно сложности схем.

Задачу построения схем, надежность которых близка к максимально высокой надежности (такие схемы называют асимптотически оптимальными по надежности) решали: М.А. Алехина [8] в случае однотипных константных неисправностей только на входах или только на выходах базисных элементов в полных неприводимых базисах из двухвходовых элементов; В.В. Чугунова [9] в случае инверсных неисправностей на входах элементов в полных неприводимых базисах из двухвходовых элементов; A.B. Васин [10] в случае инверсных неисправностей на выходах элементов во всех полных базисах, содержащих функции не более, чем трех переменных.

В отличие от названных работ в этой диссертации впервые рассматривается задача построения надежных схем из ненадежных элементов, реализующих функции трехзначной логики (1-ая глава) и функции двухзначной

логики (булевы функции) при неисправностях двух типов (2-ая глава).

Поскольку до появления работ автора ни задача построения асимптотически оптимальных по надежности схем, ни задача построения надежных схем, реализующих функции трехзначной логики, не исследовались, для их решения потребовалась разработка новых оригинальных методов. Все результаты 1-ой главы являются новыми, по лучены впервые.

Во второй главе решается задача синтеза надежных схем, реализующих булевы функции, но предполагается, что базисные элементы подвержены сразу двум типам неисправностей: инверсным неисправностям на выходах с вероятностью s (s Е (О,1/4)) и появлению неопределенности на выходе * (* 0 {0,1}) с вероятностью 6 (5 Е (0,1/4)). Предполагается также, что 1) в каждый такт работы любой элемент схемы подвержен только одной неисправности; 2) при появлении на выходе какого-либо элемента схемы неопределенности схема продолжает работать. Такие неисправности элементов рассматриваются впервые, ранее не исследовались.

Пусть В - произвольный полный конечный базис в Рг. Пусть / -произвольная булева функция. Считаем, что схема 5 из ненадежных элементов реализует булеву функцию / в базисе В, если она реализует ее при отсутствии неисправностей. Предполагается, что все элементы схемы переходят в неисправные состояния независимо друг от друга. Обозначим

через Ре(/) = inf P(S), где инфимум берется по всем схемам S из ненадеж-s

ных элементов, реализующим булеву функцию /. Схема А из ненадежных элементов, реализующая булеву функцию / в базисе В, называется асимптотически оптимальной (асимптотически наилучшей) по надежности, если Р(Л) ~ Р£(/) при г 0, т. е. lim = 1.

М.А. Алехиной [11] доказано, что в базисах {.Ti|.X2} и {х\ 4- -^2} при инверсных неисправностях на выходах элементов с вероятностью е почти все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотиче-

ски равной Зг при £ —0. Решенная в этой статье задача является частным случаем задачи, решенной во 2-ой главе диссертации, если считать 5 = 0.

Пусть Вз - множество всех булевых функций, зависящих от трех переменных х\, .т2, гсз-

A.B. Васин [10] решил задачу синтеза асимптотически оптимальных по надежности схем во всех полных базисах В С при инверсных неисправностях на выходах элементов. Он доказал, что почти любую булеву функцию можно реализовать асимптотически оптимальной по надежности схемой, функционирующей с ненадежностью, асимптотически равной кв • £ при £ —> 0. Константа кв зависит от базиса В, и кв Е {1, 2, 3, 4, 5}.

Задачи синтеза надежных схем, на выходе которых могут быть три различных значения, рассмотрена в диссертационной работе.

Диссертация состоит из введения, двух глав, заключения и списка литературы, содержащего 29 наименований. Общий объем работы - 87 страниц.

В разделе 1.1 вводятся вспомогательные понятия и определения, необходимые для формулировки результатов.

Пусть п Е N, а Pj(n) - множество функций трехзначной логики, каждая из которых зависит от переменных xi,...,xn, т.е. функций /(:xi,...,xn) : {0,1,2}" {0,1,2}. Обозначим через Р3 множество всех функций трехзначной логики.

Пусть В ~ произвольный полный конечный базис (В С Р3). Пусть f(x 1,..., хп) - произвольная функция трехзначной логики, S - любая схема, ее реализующая. Обозначим через xl (I G N) набор длины I с координатами из множества {0,1, 2}. В частности, (жх, ...,хп) = хп.

Будем считать, что схема S из ненадежных элементов реализует функцию f(xn), если при поступлении на входы схемы S набора ап при отсутствии неисправностей в схеме на ее выходе появляется значение f{än). Предполагается, что элементы схемы переходят в неисправные состояния независимо друг от друга, а неисправности элементов могут быть произвольными.

Обозначим через P{(S, än) вероятность появления значения г (г £ {0,1, 2}) на выходе схемы S при входном наборе än, а через Pf(än)^r(S, än) - вероятность появления ошибки на выходе схемы S при входном наборе а", на котором f{än) = т, т.е. P/(än)^r(S, ~ап) = PT+i(S, än) + PT+2(S, ап). (В выражениях т + 1 и т + 2 сложение осуществляется по модулю 3.)

Например, если входной набор ап схемы S такой, что f(än) = 0 (т.е. при отсутствии неисправностей в схеме S на ее выходе появляется значение 0), то вероятность ошибки на этом наборе равна Pf(ä^o{S,än) = P1(S,än) + P2(S,än).

Ненадео/спостъю схемы S будем называть число P(S) = m£ix{Py(än)^T(5', <2П)}, где максимум берется по всем входным наборам ап схемы S. Надежность схемы S равна 1 — P(S).

Далее в первой главе всюду, кроме раздела 1.4.1, предполагается, что базисные элементы с вероятностью £ подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что элемент с функцией ip(xm) на любом входном наборе ат таком, что (p(äm) = т, с вероятностью 1 — 2е (г £ (0,1/4)) выдает значение г, с вероятностью £ выдает значение г +1 (mod 3) и с вероятностью £ выдает значение т + 2 (mod 3).

Очевидно, что ненадежность любого базисного элемента равна 2е.

Пусть Ре(/) = infP(S'), где инфимум берется по всем схемам S из ненадежных элементов, реализующим функцию / над базисов В. Схема А из ненадежных элементов, реализующая функцию трехзначной логики /, называется асимптотически оптимальной по надежности, если Р(А) Pe{f) при £ О, т.е. lim Щ = 1.

В разделе 1.2 решается задача построения асимптотически оптимальных по надежности схем в базисе Россера - Туркетта {0,1,2, Jq(xi), Ji(xi), </2(^1), max{xi, х2}, min{x'i, ж2}}.

В разделе 1.2.1 получена верхняя оценка ненадежности схем, а именно доказано (теорема 1.5), что любую функцию трехзначной логики можно реализовать такой схемой С, что Р(С) < б£ + 126е2 при всех £ G (0,1/1000]. Следовательно, любую функцию из Р3 можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше б£.

В разделе 1.2.2. получены нижние оценки ненадежности схем.

Пусть К\{п) - множество функций трехзначной логики, каждая из которых зависит от переменных (n ^ 3), принимает все

три значения 0,1,2 и не представима ни в виде Xk V h{xn), ни в виде xkhh{xn) (к G {1, 2,.... n}, h(xn) - произвольная функция трехзначной логики, xSzy = minja:, у}, х V у = тах{ж, у}). Нетрудно проверить (утверждение 1), что класс К\{п) содержит почти все функции из Рз(п). Пусть

оо

Кг = U КЛп)- В

теореме 1.6 доказано, что для произвольной функции

п=з

/ 6 К\ любая схема S, реализующая /, при е е (0,1/1000] функционирует с ненадежностью P(S) > бе — 16е2 + 12е3. Следовательно, любая схема, реализующая функцию / G К\ функционирует с ненадежностью, которая асимптотически (при £ 0) не меньше бе. Это означает, что для функции / 6 К\ схема, удовлетворяющая условиям теоремы 1.5, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 6£ при е —> 0.

Таким образом, в базисе Россера - Туркетта: 1) любую функцию из Р3 можно реализовать схемой, ненадежность которой асимптотически (при £ —У 0) не больше 6г; 2) для почти любой функции такая схема является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной б£ при s —> 0.

В разделе 1.3 предложен метод построения надежных схем в полном базисе, состоящем из функции Вебба V^(xь-тг) = max(.Ti,.T2) + 1 (mod 3).

В разделе 1.3.1 получена верхняя оценка ненадежности схем, а именно доказано (теорема 1.9), что любую функцию / € Рз можно реализовать такой схемой D, что P(D) < 8е + 268s2 при всех е Е (0,1/104]. Следовательно, любую функцию из Рз можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше 8е.

В разделе 1.3.2 получена нижняя оценка ненадежности схем.

Пусть К2{п) - множество функций трехзначной логики, каждая из которых зависит от переменных rci,..., (n ^ 3), принимает все три значения 0,1,2 и не представима в виде шах { хь h{xn) } + с {к в {1,..,п}, с <Е {0, 1, 2}, h{xn) -произвольная функция трехзначной логики). Нетрудно проверить (утвер-

ждение 2), что класс /^(п) содержит почти все функции из Рз{п). Пусть 00

К2 = [J К2(п)- В теореме 1.10 доказано, что для произвольной / £ Кч

71=3

любая схема S, реализующая /, при е £ (0,1/104] функционирует с ненадежностью P(S) > 6s — 16е2 + 12е3. Следовательно, любая схема, реализующая функцию f € К2, функционирует с ненадежностью, которая асимптотически (при £ —> 0) не меньше б£.

Таким образом, из теорем 1.9 и 1.10 получаем следующий результат: в базисе {Уз(х1,х2}} почти любую функцию трехзначной логики можно реализовать надежной схемой, функционирующей с ненадежностью, асимптотически не больше и асимптотически не меньше бе при г —> 0.

Пусть ат,/5т - некоторые троичные наборы (т ^ 3). Обозначим через /э(ат, ¡Зт) число координат, в которых наборы ám и /Зт различаются.

Обозначим через Gm класс функций д(хт) £ Р3, каждая из которых обладает следующими свойствами: существуют такие троичные наборы ám, Рт, 7™, что

1) значения ^(а-771), дфт), д(ут) попарно различны;

2) для любого набора á™ (p(ám,á™) ^ 1) верно д(а™) = д(ат)', для любого набора /З]71 (рфт, ^f1) ^ 1) верно дф™) = дфт); для любого набора 7Г M7m, 7Р) ^ 1) верно = д{7т).

Наборы ám, 7т будем называть характеристическими наборами

оо

функции д{хш). Пусть G = (J Gm.

т=3

ет функцию д{хт) G G с ненадежностью P(Sg), причем v°,v1,v2 - вероятности ошибок схемы Sg па характеристических наборах ат (д(ат) = 0), Рт {д0т) — 1), 7т (д(ут) — 2) соответственно; тогда произвольную функцию / можно реализовать такой схемой А, что Р{А) ^ тах{г?°, v1, v2} + mpP(Sg) + (2т - т - 1 )р2.

В разделе 1.4.2 предполагается, что базисные элементы с вероятностью £ подвержены инверсным неисправностям на выходах.

Пусть Щп) - множество функций трехзначной логики, каждая из которых зависит от переменных xi, ...,хп и отлична от функций х\, ...,хп. Очевидно, что класс К^(п) содержит почти все функции; пусть =

оо

I^J Кз(п). Из теоремы 1.13 следует, что в произвольном полном конечном

п=i

базисе В для функции / G K-¿ любая, реализующая ее схема S функционирует с ненадежностью P{S) > 2е.

В теореме 1.14 доказано, что в полном конечном базисе В любую функцию / G Рз можно реализовать такой схемой А, что при всех е G (0,1/(AilO4)] верно неравенство Р(А) ^ 2Á2e + ki£2, где Ai - число элементов в схеме, реализующей функцию Вебба, \2 - число элементов в схеме, реализующей функцию д{хт) G G, ki = 17т\2\2 + 65(2m — т — l)Aj.

Из теоремы 1.13 следует, что ненадежность схем, построенных при доказательстве теоремы 1.14 (и содержащих хотя бы один функциональный элемент), по порядку равна е. Таким образом, в произвольном полном конечном базисе любую функцию / G можно реализовать надежной схемой (функцию / $ можно реализовать абсолютно надежно, не используя функциональных элементов).

Однако при некоторых условиях на базис, схемы из теоремы 1.14 для некоторых функций могут быть не просто надежными, а асимптотически оптимальными по надежности.

Доказано (�