Часть 3 (1132845)
Текст из файла
III. Синтез и сложностьуправляющих систем15. Задача синтеза. Методысинтеза схем на основе ДНФи связанные с ними верхниеоценки сложности функцийУтверждение 15.1 Для любой функцииалгебры логики f (x1, . . . , xn ), f 6= 0,существуют формула Ff , Ff ∈ UΦ, иπ-схема Σf , которые реализуют f и длякоторых справедливы неравенства:L (Ff ) 6 2n · |Nf | − 1,L (Σf ) 6 n |Nf | ,D (Ff ) 6 dlog(n · |Nf |)e + 2.Следствие 1. В силу указанныхнеравенств, с учетом того, что ФАЛ 0 можнореализовать π-схемой сложности 2, а такжеформулой из UΦ, имеющей сложность 2,выполняются неравенстваLC (n) 6 LΦ (n) 6 n · 2n+1 − 1,LK (n) 6 Lπ (n) 6 n · 2n .Следствие 2.D (n) 6 n + dlog ne + 2.Утверждение 15.2 Для любой ФАЛf , f ∈ P2 (n) и f 6= 0, существуют π-схемаΣf и формула Ff , Ff ∈ UΦ, которыереализуют f и для которых справедливынеравенства:L (Σf ) 6 2n + |Nf | − 2,L (Ff ) 6 2n+1 + |Nf | − 4.СледствиеLπ (n) 6 2n+1 − 2,LΦ (n) 6 3 · 2n − 4.Функции, встречающиеся в приложениях:1.
линейная ФАЛ порядка n, то есть ФАЛ `nили ФАЛ `n ;2. мультиплексорная ФАЛ µn порядка n;→−3. дешифратор Q n (дизъюнктивный→−дешифратор J n ) порядка n;→−4. универсальная система P 2 (n) порядка n,состоящая из всех различных ФАЛ множества P2 (n), упорядоченных в соответствиис номерами их столбцов значений.Утверждение 15.3 Для любогонатурального n в UСБ существуетуниверсальная СФЭпорядка n, сложность2nкоторой равна 2 − n.Следствие→−nLСБ( P 2(n)) 6 22 − n.16.
Нижние оценки сложностиФАЛ, реализация некоторыхФАЛ и минимальностьнекоторых схемУтверждение 16.1 Если ФАЛf (x1, . . . , xn ) существенно зависит от всехсвоих БП, тоLC (f ) > n − 1,LK (f ) > n.Если при этом ФАЛ f не являетсямонотонной ФАЛ (каждая БП xi , i ∈ [1, k ],не является ни монотонной, ниинмонотонной БП ФАЛ f ), тоLC (f ) > n(соответственно LK (f ) > n+k ).СледствиеLC(`n ) > n,LC(µn ) > 2n + n,LK(`n ) > 2n,LK(µn ) > 2n + 2n.Утверждение 16.2 Для системыF = (f1, .
. . , fm ), состоящей из попарноразличных ФАЛ отличных от констант (отпеременных), справедливо неравенствоLK (F ) > m(соответственноLCБ (F ) > m).Следствие− − C →nK →L Qn > 2 ,L Q n > 2n ,→→−−LC J n > 2n ,LK J n > 2n ,→→−−nnLCБ P 2 (n) > 22 − n, LK P 2 (n) > 22 − 2.Замечание В силу следствияуниверсальная СФЭ Un , построенная вутв. 15.3, является минимальной посложности СФЭ в классе UCБ .Утверждение 16.3 Если длясущественной БП xn ФАЛ f ∈ P2(n), и длялюбого (некоторого) σ, σ ∈ B , ФАЛf |xn =σ = f (x1, . . .
, xn−1, σ) 6≡ 0, 1, тоLС&,∨(f ) > min{LС&,∨(f |xn =0), LС&,∨(f |xn =1)} + 2ССсоответственно L&,∨(f ) > L&,∨(f |xn =σ ) + 1 .СледствиеLС(µn ) > 2n+1 + n − 1,D (µn ) > n + 2.Утверждение 16.4 Если система ФАЛF = (f1, . . . , fm ) состоит из попарноразличных ФАЛ от БП X (n), отличных от0 и 1, тоK1−nL (F ) > 2mX Nf .jj =1→−Следствие LK( J n ) > 2n+1 − 2Утверждение 16.5 Для любогонатурального n выполняются неравенства:LС(`n ) 6 4n − 4, LС(`¯n ) 6 4n − 4 + b1/nc ;Lπ (µn ) 6 3 · 2n − 2, LФ(µn ) 6 2n+2 − 3;→−→−LС( Q n ) 6 2n + O (n · 2n/2), LК( Q n ) 6 2n+1 − 2;→−LС( J n ) 6 2n + O (n · 2n/2).Следствие→−→−LС( Q n ) ∼ LС( J n ) ∼ 2n .17.
Разложение ФАЛ иоперация суперпозиции схем.Корректность суперпозициидля некоторых типов схем,разделительные контактныесхемы и лемма ШеннонаУтверждение 17.1. Пусть КС Σ являетсярезультатом стыковки вида Σ = Σ00(Σ0), а F ,F 0 и F 00 — матрицы, реализуемые КС Σ, Σ0 иΣ00 соответственно. ТогдаF > F 0 · F 00 и F = F 0 · F 00,если КС Σ00 разделительна по входам или КСΣ0 разделительна по выходам.Следствие 1. В случае разделительностиКС Σ00 по входам в каждой вершине КС Σ,Σ = Σ00(Σ0), которая соответствует выходуКС Σ0, реализуется тот же самый столбецФАЛ, что и в КС Σ0.Следствие 2.
Равенство F = F 0 · F 00выполняется на любом наборе значений БП,на котором КС Σ00 разделительна по входамили КС Σ0 разделительна по выходам.Замечание. Отождествление входов(выходов) у разделительной по входам(выходам) КС дает разделительную порассматриваемой группе полюсов КС.18. Каскадные контактныесхемы и схемы изфункциональных элементов.Метод каскадов и примерыего применения, методШеннонаУтверждение 18.1 Если (1, m)-ККС Σ0реализует систему ФАЛ F 0 = (f10, .
. . , fm0 ), тосуществует (1, m)-ККС Σ00, которая 000реализует систему ФАЛ F = f 1, . . . , f m идля которой L(Σ00) 6 2L(Σ0).Утверждение 18.2 Для любогонатурального n и σ ∈ B выполняютсянеравенства: →−1nLK (`σn ) 6 4n − 4 +, LK P 2(n) 6 2 · 22 ,n→− LK J n 6 2n+2 − 6.Утверждение 18.3 Для функцийШеннона LK (n) и LC (n) выполненысоотношения:2n2nKCL (n ) . 4 ,L (n) . 8 .nn19. Нижние мощностныеоценки функций Шеннона, ихобобщение на случай синтезасхем для ФАЛ изспециальных классовУтверждение 19.1 Для некоторыхпоследовательностей εi = εi (n), гдеi = 1, .
. . , 4, и n = 1, 2, . . . , таких, чтоεi (n) > 0 при n > n0 и εi (n) стремится к 0при n стремящемся к бесконечности дляпочти всех ФАЛ f , f ∈ P2(n), выполняютсянеравенства:K 2nC 2nL (f ) > 1 − ε1 (n),L (f ) > 1 + ε2 (n),nn 2n, D (f ) > n − log log n − ε4 (n).LΦ (f ) > 1 − ε3 (n)log nСледствиеD (n) > dn − log log n − o (1)e,2nCL (n ) & ,n2nΦ,L (n ) &log n2nKL (n ) & .nУтверждение 19.2Для класса ФАЛ Q такого, чтоlog |Q(n)|n=olog log |Q(n)|(log n = o (log log |Q(n)|)) ,выполняются асимптотические неравенстваlog |Q (n)|log log |Q(n)|log |Q (n)|(соответственно LK (Q (n)) &).log log |Q(n)|LC (Q (n)) &20. Дизъюнктивноуниверсальные множествафункций.
Асимптотическинаилучший методО. Б. Лупанова для синтезасхем из функциональныхэлементов в базисе {&, ∨, ¬}Утверждение 20.1 Для любых 2m натуральных p , m и s , где p = s ,существует стандартное ДУМ G порядка mи высоты s , которое является ДУМ ранга pи для которого:1) λ = |G | 6 p 2s ;2) система из p характеристических ФАЛψ1, .
. . , ψp ДУМ G обладает темсвойством, что для любой ФАЛ g ,g ∈ P2 (m), и соответствующих ФАЛg1, . . . , gp из G справедливыпредставленияg = g1 ∨ · · · ∨ gp = ψ1g1 ∨ · · · ∨ ψp gp .Утверждение 20.2 Для любой ФАЛ f ,f ∈ P2(n), существует реализующая её СФЭΣf , Σf ∈ UC, такая, что 2n5 log n + O (1)L Σf 61+.nnСледствие. Из этого утверждения с учетомследствия из утверждения 20.1 вытекает, что2nL (n ) ∼ .nC21. Регулярные разбиенияединичного куба имоделирование функцийпеременными.Асимптотически наилучшийметод синтеза формул вбазисе {&, ∨, ¬}.Утверждение 21.1 Для любыхнатуральных m, λ и q = m + λ и для любойсистемы ФАЛ g = (g1, .
. . , gλ) из P2λ(m)существует m-регулярное разбиение∆ = (δ1, . . . , δ2q−m ) куба B q такое, что любаяФАЛ gi на любой компоненте δj совпадаетлибо с одной из БП xm+1, . . . , xq , либо с ееотрицанием.Замечание. Если в условиях утвержденияαα = (α1, .
. . , αλ) = ν −1(j − 1), то gi ≡ xi +j mна δj .Утверждение 21.2 Для любой ФАЛ f ,f ∈ P2(n), в UΦ существует реализующая ееформула Ff , для которой2n2 log log n + O (1)L(Ff ) 61+,log nlog nD (Ff ) 6 n − log log n + O (1).Следствие. Из этих оценок с учетомнижних оценок следствия изутверждения 19.1 вытекает, что2n,L (n) ∼log nΦD (n) 6 n − log log n + O (1).22. Асимптотическинаилучший метод синтезаконтактных схем. Синтез схемдля ФАЛ из некоторыхспециальных классовУтверждение 22.1 Для любой ФАЛ f ,f ∈ P2(n), существует реализующая ее КСΣf такая, что 2n1L(Σf ) 6.1+O √nnСледствие. Из этой оценки с учетомнижней оценки следствия изутверждения 19.1 вытекает, что2nL (n ) ∼ .nKЗамечание. Построенную КС Σf можноразбить на не более, чем n 2√λp · 2p + 2n−m+1 + (λ + 1)2q +1 = On n«звезд», каждая из которых состоит изконтактов одного и того же типа.23. Синтез схем длядешифраторов имультиплексоров,асимптотически точныеоценки их сложности.Утверждение 23.1 Для n = 1, 2, 3, .
. .выполняются неравенства n→−2,LК( Q n ) 6 2n + On n→−2.LК( J n ) 6 2n+1 + OnСледствие. Оценки утверждения 23.1 иследствия из следствия из утверждений16.2, 16.4 дают асимптотические равенства−−К →nК →L ( Q n) ∼ 2 ,L ( J n ) ∼ 2n+1.Утверждение 23.2 Для n = 1, 2, .
. .выполняются неравенстваLπ (µn ) 6 2 · 2n + O (2n /n) ,LC(µn ) 6 2 · 2n + O (2n /n) ,D (µn ) 6 n + 6,причем существует такая реализующая ФАЛµn и бесповторная по информационным БПформула Mn с поднятыми отрицаниями,глубина которой удовлетворяет последнемуиз них, альтернирование не больше 3, асложность не превосходит 7 · 2n .Следствие. Из полученных оценок в силуследствий из утверждения 16.3 вытекает, чтоLС(µn ) ∼ 2n+1,D (µn ) = n + O (1)..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
