ОК_Часть_3_2015_(320-328) (1132807), страница 6
Текст из файла (страница 6)
Неравенства (5.11)–(5.14) выводятся из соответствующего рассматриваемому классу схем U с функционалом сложности L неравенства (5.3)–(5.6) на основе мощностного неравенства (5.2), где δ = 1/n с использованиемnлеммы 5.1, где q = 22 /n, и1)2)3)4)a = 8,a = 8n,a = 8n,a = 12n,yyyy= LC (n) + n,= LΦ (n) + 1,= LK (n),= Lπ (n),еслиеслиеслиеслиU = UC ;U = UΦ ;U = UK ;U = Uπ .Действительно, подставляя указанные значения в (5.9) по-§5. Нижние мощностные оценки45лучим, что доля тех ФАЛ f , f ∈ P2 (n), для которыхlog(n + 3) − o(1)2nC1+−n>1) L (f ) >n+3n+5(5.16)2nlog n − 3 − o(1)>1+;nnn3 + o(1)2 − log n2nΦ1−;(5.17)2) L (f ) >−1>log n + 3log nlog n2nlog(n + 3 + log n) − o(1)3) LK (f ) >1+>n + 3 + log nn + 5 + log n2n3 + o(1)1−,>nn(5.18)не меньше, чем (1 − 1/n).
Следовательно, неравенство (5.11)((5.12), (5.13)) будет справедливо для достаточно большихn при ε1 (n) = log nn−4 (соответственно ε2 (n) = log4 n , ε3 (n) =4n ).Аналогичным образом устанавливается справедливость(5.14) и (5.15) при ε4 (n) = log6 n = ε5 (n).Теорема доказана.Следствие.D(n) > n − log log n − o(1),2n2nLC (n) &, LΦ (n) &,nlog n2n2nLK (n) &, Lπ (n) &.nlog nМощностные соображения можно использовать при получении нижних оценок для функций Шеннона, связанныхс реализацией ФАЛ из класса Q, Q = Q (1) , Q (2) , . .
.. . . , Q (n) , . . . , гдеQ ⊆ P2 и Q (n) = Q ∩ P2 (n) 6= ∅,n = 1, 2, . . . .46Глава 3. Синтез и сложность управляющих системПусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (Q (n)) —функция Шеннона (для класса схем U относительно функционала сложности Ψ), связанная с классом ФАЛ Q, то естьΨ (Q (n)) = max Ψ (f ) .f ∈Q(n)Следующее «мощностное» неравенство обобщает равенство (5.1)и вытекает непосредственно из определений:kU (Ψ (Q (n)) , n)k > |Q (n)| .(5.19)Оно позволяет получить нижнюю оценку функции Шеннона Ψ (Q (n)) на основе известной верхней оценки величиныkU (Ψ, n)k.Рассмотрим, в частности, нижние мощностные оценкидля функций LC (Q (n)) и LK (Q (n)), то есть функций Шеннона для сложности реализации ФАЛ из класса Q схемамииз классов UC и UK соответственно.
На основе мощностныхсоображений (см. (5.19)) аналогично тому, как это было сделано в теореме 5.1 для случая Q = P2 , доказывается следующее утверждение.Лемма5.2. Для класса ФАЛ Q такого, что n =log|Q(n)|= o log log|Q(n)| (log n = o (log log |Q(n)|)), выполняются следующие асимптотические неравенстваLC (Q (n)) &(соответственноlog |Q (n)|,log log |Q(n)|LK (Q (n)) &log |Q (n)|).log log |Q(n)|(5.20)(5.21)Пусть, например, класс Q состоит из всех ФАЛ, симметричных по первым двум БП. Легко видеть, что при этом§6.
Метод Лупанова синтеза СФЭ473 n|Q (n)| = 2 4 2 , так как f ∈ Q(n) тогда и только тогда, когдавторая и третья четверти столбца значений αef совпадают.Следовательно, в силу леммы 5.2, отсюда вытекает, чтоLC (Q(n)) &§63 2n· ,4 nLK (Q (n)) &3 2n· .4 n(5.22)Дизъюнктивно-универсальные множествафункций. Асимптотически наилучшийметод О. Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬}Рассмотрим метод синтеза схем из класса UC , который былпредложен О.Б.
Лупановым [14] и позволил впервые установить асимптотику функции Шеннона LC (n). Этот метод,как и метод Шеннона (см. §4), основан на представленииреализуемой ФАЛ f, f ∈ P2 (n), в виде (4.5) и построенииискомой СФЭ Σf , реализующей ФАЛ f , как суперпозициисхем вида Σf = Σ00 (Σ0 ). При этом схема Σ00 по-прежнему является мультиплексором порядка (n − q) от адресных БПx00 = (xq+1 , . . . , xn ), а схема Σ0 реализует все ФАЛ видаfσ00 (x0 ), где x0 = (x1 , .
. . , xq ) , σ 00 ∈ B n−q , и fσ00 (x0 ) = f (x0 , σ 00 ).Однако, в отличие от метода Шеннона, каждая ФАЛ fσ00 (x0 )берется не с выхода универсального многополюсника от БПx0 , а реализуется на выходе Σ0 как дизъюнкция некоторыхФАЛ, выбранных из специального множества G, G ⊆ P2 (q),реализованного на выходах соответствующей подсхемы схемыΣ0 .Множество ФАЛ G, G ⊆ P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . .
. ∨ gp ,48Глава 3. Синтез и сложность управляющих системгде gi ∈ G при всех i, i = 1, . . . , p. Стандартный способ построения таких множеств связан с разбиениями единичногокуба.Пусть Π = (π1 , . . . , πp ) — разбиение куба B m , и пусть длявсех i, i = 1, . . . , p, ФАЛ ψi (x1 , . . . , xm ) — характеристическая ФАЛ множества πi , а G(i) — множество всех тех ФАЛg, g ∈ P2 (m), которые обращаются в 0 вне πi . Заметим, чтомножество ФАЛ G видаG = G(1) ∪ . . .
∪ G(p)является ДУМ порядка m и ранга p. Действительно, любаяФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . . . ∨ gp ,(6.1)где gi = ψi g и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.Заметим также, что мощность множества G(i) , i = 1, . . . , p,равна 2si , где si = |πi |, и что множество G(i) ∩ G(j) состоит из ФАЛ, тождественно равной 0, если 1 6 i < j 6 p.Следовательно,p pXX (i) λ = |G| =2si 6 p2s ,G − (p − 1) 6i=1i=1гдеs = max si .16i6pУказанное ДУМ G будем называть ДУМ, связанным сразбиением Π. Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛ ψ1 = χδ1 , . .
. , ψp = χδp —его характеристическими ФАЛ. Заметим, что характеристические ФАЛ попарно ортогональны, то есть одновременно в 1 не обращаются, и принадлежат G. Заметим также,§6. Метод Лупанова синтеза СФЭg1 g2 . . .g2s g2s +1. .
.g2s+1 −1 . . . g(p−1)(2s −1)+2. . . gλx1 x2 . . . xm−1 xm... 00 0 01 0 0 ... 0...π1 ............π2 ...πp−1 πp 0 1 ... 10...0...0...00 0 .... . .. . .. . .0 0 ...1...0...0.........0...00...0.........0...1.........0 0 ... 01...1...0...00 0 .... . .. . .. . .0 0 ...0...0...1.........0...01...0.........0...0...............49......0...0...0...0...0.........0...00...0.........0...0.........0......0 0 .... . ..
. .. . .0 0 ......0 0 ... 00...0...1...1...0 0 .... . .. . .. . .0 0 ...0...0...0.........0...00...0.........1...0.........o2s/o/O...2s −1s=s2...0...O00 0 ... 0...s=s10......Oos2 p −1s=sp−10Osp 6s0/Рис. 6.1: к определению дизъюнктивно-универсальногомножествачто представление (6.1) в случае рассматриваемого ДУМ Gравносильно представлению:g = ψ1 g1 ∨ ψ2 g2 ∨ · · · ∨ ψp gp(6.2)Будем считать стандартным ДУМ порядка m и высоты s, гдеs 62m ,(6.3)50Глава 3. Синтез и сложность управляющих системДУМ ранга p, p = d2m /se, связанное с разбиением Π =(π1 , . .
. , πp ) куба B m на последовательные отрезки, для которого номер любого набора из множества πi меньше номералюбого набора из множества πj , если i < j, и выполнены соотношенияs1 = s2 = · · · = sp−1 = s,sp = 2m − (p − 1) s 6 s.(6.4)Таблица значений ФАЛ ДУМ G приведена на рис. 6.1.Из проведенных построений и отмеченных выше свойствстандартного ДУМ вытекает справедливость следующего утверждения.6.1.
Для любых натуральных p, m и s, где p =Лемма2m,существуетстандартное ДУМ G порядка m и высоsты s, которое является ДУМ ранга p и для которого:1) λ = |G| 6 p2s ;2) система из p характеристических ФАЛ ψ1 , . . . , ψpДУМ G обладает тем свойством, что для любойФАЛ g, g ∈ P2 (m), и соответствующих ФАЛg1 , . . . , gp из G справедливо не только представление(6.1), но и представление (6.2).Теорема 6.1. Для любой ФАЛ f, f ∈ P2 (n), существуетреализующая ее СФЭ Σf , Σf ∈ UC , такая, что2n5 log n + O (1)L (Σf ) 61+.(6.5)nnДоказательство.
Пусть x0 = (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn )и fσ00 (x0 ) = f (x0 , σ 00 ) для всех σ 00 из B n−q . Пусть, далее,Σ00 — мультиплексор порядка (n − q) от адресных БП x00 иинформационных БП y = (y0 , . . . , y2n−q −1 ), который построен в соответствии с леммой 2.3, представляет собой формулуFn−q и реализует мультиплексорную ФАЛ µn−q (x00 , y).§6. Метод Лупанова синтеза СФЭ51Пусть s — некоторый параметр, удовлетворяющий (6.3),а G — стандартное ДУМ порядка m = q и высоты s, удовлетворяющее требованиям леммы 6.1. Обозначим через ΣG→−СФЭ, которая реализует систему ФАЛ G и представляетсобой объединение схем, построенных для каждой из них всоответствии с леммой 1.2.
Заметим, что, в силу леммы 2.3,(1.3) и леммы 6.1, выполнены неравенстваL Σ00 6 4 · 2n−q ,(6.6)L (ΣG ) 6 3p2s+q .Схема Σ0 содержит СФЭ ΣG в качестве подсхемы и реализует каждую ФАЛ fσ00 (x0 ), где σ 00 ∈ B n−q , на одном из своих выходов как ФАЛ g (x0 ) вида (6.1) с помощью СФЭ из(p − 1) ФЭ ∨, входы которой присоединены к соответствующим выходам ΣG . Искомая СФЭ Σf имеет вид Σf = Σ00 (Σ0 )и реализует ФАЛ f в соответствии с разложением (4.5). Длянее, в силу (6.6), будут выполняться неравенстваL (Σf ) 6 2n−q (p − 1) + L Σ00 + L (ΣG ) 66 2n−q (p − 1) + 4 · 2n−q + 3p2s+q ,из которых, выбрав значения параметровs = dn − 5 log ne ,m = q = d2 log ne ,удовлетворяющие (6.3), в соответствии с леммой 6.1 получим n2n2L (Σf ) 6+O=n − 5 log nn22n5 log n + O (1)=1+.nnТеорема доказана.52Глава 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
