Содержание к диссертации
Введение
I. Некоторые свойства схем из ненадежных элементов 19
II. Верхние оценки ненадежности схем при инверсных неисправностях на входах элементов 31
III. Нижние оценки ненадежности схем при инверсных неисправностях на входах элементов 65
IV. Сложность асимптотически наилучших по надежности схем при инверсных неисправностях на входах элементов 89
Литература 107
- Некоторые свойства схем из ненадежных элементов
- Верхние оценки ненадежности схем при инверсных неисправностях на входах элементов
- Нижние оценки ненадежности схем при инверсных неисправностях на входах элементов
- Сложность асимптотически наилучших по надежности схем при инверсных неисправностях на входах элементов
Введение к работе
К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. Разработка специальных методов синтеза схем из ненадежных функциональных элементов связана, главным образом, с выбранной математической моделью неисправностей. Одна из основных моделей определяется инверсными неисправностями на входах или на выходах элементов. В диссертации рассматривается задача построения асимптотически оптимальных (асимптотически наилучших) по надежности схем в предположении, что функциональные элементы подвержены инверсным неисправностям только на входах элементов. Решение этой задачи усложняется дополнительным требованием к сложности схем, которое состоит в том, чтобы сложность асимптотически оптимальных по надежности схем по порядку равнялась сложности минимальных схем, построенных только из надежных элементов. Задача решается в неприводимых полных базисах, содержащих функции не более чем двух переменных.
Впервые задачу синтеза надежных схем из ненадежных элементов рассматривал Дж. фон Нейман [1]. Он рассматривал инверсные неисправности на выходах элементов, когда функциональный элемент с приписанной ему булевой функцией f(x)=flx\, %2,..., х„) в неисправном состоянии,
в которое переходит с вероятностью є (єє(0; 1/2)), реализует функцию /(Зс). С помощью итерационного метода Дж. фон Нейман установил, что
при єє(0; 1/6) произвольную булеву функцию можно реализовать схемой, вероятность ошибки, на выходе которой при любом входном наборе значений переменных не превосходит с\Є (с\ - некоторая абсолютная константа). Однако сложность такой схемы с ростом числа итераций увеличивается экспоненциально (примерно, в Зк раз, где А: - число итераций).
4 Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах Р.Л. Добрушина, СИ. Ортюкова, Д. Улига [2 - 7] и некоторых других авторов, причем главное внимание уделялось сложности схем (задача синтеза схем наилучших по надежности не ставилась). Сформулируем результаты названных авторов. Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в произвольном конечном полном базисе B = {ev е2, ...,ет}, meN [8].
(Множество всех функциональных элементов Eh функции которых е, принадлежат базису В, будем также называть базисом В [9].) Каждому элементу базиса Et приписано положительное число v(() - вес данного элемента. Пусть сложность L(S) схемы S из ненадежных элементов [8], реализующей булеву функцию f(x), определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимым образом с вероятностью є переходят в неисправные состояния. Ненадежность P(S)
схемы S определяется как максимальная вероятность ошибки на выходе схемы при всевозможных входных наборах. Вводится функция Шеннона L (ri) = max mm L(S), характеризующая сложность схем, реализующих
функции от п переменных в базисе В, где минимум берется по всем схемам S из ненадежных элементов, реализующим функцию f[x\, лг2, —, хп) с ненадежностью P(S)
Пусть р = m'm{v{Ei)l{n{Ei)-\)), где минимум берется по всем эле-
Е,
ментам Е, базиса, для которых n(Et) > 1, п(Е{) - число существенных переменных функции eh реализуемой элементом Eh a v(E,) - вес функционального элемента ;, / = 1, ...,т.
О.Б. Лупанов [10] показал, что для схем, реализующих булевы функции от п переменных и состоящих только из надежных элементов (т. е. при є = 0 и р = 0), выполняется соотношение L0 0 (п) ~ р 2" / п.
5 С. И. Ортюков [6] для инверсных неисправностей на выходах элементов получил следующий результат: пусть 0
L - минимальное число надежных элементов, необходимое для реализации функции голосования g(xl,x2,xi) = дг,д:2 vjCjjc3 vx2x, в рассматриваемом базисе, q(s) - некоторая функция такая, что д(є) = є + Зє2+о(є2) при є -» 0. Тогда существует такая функция р(е) -> р при є -> 0, что LJn)zpWn/n.
Д. Улиг [7] для инверсных неисправностей на выходах элементов с вероятностью ошибки є доказал, что для любых, сколь угодно малых чисел с и b (с, b > 0) существует число є' (є' є(0, 1/2)) такое, что при любом є (єє(0, є')), и любом р, удовлетворяющем условию р> (1 + Ь) є L (точнее
р> q{) Lg), справедливо соотношение Ьрг(п)^(1 + с)р-2" In.
Таким образом, в результатах СИ. Ортюкова и Д. Улига имеет место асимптотика функции Шеннона с точностью до множителя, сколь угодно близкого к единице (при этом вероятность сбоя є ограничена константой), т.е. найденные ими методы синтеза позволяют строить асимптотически оптимальные по сложности схемы, функционирующие с некоторым уровнем надежности.
Из результатов Н. Пиппенджера [11] следует, что при инверсных неисправностях на выходах элементов с вероятностью ошибки єє(0, 1/200] любую булеву функцию от п переменных в базисе {&, v, } можно реализовать такой схемой S, что P(S) < 18s, L(S) 170 2" I n.
СВ. Яблонский [12] рассматривал задачу синтеза надежных схем в базисе В = {х\&.хг, х\\/хг, jc, , g(xl,x2,xJ)}. Он предполагал, что элемент,
реализующий функцию голосования g(x1,x2,xi) = xlx2 vx2x3 vxlx2 абсолютно надежный, а конъюнктор, дизъюнктор и инвертор - ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них
не больше с. Им доказано, что для любого р > О существует алгоритм, который для каждой булевой функции J[x\, xj, ..., хп) строит такую схему S, что P(S)
В.В. Тарасов [13] рассматривал задачу построения схем сколь угодно высокой надежности (когда P(S) -> 0). Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом В.В. Тарасовым выявлены необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных им результатов следует невозможность построения сколь угодно надежных схем для произвольных функций при инверсных неисправностях только на входах элементов или только на выходах в базисах из двухвходовых функциональных элементов.
СИ. Аксеновым [14] получена оценка ненадежности схем в произвольном полном базисе В при инверсных неисправностях на выходах элементов. Он доказал, что в произвольном полном базисе В при єє(0; Єо) любую булеву функцию можно реализовать такой схемой S, что P(S) < kz + + cz , где к (к < 5) - минимальное число надежных элементов, необходимое для реализации какой-либо из функций вида: gi(x,, х2, х3) =
— Л| Xj V Л| Xj V Л2 Xj , g 2 \Х\) ^2 , Х^ , Л4 j Лj Aj V Xj X^ , gj ^Xj, X2 , Xj , X^ j
= (x,0' vx22)(x33 vx*), ст,є{0, 1}, /є{1, 2, 3,4}, а є - ненадежность базисного элемента. Константы к, с, Sq положительны и зависят от базиса В. Таким образом, в произвольном полном базисе любую булеву функцию можно реализовать схемой, ненадежность которой асимптотически не больше 5 є при є -> 0. Вопрос о возможности снижения мультипликативной константы 5 в оценке ненадежности для произвольного базиса пока остается открытым.
М.А. Алехина [15] решала задачу построения асимптотически оптимальных (асимптотически наилучших) по надежности схем при однотип-
7 ных константных неисправностях только на входах или только на выходах элементов. Чтобы сформулировать полученные М.А. Алехиной результаты, введем необходимые определения.
Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью єє(0; 1/2), реализует константу 0, то она называется неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, то такая неисправность называется неисправностью типа 1 на выходе элемента.
Если неисправность элемента такова, что поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью єє(0; 1/2) может превратиться в нуль, то она называется неисправностью типа 0 на входе элемента. Если же неисправность элемента такова, что поступающая на его вход единица не искажается, а нуль с вероятностью с может превратиться в единицу, то она называется неисправностью типа 1 на входе элемента.
Ненадежность P(S) схемы S определяется также как для инверсных
неисправностей на выходах элементов, и равна максимальной вероятности ошибки на выходе схемы S. Надежность схемы S равна 1 - P(S).
Пусть Ръ (/) = inf P(S), где инфимум берется по всем схемам S из не-
надежных элементов, реализующим функцию J[x\, Х2, ..., хп). Схема А из ненадежных элементов, реализующая функцию/ называется асимптотически наилучшей (асимптотически оптимальной) по надежности, если
Р{А) ~ Pz (/) при є -> 0, т. е. fen 5fQ = 1.
М.А. Алехиной [15] доказано, что во всех неприводимых полных базисах (исключая три случая), содержащих функции не более чем двух переменных, почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежно-
8 стью асимптотически равной azl при с -> 0, константы ant зависят от базиса и типа неисправностей, ае{\, 2, 3}, /є{1, 2}. Сложность таких схем по порядку равна сложности схем, построенных только из надежных элементов (т. е. увеличивается несущественно).
В работе [16] М.А. Алехина рассматривала инверсные неисправности на входах элементов и доказала, что при инверсных неисправностях на входах элементов в базисах {х\ \ х2} и {лг^хг} почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежностью, асимптотически равной 2є при є -> 0. Асимптотически наилучшие по надежности схемы можно строить со сложностью, по порядку равной сложности минимальных схем, состоящих только из надежных элементов.
Вопрос о возможности построения асимптотически наилучших по надежности схем в других, отличных от {х\ \Х2}, {х\-1х2}, базисах из двухвхо-довых функциональных элементов при инверсных неисправностях на входах элементов, оставался открытым. Ответ на него для всех остальных неприводимых полных базисов из двухвходовых функциональных элементов получен в данной диссертационной работе. Существенное внимание уделяется сложности асимптотически оптимальных по надежности схем. Показано, что во всех неприводимых полных базисах из двухвходовых элементов при инверсных неисправностях на входах элементов для почти всех булевых функций можно построить схемы, асимптотически наилучшие по надежности, причем их сложность по порядку равна сложности схем, построенных только из надежных элементов.
Введем основные понятия и определения.
Будем считать, что схема реализует функцию J[x\, х2,..., х„), если при поступлении на входы схемы набора a = (а\,а2, ..., ап) при отсутствии неисправностей на выходе схемы появляется значение f(a). Предполагается, что все элементы схемы имеют не более двух входов, один выход и не-
9 зависимо друг от друга с вероятностью єє(0; 1/2) подвержены инверсным неисправностям на входах. Эти неисправности характеризуются тем, что поступающее на каждый вход элемента значение а, ае{0, 1}, с вероятностью s может превратиться в значение а .
Ненадежность P(S) схемы S, реализующей функцию f(x), при инверсных неисправностях на входах элементов определяется так же, как и при инверсных неисправностях на выходах, т.е.
P(S) = maxP/(3)(S,a),
где Р- {S,a) - вероятность появления значения f(a) на выходе схемы S
при входном наборе а, а максимум берется по всем возможным входным наборам а. Надежность схемы S равна 1 - P(S).
Понятие асимптотически оптимальной по надежности схемы вводится, как и раньше. Обозначим Pz{f) - inf P(S), где S- схема из ненадежных
элементов, реализующая булеву функцию Дхь jc2, ..., хп). Схему А из нена-
i дежных элементов, реализующую булеву функцию Х^ь *2, —, Хп), назовем
асимптотически оптимальной (асимптотически наилучшей) по надежности, если Р{А) ~ Pz(f) при є -» 0, т.е.
Inn і
є Р{А)
Напомним, что веса всех элементов равны единице, поэтому сложность 1(5) схемы S равна числу функциональных элементов в ней.
Определение. Булевы функции f\ назовем конгруэнтными, если одна из них может быть получена из другой заменой переменных (без отождествления).
Пусть М- это множество всех булевых функций, зависящих не более чем от двух переменных. Тогда множество попарно неконгруэнтных булевых фуНКЦИЙ, ЗаВИСЯЩИХ (ВОЗМОЖНО, фиКТИВНО) ОТ ПеремеННЫХ Х\, Х2, есть
М(Х\, Хг) = {Х\80С2, X\VX2, Х\ \Х2, Х\ІХ2, Xi-»X2, *1 "А Х2, Х\~Х2, Х\@Х2, Х\,0, 1}.
10 При перечислении функций использованы следующие обозначения:
Xj|x2 = Х{ VX2 , Xj 4 Х2 = Х{ &Х2 , Х\ ~ Х2 = Xi&X^Xj &х2 , хх -> х2 = x{v х2, Х\ "А Х2 = Xi &Х2 , Х( ФХ2 = Xj &х2 v х1 &х2.
Определение. Множество В с М(х\, х2) назовем неприводимым полным базисом (в Р2), если множество В полно и никакое его собственное подмножество полным не является.
Введем в рассмотрение неприводимые полные базисы: В\ ={xi IХ2}, В2 = {х\1х2}, В3 = {xi->x2, xi-f>x2}, В4 = {xi->x2, xix2}, B5 = {x\-f>x2, x\~x2}, B(, = {x\x2, X\8lx2, 1}, B1 = {x\~x2, X\vx2, 0}, Bg = {x\~x2, x\&x2, xix2},
B9 = {X\~X2, X\VX2, X\X2), BiQ = {Xl~X2, X\&X2, 0}, B\\ = {X\X2, X\\?X2, 1},
B\2 = {x,-/>x2, Xi}, Bu = {xi->x2, x{}, BH = {х,-У>х2, 1}, Bl5 = {x,->x2, 0},
Bl6 = {X\&X2, Xj }, 517 = {X!VX2, X! }.
В P2 существует ровно 17 (с точностью до переименования переменных) неприводимых полных базисов, содержащих функции не более чем двух переменных. Любой другой базис, отличный от базисов В\ - Вп (например, 5)8 = {xi&x2, Xivx2, Xj}), можно получить переименованием переменных без отождествления, а также добавлением одной или нескольких функций из множества М(хь х2) к некоторому базису из указанного списка.
В диссертационной работе доказано: для каждого базиса В из введенных выше базисов В\ - В^ при инверсных неисправностях на входах элементов существуют такие константы a, b, d, Ь, d, d', с' и класс булевых функций К(п) (см. табл. 1 - 3), что справедливы следующие утверждения.
Если єє(0; d\, то любую булеву функцию /(х,, х2, ...,*„) можно реализовать схемой S с ненадежностью P(S) < яє + Ъгг.
Если єє(0; d], то при реализации любой функции /(х,, х2, ...,хп) & К(п) любой схемой S верно неравенство P(S) >as + Ьг2.
3) Если єє(0; d'], то сложность асимптотически наилучших по надежности схем S по порядку равна сложности схем, построенных только из надежных элементов: L(S) &с'-2п In.
Полученные результаты сформулируем в виде теорем.
Пусть В - один из базисов В\ - В ^, а в схемах возникают инверсные неисправности на входах элементов.
Теорема 1. Пусть константы а, Ь', с', d (см. табл. 1) соответствуют базису В и єє(0; d']. Тогда любую булеву функцию f{xx, х2,...,*„) в базисе В
можно реализовать такой схемой S, что P(S) <аг + Ь'в2,1(5) с' 2" I п.
Таблица 1.
Заметим, что результат СИ. Аксенова [14] можно перенести на случай инверсных неисправностей на входах элементов (в этом случае ненадеж-
ность базисного элемента не больше 2є) следующим образом: при єє(0; Єо)
12 произвольную булеву функцию можно реализовать такой схемой S, что
J 'J
P(S) < 2kz + cz < ІОє + се , то есть множитель при є не больше 10. В то время как у нас этот множитель принимает значения 2,3 и 4.
Оценки теоремы 1 установлены конструктивно, т.е. представлены методы синтеза схем S, удовлетворяющих указанным оценкам по надежности и сложности.
Константы Ъ' и с' (см. табл. 1) не являются единственной парой значений, для которой справедлива теорема 1. Теорема 1 справедлива, например, для значений Ь" и с" соответственно. Однако, уменьшение одной из констант влечет увеличение другой, т.е. «улучшая» одну характеристику схемы (например, повышая надежность) «ухудшаем» другую (сложность).
Теорема 2. Пусть константы a,b,d и класс булевых функций К{п) (см. табл. 2) соответствуют базису В. Тогда для любой булевой функции /(*,, х2, ...,xn),f< К{п), и любой схемы S, реализующей/в базисе В, при
єє(0; d] верно неравенство: P(S) > аг + bє2, причем а - та же константа,
что и в теореме 1.
Установлено, что для всех базисов В\ - В\$ константа а, фигурирующая в теоремах 1 и 2 одна и та же. Это свидетельствует о том, что используемые методы синтеза позволяют строить схемы асимптотически наилучшие по надежности для почти всех булевых функций (при растущем п). Сложность предлагаемых схем по порядку равна сложности схем, построенных только из надежных элементов. Таким образом, из теорем 1 и 2 следует утверждение.
Следствие 1. Схемы, построенные при доказательстве теоремы 1, являются асимптотически оптимальными по надежности для почти всех булевых функций в базисах В\ - В\%, причем сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов.
Таблица 2.
Используемые в таблице 2 обозначения: i = l,n, 8, цє{0,1}, /z(x) -
произвольная булева функция от п переменных (х = (хь х2,..., х„)).
Диссертация состоит из введения, четырех глав и списка литературы, содержащего 25 названий. Общий объем работы - 110 страниц, в работе содержится 28 рисунков и 5 таблиц. Нумерация таблиц и рисунков сквозная в пределах главы.
Первая глава диссертации содержит необходимые определения, обозначения и ряд вспомогательных утверждений, используемых в дальнейшем для получения верхней и нижней оценок ненадежности схем. Отметим наиболее важные из них. Теорема 1.1 утверждает, что ненадежность схемы в некоторых случаях можно оценить снизу с помощью вероятностей ошибок на выходе подсхемы, содержащей выход этой схемы. Эта теорема
14 используется при доказательстве нижних оценок ненадежности схем. Теорема 1.2 [15] утверждает, что для двойственных схем на противоположных входных наборах вероятности ошибок равны. Поэтому (следствие 1.1 [15]), равны ненадежности двойственных схем. Следовательно, утверждение о надежности, доказанное для функции /в базисе В при инверсных неисправностях на входах элементов, верно для двойственной функции /* в двойственном базисе В* при тех же неисправностях элементов. В диссертационной работе свойства двойственных схем используются следующим образом: получив результат в базисе В для функции / переносим его в двойственный базис В* на функцию/", сокращая тем самым объем исследовательской работы.
Леммы 1.1-1.8 содержат утверждения, позволяющие развивать определенную технику вычислений вероятностей ошибок на выходе схем.
Лемма 1.9 [15] позволяет оценить снизу ненадежность схемы наименьшей из вероятностей ошибок подсхемы, содержащей выход схемы.
Вторая глава диссертации содержит описание методов синтеза надежных схем в каждом из базисов В\ -5]8. С помощью этих методов получены верхние оценки ненадежности схем.
Сначала описывается общий метод синтеза надежных схем в произвольном полном конечном базисе, который позволяет найти оценку ненадежности схемы S, реализующей булеву функцию / Для этого построим схему Sh, реализующую функцию Х\ IХ2, И обозначим вероятности ошибок на выходе схемы Sh следующим образом: р'0(00) = а, р'0(0\) = Р, р0(Щ ~ = 8, р\ (11) = т. Найдем оценку ненадежности схемы S, реализующей булеву функцию/ используя теорему 2.2.
Обозначим u. = max {а, Р, 8, т} - ненадежность схемы /,. .
Теорема 2.2. Если цє(0; 1/50], то любую функцию /можно реализовать схемой S такой, что P(S) < 4ц.
15 Полученный результат конкретизируется для каждого из базисов В\, В2, #4_ #ib ^16 - #18- Иначе получены оценки ненадежности схем в базисах Вт,, Ви, Ви, Ви, В\5. Здесь в качестве схемы Sh берем схему, реализующую функцию Х\іх2, двойственную функции Хі\х2. Вычисляем вероятности ошибок /7*(11), /?,*(Ю), РІ(01), р'0(00) на выходе этой схемы. Полагая р\ (11) = а, /?* (10) = р, р\ (01) = у, р'0 (00) = т, воспользуемся теоремой 2.2
и получим оценку ненадежности схемы S, реализующей произвольную булеву функцию/
Затем строятся схемы, более надежные, чем схемы S. В базисах В\, В2, В[6, и Вц для повышения надежности схемы S использовалась схема ф(5), построенная следующим образом: возьмем два экземпляра схемы S, реализующей булеву функцию /(*,, х2,..., хп), соединим их выходы с входами
схемы Sh, реализующей функцию х\ \ х2; затем возьмем два экземпляра этой схемы и соединим их выходы с входами еще одной схемы Sh. Схема ф(5) построена.
В базисах В^, В\2, Вц, В^, Вц для повышения надежности используется схема ф(5), в которой в качестве схемы Sh рассматривается схема, реализующая функцию х\-1х2.
Очевидно, что в результате применения (возможно, неоднократного) операции ф к схеме S, реализующей булеву функцию/получаются схемы, реализующие ту же функцию/
В базисах #4 и В5 для повышения надежности использовалась схема \\)\(S, S'): возьмем один экземпляр схемы S, реализующей функцию / два экземпляра схемы S', реализующей функцию /, и соединим выходы схем 5", S', S соответственно с первым, вторым и третьим входами схемы Sg, реализующей функцию g(xt, х2, x3) = xlx2vxlxivx2x3. Очевидно, что в результате применения (возможно, неоднократного) операции i|/i к схемам S и S', реализующим булевы функции / и / соответственно, получаются схемы, реализующие функцию/
В базисах Be, В-;, В% и Вд для повышения надежности использовалась схема \|/(5): возьмем три экземпляра схемы S, реализующей булеву функцию/ и соединим их выходы с входами схемы Sg, реализующей функцию голосования g(xl,x2,x3) = xlx2 vx2x, vxlxi. Очевидно, что в результате
применения (возможно, неоднократного) операции \|/ к схеме S, реализующей булеву функцию/получаются схемы, реализующие функцию/
В базисах #ю и Вп для повышения надежности использовалась схема 11/2(5, S')\ возьмем два экземпляра схемы S, реализующей функцию/ один экземпляр схемы «S*, реализующей функцию /, и соединим выходы схем S, S', S соответственно с первым, вторым и третьим входами схемы Sg, реализующей функцию g(x{, х2, xi) = xlx2 vx,x3 vx2x3. Очевидно, что в результате применения (возможно, неоднократного) операции щ к схемам S и S', реализующим булевы функции /и / соответственно, получаются схемы,
реализующие функцию/
В базисе Z?i8 для повышения надежности использовалась следующая схема ф(5): возьмем два экземпляра схемы S, реализующей булеву функцию/ и соединим их выходы с входами конъюнктора, затем выходы двух экземпляров таких схем соединим с входами дизъюнктора. Очевидно, что в результате применения (возможно, неоднократного) операции ф к схеме S, реализующей булеву функцию/ получаются схемы, реализующие ту же функцию/
Таким образом, во второй главе доказано, что каждому из базисов В\ - В\% можно сопоставить константы а, Ъ, d (см. табл. 3) такие, что при єє(0; d\ произвольную булеву функцию f(x1,x2,...,xn) можно реализовать схемой S, ненадежность которой P(S) < az + be2.
Построенные во второй главе схемы являются не просто надежными, а как будет показано в третьей главе, асимптотически наилучшими по надежности для почти всех функций.
17 Таблица 3.
Нижние оценки надежности схем получаются из верхних оценок ненадежности сразу по определению надежности.
Третья глава диссертации посвящена нижним оценкам ненадежности схем. Доказано, что надежные схемы, построенные во второй главе, являются асимптотически наилучшими по надежности во всех рассматриваемых базисах В\ -В\% для почти всех функций.
Для получения нижних оценок ненадежности схем в базисе В используются следующие методы:
в произвольной схеме S, реализующей функцию/ К{п), выделяется некоторая связная подсхема, содержащая выход схемы и по некоторым вероятностям ошибок подсхемы оценивается ненадежность схемы S;
в произвольной схеме S, реализующей функцию/ g K(ri), выделяется связная подсхема специального вида (с-схема), содержащая выход схе-
18 мы, по некоторым вероятностям ошибок которой можно оценить ненадежность всей схемы.
3) для схемы S, реализующей функцию/ К(п), доказывается существование набора значений входных переменных, на котором вероятность ошибки на выходе схемы не меньше as + bz2, если єє(0; d ].
Оценки для вероятностей ошибок на выходе схем и подсхем получены с помощью лемм 1.1-1.9 первой главы.
Сформулируем результаты третьей главы.
Доказано, что каждому из базисов В\ - В\% можно сопоставить константы a,b,d и класс булевых функций К{п) (см. табл. 2) такие, что при
єє(0; d] любая схема S реализует булеву функцию /(*,, х2,..., хп),
f . К(п), с ненадежностью P(S) > az + be2. Константа а здесь та же, что и во второй главе.
Четвертая глава диссертации посвящена сложности асимптотически наилучших по надежности схем. Доказано, что сложность асимптотически наилучших по надежности схем в рассматриваемых базисах по порядку равна сложности схем, построенных только из надежных элементов для почти всех булевых функций. А именно, доказано (см. теорему 1), что базису В можно сопоставить константы a, b',c', d (см. табл. 1) такие, что при єє(0; d'] любую булеву функцию f(xx, х2, ...,хп) можно реализовать схемой S, для которой P(S) <аг + Ь'г2, L(S) с' 2" I п.
Результаты диссертации опубликованы в работах [17 - 25], среди них 4 основные работы опубликованы в журналах, рекомендуемых ВАК для публикации результатов диссертаций. 3 работы из 9 написаны в соавторстве с научным руководителем М.А. Алехиной. В совместных работах результаты являются собственными, М.А. Алехиной принадлежат постановка задачи и идея доказательства.
Автор выражает благодарность своему научному руководителю профессору М.А. Алехиной за постоянное внимание к работе, поддержку и полезные советы.
Некоторые свойства схем из ненадежных элементов
Будем рассматривать реализацию булевых функций схемами из ненадежных функциональных элементов в конечном базисе В. Все входы элементов схемы независимо друг от друга с вероятностью єє(0; 1/2) подвержены инверсным неисправностям. Эти неисправности характеризуются тем, что поступающее на вход элемента значение а, (ае{0, 1}) с вероятностью s может превратиться в значение а .
Ненадежность P(S) схемы S определяется как максимальная вероятность ошибки Pj{S)(S,a) при всевозможных входных наборах а схемы S, реализующей булеву функцию f(x). Следовательно, надежность схемы S равна \-P(S). Обозначим через С подсхему, получаемую из схемы S удалением подсхемы В (рис. 1.1). Очевидно, что схема С реализует /. Если выполнено неравенство: P(S) Р(С), то будем говорить, что схема С надежнее схемы S и получается из S удалением подсхемы В. Определение. Схема S, реализующая булеву функцию отличную от константы, является с-схемой, если из нее нельзя получить более надежную схему удалением подсхемы, содержащей выход схемы S и реализующей инверсию.
Определение. Две схемы S и S двойственны, если одна получается из другой заменой всех элементов на двойственные им элементы соответственно. Теорема 1.2 [15]. Для любых двойственных схем S и S , и любого входного набора а верно равенство: P-f{d){S,a) = Pjt )(S ,a), где Ъ = {ах,аг,..., aj,/[xh х2, ..., xn),f(xh х2, ..., хп) - функции, реализуемые схемами S и S соответственно. Следствие 1.1 [15]. Для любых двойственных схем S и S верно равенство P(S) = P(S ). Теорема 1.2 и следствие 1.1 доказаны в работе [15] для произвольных неисправностей функциональных элементов. Нами эти утверждения используются для случая инверсных неисправностей на входах элементов.
Таким образом, утверждения о надежности, доказанные для функции/ в базисе В при инверсных неисправностях на входах элементов верны для двойственной функции/5 в двойственном базисе В при тех же неисправностях. Приведем вспомогательные леммы, необходимые в дальнейшем для вычисления вероятностей ошибок на выходе подсхем.
Пусть S - произвольная схема, реализующая булеву функцию / отличную от константы, а ее выходному элементу Е приписана функция е. Первый вход элемента Е соединен с выходом некоторой подсхемы Si, второй вход элемента Е соединен с выходом некоторой подсхемы 1 (рис. 1.2), причем Si и 5г не имеют общих элементов. Обозначим через Pj(Sp а) вероятность ошибки на входном наборе а схемы Si, реализующей функцию Л /=1,2.
Лемма 1.8. Пусть S - произвольная схема, реализующая неконстантную булеву функцию/ такова, что вход ее выходного элемента Е - инвертора - соединен с выходом некоторой подсхемы С (рис. 1.4). Обозначим Pi (С, а) и Ро(С, а)- вероятности ошибок на выходе схемы С на входном наборе а схемы S. Тогда вероятности ошибок на выходе схемы S равны: ОД а) = Е + Р0(С, д)(1-2б), зо если набор а является нулевым для/ т.е. Да) = 0; Po(Sfl) = E + Pi(C,fl)(l-2e), если набор а является единичным для/ т.е. f(a) = 1. Для доказательства достаточно вычислить вероятности ошибок. В леммах 1.1-1.8 установлена возможность вычисления вероятности ошибки на выходе отдельного элемента схемы.
Лемма 1.9 [15]. Пусть/- произвольная булева функция, отличная от константы, и S - любая схема ее реализующая. Пусть подсхема В схемы S содержит выход схемы S и реализует булеву функцию/ с ненадежностью Р(В) 1/2. Обозначим 1 - минимум вероятностей ошибок на выходе схемы В по таким входным наборам Ъ , что f (b) = 0. Аналогично р - минимум вероятностей ошибок на выходе схемы В по таким входным наборам Ъ , что f (b) = 1. Тогда вероятности ошибок на выходе схемы S удовлетворяют неравенствам: P[(S, а) р\ если /(a) = 0; Po(S, а) /?, если /(20 = 1. Замечание 1.1. Из леммы 1.9 следует, что P(S) тах{р,р1}. Лемма 1.9 и замечание 1.1, доказанные в работе [15] для произвольных неисправностей функциональных элементов, используются нами далее для случая инверсных неисправностей на входах элементов. Таким образом, лемма 1.9 и замечание 1.1 позволяют найти оценку надежности схемы при инверсных неисправностях на входах элементов по некоторым вероятностям ошибок ее связной подсхемы, содержащей выход схемы.
Верхние оценки ненадежности схем при инверсных неисправностях на входах элементов
Обозначим через А (рис. 2.4) подсхему схемы S, выход которой является выходом схемы S, а на входы подаются значения х„, fo = Дх\, Х2, ..., хп-\, 0) и/ =.Дхь х2, л-ь !) Поскольку выделенная подсхема Л состоит из четырех экземпляров схемы Sh, то ее ненадежность Р{А) А/л. Функции /о =Лхи Х2,»., Хд-ь 0) и/ =Дхь х2,..., х„.ь 1), согласно индуктивному предположению, можно реализовать схемами с ненадежностью не более 4ц.
Пусть а = (а\, а2, а„) - входной набор схемы S. Если подсхема А исправна, а ап = О, то значение на выходе схемы S равно значению на выходе схемы S", причем неважно как сработает подсхема 5 , реализующая/].
В работе [16] М.А. Алехиной получена верхняя оценка ненадежности схем, реализующих произвольные булевы функции в базисе { i U2}. В [16] доказано, что при єє(0; 1/320] любую булеву функцию/в базисе {х\ 1 } можно реализовать такой схемой S, что P(S) 2s + 161 є2. Эту оценку ненадежности можно улучшить.
По теореме 2.2 при єє(0; 1/100] любую булеву функцию можно реализовать схемой S, ненадежность которой P(S) 8s. Применяя теорему 2.1, по схеме S построим схему 9(5), ненадежность которой Р(ф(5)) max{2s + 160s2, 361s2} Зє + 61є2. Применяя теорему 2.1 еще раз, получим схему ф2(5), для которой Р(ф2(5)) max{2s + 30s2 + 964s3 + 7198є4, 81s2 + 2144s3 + 14160є4} 2є + 41є2, при єє (0; 1/100]. Четвертый шаг итерации позволяет строить схему ф3(5), ненадежность которой Р(ф3(5)) ; max{2s + 16є2 + 484s3 + 3198s4, 49s2 + 1108s3 + 6240s4} 2є + 22є2, при є 1/100. По схеме ф3(5) построим схему ф4(5), реализующую/с ненадежностью Дф4(5)) max{2s + 16s2 + 256s3 + 880є4, 49s2 + 576s3 + + 1680s4} 2є + 19є2, при єє (0; 1/100].
Схема ф4(5) искомая, т.е. S - q 4(S). Теорема 2.3 доказана. Очевидно, что функции х, в базисе {хі 1} можно реализовать абсолютно надежно, константу 1 можно реализовать схемой, ненадежность которой асимптотически равна 9s2 при є - 0 (смотри далее пример 2.1).
Пример 2.1. При єє (0; 1/1900] константу 1 в базисе {xjU2} можно реализовать такой схемой А, что Р(А) 9s2 + 942s3 + 19801s4. Действительно, моделируя формулу xil (xil х\), строим схему S из двух элементов, реализующую константу 1. По лемме 1.7 вероятность ошибки на выходе схемы S удовлетворяет условию: P(S) 3s. Затем построим схему ф(5) (рис 2.1, в качестве подсхемы S/, берем один функциональный эле 37 мент), которая позволяет улучшить найденную оценку. Ненадежность схемы ф(5) удовлетворяет неравенству: P(y(S)) 8є при єє (0; 1/1900]. По схеме ф(5) построим схему ф2(5): в схеме ф(5) заменим подсхему S на ф(5). Ненадежность схемы ф (S) удовлетворяет неравенству: Р(ф (S)) 9є + + 942є3 + 19801s4 при єє (0; 1/1900]. Схема ф2(5) является искомой схемой.
Таким образом, показано, что все булевы функции в базисе {х\ \ х2} можно реализовать схемами, ненадежность которых асимптотически не более 2є при є - 0. В частности, функции х,- можно реализовать абсолютно надежно, а константу 1 можно реализовать схемой, ненадежность которой асимптотически не более 9є при s - 0.
Доказательство. Пусть схема Sh реализует функцию хііх2 в базисе {х\- х2, x\-frx2} с вероятностями ошибок на выходе рЦОО) - 2є + Зє2; р\ (01) = є; р\ (10) = 6s; р\ (11) = 4є2. В силу двойственности функций х\1х2 и х\ \х2 можно воспользоваться результатами теорем 2.1 и 2.2, полагая а = = р\ (11) = 4є2, р = р\ (10) = 6s, 8 = р\ (01) = є, т = р\ (00) = 2є + Зє2. Следовательно, цє(0; 6є] и єє(0; 1/300]. По теореме 2.2 при єє(0; 1/300] любую булеву функцию можно реализовать схемой S, ненадежность которой P(S) 24є. Применяя теорему 2.1, по схеме S построим схему ф(5), не 39 надежность которой Р((р(5)) max{2s + 1499є2, 2854є2 + 321є3 + 9є4} 9s + 156s2. Применяя теорему 2.1 еще раз, получим схему ф2(5), для которой Р(ф2(5)) max{2s + 299s2 + 7800s3 + 48672s4, 544є2 + 14805s3 + + 99225s4} 3s + 26s2, при єє(0; 1/300]. Четвертый шаг итерации позволя-ет строить схему ф (S), ненадежность которой Р(ф (S)) max{2s + 71s + + 676s3 + 1352s4,124s2 + 1265s3 + 3025s4} 2s + 74s2, при єє(0; 1/300]. По схеме ф3(5) построим схему ф4(5), реализующую / с ненадежностью Дф4(5)) max{2s + 47s2 + 1628s3 + 10952s4, 82s2 + 2869s3 + 22801s4} 2s + 53є2, при єє(0; 1/300]. Аналогично, по схеме (p\S) строим схему Ф5(5), ненадежность которой P((?\S)) max{2s + 47є2 + 1166s3 + 5618s4, 82s2 + 2070s3 + 11881s4} 2s + 51s2, при єє(0; 1/300]. Схема ф5(5) искомая, т.е. S = ф5(5). Теорема 2.4 доказана. Очевидно, что функции х, в базисе { I-»JC2, х\ 4 хг) можно реализовать абсолютно надежно. Константы 1 и 0 можно реализовать схемами, ненадежность которых асимптотически не больше є2 при є - 0 (далее примеры 2.2 и 2.3). Пример 2.2. При єє(0; 1/16] константу 1 в базисе {хі- хг, x\-f xi) можно реализовать такой схемой А, что Р(А) є2 + 8є3. Действительно, моделируя формулу (xi-/ xi)-f (x\- xi), строим схему S\ из трех элементов, реализующую константу 0. Используя леммы 1.4 и 1.5, найдем вероятность ошибки на выходе схемы S\: Р\ = є2 + є2(1 -- є)2(1 - 2є)2 + 2s2(l - є)(1.- 2s) 4є2 при єє(0; 1/16]. Моделируя формулу (xi -f x\) - (x\ - x{), строим схему 5г из трех элементов, реализующую константу 1. Используя леммы 1.4 и 1.5, найдем вероятность ошибки на выходе схемы S2: Ро = ъ2 + s2(l - є)2(1 - 2s)2 + 2є2(1 - є)(1 - 2є) 4є2 при se(0; 1/16]. Построим схему 3. Для этого возьмем импликатор, первый вход которого соединим с выходом схемы S\, а второй - 5г. Вычислим ве 40 роятность ошибки на выходе построенной схемы .%. Она удовлетворяет \ А 4 1 1 "Ї неравенству: Ро г+ 16є (1 - 2є) + 8є (1 - 2є) є + 8s . Схема S3 является искомой схемой А. Пример 2.3. При ЕЄ(0; 1/16] константу 0 в базисе {х\- Х2, x\-f xi) можно реализовать такой схемой В, что Р(В) є2 + 8є3. Действительно, используем схемы Si и S2 из примера 2.2 для построения схемы S3, реализующей константу 0: возьмем антиимпликатор, первый вход которого соединим с выходом схемы Si, а второй - Si- Вычислим вероятность ошибки на выходе построенной схемы S3. Она удовлетворяет неравенству: Pi є + 16є (1 - 2s) + 8s (1 - 2є) є + 8є . Схема S3 является искомой схемой В.
Нижние оценки ненадежности схем при инверсных неисправностях на входах элементов
Найдем нижние оценки ненадежности схем базисах В\ - В\%. Нижняя оценка ненадежности схем, реализующих булевы функции в базисе {xi I Хг), получена в теореме 3.1. Пусть К\{п) - множество функций х-, и константа 1, где / = 1,п. Теорема 3.1. [16] Пусть єє(0; 1/4], f(x) - булева функция,/ g K\{ri) и S - любая схема, реализующая/в базисе {х\ хг}. Тогда P(S) 2є - є2. Из теоремы 3.1 следует, что любая схема, удовлетворяющая условиям теоремы 2.3 и реализующая булеву функцию /(х),/й К\{п), является асимптотически наилучшей по надежности и функционирует с ненадежностью, асимптотически равной 2є при s -» 0. Число функций в классе К\{п) равно п + 1 и мало по сравнению с общим числом 22" булевых функций от п переменных. Таким образом, показано, что почти все булевы функции, кроме х,- и константы 1, в базисе {xi 1x2} можно реализовать схемами, ненадежность которых асимптотически равна 2s при є -» 0. Очевидно, функции х,- можно реализовать абсолютно надежно. Поскольку ненадежности двойственных схем при инверсных неисправностях на входах элементов равны [16], то доказанные утверждения справедливы в базисе {хі хг}, двойственном базису {х\ \хг) для функций f К2(п), где Ki(ri) - множество функций х,- и константа 0, где / = 1, и. 2. Въ = { і- л Х\Ч хг)
Нижние оценки ненадежности схем, реализующих булевы функции в базисе {xi-»x2, xi -Ахг}, получены в теореме 3.2. Пусть з(л) - множество функций Xi, Хг, ..., х„, 0 и 1. Теорема 3.2. Пусть еє(0; 1/4], f(x) - булева функция, f Къ(п) нелюбая схема, реализующая/в базисе {х\- х2, хі -frx2}. Тогда P(S) 2s - є2. Доказательство. Пусть/- булева функция, удовлетворяющая условиям теоремы, a S - произвольная схема, ее реализующая. Схема S содержит, по крайней мере, один элемент. Возможны два случая. 1. Выходной элемент Е является импликатором. Тогда для вероятностей ошибок элемента Е (см. лемму 1.4) имеем: рх = 2s - є2 и р = є2. По лемме 1.9, учитывая замечание 1.1, при єє(0; 1/4] верно неравенство P(S) 2s - є2, т.е. утверждение теоремы верно. 2. Выходной элемент Е является антиимпликатором. Тогда для вероятностей ошибок элемента Е (см. лемму 1.5) имеем: р = 2г - є2 и р1 = Б2. ПО лемме 1.9, учитывая замечание 1.1, при єє(0; 1/4] верно неравенство P(S) 2є - є2, т.е. утверждение теоремы верно. Теорема 3.2 доказана. Из теоремы 3.2 следует, что любая схема, удовлетворяющая условиям теоремы 2.4 и реализующая булеву функцию f(x),f$ К п), является асимптотически наилучшей по надежности и функционирует с ненадежностью, асимптотически равной 2є при є - 0. Число функций в классе К (п) равно 2 + п и мало по сравнению с общим числом 2Г булевых функций от п переменных. Очевидно, что функции JC, в базисе {х\- хі, хі-/ хг} можно реализовать абсолютно надежно. Утверждение о нижних оценках ненадежности схем, реализующих константы 1 и 0 в базисе {х\- Х2, Х\Ч хг) содержат теоремы 3.3 и 3.4.
Теорема 3.3. Пусть єє(0; 1/4] и схема А - любая схема, реализующая константу 1 в базисе {xi- x2, i -Ax2}, тогда Р(А) s2. Доказательство. Пусть А - произвольная схема, реализующая константу 1. Выделим в ней выходной элемент Е. Каким бы он ни был в рассматри 67 ваемом базисе, для него/? є2. При єє(0; 1/4] применима лемма 1.9, поэтому (см. замечание 1.1) Р(А) є2. Теорема 3.3 доказана. Из теоремы 3.3 следует, что любая схема, удовлетворяющая условиям примера 2.2 и реализующая константу 1 в базисе {хі- х2, хі-/»х2}, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной є2 при є -» 0. Теорема 3.4. Пусть єє(0; 1/4] и схема А - любая схема, реализующая константу 0 в базисе {хі-»х2, х\ -/»х2}, тогда Р(В) є2. Доказательство такое же, как и в теореме 3.3. Из теоремы 3.4 следует, что любая схема, удовлетворяющая условиям примера 2.3 и реализующая константу 0 в базисе {хі-»х2, і -/» 2}, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной є2 при є -» 0. Таким образом, показано, что почти все булевы функции, кроме х,- и констант 0 и 1, в базисе {xi- x2, x\-f xi} можно реализовать схемами, ненадежность которых асимптотически равна 2є при є -» 0. Функции х,- можно реализовать абсолютно надежно, а константы 1 и 0 можно реализовать схемами, ненадежность которых асимптотически равна є2 при є -» 0. 3. В4 = {хг+Хг, JCijt2} Нижняя оценка ненадежности в базисе (хі- х2, Хіх2} получена в теореме 3.5. Напомним, что К\(п) - множество функций вида х;- и константа 1, где / = 1,и. Теорема 3.5. Пусть єє(0; 1/4], Дх) - булева функция, ft K\(ri) и S любая схема, реализующая/в базисе {хі-»х2, хіх2}. Тогда P(S) 2є - 2є . Доказательство. Пусть/- булева функция, удовлетворяющая условиям теоремы, a S - произвольная схема, ее реализующая. Схема S содержит, по крайней мере, один элемент. Возможны два случая. 1. Выходному элементу Ei приписана функция Ф. Для него вероятности ошибок на выходе равны: Р0(01) = Ро(Щ = 2є - 2є2 =р. При єє(0; 1/4] применима лемма 1.9, поэтому (см. замечание 1.1) P(S) 2є - 2є2. 2. Выходному элементу Ei приписана функция -». Для него вероятность ошибки на выходе равна: Л(10) = 2є - є2 = р1. При єє(0; 1/4] применима лемма 1.9, поэтому (см. замечание 1.1) P(S) 2є - 2є2. Теорема 3.5 доказана. Из теоремы 3.5 следует, что любая схема, удовлетворяющая условиям теоремы 2.5 и реализующая булеву функцию f(x),f Ki(ri), является асимптотически наилучшей по надежности и функционирует с ненадежностью, асимптотически равной 2є при s -» 0. Таким образом, показано, что почти все булевы функции, кроме х,- и константы 1, в базисе {хі- 2, i 2} можно реализовать схемами, ненадежность которых асимптотически равна 2є при є -» 0. Очевидно, функции х,- можно реализовать абсолютно надежно.
Сложность асимптотически наилучших по надежности схем при инверсных неисправностях на входах элементов
Оценим сложность асимптотически наилучших по надежности схем в базисах В\ - В\% при инверсных неисправностях на входах элементов, используя теоремы 4.1 и 4.2. Теорема 4.1 [15]. Пусть В - произвольный полный базис, к - сложность минимальной схемы &, реализующей функцию штрих Шеффера х{\х2 с вероятностями ошибок на выходе /?0 (00) = а, /? (01) = J3, р 0{Щ = 5, р\(\ 1) = т и ц. = тах{а, р, б, т}. Тогда при цє(0; \/600к] произвольную булеву функцию /от п переменных можно реализовать такой схемой 5, что 1(5) 56-к-2"/п и Р(5) 7ц. Теорема 4.2 [15]. Пусть 5" - схема, реализующая произвольную булеву функцию / в базисе В, Sg - схема, реализующая функцию голосования g(x\, Х2, хг) = х\Х2 v х&з v хг х3 в том же базисе. Тогда можно построить схему 1(/(5), реализующую функцию/ для которой 1(1)/(5)) = 31(5) + L(Sg) ; 31(5), 5)) (5) + (52). Теоремы 4.1 и 4.2, доказанные в работе [15] для произвольных неисправностей функциональных элементов, используются нами далее для случая инверсных неисправностей на входах элементов.
Доказательство. Построим схему S, реализующую функцию голосования g(xi, Х2, Хз) = од v х\Хз v х2хз, из шести элементов, моделируя формулу [(( i Ui) I ( 21 2)) 1 з] I C i 1) (рис. 4.1). L(S) = 6. Найдем вероятности ошибок на выходе схемы S: Л(000) 2є + 2є2, Рі(001) 5є, Рі(ОЮ) 4s, Ро(ОП) 6s, Л(ЮО) 4s, Ро(ЮІ) 6s, Ро(ПО) 3s, P0(\U) 9s2. Следовательно, P(S) 6s. Найденную оценку ненадежности можно улучшить с помощью схемы ф(5), удовлетворяющую условиям теоремы 2.1, используя в качестве схемы Sh, реализующей функцию хх\х2, один базисный элемент. Вероятности ошибок на выходе схемы Sh равны: р 0(00) = s2; рЦОІ) = є - s2; p 0(\0) = є - є2; р\ (11) = 2є - 2є2. Полагая а = р\ (00) = s2, р = 8 = р\ (01) = р\ (10) = є - s2, т = = p\{\ 1) = 2є- 2є2, при єє(0; 1/1200] применим теорему 2.1 и по схеме S построим схему ф(5), ненадежность которой Р(ф(5)) max{2s + 96s2,225s2} 2є + 96є2, а сложность І(ц/(5)) = 15. Применяя теорему 2.1 еще раз, получим схему ф2(5), для которой Р(ф2(5)) max{2s + 16є2 + 1144s3 + 18048є4, 49s2 + 2648s3 + 35720s4} 2є + 17s2, L(q \S)) = 63 при єє(0; 1/1200]. Рис. 4.1 В качестве схемы Sg, реализующей функцию голосования, возьмем схему ф2(), поэтому P(Sg) 2є + 17є2 и L(Sg) = 63 при єє(0; 1/1200]. Возьмем три экземпляра схемы S, удовлетворяющей условиям леммы 4.1, и соединим их выходы с входами схемы Sg.
Доказательство. Возьмем схему S, удовлетворяющую условиям теоремы 4.3, применим к ней операцию ц/, выбрав в качестве Sg схему, использованную в доказательстве теоремы 4.3. Получим схему ij/(5). Поскольку оценка сложности схемы у(5) асимптотическая (по числу п), сложность схемы Sg на эту оценку не влияет, её можно не вычислять.
Поскольку оценка сложности схемы ц/(5) асимптотическая (по числу переменных п функции/), в качестве схемы Sg можно брать схему, удовлетворяющую по надежности условиям теорем второй главы в соответствии с рассматриваемым базисом. Сложность такой схемы можно не находить, поскольку L(Sg) от п не зависит.
Сравнивая результаты М.А. Алехиной с результатами теорем 4.3 и 4.4, приходим к выводу, что произвольную булеву функцию в базисе {х\ I хг) можно реализовать схемами меньшей сложности, но с большей ненадежностью.
Таким образом доказано, что в базисе {xi \xi) при инверсных неисправностях на входах элементов почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, ненадежность которых асимптотически равна 2є при s - 0. Сложность этих схем для почти всех булевых функций по порядку равна сложности схем, построенных только из надежных элементов.
Ненадежности двойственных схем при инверсных неисправностях на входах элементов равны [15], поэтому результаты, полученные в базисе {х\ {xi}, справедливы в базисе {хііхг}. 2. Въ = {xi- x2, x\-f xi} Утверждение о сложности асимптотически наилучших по надежности схем в базисе {ху- хг, х\фхг} содержит теорема 4.5, для доказательства которой воспользуемся леммой 4.2.
Таким образом доказано, что в базисе {х\- хг, x\-frxi} при инверсных неисправностях на входах элементов почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, ненадежность которых асимптотически равна 2є при є - 0. Сложность этих схем для почти всех булевых функций по порядку равна сложности схем, построенных только из надежных элементов.
