Материалы для подготовки к экзамену (2012-2013 учебный год) (1156402), страница 7
Текст из файла (страница 7)
Существуют квазибесповторные формулы F¬ , F& и F∨ над базисом Б, которые реализуют ФАЛ x1 , x1 · x2 и x1 ∨ x2 соответственно.Доказательство. В силу полноты системы ФАЛ {ϕi }bi=1 можно построить формулы F0 , F1 от БП y над Б, которые реализуют константы 0, 1 и являются квазибесповторными в связи с отсутствием существенных БП. Из полноты следуеттакже, что среди базисных ФАЛ есть немонотонная ФАЛ ϕ0 (x1 , . . . , xk0 ) и нелинейная ФАЛ ϕ00 (x1 , . .
. , xk00 ). В силу леммы о немонотонной ФАЛ найдётся набор0(α1 , α2 , . . . , αk0 ) из B k и число i, 1 6 i 6 k 0 , такие, чтоϕ0 α1 , . . . , αi−1 , xi , αi+1 , . . . , αk0 = xi .Следовательно, формулаF¬ x = F¬ x, y = ϕ0 Fα1 , . . . , Fαi−1 , x, Fαi+1 , . . . , Fαk0является бесповторной формулой над Б, реализующей ФАЛ x. Положим:F¬(1) (x, y) = F¬ (x) и F¬(0) (x, y) = x.Из доказательства леммы о нелинейной ФАЛ следует, что найдётся такой набор00β = (β1 , . . . , βk00 ) из B k , натуральные числа i и j, 1 6 i < j 6 k 00 , а также константа γ, γ ∈ B, для которыхϕ00 β1 , . . . , βi−1 , xi ⊕ βi , βi+1 , .
. . , βj−1 , xj ⊕ βj , βj+1 , . . . , βk00 = xi · xj ⊕ γ.34Глава 1.Тогда формула F& видаF& x1 , x2 , y = F¬(γ) ϕ00 Fβ1 , . . . , Fβi−1 , F¬(βi ) (x1 , y), (β )Fβi+1 , . . . , Fβj−1 , F¬ j (x2 , y), Fβj+1 , . . . , Fβk00 , yявляется квазибесповторной формулой над Б и реализует ФАЛ x1 · x2 . Квазибесповторная формула F∨ (x1 , x2 , y), которая реализует ФАЛ x1 ∨ x2 , получается изформулы F¬ F& F¬ x1 , y , F¬ x2 , y , y , y«удалением» всех вхождений двух последовательных формул F¬ .Лемма доказана.Распространим операцию сложения двоичных наборов (слов) по модулю 2(см. §4) на тот случай, когда длина второго слагаемого может быть больше длиныпервого.
Для наборов α = (α1 , . . . , αm ) ∈ B m и β = (β1 , . . . , βn ) ∈ B n , где n > m,определим их сумму α ⊕ β как набор γ = (γ1 , . . . , γn ) ∈ B n , который в случаеn = m представляет собой введённую ранее поразрядную сумму по модулю 2 этихнаборов.В случае n > m разобьём слово β на последовательно (слева направо) расположенные и составленные из подряд идущих символов непустые слова β (1) , .
. . , β (k) ,где k > 2 и β (j) ∈ B λj для всех j, j = 1, . . . , k, такие, что:1) λ1 = m и при любом j, j ∈ [2, k − 1], число λj равно числу 1 в слове β (j−1) ;2) число 1 в слове β (k−1) либо равно 0, либо больше, чем λk = (n − m) − λ1 −− λ2 − · · · − λk−1 .Заметим, что указанное разбиение набора β однозначно определяется числом m,m < n.Сопоставим построенной последовательности слов β (1) , .
. . , β (k) последовательность слов α(1) , . . . , α(k) , где α(j) ∈ B λj при всех j, j ∈ [1, k], такую, что:1) α(1) = α и при любом j, j ∈ [2, k − 1], слово α(j) состоит из тех и только тех,(j−1)расположенных в порядке возрастания их номеров, λj разрядов αt,16t6(j−1)(j−1)(j−1)6 λj−1 , вектора α= α1, . . . , αλj−1 , для которых соответствующие(j−1)(j−1)(j−1) им разряды βtвектора β1, .
. . , βλj−1 = β (j−1) равны 1;2) вектор α(k) состоит из λk нулей.Определим искомый вектор γ = α ⊕ β как конкатенацию (последовательность)векторов α(1) ⊕ β (1) , . . . , α(k) ⊕ β (k) и заметим, что при этом уравнение α ⊕ β = γимеет единственное относительно β решение при любых α, α ∈ B m , и γ, γ ∈ B n .§6.35На основе введённой операции при любых β, β ∈ B t , и λ 6 t обычным образом определяется сумма δ ⊕ β, где δ ⊆ B λ , а также сумма g ⊕ β, где g == (g1 , . . . , gλ ) ∈ P2λ (m). При этом последняя сумма является набором длины t,который по-прежнему состоит из ФАЛ системы g или их отрицаний и задаёт m–регулярное множество наборов куба B t .
Заметим также, что любая ФАЛ системы gхотя бы один раз входит в систему g ⊕ β без отрицания, если число 1 в наборе βбольше или равно λ.Пусть G ⊆ P2 (m) и |G| = λ, а ∆ = (δ1 , . . . , δ2q−m ), где q > m, — разбиение куба B q на m–регулярные компоненты. Будем говорить, что разбиение ∆ моделируетФАЛ из G с помощью БП или их отрицаний, если для любого i, i ∈ [1, 2q−m ], любая ФАЛ g, g ∈ G, совпадает на δi с некоторой буквой xσj , где 1 6 j 6 q и σ ∈ B.Компонента δi считается при этом хорошей компонентой разбиения ∆ (относительно множества G) в том случае, когда для любой ФАЛ g, g ∈ G указанноесовпадение имеет место при σ = 1.Лемма 6.2. Пусть G ⊆ P2 (m), |G| = λ, q > m + λ и пусть δi , i = 1, .
. . , 2q−m , —→−m–регулярное разбиение куба B q , которое соответствует системе ФАЛ G ⊕ β,где β ∈ B q−m и ν(β) = i−1. Тогда система множеств ∆ = (δ1 , . . . , δ2q−m ) образуетm–регулярное разбиение куба B q , которое моделирует ФАЛ из G с помощью БПλ−10или их отрицаний и имеет при этом Cq−m+ · · · + Cq−m«плохих» компонент.Доказательство. Покажем сначала, что система множеств ∆ является разбиениемкуба B q . Для этого в силу того, что мощность каждого из них равна 2m , достаточноубедиться в том, что ∆ — покрытие куба B q , то есть любой набор γ, γ ∈ B q , входитхотя бы в одно из множеств δi , i ∈ [1, 2q−m ].Действительно, представим набор γ в виде γ = (α, γ̂), где α ∈ B m , и найдём→−набор β, β ∈ B q−m , который является единственным решением уравнения G (α) ⊕β = γ̂. Следовательно, γ ∈ δi , где ν(β) = i − 1, и система множеств ∆ являетсяразбиением куба B q .Заметим, что в силу отмеченных выше свойств операции сложения по модулю 2,разбиение ∆ обладает всеми необходимыми для моделирования множества ФАЛ Gсвойствами, и что при этом число его «плохих» компонент не больше, чемλ−10Cq−m+ · · · + Cq−m.Лемма доказана.Следствие.
В случае q > m+3λ число плохих компонент разбиения ∆ не больше,чем (2e6 )q−m , где e6 < 1.Теорема 6.1. Для любой ФАЛ f , f ∈ P2 (n) существует реализующая её формула Ff , Ff ∈ UФБ , такая, что2n log log n ± O(1) 1+.(6.1)L Ff 6 ρБlog nlog n36Глава 1.Доказательство. Выберем ФЭ Ej , введём натуральные параметры m, s, t, p, l, λ иопределим разбиение Π, формулу Fp , ФАЛ ϕ, ϕ–УМ G порядка m так, как это былосделано в доказательстве теоремы 5.1 и так, чтобы выполнялись соотношения (5.2)–(5.6).Выберем, далее, натуральный параметр q так, чтоm + 3λ 6 q 6 n(6.2)и построим по лемме 6.2 для множества ФАЛ G соответствующее m–регулярноеразбиение ∆ = (δ1 , . .
. , δ2q−m ) куба B q от БП x0 = (x1 . . . xq ). Заметим, что дляпроизвольной ФАЛ g(x0 ) и любого i, i ∈ [1, 2q−m ], в силу ϕ–универсальности множества G, m–регулярности разбиения ∆ и возможности моделировать ФАЛ из Gна компонентах ∆ с помощью БП или их отрицаний всегда найдутся такие натуральные числа j1 , . .
. , jp из [m + 1, q] и булевы константы α1 , . . . , αp , для которыхравенствоα g x0 = ϕ xαj11 , . . . , xjpp(6.3)выполняется на любом наборе из δi .Возьмём (см. (5.7)) разложение ФАЛ f по БП x00 = (xq+1 . . . xn ) и продолжимего на основе (6.3) так, что000f x ,x=_Kσ00 x000· fσ00 x =σ 00 ∈B n−q2q−m_i=1xi _αα0000 xi · Kσ00 x00 · ϕ xj 1,i,σ00 , . . .
, xj p,i,σ00 ,1,i,σj,i,σσ 00 ∈B n−q(6.4)гдеx (x0 ) — характеристическая ФАЛ компоненты δi разбиения ∆. Искомая форiмула Ff получается из последнего представления (6.4) ФАЛ f следующим образом:1) характеристическая ФАЛДНФ;x , i ∈ [1, 2q−m ], реализуется по своей совершеннойi2) мультиплексорная ФАЛ µn−q порядка (n − q) от адресных БП x00 , связанная сразложением f по этим БП, реализуется с помощью бесповторной по информационным БП формулы из UC сложности не больше, чем 4 · 2n−q (см. [ ]);3) каждая ФАЛ вида (6.3) реализуется одной формулой Fp с необходимыми инверсиями её БП в случае «плохой» компоненты δi ;4) все используемые при реализации формул из пунктов 1-3 элементы базиса Б0заменяются соответствующими им бесповторными формулами F& , F∨ , F¬ излеммы 6.1.Для сложности построенной таким образом формулы Ff будет (ср.
с (5.7)) справедливо неравенствоL Ff 6 Lj · t · 2n−m + O 2n−m 1 + t · eq−m+ q · 2q ,(6.5)6§7. Мультиплексорные ФАЛ и обобщённое разложение37которое при значениях параметровm = b2 log log nc ,s = blog n − log log nc − 2,удовлетворяющих при достаточно больших n условиям (6.2), даёт оценку (6.1).Теоремa доказана.Теорема 6.2.
Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её формула Ff , Ff ∈ UФ , такая, чтоL Ff2n6log n1+O1log n.(6.6)Доказательство. Искомая формула Ff строится, как и при доказательстве теоремы 6.1, на основе представления (6.4). При этом вместо ФЭ Ej необходимо взятьe базиса Б,e а вместо формулы Ft , ФАЛ ϕ(y1 , . . . , yp ) и ϕ–УМ G необходимоФЭ Ee t , ФАЛ ϕ(yиспользовать формулу Fe 1 , . .
. , yp ) и ϕ–УМeG из доказательства теоремы 5.2 соответственно. Заметим, что в данном случае отпадает необходимостьмоделирования базисных ФАЛ бесповторными формулами из леммы 6.1.Сложность построенной таким образом формулы Ff по-прежнему удовлетворяет неравенству (6.5), из которого при следующих значениях параметров2mt=,3(s − 5)m = b2 log log nc ,s = blog nc − 3,p = 3t + 1,удовлетворяющих при достаточно больших n всем необходимым условиям, вытекает (6.6).Теорема доказана.Следствие.ФL§72nn =log n11±O.log nМультиплексорные ФАЛ и обобщённое разложение. Оптимальная по задержке реализация мультиплексорных ФАЛ впроизвольном базисеПусть ∆ = (δ1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
