Материалы для подготовки к экзамену прошлых лет, страница 6

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

. , y2n −1 (см. рис. 5.7 в [2, глава 2]).e n , которая реализует ФАЛАналогичным образом можно построить π–схему Σe n ) ∼ 2n+1 и содержит o(2n ) размыкающих контактов. Дляµn со сложностью L(Σэтого достаточно (см. доказательство леммы 7.2 из [2, глава 4]) каждую из характеристических ФАЛ χ1 , . . . , χ2p реализовать соответствующей каноническойπ–схемой. Кроме того, для построения m–регулярного разбиения единичного куба от БП x0 = (x1 , . . . , xq ), на компонентах которого ЭК от БП x0 моделируются,как правило, с помощью БП, а не их отрицаниями, достаточно использовать технику [11]. Искомая формула, удовлетворяющая (2.3), получается моделированиемe n.π–схемы ΣКонтактный мультиплексор Σ̌ порядка n из ориентированных контактов, сложность которого дает оценку (2.5) имеет вид Σ̌ = Σ00 (Σ0 ), где для q = n2 Σ0и Σ00 — (1, 2q )– и (2n−q , 1)–контактные деревья от БП x0 = (x1 , . .

. , xq ) и x00 =§3. Сложность линейной функции в классе СФЭ27(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 ) .§3Сложность линейной функции в классе схем из функциональных элементовТе СФЭ из класса UС , которые реализуют линейные ФАЛ ln или ln , будем называтьлинейными схемами порядка n.

ПоложимL (n) = min LС (ln ) , LС ln ,а линейные СФЭ порядка n и сложности L (n) будем называть минимальнымилинейными СФЭ. Из [2] (см. лемму 3.1 гл. 4) следует, что если n > 2, тоL (n) 6 min LС (ln ) , LС ln 6 4n − 4,(3.1)а из теоремы 2.1 в силу незабиваемости множества всех БП линейной ФАЛ вытекает, чтоL (n) > 2n − 2Докажем,что верхняя оценка (3.1) дает точные значение сложностей LС (ln ) иLС ln .Лемма 3.1. Пусть Σ — линейная СФЭ порядка n от БП X (n) и пусть её БП xiпоступает только на вход ФЭ E СФЭ Σ, связанного с вершиной v.

Тогда в случаеE = &(E = ∨) на второй вход ФЭ E поступает ФАЛ 1 (соответственно 0), ав случае E = ¬ СФЭ Σ0 , которая получается из Σ удалением E и объявлением vвходной вершиной БП xi , также является линейной СФЭ порядка n.Доказательство. Из свойств линейной ФАЛ следует, что СФЭ Σ0 реализует отрицание той ФАЛ, которую реализует СФЭ Σ, и потому СФЭ Σ0 тоже являетсялинейной СФЭ порядка n.Пусть теперь E — двухвходовой ФЭ, который соответствует ФАЛ ϕ (y1 , y2 ), ипусть на второй вход E поступает дуга из вершины w. При этом ФАЛ g, котораяреализуется в вершине w, не зависит, очевидно, от БП xi . Предположим, что g 6≡ σ,где σ = 0 в случае ϕ = y1 · y2 и σ = 1 в случае ϕ = y1 ∨ y2 , то есть g|K =αi−1 αi+1σ для некоторой ЭК K вида xα1 1 .

. . xi−1xi+1 . . . xαnn . Тогда в силу особенностейструктуры СФЭ Σ и в силу тождества ϕ (σ, xi ) = σ СФЭ Σ|K реализует константу,что противоречит линейности Σ.Лемма доказана.28Глава 2. Синтез схем для индивидуальных функцийСледствие 1. Степень любого входа минимальной линейной СФЭ порядка n, n >2, не меньше двух.Следствие 2. Справедливы равенстваL (2) = LС (l2 ) = LС l2 = 4.(3.2)Действительно, в соответствии со следствием 1 ранг любой линейной СФЭ порядка 2 не меньше четырех. Поэтому в силу того, что в Σ есть хотя бы один ФЭ¬, справедливо неравенство L (Σ) > 4, из которого в соответствии с (3.1) вытекает(3.2).Теорема 3.1. Для любого натурального n, n > 2, выполняются равенстваL (n) = LС (ln ) = LС ln = 4n − 4.(3.3)Доказательство. В силу (3.1) для доказательства (3.3) достаточно убедиться втом, чтоL (n) > 4n − 4.(3.4)Установим справедливость (3.4) индукцией по n, n = 2, 3, .

. ..При n = 2 неравенство (3.4) выполняется в силу (3.2), что составляет базис рассматриваемой индукции. Для обоснования индуктивного перехода возьмем произвольную минимальную линейную СФЭ Σ порядка n, n > 3, от БП X (n) и покажем,что для некоторых i, i ∈ [1, n], и σ, σ ∈ B, выполняется неравенствоL (Σ) > L Σ|xσi + 4.(3.5)Будем считать, что на каждом шаге преобразования СФЭ Σ в СФЭ Σ00i,σ = Σ|xσiудаляется один ФЭ E с константой на входе. При этом вершина, с которой связан ФЭ E, обьявляется константной входной вершиной типа σ новой схемы, еслина выходе E реализуется константа σ, σ ∈ B, и удаляется вместе с E в остальныхслучаях.

Заметим, что для любой промежуточной схемы Σ0 указанного преобразования выполняется неравенствоL Σ00i,σ 6 L Σ0 − IC Σ0 ,(3.6)где IC (Σ0 ) — число дуг Σ0 , исходящих из её константных входов. Будем предполагать также, что в любой вершине СФЭ Σ00i,σ реализуется неконстантная ФАЛ.Полустепень исхода, то есть число исходящих дуг вершины v СФЭ Σ будемобозначать через d+ (v), а число исходящих из v дуг, которые ведут в вершины,связанные с ФЭ типа Φ, Φ ⊆ Б0 , — через d+Φ (v). Заметим, что для любой вершиныv СФЭ Σ и для любого любого i, i ∈ [1 , n] , выполняются неравенства++++d+¬ (v) 6 1, d (xi ) = d& (xi ) + d∨ (xi ) + d¬ (xi ) > 2,(3.7)первое из которых вытекает непосредственно из минимальности Σ, а второе — изследствия 1 леммы 3.1.

Нетрудно убедиться в том, что неравенство (3.5) выполняется в следующих случаях:§3. Сложность линейной функции в классе СФЭ291. d+ (xi ) > 4 — при любом σ;++2. d+& (xi ) > 2 или d& (xi ) = d¬ (xi ) = 1 — при σ = 0;++3. d+∨ (xi ) > 2 или d∨ (xi ) = d¬ (xi ) = 1 — при σ = 1;Действительно, в каждом из этих случаев СФЭ Σ0 , которая получается при переходе от СФЭ Σ к СФЭ Σ00i,σ в результате удаления d+ (xi ) ФЭ, связанных с входомxi , имеет при d+ (xi ) < 4 не меньше, чем (4 − d+ (xi )), константных входных дуг и,следовательно, в силу (3.6) выполняется (3.5).Таким образом, с учетом (3.7) осталось рассмотреть основной случай — случай,++когда d+& (xi ) = d∨ (xi ) = 1 и d¬ (xi ) = 0 для каждого i, i ∈ [1, n]. В этом случае вСФЭ Σ найдутся два входа, связанные с одним и тем же ФЭ типа & или ∨. Пустьдля определенности, данными входами Σ будут БП x1 и x2 , котороые поступаютна входы одного и того же ФЭ &, связанного с вершиной v.

Пусть при этом втораядуга, исходящая из вершины xi , i = 1, 2, идет в вершину wi , связанную с ФЭ∨, на другой вход которого поступает дуга из вершины ui . Заметим, что в силуминимальности Σ для любого i, i = 1, 2, вершина ui отлична от вершины v, таккак при v = ui в вершине wi реализуется ФАЛ xi .Покажем, что в случае w1 6= w2 неравенство (3.5) выполняется. Действительно,рассмотрим в этом случае СФЭ Σ0 , которая пролучается при переходе от СФЭΣ к СФЭ Σ001,0 в результате удаления двух ФЭ, связанных с вершинами w1 и v, атакже одного ФЭ, связанного с какой-либо вершиной v 0 , в котороую идет дуга изv.

Так как u2 6= v и, следовательно, v 0 6= w2 , то вход x2 схемы Σ0 поступает только на вход ФЭ ∨, связанного с вершиной w2 . Из леммы 3.1 вытекает, что при этомв вершине u2 СФЭ Σ0 реализуется ФАЛ 0, то есть при переходе от Σ0 к Σ001,0 ещёодин ФЭ - ФЭ ∨, связанный с вершиной w2 , — будет удален. Неравенство (3.5) вслучае w1 6= w2 доказано.Пусть, наконец, w1 = w2 и, следовательно, x1 = u2 , x2 = u1 и пусть, для+определенности, либо d+ (v) > 2, либо d+ (v) = d+ (w) = 1 и d+&,∨ (v) > d∨,¬ (w).Рассмотрим СФЭ Σ0 , которая получается при переходе от СФЭ Σ к СФЭ Σ001,0 врезультате удаления двух ФЭ, связанных с вершинами v и w, а также всех тех ФЭ,входы коорых присоединены к v (число таких ФЭ равно d+ (v)). Заметим, что вслучае d+ (v) > 2 неравенство (3.5) вытекает из неравенства L (Σ) − L (Σ0 ) > 4, а0в случае d+ (v) = d+&,∨ (v) = 1 — из неравенства L (Σ) = L (Σ ) + 3 и неравенства+++(3.6), где IC (Σ) > 1. В оставшемся случае d (v) = d∨ (v) = d (w) = d+& (w) = 1 из0вершины v(w) исходит единственная дуга, ведущая в вершину v (соответственноw0 ), связанную с ФЭ ∨ (соответственно &).

В этом случае СФЭ Σ0 имеет в вершинеw2 вход x2 степени 1, поступающий на вход ФЭ &, и, следовательно, в силу леммы3.1 удовлетворяет неравенству L (Σ0 )−L Σ001,0 > 1, из которого, с учетом равенстваL (Σ) − L (Σ0 ) = 3, вытекает (3.5).Теорема доказана.30Глава 2. Синтез схем для индивидуальных функций§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 n сской для всех наборов α из множества Bчет.(Bнеч.четным (соответственно нечетным) числом единиц.Наряду с КС из «обычных» (абсолютно надежных) контактов будем рассматривать КС из нанадежных контактов, которые могут выходить из строя в результатеобрыва, когда ФАЛ проводимости контакта становится равной 0 или замыкания,когда эта ФАЛ становится равной 1.