ОК_Часть_3_2015_(320-328) (1132807), страница 7
Текст из файла (страница 7)
Синтез и сложность управляющих системСледствие. Из (6.5) с учётом следствия из теоремы 5.1вытекает, что2nLC (n) ∼.nОтметим, в заключение, что в соответствии с (6.5) и теоремой 5.1 сложность LC (f ) для почти всех ФАЛ f, f ∈P2 (n), асимптотически равна функции Шеннона LC (n), тоесть сложности самой сложной ФАЛ из P2 (n). Тем самым,в отличие от класса ДНФ (см. §7 главы 1), в классе схемUC имеет место т.
н. эффект Шеннона — асимптотическоеравенство сложности почти всех ФАЛ и сложности самойсложной ФАЛ от заданного числа БП, стремящегося к бесконечности.§7Регулярные разбиения единичного куба и моделирование функций переменными. Асимптотически наилучший метод синтеза формулв базисе {&, ∨, ¬}.Множество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q , если m < q, |δ| = 2m и все префиксы1 длины m наборов из δ различны. Заметим, что mрегулярному множеству δ, δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , .
. . , ψq−m ) из P2q−m (m)так, что набор α = (β, γ), где β ∈ B m и γ ∈ B q−m , принадлежит δ тогда и только тогда, когда ψ (β) = γ. Заметим также, что любая ФАЛ g, g ∈ P2 (q), совпадает наm-регулярном множестве наборов δ, δ ⊆ B q , с некоторойФАЛ из P2 (m), если рассматривать P2 (m) как множествовсех ФАЛ из P2 (q) с несущественными БП xm+1 , . . . , xq . Приэтом любая ФАЛ из связанной с δ системы функций совпадает на δ с соответствующей БП куба B q .1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственно суффиксом).§7.
Регулярные разбиения единичного куба53Для наборов β = (β1 , . . . , βq ) и α = (α1 , . . . , αq ) черезβ ⊕ α будем обозначать набор вида (β1 ⊕ α1 , . . . , βq ⊕ αq ).Для множества δ, δ ⊆ B q , и набора α, α ∈ B q , определиммножество δ ⊕ α как множество различных наборов видаβ ⊕ α, где β ∈ δ, то есть множество, получающееся из множества δ сдвигом (параллельным переносом) на набор α.Заметим, что для m-регулярного множества δ, δ ⊆ B q , илюбого набора α, α ∈ B q , множество δ ⊕ α также являетсяm-регулярным. Если при этом ν (α) < 2q−m , то естьα = (0, . .
. , 0, γ),| {z }mгде γ = (γ1 , . . . , γq−m ) и ν (γ) = ν (α), а множество наборовδ соответствует системе ФАЛ g = (g1 , . . . , gq−m ), то множество наборов δ ⊕ α будет соответствовать системе ФАЛ(g1 ⊕ γ1 , . . . , gq−m ⊕ γq−m ), получающейся из системы g инвертированием некоторых ФАЛ.Лемма 7.1. Для любых натуральных m, λ и q = m + λ идля любой системы ФАЛ g = (g1 , . . . , gλ ) из P2λ (m) существует m-регулярное разбиение ∆ = (δ1 , .
. . , δ2q−m ) куба B qтакое, что любая ФАЛ gi на любой компоненте δj совпадает либо с одной из БП xm+1 , . . . , xq , либо с её отрицанием.Доказательство. Пусть δ = δ1 — m-регулярное множество,соответствующее системе ФАЛ g = (g1 , . . . , gλ ), и пусть δi =δ1 ⊕ α, где ν(α) = i − 1, для всех i, i = 1, . . . , 2q−m . Из построения системы множеств ∆ = (δ1 , . . . , δ2q−m ) следует, чтокаждое из них обладает требуемым свойствами, связаннымис можелированием ФАЛ из g с помощью БП.Покажем теперь, что ∆ — покрытие куба B q . Для этоговозьмем произвольный набор из B q вида (β, γ), где β ∈ B mи γ ∈ B q−m , а по нему найдем в множестве δ набор вида(β, γb), который имеется в δ в силу m-регулярности этого54Глава 3. Синтез и сложность управляющих системмножества.
Следовательно,(β, γ) = (β, γ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 .§7. Регулярные разбиения единичного куба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Глава 3. Синтез и сложность управляющих систем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+O,log n − 2 log log nlog2 nиз которого для сложности формулы Ff следует оценка (7.1).Теорема доказана.Следствие.
Из (7.1) с учётом нижних оценок следствияиз теоремы 5.1 вытекает, чтоLΦ (n) ∼§82n.log nАсимптотически наилучший метод синтезаконтактных схем. Синтез схем для ФАЛ изнекоторых классовЗаметим сначала, что асимптотически наилучший метод синтеза СФЭ из §6 без существенных изменений переносится накласс контактно-вентильных схем (КВС), в которых нарядус контактами можно использовать «вентили», то есть ориентированные ребра, проводящие только в направлении своей§8. Асимптотически наилучший метод синтеза КС57ориентации. Действительно, для любой ФАЛ 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)и на его основе реализовать ФАЛ g с помощью корректной суперпозиции т.н. итеративно-контактных схем, показанной на рис.
8.1b, где ФАЛ ψ1 , . . . , ψp управляют проводимостью соответствующих контактов. Асимптотически наилучший метод синтеза КС связан с «моделированием» этойсуперпозиции и представления (8.1) на компонентах подходящего m-регулярного разбиения куба B m+p .Пусть δ̌ — m-регулярное множество наборов куба B m+p ,→−соответствующее системе ФАЛ ψ = (ψ1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
