Слайды лекций (1132834), страница 2
Текст из файла (страница 2)
. , xn ), то{t1 −t5 }000Θ (Σ ) = Θ (Σ ), а если Σ0 ⇒ Σ00, где k < n,τk000то Θ (Σ ) − Θ (Σ ) делится на 2n−k .Утверждение 14.4 В классе UK несуществует конечной полной системытождеств.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 Если для ФАЛ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С(µn ) > 2n+1 + n − 1.Утверждение 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).Утверждение 23.3 Для монотоннойсимметрической ФАЛ sn2,n с порогом 2 приn > 2 выполняются неравенства:√С [2,n]2n − 3 6 L (sn ) 6 2n + O ( n).Следствие.LС(sn[2,n]) ∼ 2n.24.
Задача контроля схем итесты для таблиц.Построение всех тупиковыхтестов, оценки длиныдиагностического тестаУтверждение 24.1 Функция тестаf (y1, . . . , yp ) для отделимой по столбцамматрицы M , M ∈ B p,s , и цели контроля Nможет быть задана с помощью КНФ_^ ytf ( y1 , . . . , yp ) =(i ,j )∈N16t6pM <t ,i >6=M <t ,j >Следствие. Каждая элементарнаяконъюнкция вида yt1 · · · ytr сокращеннойДНФ функции f (y1, . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
