Материалы для подготовки к экзамену (2012-2013 учебный год), страница 14

, z2q −1 ) на основе сокращённой ДНФ µq , используя для этого 2q ФЭ & и (2q − 1) ФЭ ∨.b n порядка n, которыйОценка (3.4) достигается на контактном мультиплексоре Σполучается в результате стыковки асимптотически наилучшего контактного де(&)шифратора Σn порядка n (см. лемму 7.2 из [3, глава 4]) с (2n , 1)–контактнойзвездой из 2n контактов БП y0 , . . . , y2n −1 (см.

рис. 5.7 в [3, глава 2]).e n , которая реализуетАналогичным образом можно построить π–схему Σn+1neФАЛ µn со сложностью L(Σn ) ∼ 2и содержит o(2 ) размыкающих контактов. Для этого достаточно (см. доказательство леммы 7.2 из [3, глава 4]) каждую68Глава 2.из характеристических ФАЛ χ1 , . . . , χ2p реализовать соответствующей канонической π–схемой. Кроме того, для построения m–регулярного разбиения единичногокуба от БП x0 = (x1 , . . .

, xq ), на компонентах которого ЭК от БП x0 моделируются,как правило, с помощью БП, а не их отрицаниями, достаточно использовать технику [?]. Искомая формула, удовлетворяющая (3.3), получается моделированиемe n.π–схемы ΣКонтактный мультиплексор Σ̌ порядка n из ориентированных контактов, сложность которого даёт оценку (3.5) имеет вид Σ̌ = Σ00 (Σ0 ), где для q = dn/2e Σ0 и Σ00 —(1, 2q )– и (2n−q , 1)–контактные деревья от БП x0 = (x1 , . . .

, xq ) и x00 = (xq+1 , . . . , xn )соответственно, построенные из контактов, ориентированных от входов к выходам. При этом каждый выход zν(σ0 ) , где σ 0 = (σ1 , . . . , σq ) ∈ B q КС Σ0 , на котоσром реализуется ЭК K 0 = xσ1 1 . . . xq q , соединяется с каждым входом uν(σ00 ) , гдеσ 00 = (σq+1 , . . . , σn ) ∈ B n−q , КС Σ00 , для которого функция проводимости от uν(σ00 )σq+1.

. . xσnn , контактом БП yν(σ0 ,σ00 ) , ориентированным пок выходу Σ00 равна K 00 = xq+1направлению от zν(σ0 ) к uν(σ00 ) .Теорема доказана.§4Сферические функции. Сложность линейной и других функций в классе контактных схем и самокорректирующихся контактных схемФункцию f из P2 (n) будем называть α–сферической, где α ∈ B n , если для любыхнаборов β и γ из B n , отличающихся от α ровно в одном и ровно в двух разрядах соответственно, f (β) = 0 и f (γ) = 1. При этом 0̃–сферическую ФАЛ, будемназывать просто сферической. Пусть sin , где 0 6 i 6 n, — элементарная симметрическая ФАЛ с рабочим числом i, то есть ФАЛ от БП x1 , .

. . , xn , обращающаясяв 1 на всех тех наборах, которые содержат ровно i единиц. Заметим, что ФАЛ s23является сферической, а ФАЛ s13 — 1̃–сферической и что ФАЛ ln (ln ) являетсяnn ), содержащего всеα–сферической для всех наборов α из множества Bчёт.(Bнеч.наборы B n с чётным (соответственно нечётным) числом единиц.Наряду с КС из «обычных» (абсолютно надёжных) контактов будем рассматривать КС из ненадёжных контактов, которые могут выходить из строя в результатеобрыва, когда ФАЛ проводимости контакта становится равной 0 или замыкания,когда эта ФАЛ становится равной 1. Будем говорить, что КС Σ корректирует p,p > 0, обрывов и q, q > 0, замыканий, если она эквивалентна любой КС, получающейся из Σ в результате обрыва не более чем p, и замыкания не более чем qконтактов.Лемма 4.1. Если КС Σ реализует сферическую ФАЛ f из P2 (n), то в Σ встречаются замыкающие контакты всех БП x1 , .

. . , xn , причём контакты всех этихтипов, за исключением, быть может, двух, встречаются в ней не менее двухраз.§4. Сферические функции69Доказательство. Из сферичности ФАЛ f следует, что она существенно зависит отвсех своих БП и не является антимонотонной ни по одной из них. Следовательно,в Σ имеются замыкающие контакты всех БП x1 , .

. . , xn . Обозначим через a1 и a2полюса КС Σ, а через E1 (E2 ) — множество тех её контактов, каждый из которыхявляется первым (соответственно последним) замыкающим контактом для какойлибо проводящей цепи КС Σ идущей от a1 к a2 .Докажем, сначала, что E1 ∩E2 = ∅. Действительно, пусть E1 ∩E2 6= ∅ и поэтомув КС Σ имеется контакт K вида xi , 1 6 i 6 n, который является первым (последним) замыкающим контактом проводящей цепи C1 (соответственно C2 ), идущейот a1 к a2 .

Для j = 1, 2 обозначим через Cj0 и Cj00 начальную (до контакта K) изаключительную (после контакта K) подцепи цепи Cj . Пусть, далее, цепь C состоит из начальной подцепи C10 , контакта K и заключительной подцепи C200 , еслицепи C1 и C2 проходят контакт K в одном направлении и состоит из начальнойподцепи C10 , которая сразу переходит в заключительную подцепь C200 в противномслучае.

Заметим, что подцепи C10 и C200 по построению состоят только из размыкающих контактов, среди которых нет контактов вида xi и поэтому цепь C будетпроводить на набореβ = (0, . . . , 0, 1, 0, . . . , 0),| {z }iчто противоречит сферичности ФАЛ f .Докажем теперь, что каждое из множеств Es , s = 1, 2, содержит замыкающиеконтакты всех БП x1 , . . . , xn за исключением, быть может, одной. Действительно,из сферичности ФАЛ f следует, что для любых i и j, 1 6 i < j 6 n, в КС Σ имеетсяцепь C, идущая из a1 в a2 , которая проводит на набореγ = (0, . .

. , 0, 1, 0, . . . 0, 1, 0, . . . , 0)| {z }| {z }in−j+1и состоит из замыкающих контактов БП xi , xj , а также размыкающих контактовостальных БП. Заметим, что в C не могут отсутствовать замыкающие контактыни одной из БП xi , xj , так как иначе ФАЛ f обращалась бы в 1 на некоторомнаборе β, содержащем ровно одну 1. Следовательно, первый из контактов вида xi ,xj на цепи C войдёт в E1 , а последний — в E2 и поэтому как в E1 , так и в E2контакты вида xi , xj не могут отсутвствовать одновременно.

Таким образом, вомножестве E1 ∪ E2 не могут отсутствовать замыкающие контакты трёх и болееБП.Лемма доказана.Следствие 1. Если КС Σ реализует α–сферическую ФАЛ f из P2 (n), где α =(α1 , . . . , αn ), то контакты всех типов xα1 1 , . . . , xαnn встречаются в Σ по крайнеймере t = 1 раз, причём контакты всех этих типов за исключением, быть может,двух встречаются в Σ не менее r = 2 раз.70Глава 2.Следствие 2. Если КС Σ корректирует p, p > 0 обрывов, то в условиях следствия 1 имеем t > p + 1 и r > 2 d(p + 1)/2e, то естьp+1L(Σ) > 2(p + 1) + 2(n − 2).2Теорема 4.1. При любом натуральном n имеют место равенстваLК (s1n ) = LК (snn−1 ) = 3n − 2,а если n > 2, тоLК (ln ) = LК (ln ) = 4n − 4.(4.1)Доказательство. Все необходимые верхние оценки могут быть получены с помощью метода каскадов (см., например, § 3 из [3, гл.

4]).n−1 не являетсяПусть КС Σ реализует ФАЛ f = sn−1n . Из того, что ФАЛ snни монотонной ни антимонотонной ни по одной из своих БП, следует что в КС Σвстречаются константы всех типов x1 , . . . , xn , x1 , . . . , xn . Заметим, что при этомконтакты всех типов x1 , . . . , xn за исключением, быть может, двух встречаютсяв Σ не менее двух раз. Действительно, пусть, например, контакты типов x1 , x2 ,x3 встречаются в Σ только по одному разу. Тогда, подставив константу 1 вместовсех БП x4 , . .

. , xn , мы получим КС Σ0 , которая реализует сферическую ФАЛ s23 исодержит только по одному замыкающему контакту своих БП, что противоречитлемме 4.1. Следовательно,L(Σ) > 3n − 2.Случай, когда КС Σ реализует ФАЛ f = s1n , сводится к рассмотренному случаюинвертированием БП.Пусть теперь n > 2 и КС Σ реализует ФАЛ f = ln . Из того, что ФАЛ f являn , в силу (1.1) и следствия 1 из леммы 4.1ется α–сферической при любом α из Bнеч.вытекает неравенство:2n−2 L(Σ) > 2n−1 (2n − 2),из которого следует, чтоL(Σ) > 4n − 4.Случай, когда f = ln , рассматривается аналогично.Теорема доказана.Для ФАЛ f и p > 0, q > 0 определим «самокорректирующуюся» сложностьLК(p,q) (f ) как минимальную из сложностей тех КС, реализующих ФАЛ f , которыекорректируют p обрывов и q замыканий.Теорема 4.2.

При любоых натуральных p и n, n > 2, имеют место равенстваp+1К(n − 2),(4.2)L(p,0) (ln ) = 4(p + 1) + 42§5. Теорема Храпченко71LК(1,1) (ln ) = 8n.(4.3)Доказательство. Нижняя оценка в (4.2) доказывается аналогично нижней оценке (4.1) с использованием следствия 2 леммы 4.1. Верхнюю оценку (4.2) в случаеp = 1 даёт схема из [?, гл. 3, § 1], которая получается из КС, построенной для линейной ФАЛ по методу каскадов, добавлением 4 контактов.

В общем случае p > 1искомая КС представляет собой результат параллельного соединения dbp + 1c 2eуказанных выше самокорректирующихся КС и ((p + 1) − 2 b(p + 1)/2c) КС, построенных по методу каскадов.Верхнюю оценку в (4.3) даёт КС, которая получается в результате последовательного соединения двух упомянутых выше КС для линейной ФАЛ, корректирующих 1 обрыв. Для доказательства нижней оценки заметим, что в силу теоремы омаксимальном потоке и минимальном разрезе в КС Σ, которая реализует ФАЛ fи корректирует p обрывов, для любого набора α, α ∈ Nf , сущестует не менее,чем (p + 1) не пересекающихся по контактами проводящих на наборе α цепей, соединяющих полюса Σ. Если при этом f = lnσ и КС Σ корректирует q замыканий, токаждая из указанных цепей иемет длину не меньше чем (q + 1)n, и следовательно,|E(Σ|α )| > (p + 1)(q + 1)n(4.4)для любого набора α, α ∈ Nf . Из (4.4) в силу (1.1) при δ = Nf вытекает, чтоσLК(p,q) (ln ) > (p + 1)(q + 1)n.Теорема доказана.§5Теорема Храпченко.