Асимптотически оптимальные по надежности схемы в полных базисах из трехвходовых элементов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

004612378

Васин Алексей Валерьевич

АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫЕ ПО НАДЕЖНОСТИ СХЕМЫ В ПОЛНЫХ БАЗИСАХ ИЗ ТРЕХВХОДОВЫХ ЭЛЕМЕНТОВ

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

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

►1 1 НОЯ 2010

Казань 2010

004612378

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» на кафедре «Дискретная математика».

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

доцент Алехина М. А.

Официальные оппоненты: доктор физико-математических наук,

профессор Мошков М. Ю.;

кандидат физико-математических наук, доцент Нурмеев Н. Н.

Ведущая организация: ФГОУВПО «Московский государственный

университет им. М. В. Ломоносова»

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

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

Автореферат разослан « » октября 2010 г.

Ученый секретарь диссертационного совета Д 212.081.24 при КФУ кандидат физико-математических наук

Еникеев А. И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории синтеза, надежности и сложности управляющих систем.

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

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

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

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

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

Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах Р. Л. Добрушина, С. И. Ортюковэ, Д. Улига и некоторых других авторов, причем главное внимание уделялось сложности таких схем (задача синтеза наилучших по надежности схем не ставилась). Сформулируем полученные ими результаты.

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в произвольном полном конечном базисе В = {ei,e2, ...,em}, т £ N (множество всех функциональных элементов E¡, функции которых &¡ принадлежат базису В, будем также называть базисом2 В). Каждому элементу £¿ базиса приписано положительное число v(E¡) - вес данного элемента. Сложность L(S) схемы 5 определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимо друг от друга с вероятностью е подвержены инверсным неисправностям на выходах элементов. Пусть Pf^(S,á) - вероятность появления значения /(а) на выходе схемы S при входном наборе а схемы S. Ненадежность P(S) схемы S, реализующей булеву функцию f(x), равна P(S) = таxPf^(S,a), где максимум берется по всем возможным входным наборам а схемы S. Надежность схемы S равна 1 — P(S). Вводится функция Шеннона Lp.(n) = maxminL(5),

/ s

характеризующая сложность схем, реализующих булевы функции от п переменных в базисе В, где минимум берется по всем схемам S из ненадежных элементов, реализующим функцию f(xi,x2,...,хп) с ненадежностью P(S) < р, а максимум - по всем булевым функциям / от п переменных.

Пусть р = min(v(Ei)/(n(Ei) — 1)), где минимум берется по всем элемен-

Ei

там Ei базиса, для которых n(£'¡) > 1, n(Ei) - число существенных перемен-

"Лупапоп О. Б. Асимптотические оценки сложности управляющих систем. - М. : Изд-во МГУ, 1984.

ных функции ei, реализуемой элементом Е{, a v(Ei) - вес функционального элемента Ei, i = 1,..., т.

О. Б. Лупанов3 показал, что для схем, реализующих булевы функции от п переменных и состоящих только из надежных элементов (т.е. при £ = 0 и р — 0), выполняется соотношение Lo,o ~ р2"/п.

С. И. Ортюков4 для инверсных неисправностей на выходах элементов получил следующий результат. Пусть 0 < е < £о. р > q(e)Lg, где Lg - минимальное число надежных элементов, необходимое для реализации функции голосования д(:ii,x2,xz) = Х1Х2 V ж^з V х^х^ в рассматриваемом базисе, q(s) - некоторая функция, такая что q(e) = е + Зе2 + о(е2) при е 0. Тогда существует такая функция р(е) —»• р при е 0, что Lpß(n) < р(е)2п/п.

Д. Улиг5 для инверсных неисправностей на выходах элементов с вероятностью ошибки е доказал, что для любых сколь угодно малых чисел b и h (b,h > 0) существует такое число е'(е' g (0,1/2)), что при любом е (е 6 (0,е']) и любом р, удовлетворяющем условию р > (1 + h)eLg (точнее р > q(e)Lg), справедливо соотношение Lpfi(n) < (1 + Ъ)р2п/п.

Таким образом, в результатах С. И. Ортюкова и Д. Улига асимптотика функции Шеннона сохраняется с точностью до множителя, сколь угодно близкого к единице (при этом вероятность сбоя е ограничена константой), т.е. найденные ими методы синтеза позволяют строить асимптотически оптимальные по сложности схемы, функционирующие с некоторым уровнем надежности.

Из результатов Н. Пиппенджера6 следует, что в базисе {xi&x2,x\ V Х2, х\} при инверсных неисправностях на выходах элементов любую булеву функцию от п переменных можно реализовать такой схемой S, что P{S) < 18s при всех е е (0,1/200], L(S) < 1702"/п.

С. В. Яблонский7 рассматривал задачу синтеза надежных схем в базисе В = {xi$zx2,xi V х2,х\,д(х\,х2,хз)}. Он предполагал, что элемент, реали-

3Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Изд-во МГУ, 1984.

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

5Uhlig D. Reliable networks from unreliable gates with almost minimal comlexity // Fundamentals of Computation Theory. Intern, conf. FCT'87 (Kasan, June 1987). - Berlin : Springer-Verl, 1987. - P. 462-469.

6Pippenger N. On networks of Noisy Gates //26 Symposium on Foundation on Computer science (Portland, 21-23 October 1985). - Portland : IEEE, 1985. - P. 30-38.

7 Яблонский С. В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center. - ¡982. - .V« 7. - P. 11-19.

зующий функцию голосования д{х 1,2:2, жз) = Х\Х2 V х\хз V Ж2Ж3, абсолютно надежный, а конъюнктор, дизъюнктор и инвертор - ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше е. Им доказано, что для любого р > О существует алгоритм, который для каждой булевой функции Х2,. ■ ■, хп) строит такую схему 5, что Р(5) < р, 1(5) < 2"_1/п.

В. В. Тарасов8 рассматривал задачу построения схем сколь угодно высокой надежности (когда Р(Б) —^ 0). Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом В. В. Тарасов нашел необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных им результатов следует невозможность построения сколь угодно надежных схем для всех, отличных от Х2, ■ ■ ■, хп, функций /(а?!, Жг, • ■ •, хп) при инверсных неисправностях на выходах элементов.

Пусть Ре(/) — т{Р(3), где инфимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию /. Схема А из ненадежных элементов, реализующая функцию /, называется асимптотически наилучшей (асимптотически оптимальной) по надежности, если Р(А) ~ РЕ(/) при с —> 0,

, ад 1

т.е. 11т—— = 1. Р(А)

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

Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью е £ (0;1/2), реализует константу 0, то она называется неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, то такая неисправность называется неисправностью типа 1 на выходе элемента.

8Тарасов В. В. К синтезу падежных схем из ненадежных элементов // Матем. заметки. — 1976. — Т. 20. - Л» 3. - С. 391—400.

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

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

Введем обозначения: Вг - это множество всех булевых функций, зависящих от двух переменных х\, Х2, а - это множество всех булевых функций, зависящих от трех переменных XI, Х2, жз-

М. А. Алехиной доказано, что во всех неприводимых полных базисах В С 1?2 (исключая три случая) почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами 5, функционирующими с ненадежностью Р(5), асимптотически равной ае1 при е —> 0, константы а и £ зависят от базиса и типа неисправностей, а (Е {1, 2, 3}, í £ {1,2}. Для почти всех функций сложность таких схем в случаях константных неисправностей только на выходах или только на входах элементов удовлетворяет соотношению Ь(Б) < кв2п/п, причем мультипликативная константа кв зависит только от базиса В, 40 < кв < 168.

Если неисправность элемента такова, что поступающее на вход значение а [а 6 {0,1}) с вероятностью е 6 (0;1/2) может превратиться в а, то она называется инверсной неисправностью на входе элемента.

В. В. Чугуновой10 доказано, что во всех неприводимых полных базисах ВСВ2 при инверсных неисправностях на входах почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами 5\ функционирующими с ненадежностью Р(5), асимптотически равной ае при е -> 0, константа а зависит от базиса, а Е {2,3,4}. Для почти всех функций сложность предлагаемых схем удовлетворяет соотношению ¿(5) < кв2"/п, причем мультипликативная константа кв также зависит только от базиса В, 168 < кв < 504.

М. А. Алехина11 рассматривала инверсные неисправности на выходах элементов и доказала, что при инверсных неисправностях на выходах элемен-

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

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

тов в базисах {х\\х2} и {xi 4-^2} почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами S, функционирующими с ненадежностью, асимптотически равной Зе при е —)- 0. Сложность предлагаемых схем для почти всех функций L(S) < кв2"/п, причем мультипликативная константа кд также зависит только от базиса В, кд = 672.

С. И. Аксеновым12 получена верхняя оценка ненадежности схем в произвольном полном конечном базисе В при инверсных неисправностях на выходах элементов. Он доказал, что существуют такие положительные константы ео и d, зависящие от базиса В, что любую булеву функцию можно реализовать схемой S, ненадежность которой

P(S) < 5е + de2 (1)

при любом е £ (0;во].

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

С. И. Аксенов13 получил следующий результат. Пусть

Ti = {í, 0, 1} U {Ж1&Ж2, Х1&СХ2&Х3, •■•},

Т2 = {0, 1} U {Xi&X2, Xi$¿X2&X3, ...,Xi&¿X2&---&Xk, ...}U

U {XI&ZX2, X1&X2&ZX3, ..., Xi&¿X2&---&ÍXki ••■}

и T3 = TJ, T4 = TJ (T3 и T4 - множества функций, двойственных функциям множеств Ti и Тг соответственно). Если полный в Р2 базис В не является подмножеством ни одного из множеств T¿, i = 1,2,3,4, то существуют такие положительные константы ео и d, что в базисе В любую булеву функцию / можно реализовать схемой S с ненадежностью P(S)' < 4ё -f de2 при всех

Пусть булева функция т[хltX2, ■■■,Хк) зависит от к (к > 3) переменных и обладает следующим свойством: найдется такой набор (&i, 62,...,

'^Аксенов С. И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Известия высших .учебных заведений. Поволжский регион. -№ б (21). — 2005. — С. 42-55. — (Естественные науки).

"Аксенов С: И. О надежности схем в широком классе полных базисов // Дискретная математика и ее приложения : материалы IX Международного семинара, посвященного 75-летию со дня рождения академика О. Б. Лупанова (г. Москва, 18 23 июня 2007 г.). — М.: Изд-во мех.-мат. фак-та МГУ, 2007. — С. 55-56.

что на нем и всех соседних с ним наборах функция т принимает значение О, а на наборе (¿1, 62,..., 6к) и всех соседних с ним наборах - значение 1. Пусть (5.— множество всех булевых функций с названным свойством. Введем обозначение: А^в(С) - наименьшее число надежных элементов, необходимое для реализации какой-либо функции из множества (5 в базисе В.

М. А. Алехиной и С. И. Аксеновым14 доказано, что в произвольном полном конечном базисе В для любого Ь > 0 существуют такие константы £о £ (0,1/2) и й > 0, что при любом п любую булеву функцию /(х^ Х2, •••,2;п) можно реализовать схемой й, для которой при любых е € (0,£о] верно Р(5) < еМв(6) + Ле2, ¿(5) < 3(1 + Ъ)р2п/п при п оо.

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

Вопрос о возможности построения асимптотически наилучших по надежности схем при инверсных неисправностях на выходах элементов в базисах, не содержащих медиану, а также отличных от {х^хг} и {жх 4 Х2}, оставался открытым.

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

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

14Алехина М. А.. Аксенов С. И. О сложности надежных схем при инверсных неисправностях на выходах элементов // Дискретная математика и ее приложения : материалы IX Международного семинара, посвященного 75-летию со дня рождения академика О. Б. Лупанова (г. Москва., 18-23 июня 2007 г.). — М. : Изд-во мех.-мат. фак-та МГУ, 2007. - С. 56 -59.

1,3Алехина М. А., Шилов А. В. Верхние оценки ненадежности схем в некоторых базисах при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. -- 2006. ДО 5 (26). — С. 4 -12. - (Естественные науки).

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

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

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

2. Найдены все полные базисы В С Вз, в которых для почти всех функций любая схема 5 имеет ненадежность Р(5) > 5е(1 — е)4 при всех е £ (0,1/960]. Следовательно,

a) в этих базисах для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью, асимптотически равной Ъе при е -> 0;

b) мультипликативная константа 5 в результате (1) С. И. Аксенова не может быть понижена в некоторых полных базисах.

3. Для любого полного базиса В С Вз найдена такая константа с 6 {1,2,3,4,5}, что для почти всех функций ненадежность асимптотически оптимальных по надежности схем асимптотически равна се при € 0.

4. Найдены все функции трех переменных, наличие которых в полном базисе позволяет реализовать произвольную булеву функцию / такой схемой 5, что Р(Б) ~ е при е 0.

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

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

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

Апробация работы. Результаты диссертации представлены на международных и российских конференциях и семинарах, среди которых: IX и X Международный семинар «Дискретная математика и ее приложения» (г. Москва, 2007 г. и 2010 г.); Международная конференция «Проблемы автоматизации и управления в технических системах» (г. Пенза, 2008 г. и 2009 г.); VIII Международная научная конференция «Дискретные модели в теории управляющих систем» (г. Москва, 2009 г.); VII молодежная научная школа по дискретной математике и ее приложениям (г. Москва, 2009 г.); IV Всероссийская конференция «Проблемы оптимизации и экономические приложения» (г. Омск, 2009 г.); XVIII Международная школа-семинар «Синтез и сложность управляющих систем имени академика О. Б. Лупанова» (г. Пенза, 2009 г.); семинар «Математические вопросы кибернетики» под руководством профессора О. М. Касим-Заде (МГУ им. М. В. Ломоносова); семинар «Надежность управляющих систем» под руководством профессора Н. П. Редькина (МГУ им. М. В. Ломоносова).

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

Структура диссертации и объем. Диссертация состоит из введения, шести глав, приложения и списка литературы. Объем диссертации составляет 100 страниц, включая две таблицы и 11 рисунков. Список литературы содержит 44 источника.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении приводится обзор результатов, связанных с темой диссертации, постановка задачи, дается характеристика работы, вводятся вспомогательные понятия и обозначения, необходимые для формулировки результатов диссертационной работы, формулируются в общем виде полученные результаты.

Булевы функции /1 и /2 назовем конгруэнтными, если одна из них может быть получена из другой заменой переменных (без отождествления). Пусть X С В3. Введем обозначение: Сопдг(Х) - множество всех функций, зависящих от переменных х\, ж2, 13, каждая из которых конгруэнтна некоторой функции множества X. Например, Сопдг{1, XI, Х1&Х2} = {1, XI, х2, хз, х\кх2, х2кх3, ц&Жз}. Введем обозначения:

С! = € {ОД}, » е {1,2,3}}, Щ = 8;

(?2 = Сопдг{х['ха22 £ {0,1}, i € {1,2,3}}, |(?2| = 24;

<?з = Сопдг{х?х522 е {0,1}, г € {1,2,3}}, |(73| = 24;

С = и С2 и (?з, = 56;

Мг = Сопдг{хЧ1х? Ы х\1х^х\г\а € {0,1}, г 6 {1,2,3}}, ¡Л^ =24; М2 = Сопдг{х11х12х1'Ух11х12х13Ух^х?х13\а1 € {0,1}, г е {1,2,3}}, |М2| = 8;

М3 = Сопдг^х? V х?)\а{ £ {0,1}, { £ {1,2,3}}, |М3| = 12; М4 = Сош/гК1:^3 V г^а^стг € {0,1}, г' б {1,2,3}}, |М4] = 4; М* - множество всех функций, двойственных функциям множества М,-

4

соответственно, г = 1,2,3,4; М = ^(М.иМ*), |М| = 96, \ОиМ\ = 152;

¿=1

М5 = Сопдг{хх ф х2 © а, х1 ф х2 ® х3 ф Ь |а, Ь Е {0,1}}, \М5\ = 8; 0 = Сопдф^х^2, х^х^х^3, х^Ч*?®? {0,1},

г €{1,2,3}}, |6| = 32; 0* - множество всех функций, двойственных функциям множества 0;

Ф = 6 и Сопдг{хх{х°22 V ^3)|<т; 6 {0,1}, г £ {2,3}}, |Ф| = 44; Ф* - множество всех функций, двойственных функциям множества Ф, |Ф*| = 44; Ф = Я> иСопдг{хъхи0,1}, |Ф| = 96, очевидно, что

Ф = £3\((7иМиМ5);

Н = СоПдг{х1Х2, Х1Х2Х3, XIV Х2, Х1\/ Хз, Х1(Х2ХЗ\/ Х2Хз), Х]У (Х2Х3У

Чх2х3)}, \н\ = 14;

Г2 = Сопдг{х~\х2, Х\Х2, х\х2х31 а^жгхз, Х1Х2Х3}; П* - множество всех функций, двойственных функциям множества П;

П1 = П и Сопдф^хрх? V е {0,1}, г 6 {2,3}}; ЭД -

множество всех функций, двойственных функциям множества П^

К^п) - множество всех булевых функций, зависящих от переменных XI, Х2, • . . , Хп (п > 3) И ОТЛИЧНЫХ ОТ функций 0, 1, Х{, Х(, Х,|ху, Xi 4- ху, х,- ~ х^ -> х3-, х3-, х^ ф Ху, х,&х3, х; V х, (г,7 6 {1,2,..., гг}, гф })\

К2(п) - множество всех булевых функций /(х\, х2,..., хп) (тг > 3), не представимых в виде (х°&/г(х))(' или V где

/г(х) - произвольная функция, г,] £ {1,2,..., п}, а,Ь,с 6 {0,1}, \К2(п)| > 22" - 4(п22""1 + (гг2 - гг)22""'2);

Кз(п) - множество всех булевых функций ¡(х\, х2,.. ■, хп) (п > 3), не представимых в виде (х-*&/г(х))6 или ((х; ф х])а&к(х))ь, где /г(х) -произвольная функция, г ф € {1,2,..., тг}, а,Ь 6 {ОД}.

\К3(п)\ > 22" -22""'+1(п2 + п);

/^4(71) - множество всех булевых функций /(хь Х2,..., хп) (п > 3), не представимых в виде (ж"&;/г(х))'\ где Л(х) - произвольная функция, ¿€{1,2,..., п}, а, Ъ е {0,1}, \К4{п)\ > 22" - 4тг22"~";

К(п) = К2(п) П К3{п) П К4{п) (п > 3),

\К{п)\ > 22" - 2(п2 + п)22"~' - 4(п2 - п)22"_а;

ос

К{ = У^К^п), ¿ = 1,2,3,4;

Я" = П Яз П ¿М-

Мощности введенных множеств легко вычисляются непосредственным подсчетом.

Замечание. Нетрудно проверить, что —> 1 при п —оо. Следовательно, множество К содержит почти все булевы функции.

Доказано утверждение 3.

Утверждение 3. Пусть В - произвольный полный конечный. базис, функция /(х], хг,х„)(п > 1) отлична от х; (г = 1,2, ...,п). Тогда существуют такие целое число с 6 {1,2,3,4,5}

и схема Б, реализующая функцию /, что ~ ее при

е 0.

Первая глава диссертации содержит необходимые определения, обозначения и ряд вспомогательных утверждений, используемых в дальнейшем для получения верхних и нижних оценок ненадежности схем. Отметим наиболее важные из них. В теореме 1.2 явно найдены константы ¿,£о для результата С. И. Аксенова16 и доказано, что в произвольном полном конечном базисе любую булеву функцию / можно реализовать схемой, ненадежность которой Р(5) < 5е + 182е2 < 5,2е при всех е е (0,1/960]. Результат теоремы 1.2 используется при доказательстве верхних и нижних оценок ненадежности схем. Леммы 1.4-1.13 и теорема 1.6 содержат утверждения, позволяющие развивать определенную технику вычислений вероятностей ошибок на выходе схем.

Во второй главе описываются полные базисы, в которых для почти всех функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной е при е 0. В разделе 2.1 получены верхние оценки ненадежности схем и доказано (теоремы 2.1, 2.2 и 2.3), что если полный конечный базис В содержит функцию ¡р Е С, то любую функцию / в этом базисе В можно реализовать схемой А с ненадежностью Р(А) < е + 200с2 при всех е 6 (0,1/960]. В разделе 2.2 получены нижние оценки ненадежности схем. Из теоремы 2.4 следует, что если произвольная схема 5 содержит хотя бы один функциональный элемент, то она функционирует с ненадежностью Р(5) > е при всех е 6 (0,1/2). В теореме 2.6 доказано, что в базисе В С ДД<? при любом п > 3 любая схема, реализующая функцию /(х) е /<*2(и)| функционируете ненадежностью Р(5) > 2е — 2е2 при всех ее (0,1/4].

Таким образом, в полном базисе В С для почти всех функций асимптотически оптимальные по надежности схемы имеют ненадежность, асимптотически равную с (е —> 0), тогда и только тогда, когда В П (? ф 0.

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

"■Аксенов С. И. О надежности схем над произвольной полной системой функций при инверсных неисправностях па выходах элементов // Известия высших учебных заведений. Поволжский регион. — 2005. - № 6 (21). С. 42 55. (Естественные науки).

ненадежности схем. В теореме 3.1 доказано, что если полный базис В содержит некоторую функцию множества М, то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р{А) < 2е + 144s2 при всех е 6 (0,1/960]. В теореме 3.3 доказано, что если полный базис В содержит линейную функцию, существенно зависящую от двух и более переменных, то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р(А) < 2е + 200е2 при всех е 6 (0,1/960]. В теореме 3.4 доказано, что если полный базис В содержит функцию 1р(х1,х2,хз), конгруэнтную xi(x¡3 V х^3) (сг2,<73 € {0,1}), ВПФ* ф 0, то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р(А) < 2е + 204е2 при всех е Е (0,1/960]. В теореме 3.5 доказано, что в базисах, двойственных базисам, удовлетворяющим условиям теоремы 3.4, любую функцию / можно реализовать схемой А с ненадежностью Р(А) < 2е + 204е2 при всех с б (0,1/960]. В разделе 3.2 получены нижние оценки ненадежности схем. В теореме 3.6 доказано, что в полном базисе ßCOUÖ'U Сопдг{х ь0,1}, или В С Ф U Congr{xh0,1}, или В С Ф* U Сопдг{хг, 0,1} при любом п > 3 любая схема, реализующая функцию /(í) G Кз(п), функционирует с ненадежностью P(S) > Зе(1 — е)3 при всех е € (0,1/960].

Таким образом, в полном базисе В С B¡\G для почти всех функций асимптотически оптимальные по надежности схемы имеют ненадежность, асимптотически равную 2е (е —> 0), тогда и только тогда, когда выполнено одно из условий: или В П М Ф 0; или В С (Фи М5) и В П Мъ ф 0; или В содержит функцию (/¡(¡Ei, 2:2,2)3), конгруэнтную x^x^Vx^3), и ВГ\Ф* ф 0; или В содержит функцию 2:2,2)3), конгруэнтную xj V х^х^3, и В П Ф ф 0.

В четвертой главе описываются базисы, в которых асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной Зе при е —\ 0. В разделе 4.1 получены верхние оценки ненадежности схем. Из теоремы 4.2 следует, что если полный базис В содержит некоторую функцию из множества Н, то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р(А) < Зе + 126е2 при всех е € (0,1/600]. В теореме 4.3 доказано, что если полный базис В содержит функции ipi £ В и <р2 € 0*, то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р{А) < Зе + 225е2 при всех е 6 (0,1/960].

В теореме 4.4 доказано, что если полный базис В удовлетворяет хотя бы одному из следующих условий-.

1) В содержит функцию, конгруэнтную функции = хДаг^2 V Ж33) (стг, аз £ {0,1}), и хотя бы одну из функций 1, Жь

2) В содержит константу 1 и функцию, конгруэнтную функции V = 21(2:2 Фх3Ш 03) (<т3 6 {0,1});

3) В содержит функцию, конгруэнтную функции <р = х\(х2 © £3), и хотя бы одну из функций 1, Х\,

то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р(А) < Зе + 293е2 при всех е £ (0,1/960]. В теореме 4.5 доказано, что в базисах, содержащих функции, двойственные функциям из условий 1-3 теоремы 4.4, любую функцию / можно реализовать схемой А с ненадежностью Р(А) < Зе + 293е2 при всех е е (0,1/960].

В разделе 4.2 получены нижние оценки ненадежности схем. В теореме 4.6 доказано, что в полном базисе В С П и Сопдг{х\, 0,1}, или В С Г2* и Сопдг{х1, 0,1}, или В С Ах и Сопдг{хх, 0}, или В С и Сопдг{х1,1} при любом п > 3 любая схема, реализующая функцию /(х) £ Кз(п), функционирует с ненадежностью Р(Б) > 4е(1 — е)3 при всех £ е (0,1/960].

Таким образом, в полном базисе В С В3 для почти всех функций асимптотически оптимальные по надежности схемы имеют ненадежность, асимптотически равную Зе (е —> 0), тогда и только тогда, когда В удовлетворяет условиям одной из теорем 4.2, 4.3, 4.4 или 4.5 (двойственный вариант теоремы 4.4).

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

1) В содержит функцию, конгруэнтную функции = 2:12:22:3, и хотя бы одну из функций £1, 1;

2) В содержит функцию, конгруэнтную функции (р\ — щУ Х2 V 2:3, и хотя бы одну из функций XI, 0;

3) В содержит функцию Х\ И ХОТЯ бы одну из функций <Р2 = Х\{Х2®Хъ@0ъ) или <р3 = Х1Х2Х3, где СГ3 е {0,1};

4) В содержит функцию х\ и хотя бы одну из функций <Р2 = 2:1 V (х2 ®1з® сг3) или (р3 = х\ V х2 V 2:3, где сг3 € {0,1},

то любую функцию / в базисе В можно реализовать схемой А с ненадежностью Р(А) < 4е + 250е2 при всех е € (0,1/960]. В разделе 5.2 получены нижние оценки ненадежности схем. В теоремах 5.2-5.5 доказано, что в полном базисе В С Сопдг{х\к.Х2, г^&хг&^з, ¿1. 0,1}, или В С Соггдг^&яг. г^&а^&жз, Й1&а:2, ¿1&Х2&Х3, 0,1}, или В С Сопдг{хх\/ Х2, х\У Х2У х^, х\, 0,1}, или В С Сопдг{х\\/Х2, х^У х^, VХ2, Vжз, 0,1} при любом

п > 3 любая схема, реализующая функцию /(ж) € /С4(п), функционирует с ненадежностью Р(Б) > 5е(1 - е)А при всех е £ (0,1/960].

Таким образом, в полном базисе В С В3 для почти всех функций асимптотически оптимальные по надежности схемы имеют ненадежность, асимптотически равную 4е (е —► 0), тогда и только тогда, когда В удовлетворяет условиям теорем 5.1 и 4.6.

Из теорем 1.2 и 5.2-5.5 следует, что в полном базисе В С В$ для почти всех функций асимптотически оптимальные по надежности схемы имеют ненадежность, асимптотически равную 5е (е 0), тогда и только тогда, когда В С Сопзг{з;1&;ж2, а^&жг&а^, х\, 0,1), или В С Сопдг{х\&сх2, а^&з^&^з, ¿1&2:2, 51&а:2&2:з, 0,1}, или В С Соп£г{а:1 V 2:2, 2:1 V 2:2 V г3, ¿1, 0,1}, или В С Соп5г{а;1 V £2. 2:1 V 2:2 V 2:3, Ж1 V 2:2, V 2:2 V хз, 0,1}.

В шестой главе рассматривается сложность асимптотически оптимальных по надежности схем. Схемы, построенные при доказательстве теоремы 6.1, для почти всех функций являются асимптотически оптимальными по надежности, а их сложность отличается от сложности минимальных схем, построенных из абсолютно надежных элементов, в 3(1 + 6) раз, где Ъ - любое сколь угодно малое положительное число.

Выводы. Основные результаты работы в самом общем виде можно сформулировать в виде теорем 1, 2.

Теорема 1. Для любого полного базиса В С можно указать такое натуральное с € {1,2,3,4,5}, что для любой булевой функции / существует схема S, реализующая /, для которой

P(S) <С£ + d\£2,

и для любой булевой функции f £ К

Ре(Л >С£- d2s2

при всехе б (0; 1/960], где di и d2 - некоторые (абсолютные) положительные константы.

Теорема 2. Для любого полного базиса В С В3, любого действительного числа b > 0 существует такая константа £о 6 (0; 1/2), что при любом п > 3 любую булеву функцию /(гь х2, ■■•, хп) 6 К(п) можно реализовать схемой Sj, для которой P(S}) - РЕ(/) < d3e2 при всех е е (0,е0], L(Sf) < 3(1 + Ъ)р2п/п при п —> оо, где d3 - некоторая (абсолютная) положительная константа.

Из теоремы 1 следует, что в рассматриваемом базисе В можно указать такое натуральное с € {1, 2,3,4, 5}, что для любой функции / 6 К можно построить асимптотически оптимальную по надежности схему А, реализующую /, для которой Р(А) ~ се при е 0.

Из теоремы 2 следует, что для почти всех булевых функций / можно строить асимптотически оптимальные по надежности схемы, сложность которых асимптотически не больше чем в 3(1 + Ь) раз превышает сложность минимальных схем, построенных из абсолютно надежных элементов, где Ь -любое сколь угодно малое положительное число.

Для всех базисов В С В3 константы с, d\, d2 найдены явно и представлены в таблицах 1 и 2.

Таблица 1

В с ¿1

В П ф 0 1 8

в п <з2 ф 0 1 200

в С\вгф0 1 8

Вп М ф 0 2 144

В содержит линейную функцию, существенно зависящую от 2 или более переменных 2 200

В содержит функцию 1р(хх,х2,хз), конгруэнтную х^х1^ V Ж33), и В П Ф* ф 0 2 204

В содержит функцию <р*(х\, Х2, Ж3), конгруэнтную Х1 V Ж^Ж^3, и ВПФ ^ 0 2 204

ВпЯ ф 0 3 126

Б удовлетворяет хотя бы одному из следующих условий: 1) В содержит функцию, конгруэнтную функции </з = ж^ж^2 V Жд3) (°"2,сз 6 {0,1}), и хотя бы одну из функций 1, х\, 2) В содержит константу 1 и функцию, конгруэнтную функции = х\(х1 ® ж3 ф сг3)(сг3 € {0,1}); 3) В содержит функцию, конгруэнтную функции Ц> = Х1(Х2 ф Хз), и хотя бы одну из функций 1, XI 3 293

В удовлетворяет хотя бы одному из следующих условий: 1) В содержит функцию, конгруэнтную функции <р = XI V Ж^Жд3 (<Т2, оз £ {0,1}), и хотя бы одну из функций 0, ху, 2) В содержит константу 0 и функцию, конгруэнтную функции <р — XI V (ж2 © ж3 ® стз)(сг3 е {0,1}); 3) В содержит функцию, конгруэнтную функции (р = X1 V (Ж2 ф Жз ф 1), и хотя бы одну из функций 0, XI 3 293

В содержит функцию, конгруэнтную функции (р\ = Х\Х2Хз, и хотя бы одну ИЗ функций XI, 1 4 250

В содержит функцию, конгруэнтную функции <р\ = х,\ V жг V жз, и ХОТЯ бы одну ИЗ функций &1, 0 4 250

В содержит функцию х\ и хотя бы одну из функций, конгруэнтных функции <р2 = Х[(х2 ©Жз ф<т3) или ¡Рз = Х\Х2ХЗ, где сг3 6 {0,1} 4 250

В содержит функцию х\ и хотя бы одну из функций, конгруэнтных функции <¿>2 = х\'4{х2®хз®аз) или <рз = Х1\/Х2^хз, где сгз 6 {0,1} 4 250

В С Сопдг{Ж1&Ж2, Ж1&Ж2&Ж3, жь 0,1} 5 182

В С Сопдг{ж1&Ж2, Ж1&Ж2&Ж3, Ж1&Ж2, ЖХ&Ж2&Ж3, 0, 1} 5 182

В С Сопдг{Ж! V Ж2, Ж1 V ж2 V жз, жь 0,1} 5 182

В С Сопдг{ж1 V х% Ж1 V Х2 V ж3, V жг, Жх V жг V 0,1} 5 182

Таблица 2

В с ¿2 К(п)

в = в3 1 0 -

в с В3\С 2 2 К2(п)

в С (6 и е* и Сопдг{хь 0,1}), или В С (Ф и и Сопдг{хъ 0,1}), или В С (Ф* и Сопдг{хь 0,1}) 3 9 Кз(п)

вс(йи Сопдг{х 1,0,1}), или В С (О* и Сопдг{хь 0,1}), или вс(^и Сопдг{хи0}), или В С (А^ и Сопдг{хь 1}) 4 12 Кз(п)

В С Сопдг{х1&х2,х1&:х2кхз,х1&х2,х1&:х2кх3,0,1} или В С Сопдг{х 1&Я2, х\к,х2кх%, х\, 0,1} 5 20 Мп)

В С Сопдг{х1 V х2, х\ V х2 V х3, х\ V х2, х\ V V хз, 0,1} или В С Сопдг{х\ V х2, х\У х2\/ хъ 0,1} 5 20 К4п)

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Работы [1-7] опубликованы в журналах, рекомендованных ВАК для публикации результатов диссертаций.

1. Васин, А. В. Об асимптотически оптимальных схемах в базисе {хку, х V у, х] при инверсных неисправностях на выходах элементов / А. В. Васин // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2008. - № 4. - С. 3-17.

2. Алехина, М. А. О надежности схем в базисах, содержащих функции не более чем трех переменных / М. А. Алехина, А. В. Васин // Ученые записки Казанского государственного университета. - Казань : Изд-во Казанского университета, 2009. - Т. 151. - Кн. 2. - С. 25-36. - (Физико-математические науки).

3. Васин, А. В. Об асимптотически оптимальных схемах в базисе {х1\х2,х\ ^ Х2,Х1&Х2,х\ V Х2,Х\\ / А. В. Васин // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2009. - № 1 (9). - С. 3-10.

4. Алехина, М. А. Синтез асимптотически оптимальных схем / М. А. Алехина, А. В. Васин // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2009. - № 2 (10). - С. 48-62.

5. Васин, А. В. 06 асимптотически оптимальных схемах в базисе {xi&zx2,xi} при инверсных неисправностях на выходах элементов / А. В. Васин // Дискретный анализ и исследование операций. - 2009. -Т. 16. - № б. - С. 12-22.

6. Алехина, М. А. Достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадежностью 2е / М. А. Алехина, А. В. Васин // Известия высших учебных заведений. Математика. - 2010. - № 5. - С. 79-82.

7. Васин, А. В. О базисах, в которых асимптотически оптимальные схемы функционируют с ненадежностью 5е / А. В. Васин // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2010. - № 1 (13). - С. 64-79.

8. Васин, А. В. О функциях, используемых для повышения надежности схем / А. В. Васин // Дискретная математика и ее приложения : материалы IX Международного семинара, посвященного 75-летию со дня рождения академика О. Б. Лупанова (г. Москва, 18-23 июня 2007 г.). -М. : Изд-во мех.-мат. фак. МГУ, 2007. - С. 71-73.

9. Васин, А. В. Об уточнении оценки ненадежности схем из ненадежных функциональных элементов / А. В. Васин // Проблемы автоматизации и управления в технических системах : труды Международной конференции (г. Пенза, 22-24 апреля 2008 г.). - Пенза : ИИЦ ПГУ, 2008. -С. 269-271.

10. Васин, А. В. О функциях специального вида / А. В. Васин // Дискретные модели в теории управляющих систем : труды VIII Международной конференции (Лесной городок Моск. обл., 6-9 апреля 2009 г.). - М. : Издательский отдел ф-та ВМиК МГУ им. М. В. Ломоносова ; МАКС Пресс, 2009. - С. 43-46.

И. Васин, А. В. Об асимптотически оптимальных схемах в базисе из всех двухвходовых элементов / А. В. Васин // Проблемы оптимизации и экономические приложения : материалы IV Всероссийской конференции (г Омск, 29 июня - 4 июля, 2009 г.) / Омский филиал Института математики СО РАН. - Омск : Полиграфический центр КАН, 2009. - С. 118.

12. Васин, А. В. Нижние оценки ненадежности асимптотически оптимальных схем в базисе {xi&cx2,x\} при инверсных неисправностях на выходах элементов / А. В. Васин // Синтез и сложность управляющих систем : материалы XVIII Международной школы-семинара (г. Пенза, 28 сентября - 2 октября 2009 г.). - М. : Изд-во мех.-мат. ф-та МГУ, 2009. - С. 18-20.

13. Васин, А. В. Об асимптотически оптимальных схемах в частных базисах, содержащих линейные функции двух или трех переменных / А. В. Васин // Проблемы автоматизации и управления в технических системах : труды Международной научно-технической конференции (г. Пенза, 20-23 октября 2009 г.). - Пенза : Изд-во ПГУ, 2009. - С. 48-50.

14. Васин, А. В. Об асимптотически оптимальных схемах в базисе {х\&.х2,х\ V Х2,х\) при инверсных неисправностях на выходах элементов / А. В. Васин // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (г. Москва, 18 - 23 мая 2009 г.). -М. : Изд-во мех.-мат. фак-та МГУ им. М. В. Ломоносова, 2009. ~ Ч. 1. -С. 15-19.

15. Васин, А. В. О базисах, в которых асимптотически оптимальные схемы имеют ненадежность 2е / А. В. Васин // Дискретная математика и ее приложения : материалы X Международного семинара (г. Москва, 1-6 февраля 2010 г.). - М. : Изд-во мех.-мат. фак. МГУ, 2010.- С. 94-97.

16. Алехина, М. А. Сложность асимптотически оптимальных схем в базисах, содержащих булевы функции, существенно зависящие не более чем от трех переменных / М. А. Алехина, А. В. Васин // Надежность и качество : труды Международного симпозиума (г. Пенза, 24-31 мая 2010 г.). - Пенза : ИИЦ ПГУ, 2010. - Т. 1. - С. 239-241.

17. Васин, А. В. О надежности схем в полных конечных базисах, содержащих линейную функцию / А. В. Васин // Надежность и качество : труды Международного симпозиума (г. Пенза, 24-31 мая 2010 г.). -Пенза : ИИЦ ПГУ, 2010. - Т. 1. - С. 241-242.

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

Васин Алексей Валерьевич

АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫЕ ПО НАДЕЖНОСТИ СХЕМЫ В ПОЛНЫХ БАЗИСАХ ИЗ ТРЕХВХОДОВЫХ ЭЛЕМЕНТОВ

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

Редактор Е. В. Денисова Компьютерная верстка А. В. Васина

Подписано в печать 07.10.2010. Формат 60 х 84 Усл. печ. л. 1,40. Заказ № 001913. Тираж 100._

Издательство ПГУ Пенза, Красная, 40, т.: 56-47-33

Введение

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

Глава 2. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью £

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

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

2.3 Выводы.

Глава 3. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью 2 е

3.1 Верхние оценки ненадежности схем

3.2 Нижние оценки ненадежности схем

3.3 Выводы.

Глава 4. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью Зе

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

4.2 Нижние оценки ненадежности схем

4.3 Выводы.

Глава 5. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью 4е или 5е

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

5.2 Нижние оценки ненадежности схем

5.3 Выводы.

Глава 6. Сложность схем

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

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

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

Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [1]. Он предполагал, что элементы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией ср в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью е (е Е (0; 1/2)), реализует функцию (р. С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит С\£ при любом е Е (0; 1/6] {с\ - некоторая абсолютная константа). Однако сложность такой схемы с ростом числа итераций увеличивается экспоненциально (примерно, в Зк раз, где к - число итераций).

Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах P.JI. Добрушина, С.И. Ортюкова, Д. Улига [2-7] и некоторых других авторов, причем главное внимание уделялось сложности схем (задача синтеза схем наилучших по надежности не ставилась). Введем необходимые понятия, чтобы сформулировать результаты названных авторов.

Определение. Полное (в Рг) множество В = {ei,e2, .,em} называется полным базисом в B¿

Определение. Полный базис В называется неприводимым полным базисом (в Р2), если никакое его собственное подмножество полным не является.

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе В = {ei, в2,., em}, т Е N [8]. (Множество всех функциональных элементов Е{, функции которых e¿ принадлежат базису В, будем также называть базисом В [9].) Каждому элементу базиса Е( приписано положительное число v(Ei) - вес данного элемента. Сложность L(S) схемы S определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимо друг от друга с вероятностью £ переходят в неисправные состояния. Ненадежность схемы определяется как максимальная вероятность ошибки на выходе схемы при всевозможных входных наборах. Вводится функция Шеннона Lp¿(n) = maxminL(S), характери s зующая сложность схем, реализующих функции от п переменных в базисе В, где минимум берется-по всем схемам S из ненадежных элементов, реализующим функцию f(xi,X2, с ненадежностью P(S) ^ р, а максимум

- по всем булевым функциям / от п переменных.

Пусть р = min(v(Ei)/(n(Ei) — 1)), где минимум берется по всем эле

Ei ментам Е{ базиса, для которых n(i?¿) > 1, п(Е{) - число существенных переменных функции e¿, реализуемой элементом Д-, a v{Ei) - вес функционального элемента Е^, г = 1,., га.

Пусть Pj?(üj(S,á) - вероятность появления значения /(а) на выходе схемы S при входном наборе а. Ненадежность P(S) схемы S, реализующей булеву функцию /(£), равна P(S) = таxPj^(S,a): где максимум берется по всем возможным входным наборам а. Надежность схемы S равна l-P(S).

О.Б. Лупанов [10] показал, что для схем, реализующих булевы функции от п переменных и состоящих из абсолютно надежных элементов (т. е. при е = 0 и р = 0), выполняется соотношение Lo,о ~ Р • 2п/п.

С. И. Ортюков [6] для инверсных неисправностей на выходах элементов получил следующий результат: пусть 0 < е < £q, р > q(£)Lg, где Lg

- минимальное число надежных элементов, необходимое для реализации функции голосования д(х 1,^2,^3) = Х1Х2 V xix% V Х2Х3 в рассматриваемом базисе, q(e) - некоторая функция такая, что = £ + Зе2 + о(е2) при £ —у 0. Тогда существует такая функция р(е) —> р при е —ь 0, что

LP,e(n) < Р(е) • 2"/п. i

Д. Улиг [7] для инверсных неисправностей на выходах элементов, с вероятностью ошибки £ доказал, что для любых, сколь угодно малых чисел Ъ и h (b, h > 0) существует число e'ie' е (0,1/2)) такое, что при любом £ £ (0, б7], и любом р, удовлетворяющем условию (1 4- h)eLg ^ р ^ 1/2 (точнее q(£)Lg ^ р ^ 1/2), справедливо соотношение LPj£(n) < (1 + b)p • 271/п.

Таким образом, в результатах С.И. Ортюкова и Д. Улига асимптотика функции Шеннона сохраняется с точностью до множителя, сколь угодно близкого к единице (при этом вероятность сбоя £ ограничена константой), т.е. найденные ими методы синтеза позволяют строить асимптотически оптимальные по сложности схемы, функционирующие с некоторым уровнем надежности.

Далее будем считать веса всех элементов равными единице. Тогда сложность 1/(5') схемы 5 равна числу функциональных элементов в ней.

Из результатов Н. Пиппенджера [11] следует, что в базисе {Ж1&Ж2, V Х2, х\} при инверсных неисправностях на выходах элементов любую булеву функцию от п переменных можно реализовать такой схемой 5, что Р(5) ^ 18е при всех 5 6 (0,1/200], Щ) < 170 • 271/п.

С.В. Яблонский [12] рассматривал задачу синтеза надежных схем в базисе В = {жх&а^ х\ V Х2, хг, Х2, Он предполагал, что элемент, реализующий функцию голосования д{х 1,^2,^3) = V х\х$ V жг^з абсолютно надежный, а конъюнктор, дизъюнктор и инвертор - ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше е. Им доказано, что для любого р > 0 существует алгоритм, который для каждой булевой функции /(#1, Х2,. ■ ■, хп) для любого п строит такую схему 5, что Р(3) ^ р, < 21г~1/п.

В.В. Тарасов [13] рассматривал задачу построения схем сколь угодно высокой надежности (когда Р(5) —> 0). Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом В.В. Тарасов нашел необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных им результатов следует невозможность построения сколь угодно надежных схем для функций, отличных от переменных, при инверсных неисправностях выходах элементов.

М.А. Алехина [17] решала задачу построения асимптотически оптимальных (асимптотически наилучших) по надежности схем при однотипных константных неисправностях только на входах или только на выходах элементов. Чтобы сформулировать полученные М.А. Алехиной результаты, введем необходимые определения.

Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью е £ (0; 1/2), реализует константу 0, то она называется неисправностью типа 0 на выходе элемента. Неисправности типа 1 на выходах элементов определяются аналогично.

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

Пусть P£(f) = inf P(S), где инфимум берется по всем схемам S из s ненадежных элементов, реализующим функцию f(x\, Х2, ■., хп). Схема А из ненадежных элементов, реализующая функцию /, называется асимптотически наилучшей (асимптотически оптимальной) по надежности, если

Р (f)

Р(А) ~ P£(f) при £ 0, т. е. Hm-^ = 1.

Обозначим В2 - множество всех булевых функций, зависящих от двух переменных х\, Х2, а В3 - множество всех булевых функций, зависящих от трех переменных xi, £2,

М.А. Алехиной [17] доказано, что во всех неприводимых полных базисах В С jb2 (исключая три случая) почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами S, функционирующими с ненадежностью, асимптотически равной P(S) ~ аеь при е —> 0, константы а и t зависят от базиса и типа неисправностей, a Е {1,2,3}, t Е {1,2}. Для почти всех функций сложность таких схем в случаях константных неисправностей только на выходах или только на входах элементов удовлетворяет соотношению L(S) < кв • 2п/п, причем мультипликативная константа кв зависит только от базиса I?, 40 ^ кв ^ 168.

Если неисправность элемента такова, что поступающее на вход значение a (a Е {0,1}) с вероятностью е Е (0; 1/2) может превратиться в ¿т, то она называется инверсной неисправностью на входе элемента.

В.В. Чугуновой [19] доказано, что во всех неприводимых полных базисах В С B<i при инверсных неисправностях на входах почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами S, функционирующими с ненадежностью, асимптотически равной P(S) ~ а£ при £ —^ 0, константа а зависит от базиса, а Е {2,3,4}. Для почти всех функций сложность предлагаемых схем удовлетворяет соотношению L(S) < кв • 2п/п, причем мультипликативная константа кв также зависит только от базиса В, 168 ^ к в ^ 504.

С.И. Аксеновым [14] получена верхняя оценка ненадежности схем в произвольном полном конечном базисе В при инверсных неисправностях на выходах элементов. Он доказал, что существуют такие положительные константы £о и d, зависящие от базиса В, что любую булеву функцию можно реализовать схемой S, ненадежность которой

P{S) < 5е + de2 (1) при любом е £ (0;£оЗ

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

В [15] С.И. Аксенов получил следующий результат: пусть

Ti = {ж, 0, 1} U {xi&,X2i Ж1&Ж2&Ж3, •••},

Т2 = {0, 1} U {XI$¿X2, Ж1&Ж2&Ж3, ., Xi&¿X2&¿.&¿Xk, .}U

U {Ж1&Ж2, Ж1&Ж2&Ж3,xi&¿x2&¿.&:xk,.}, и Т3 = Т|, Т4 = Т2 (Т3 и Т4 - множества функций, двойственных функциям множеств Ti и Т2 соответственно). Если полный в Р2 базис В не является подмножеством ни одного из множеств T¿, i = 1,2,3,4, то существуют такие положительные константы ео и с/, что в базисе В любую булеву функцию / можно реализовать схемой S с ненадежностью P(S) ^ 4е + d£2 при всех £ 6 (0; £Го].

Пусть булева функция m(xi, Х2,., хь) зависит от к {к > 3) переменных и обладает свойством: найдется такой набор (61, 62,что на нем и всех соседних с ним наборах функция т принимает значение 0, а на наборе (&i, 62,., и всех соседних с ним наборах - значение 1. Пусть G. - множество всех булевых функций с названным свойством. Обозначим Nb(G) - наименьшее число надежных элементов, необходимое для реализации какой-либо функции из множества G в базисе В.

В [16] М.А. Алехиной и С.И. Аксеновым доказано, что в произвольном полном конечном базисе В для любого Ъ > 0 существуют константы £о € (ОД/2)) и d > 0 такие, что при любом п любую булеву функцию

Х2,можно реализовать схемой S, для которой при любых £ Е (0, е0] верно P(S) < sNB(G) + de2, L(S) <3(1 + Ъ)р- 2n/n при n —CO.

В работе [22] M.A. Алехина и A.B. Шилов рассматривали реализацию булевых функций схемами из ненадежных функциональных элементах во всех полных конечных неприводимых базисах, содержащих функции двух переменных, и получили верхние оценки ненадежности схем.

Вопрос о возможности построения асимптотически наилучших по надежности схем при инверсных неисправностях на выходах элементов в базисах, не содержащих медиану [1], а также отличных от {х\\х2\ и {х\ 4, Х2} [18], оставался открытым.

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

Известно (см., например, [23]), что при инверсных неисправностях на выходах элементов в любом полном базисе любая схема S, реализующая любую булеву функцию f(xi,x2,.,жп) (тг ^ 1), отличную от Х{ (i = 1, 2, .,n), имеет ненадежность

P(S) > (2)

Пусть S - любая схема в произвольном полном базисе, и пусть S содержит N > 1 элементов. Тогда, применяя формулу полной вероятности, ненадежность P(S) схемы S при всех е £ (0,1/2) можно представить полиномом n

3) г=1 с целыми коэффициентами £ {1, 2,., iV}, a G {0,1,., щг^т}, i = 2,3, .,N.

Таким образом, верно утверждение 1.

Утверждение 1. Для любой схемы S, содержащей N ^ 1 элементов; найдется такое целое число с\ 6 {1, 2,N}, что P(S) ~ с\б при е —> 0.

Учитывая результаты (1), (2) получаем утверждение 2

Утверждение 2. Пусть В - произвольный полный конечный базис. Существуют такие константы во £ (ОД/2) и й > 0, что любую булеву функцию /(х1,х2,.,хп) (п ^ 1), отличную от а^ (г = 1,2, .,п), моэю-но реализовать схемой 5, ненадежность Р(5) которой удовлетворяет соотношению: е ^ ^ 5е + ¿е2 при любом е 6 (0,£о].

Из утверждений 1 и 2 следует утверждение 3.

Утверждение 3. Пусть В - произвольный полный конечный базис, функция ${х1,Х2->.--,х.п) (п ^ 1), отлична от Х{ (г = 1,2,.,п). Тогда существуют целое число с Е {1, 2,3,4,5} и схема Б, реализуются функцию такие, что Р(5) ~ се при е —> 0.

Из утверждения 3 следует, что число с и схема 5, функционирующая с ненадежностью Р(<5") ~ се при е 0, зависят от заданного базиса и конкретной булевой функции.

Пусть полный конечный базис задан, а каждая булева функция реализованы асимптотически оптимальной по надежности схемой 5, функционирующей с ненадежностью Р(5) ~ с/£ (с/ 6 {1,2,3,4,5}) при £—*■().

Обозначим с = тахс/, а К - множество булевых функций / таких, что /£Р2 с/ = с. Возникают следующие вопросы:

1) для каких функций / число с/ будет наибольшим?

2) Как много функций содержится в классе К?

3) Какие свойства базиса определяют число с?

Ответы на эти вопросы можно получить, решив следующую задачу.

Задача. Для каждого значения 1, 2, 3, 4, и 5 константы с описать все полные конечные базисы В, в которых любую функцию / £ К можно реализовать асимптотически оптимальной по надежности схемой функционирующей с ненадежностью ~ се при е —> 0.

В диссертации эта задача решена во всех полных базисах В С В% при условии, что элементы подвержены инверсным неисправностям на выходах. Уделено внимание сложности таких схем.

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

Пусть I С В3. Обозначим Сопдг(Х) - множество всех функций, зависящих от переменных хч, жз, каждая из которых конгруэнтна некоторой функции множества X.

Например: Сопдг{1, Хг, х1&х2} = {1, Х2, £3, Х1&Х2, Ж2&Ж3, Ж1&Ж3}. Введем следующие множества.

1. Ог = {х?х? V х?х°3 V 4243|(тг- Е {0,1}, г Е {1, 2, 3}}, \Сг\ = 8;

2. 'С?2 = СолргК^? Е {0,1}, * Е {1,2,3}}, |<32| = 24;

3. а3 = Сопдф^х? Чх?х13\а{ Е {0,1}, г Е {1,2,3}}, |С?3| = 24;

4. С? = и 02 и С3, |<?| = 56;

5. М1 = С<тдг{х11ха22 V ^о^з'К Е {0,1}, г Е {1, 2, 3}}, \Мг\ = 24;

6. М2 = V х?х?х13 V 41Е {0,1}, г Е {1, 2, 3}}, \М2\ = 8;

7. М3 = Сопрг{ж1(42 Е {0,1}, г Е {1,2,3}}, |М3| = 12;

8. М4 = СопдгК1^2^3 V Е {0,1}, г Е {1, 2, 3}}, |М4| = 4;

9. М* - множество функций, двойственных соответственно функциям множества Мг-, I = 1,2, 3,4; 4

10. М = и (Мг и м;), |М| = 96, и М\ = 152; г=1

И. М5 = Сопдг{х 1 фж2фа, £1 ФЖ2ФЖ3Ф6 |а, Ь Е {0,1}}, |М5| = 8;

12.© = С<тдг{х11х1\ х\1ха2гх1\ х{1 {ха22V ж|2жз3)1^ е {0,1>, i Е {1,2,3}}, |0| = 32;

13. 0* - множество функций, двойственных функциям множества 0;

14. Ф = © и Сопдг{х\{х^ V Жз3)|<тг- Е {0,1}, ¿Е{2,3}}, |Ф| = 44;

15. Ф* - множество функций, двойственных функциям множества Ф, |Ф*| = 44;

16. Ф = Ф и Ф* и Сопдг{хъ хъ 0,1}, |Ф| = 96, очевидно, что Ф = В3\(С? и МиМ5);

17. Н = Сопдг{х1Х2, Х1Х2Х3, х\ V ж2, х\ V х2 V ж3,х!(х2х^ V х2хз), х\ V (х2х^ V .т2хз)}, \Н\ = 14; .

18. Г2 = Сопдг{х\Х2, Ж1£2, Х1Х2Х3}',

19. - множество функций, двойственных функциям множества О;

20. Пг = П и Сопдфг^хЧ3 V х%3х%3)\а{ Е {0,1}, г Е {2,3}};

21. - множество функций, двойственных функциям множества Г^;

22. Ki(n) - множество всех булевых функций, зависящих от переменных

Xi,X2, . . . ,Хп (n ^ 3) И ОТЛИЧНЫХ ОТ фуНКЦИЙ 0, 1, Xi, Xi, X{\Xj, Х{ 4- Xj, 00-i ^^ 00 j j 001 У 00 j j 00i 00j j ОС£ CD 00j j OOj^&ZtOOj j 00£ V 00j у J — X 2 2 j . 2 ^ J ) 7

23. K2(n) - множество всех булевых функций /(ж 1,Ж2,. •., жп) (гг ^ 3), не представимых в виде (xf&ih(x))b или (xfSzxb V xfSzxbSzh(x))c, где h(x) -произвольная функция, i:j Е {1,2,. ,72}, а, 6, с Е {0,1}, ¡7^2(^)1 ^ 22" — 4 • (n22"1 + (п2 - п) • 2ЗП-2);

24. Кз(п) - множество всех булевых функций f(x 1,^2,., хп) (п ^ 3), не представимых в виде (xfSzh(x))b или ((х?- © xj)a • h(x))b, где h(x) - произвольная функция, г ф £ {1,2, .,п}, а, Ъ Е {0,1}, \Кз(п)\ ^ 22«22«-Ч1.(п2 + п);

25. К4.(11) - множество всех булевых функций /(Х\,Х2,. ,хп) (n ^ 3), не представимых в виде (xf&ch(x))b, где h(x) - произвольная функция, г Е {1,2,., п}, а, Ь Е {0,1}, \КА(п)\ 2 22" - 4п • 22П"; оо

26. Ki= \jKt{n),i = 2,3,4;

27. /Г = ДГ3 П К4]

28. К(ть) = К2(п) П К3(п) П К4(п) (n ^ 3), |X(n)| ^ 22" - 2(n2 + п) • 22"-1 -4(п2 — п) • 22"-2.

Мощности введенных множеств легко вычисляются непосредственным подсчетом.

Замечание. Нетрудно проверить, что при любом п ^ 3 мощность множества К(п) удовлетворяет неравенству

К(п)\ > 22" - 2(п2 + п) • 22"-1 - 4(п2 - п) • 22"'2.

Поэтому 1 ПРИ п оо. Следовательно, множество К содержит почти все булевы функции.

Основные результаты работы в самом общем виде можно сформулировать в виде теорем 1,2.

Теорема 1. Для любого полного базиса 5 С 53 можно указать натуральное с Е {1,2, 3,4, 5} такое, что для любой булевой функции / существует схема S, реализующая /, для которой

P(S) < ce + dis2, и для любой булевой функции / £ К

РеШ (12е2 при всех е £ (0; 1/960], где <¿1 и б?2 ~ некоторые (абсолютные) положительные константы.

Теорема 2. Для любого полного базиса В С В3, любого действительного числа Ь > 0 существует константа £о £ (0; 1/2) такая, что при любом п ^ 3 любую булеву функцию /(жь ., хп) £ К{п) можно реализовать схемой 5/, для которой -Р(<5/) — Р£(/) ^ ^£2 при всех £ б (0,£о]> Ь(5/) < 3(1 + Ь)р2п/п при п —> оо, где ¿¿з - некоторая (абсолютная) положительная константа.

Из теоремы 1 следует, что любому полному базису В С В3 можно сопоставить такое натуральное с £ {1,2,3,4,5}, что для любой функции / £ К можно построить асимптотически оптимальную по надежности схему Л, реализующую /, для которой Р(А) ~ с£ при е —> 0.

Из теоремы 2 следует, что для почти всех булевых функций / можно строить асимптотически оптимальные по надежности схемы, сложность которых асимптотически не болыне.чем в 3(1+6) раз превышает сложность минимальных схем, построенных из абсолютно надежных элементов, где Ь - любое, сколь угодно малое положительное число.

Для всех базисов В С константы с, <1х, (¿2 найдены явно и представлены в таблицах 1 и 2.

Диссертация состоит из введения, шести глав и списка литературы, содержащего 44 названия. Общий объем работы - 100 страниц, в работе содержатся 11 рисунков и 2 таблицы. Нумерация таблиц и рисунков -сквозная.

5.3. Выводы

Из теоремы 5.1 следует, что если полный базис В удовлетворяет хотя бы одному из следующих условий:

1. В содержит функцию, конгруэнтную функции <Р\ — Х\Х2Х2, и хотя бы одну из функций хг, 1;

2. В содержит функцию, конгруэнтную функции (р\ = х\ V х2 V жз и хотя бы одну из функций х\, 0;

3. В содержит функцию, конгруэнтную функции (р2 = Х1(х2 ФЖзФ<73) или <рз = ххх2х3, где <73 6 {0,1}, и функцию х\\

4. В содержит функцию, конгруэнтную функции — х\ V (х2 Ф жз Ф 0"з) или (рз = хх V х2 V ж3, где <73 Е {0,1}, и функцию жь то в этом базисе любую булеву функцию можно реализовать схемой, ненадежность которой не больше 4е + 250е2 при всех е Е (0; 1/960].

Из теоремы 4.6 следует, что если полный базис В удовлетворяет условиям теоремы 5.1, то в базисе В для почти всех булевых функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной 4е при е —» 0.

Из теорем 1.2 и 5.2, 5.3, 5.4, 5.5 следует, что в полном базисе В С Сопдг{Ж1&Ж2, Ж1&Ж2&Ж3, жь 0,1} или В С Сопдг{х\Ьх2, х\к.х2к.хз, жх&ж2, Ж1&Ж2&Ж3, 0,1} или В С Сопдг{х\ V Ж2, х\У х2У ж3, х\, 0,1} или В С Сопдг{XIV х2, жх V Ж2 V Жз, х\ V х2, х\ V ж2 V ж3, 0,1} при е Е (0; 1/960] любая схема, реализующая функцию / Е К^п), функционирует с ненадежностью, не меньше 5е(1 — е)4.

Таким образом, из теорем 5.2, 5.3, 5.4 и 5.5 следует, что других пол/ ных базисов В С В% (кроме названных в теореме 5.1), в которых почти все функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически равной 4е при £ —У 0, нет.

Итак, в полном базисе В С В3 для почти всех функций асимптотически оптимальные по надежности схемы имеют ненадежность, асимптотически равную 4е (е —> 0), тогда и только тогда, когда выполнено хотя бы одно из условий:

1. В СОДерЖИТ фуНКЦИЮ, КОНГруЭНТНуЮ фуНКЦИИ = Х1Х2Х3 и хотя бы одну из функций х\, 1;

2. В содержит функцию, конгруэнтную функции (р* = х\ V х2 V ж3 и хотя бы одну из функций Ж1, 0;

3. В содержит функцию, конгруэнтную функции <р2 = ^(жгФ^зФсз) или 3 = где (73 е {0,1}, и функцию XI,

4. В содержит функцию, конгруэнтную функции — х\ V (х2 Ф £3 ф ст3) или щ = Ж! V х2 V хз, где сг3 € {0,1}, и функцию х\.

Из теорем 1.2 и 5.2, 5.3, 5.4, 5.5 следует, что в полном базисе В С Сопдг{х\к.Х2, Х1&.Х2&Х3, х\, 0,1} или В С Сопдг{х\^х2, х\к,х2^хз, Ж1&Ж2, Х\&,Х2&1Хз, 0,1} или В С Сопдг{х\ V Х2, х\ V х2 V аг3, х\, 0,1} или В С Сопдг{х1 V х2, х\ V Х2 V ж3, ^х V Жг, V жг V ж3, 0,1} для почти всех булевых функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной 5е при г 0.

Глава 6. Сложность схем

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

Д. Улиг [7] для инверсных неисправностей на выходах элементов с вероятностью ошибки s доказал, что для любых сколь угодно малых чисел b и h (b,h > 0) существует число s'(s' G (0,1/2)) такое, что при любом £ G (0,£7], и любом р, удовлетворяющем условию р ^ (1 + h)sLg, справедливо соотношение LP)£(n) < (1 4- Ъ)р • 2п/п, где Ьд - минимальное число надежных элементов необходимых для реализации функции голосования д{х\, х2, жз) — xix2 V Ж2Ж3 V в рассматриваемом базисе.

Лемма 6.1 [17]. Пусть f - произвольная булева функция, а схема S\ реализует f с ненадежностью P(S\). Пусть схема А реализует функцию д(х \,х2,х%) = х\х2 V Х\Х% V х2х3 с ненадежностью Р(А). Тогда функцию f можно реализовать такой схемой S2, что P(S2) < Р{А) + 3P2(Sj).

Докажем основной результат этого раздела.

Теорема 6.1. Пусть полный базис В С В$. Для любого b > 0 существуют константы с G {1,2,3,4,5}, £1 G (0,1/2) и > 0, зависящие только от базиса, такие, что при любом п ^ 3 любую булеву функцию fix 1, х2:., хп) G К{п) мооюно реализовать асимптотически оптимальной по надежности схемой S, для которой P(S) < es + d3s2 при любом £ G (0,£i], L(S) < 3(1 + Ъ)р2п/п при ti —у оо.

Доказательство. Пусть полный базис В С В3. По базису В (см. табл. 1, 2) определим единственную константу с G {1,2,3,4,5} и положительную константу di такие, что любую функцию можно реализовать схемой А, ненадежность которой Р(А) ^ es + d\£2, причем для почти всех функций Р(А) ^ œ — d2£2 при £ G (0; 1/960]. Реализуем функцию g(xi,x2:x3) — xix2 V Х1Х3 V х2х% схемой Sg, ненадежность которой P(Sg) ^ с£ + ¿¿i£2.

Пусть /(^1,^2, - произвольная булева функция. Возьмем произвольное число Ъ > 0 и воспользуемся результатом Д. Улига [7], полагая К — 1. Тогда существует е2 (е2 Е (0,1/2)) такое, что при любом г Е (0, е2] и р = 2£1/? функцию / можно реализовать схемой для которой Р(5х) < и ¿(Ях) < (1 + Ь)р • 2п/гг.

Полагаем £х = шт{ 1/960, £2}. Возьмем три экземпляра схемы 5х и соединим их выходы со входами схемы Бд. Построенную схему обозначим через 5. По лемме 6.1 при е Е (0, ех] получаем Р(5) < + 3Р2(5х) < се + -1- 3(2еЬд)2 = се + где <¿3 = с?х + 12(£5)2. Очевидно, Ь(5) — 31,(5х) + < ЗЬ(5х) < 3(1 + Ь)р • 2»/п.

Теорема доказана.

Замечание 10. В теореме 6.1 константа р = 1, если базис В содержит только функции двух переменных, и р — 1/2, если в базисе В содержится функция, существенно зависящая от трех переменных.

Схемы построенные при доказательстве теоремы 6.1 для почти всех функций являются асимптотически оптимальными по надежности, а их сложность отличается от сложности минимальных схем, построенных из абсолютно надежных элементов в 3(1 + 6) раз, где Ь - любое сколь угодно малое положительное число.

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

2. Добрушин Р.Д., Ортюков С.И. О нижней оценке для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ., 1977. Т. 13, N 1. С. 82 89.

3. Добрушин Р.Л., Ортюков С.И. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ., 1977. Т. 13, N 3. С. 56 76.

4. Ортюков С. И. К вопросу о синтезе асимптотически безызбыточных самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ. 1977. Т. 13, N 4. С. 3 8.

5. Ортюков С. И. Метод синтеза асимптотически оптимальных самокорректирующихся схем, исправляющих близкую к линейной долю ошибок // Проблемы передачи информации. 1981. Т. 17, вып. 4. С. 8497.

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

7. Uhlig D. Reliable networks from unreliable gates with almost minimal comlexity // Fundamentals of Computation Theory. Intern, conf. FCT'87 (Kazan, June 1987). Proc. Berlin: Springer-Verl., 1987. P. 462 - 469. (Lecture Notes in Comput. Sci.; V. 278).

8. Редькин Н.П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992. - 192 с.

9. Jlyпанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

10. Лупанов О.Б. Об одном методе синтеза схем // Изв. ВУЗов, Радиофизика, 1958. Т. 1, N 1. - С. 120 - 140.

11. Pippenger N. On networks of Noisy Gates. // 26 Symposium on Foundation on Computer science, 21 23.10.1985, Portland. - P. 30 - 38.

12. Яблонский C.B. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center. 1982. N 7. -P. 11 - 19.

13. Тарасов В.В. К синтезу надежных схем из ненадежных элементов // Матем. заметки. 1976. -Т.20. - №3. - С. 391 - 400.

14. Аксенов С.И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. №6(21) 2005. - С. 42 - 55.

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

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

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

18. Алексеев В.Б. Лекции по дискретной математике: учебное пособие. -М.: Издательский отдел Фак-та ВМиК МГУ им. М.В. Ломоносова, 2004. 76 с.

19. Алехина М.А. О надежности схем в базисах, содержащих медиану // Труды VIII международной конференции "Дискретные модели в теории управляющих систем "(Лесной городок Моск. Обл., 6-9 апреля 2009 г.) М.: МАКС Пресс, 2009. - С. 13 - 17

20. Алехина М.А., Шилов A.B. Верхние оценки ненадежности схем в некоторых базисах при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. № 5(26) 2006. - С. 4 - 12.

21. Алехина М.А. Синтез, сложность и надежность управляющих систем: Учебное пособие. Пенза: Изд-во Пенз. гос. ун-та, 1999. - 40 с.

22. Яблонский C.B. Введение в дискретную математику: Учебное пособие для вузов. / Под ред. В.А. Садовничего. 3-е изд., стер. - М.: Высш. ж.; 2001. - 384 с.

23. Редъкин Н.П. О полных проверяющих тестах // Математические вопросы кибернетики. вып. 3, 1989, - с. 198 - 222.

24. Васин A.B. Об асимптотически оптимальных схемах в базисе {жх|ж2, х\ 1 Х2, Ж1&Ж2, xi V X2, Ж.} // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. Пенза: ИИЦ ПГУ, 2009 г. - № 1 (9). - С. 3 - 10.

25. Алехина М.А., Васин A.B. Синтез асимптотически оптимальных схем // Известия высших учебных заведений. Поволжский регион. Технические науки. Пенза: ИИЦ ПГУ, 2009 г. - № 2(10). - С. 48 - 62.

26. Васин A.B. О базисах, в которых асимптотически оптимальные схемы имеют ненадежность 2е // Материалы X Международного семинара "Дискретная математика и ее приложения "(г. Москва, 1-6 февраля 2010 г.). М.: Изд-во мех.-мат. фак. МГУ, 2010. - С. 94 - 97.

27. Васин A.B. О надежности схем в полных конечных базисах, содержащих линейную функцию // Труды международного симпозиума "Надёжность и качество, 2010"(г. Пенза, 24 31 мая 2010 г.). - Пенза: ИИЦ ПГУ, 2010 г. - Том 1. - С. 241 - 242.

28. Васин A.B. О базисах, в которых асимптотически оптимальные схемы функционируют с ненадежностью Ъе // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. Пенза: ИИЦ ПГУ, 2010 г. - № 1 (13). - С. 64 - 79.