3 (1132839), страница 7
Текст из файла (страница 7)
Следовательно,(β, γ) = (β, γb) ⊕ (0, . . . , 0, γb ⊕ γ) = (β, γb) ⊕ α,| {z }mгде ν (α) < 2q−m . Таким образом, система ∆ образует покрытие куба B m .С другой стороны, из m-регулярности δ следует m-регулярность любого из множеств δi , i = 1, . .
. , 2q−m , и поэтомуq−m2X|δi | = 2m 2q−m = 2q .i=1Следовательно, система ∆ образует разбиение куба B q .Лемма доказана.Замечание. Если в условиях леммы α = (α1 , . . . , αλ ) = ν −1 (j−αjна δj .1), то gi ≡ xi+mПрименим технику моделирования ФАЛ из ДУМ переменными для синтеза формул в стандартном базисе.Теорема 7.1 (ср. [14]). Для любой ФАЛ f , f ∈ P2 (n), в UΦсуществует реализующая ее формула Ff , для которой2n2 log log n + O (1)L (Ff ) 61+.(7.1)log nlog nДоказательство.
Пусть параметры m, s и p удовлетворяютсоотношениям m2ms62 , p=, m + p · 2s 6 n,sа G — стандартное ДУМ порядка m и высоты s, для которого |G| = λ 6 p · 2s (см. §6). Пусть, далее, q = m + λ и,следовательно, q 6 n, а ∆ = (δ1 , . . . , δ2λ ) — разбиение куба→−B q , полученное по лемме 7.1 для системы ФАЛ G .Введение55Положим x0 = (x1 , . . . , xq ) и заметим, что произвольнаяФАЛ h, h ∈ P2 (q), на любой компоненте δi , i ∈ [1, 2λ ], в силуее m-регулярности совпадает с некоторой ФАЛ ĥ(x1 , .
. . , xm ).При этом ФАЛ ĥ равна дизъюнкции p ФАЛ из ДУМ G, каждая из которых в силу леммы 7.1 совпадает на δi с буквойодной из БП xm+1 , . . . , xq . Следовательно, ФАЛ h совпадаетна δi с ЭД ранга p от указанных БП.Для ФАЛ f (x) из P2 (n), где x = (x1 , . . . , xn ), x00 =(xq+1 , . . . , xn ) рассмотрим ее представление в видеf (x) =σ_=q+1xq+1· · · xσnn σ 00 =(σq+1 ,...,σn )=2q−m_i=12q−m_i=1xix0 fσ00 x0 =x_0ix σq+1xq+1· · · xσnn Jσ00,i x , (7.2)0σ 00 =(σq+1 ,...,σn )где x (x0 ) — характеристическая ФАЛ множества δi , i = 1, . . .
, 2q−m ,iа ЭД Jσ00,i ранга p от БП xm+1 , . . . , xq , совпадает на δi с ФАЛfσ00 (x0 ) = f (x0 , σ 00 ).e f с подПостроим для ФАЛ f на основе (7.2) формулу Fнятыми отрицаниями, которая имеет видλef =F2_Ai (x0 )Fn−q x00 , Je0,i , . . . , Je1,i ,i=1где Fn−q (x00 , y0 , . . . , y2n−q −1 ) — бесповторная по информационным БП формула из леммы 2.3, реализующая ФАЛ µn−q ,а Ai , i ∈ [1, 2λ ], — совершенная ДНФ ФАЛ x .ie f опПусть, далее, формула Ff получается из формулы Fтимизацией ЭД по числу отрицаний, то есть заменой каждойЭД Jσ00 ,i вида xj1 ∨. .
.∨xjt ∨xjt+1 ∨. . .∨xjp , где t 6 p, формулой56ВведениеJbσ00 ,i вида xj1 ∨. . .∨xjt ∨xjt+1 · · · xjp . Заметим, что число ФЭ ¬во всех формулах Ai , i ∈ [1, 2λ ], равно половине их суммарного ранга, что в каждой формуле вида Jbσ00 ,i имеется одинФЭ ¬, и напомним (см. лемму 2.3), что R(Fn−q ) 6 3 · 2n−q иL¬ (Fn−q ) 6 2n−q . Следовательно, в силу леммы 2.1 главы 2,L&,∨ (Ff ) 6 2q−m q · 2m + (p − 1)2n−q + 3 · 2n−q , (7.3)L¬ (Ff ) 6 q · 2q−1 + 2n−m .(7.4)Выбирая значения параметров m и s так, чтоm = b3 log log nc − 1,s = blog n − 2 log log nc − 1,и подставляя эти значения в (7.3), (7.4), получим неравенство n 2n2L (Ff ) 6,+Olog n − 2 log log nlog2 nиз которого для сложности формулы Ff следует оценка (7.1).Теорема доказана.Следствие. Из (7.1) с учётом нижних оценок следствияиз теоремы 5.1 вытекает, чтоLΦ (n) ∼2n.log ne f и Ff вместоЗамечание.
Если при построении формул F00подформулы Fn−q (x , y0 , . . . , y2n−q −1 ) из леммы 2.3 взять формулу Mn−q из леммы 9.2 от тех же БП, а к полученной в результате формуле применить оптимизацию по глубине (теорема 2.1 главы 2), то построенная указанным способом дляФАЛ f формула F̌f будет помимо (7.1) удовлетворять такженеравенствуD(F̌f ) 6 n − log log n + O(1),(7.5)Введение57из которого с учётом нижних оценок следствия теоремы 5.1,вытекает, чтоD(n) = n − log log n ± O(1).§8Асимптотически наилучший метод синтезаконтактных схем. Синтез схем для ФАЛ изнекоторых классовЗаметим сначала, что асимптотически наилучший метод синтеза СФЭ из §6 без существенных изменений переносится накласс контактно-вентильных схем (КВС), в которых нарядус контактами можно использовать «вентили», то есть ориентированные ребра, проводящие только в направлении своейориентации.
Действительно, для любой ФАЛ f , f ∈ P2 (n),e f может быть получена на осреализующая ее (1, 1)-КВС Σнове разложения (4.5) так же, как и СФЭ Σf из теоремы 6.1.Она является результатом корректной суперпозиции видаe f = Σ00 (Σ0 ), где Σ00 — (2n−q , 1)-КД от БП x00 , а (1, 2n−q )ΣКВС Σ0 реализует систему всех ФАЛ вида fσ00 (x0 ) , σ 00 ∈B n−q . При этом схема Σ0 по-прежнему содержит в каче→−стве подсхемы (1, λ)-КС ΣG , реализующую систему ФАЛ Gна основе леммы 1.2, и реализует каждую ФАЛ g (x0 ) типаfσ00 (x0 ) на основе ее представления (6.1) в виде дизъюнкцииg = g1 ∨ · · · ∨ gp с помощью присоединения входов вентильной звезды порядка p к соответствующим выходам КС ΣG(см. рис.
8.1a), которое является корректной суперпозициe f при тех же значенияхей. Сложность построенной КВС Σпараметров, что и в теореме 6.1, будет удовлетворять неравенству (6.5).Напомним (см. §6), что в силу специфики стандартного ДУМ G вместо представления (6.1) для ФАЛ g можноиспользовать эквивалентное (6.1) представление (6.2) видаg = ψ1 · g1 ∨ · · · ∨ ψp · gp(8.1)58Введениеg1•1•...ΣG•&9 g...•gpa)g1•1•...ΣG•ψ1...•gψpgpb)Рис. 8.1: Корректная реализация дизъюнкции ФАЛg1 , .
. . , gp в классах КВС и ИКСи на его основе реализовать ФАЛ g с помощью корректной суперпозиции т.н. итеративно-контактных схем, показанной на рис. 8.1b, где ФАЛ ψ1 , . . . , ψp управляют проводимостью соответствующих контактов. Асимптотически наилучший метод синтеза КС связан с «моделированием» этойсуперпозиции и представления (8.1) на компонентах подходящего m-регулярного разбиения куба B m+p .Пусть δ̌ — m-регулярное множество наборов куба B m+p ,→−соответствующее системе ФАЛ ψ = (ψ1 , .
. . , ψp ) (см. рис. 8.2a),а ∆ = (δ1 , . . . , δ2p ) — построенное для нее по лемме 7.1 разбиение куба B m+p . Заметим, что любая ФАЛ g, g ∈ P2 (m + p),Введение59. . . xm−1 xm ψ1 x1 0 ... 010... 0101.....π1....1...0...0.....π2....0.........0...0.....πp....1110ψ200...011...1.... .
. ψp00... ...000... ...0... ...00.. . . ..011...1δ̌a)g1•1αm+1xm+1...ΣG•gpǧαm+pxm+pb)Рис. 8.2: m-регулярное множество δ̌ и связанная с нимсуперпозиция КС60Введениена любой компоненте этого разбиения вида δ̌ ⊕ α, гдеα = (0, .
. . , 0, αm+1 , . . . , αm+p ),| {z }mсовпадает с ФАЛααm+pm+1· gp ,ǧ = xm+1· g1 ∨ . . . ∨ xm+p(8.2)где gi = gψi ∈ G(i) , i = 1, . . . , p. При этом ФАЛ ǧ может быть реализована в результате операции присоединенияαm+pαm+1звезды из контактов вида xm+1, . . . , xm+pк выходам (1, λ)→−КС ΣG , реализующей систему ФАЛ G , так, как это показанона рис.
8.2b. Заметим также, что указанная операция суперпозиции является корректной на множестве наборов δ̌ ⊕ αв силу того, что из контактов присоединяемой (p, 1)-КС налюбом наборе этого множества проводит только один.Теорема 8.1 (ср. [14]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая ее КС Σf такая, что2nL (Σf ) 6n1+O1√n(8.3)Доказательство. Пусть q = m + p, а ∆ = (δ1 , . . . , δ2p ) —описанное выше разбиение куба B q , с помощью которогоФАЛ f можно представить в видеp000f x ,x=2_i=1xx0i_σq+1xq+1· · · xσnn ǧσ00 ,i x0 ,σ 00 =(σq+1 ,...,σn )(8.4)где x — характеристическая ФАЛ δi , а в качестве ФАЛ fσ00 ,iiпри всех σ 00 ,σ 00 ∈ B n−q , и i, i ∈ [1, 2p ], берется ФАЛ ǧσ00 ,i вида(8.2), совпадающая с ФАЛ fσ00 (x0 ) на компоненте δi = δ̌ ⊕ α.Введение61Пусть ΣG — (1, λ)-КС, которая реализует систему ФАЛ→−G по их совершенным ДНФ на основе контактного дерева(см.
лемму 1.2 и оценку (1.2)). Для каждого i, i = 1, . . . , 2p ,построим (1, 2n−q )-КС Σ0i (см. рис. 8.3a), которая содержитКС ΣG в качестве подсхемы и реализует каждую ФАЛ ǧσ00 ,iвида (8.2) с помощью корректной на множестве наборовδi суперпозиции, показанной на рисунке 8.2b. Пусть, далее, (1, 2n−m )-КС Σ0 получается в результате отождествления входов у построенных выше КС Σ0i , i ∈ [1, 2p ], и реализует систему из всех ФАЛ вида ǧσ00 ,i , где σ 00 ∈ B n−q , i ∈ [1, 2p ].Заметим, что при этом выполняются неравенстваL (ΣG ) 6 λ2m+1 ,L Σ0i 6 L (ΣG ) + p2n−q ,L Σ0 6 p2n−m + λ2q+1 .(8.5)Построим, наконец, каскадную (2n−m , 1)-КС Σ00 , котораяσq+1реализует столбец из всех ФАЛ вида x (x0 )·xq+1· · · xσnn , гдеii ∈ [1, 2p ] и σ 00 = (σq+1 , . .
. , σn ) ∈ B n−q . Эта КС получаетсяв результате объединения 2p схем типа (2n−q , 1)-КД от БПx00 , к выходам которых присоединены входы (2p , 1)-КС, реализующей столбец из ФАЛ x , i ∈ [1, 2p ], и получающейсяiиз (2q , 1)-КД от БП x0 в результате соответствующего отождествления входов (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
