С.А. Ложкин - Элементы теории синтеза дискретных управляющих систем (1160764), страница 3
Текст из файла (страница 3)
Справедливость нижней оценки (3.13) для почти всех ФАЛустанавливается аналогично.Рассмотрим теперь мощностные нижние оценки для КС, ИКС, а также для СФЭ и формулв произвольном базисе Б. Следующее утверждение доказывается на основе мощностныхсоотношений (3.1), (3.2) и леммы 3.1 с использованием оценок §1, §2 аналогично тому, какдоказывалась теорема 3.1.Теорема 3.2. Для некоторой последовательности ε = ε(n), n = 1, 2, . .
., такой, что ε(n) > 0при n > n0 и ε(n) стремится к 0 при n стремящемся к бесконечности, выполняютсянеравенства2n1 − ε(n) ,nn2LИКС(n)>ρ̂1 + ε(n) ,ББnn2LCБ (n) > ρБ1 + ε(n) ,n2nLФ(n)>ρ1 − ε(n) ,ББlog nLКСБ (n) > πБ(3.17)(3.18)(3.19)(3.20)TБ (n) > τБ n − log log n − ε(n) .(3.21)Следствие 3.LКСБ (n) & πБ2n,n2n,nTБ (n) > τБ n − log log n − o(1) .LИКС(n) & ρ̂ББ2n,nLCБ (n) & ρБLФБ (n) & ρБ2n,log nСледствие 4.
Нижние оценки (3.17)–(3.21) справедливы для почти всех ФАЛ из P2 (n).§4Универсальные множества ФАЛ и их построение. Асимптотическинаилучший метод синтеза СФЭ и ИКС в произвольном базисеНапомним (см. [3]), что множество ФАЛ G называется дизъюнктивно-универсальным множеством (ДУМ) ФАЛ порядка m и ранга p, тогда и только тогда, когда G ⊆ P2 (m) и длялюбой ФАЛ g, g ∈ P2 (m), найдутся функции g1 , . . . , gp из G, для которых g = g1 ∨ · · · ∨ gp .Обобщим понятие ДУМ ФАЛ следующим образом. Пусть ψ(y1 , .
. . , yp ) — существеннаяФАЛ, то есть ФАЛ, существенно зависящая от всех своих БП. Множество ФАЛ G, G ⊆⊆ P2 (m), называется ψ-универсальным множеством (ψ-УМ) порядка m, если любая ФАЛ g,g ∈ P2 (m), может быть представлена в видеg = ψ(g1 , . . . , gp ),(4.1)12Глава 1.где gi ∈ G при всех i, i = 1, . . . , p. Заметим, что в случае ψ(y1 , . . .
, yp ) = y1 ∨ · · · ∨ yp понятиеψ-УМ совпадает с понятием ДУМ ранга p.Так же, как и ДУМ (см. [3]), будем строить ψ-УМ порядка m на основе разбиения∆ = (δ1 , . . . , δp ) единичного куба B m . Для каждого i, i = 1, . . . , p, в силу существеннойзависимости ФАЛ ψ от БП yi найдётся набор двоичных констант αi,1 , . . . , αi,p такой, чтоψ(αi,1 , . . . , αi,i−1 , yi , αi,i+1 , . . . , αi,p ) = yi ⊕ αi,i .(4.2)Обозначим через G(j) , j = 1, .
. . , p, множество всех тех ФАЛ из P2 (m), которые при любомi, 1 6 i 6 p и j 6= i, равны αi,j на множестве наборов δi , и пустьG = G(1) ∪ · · · ∪ G(p) .(4.3)Нетрудно убедиться в том, что равенство (4.1) имеет место для любой функции g, g ∈ P2 (m),если gi , i = 1, . . . , p, — ФАЛ из G(i) , совпадающая на δi с ФАЛ g ⊕ αi,i . Действительно, длялюбого i, i = 1, . . . , p, и любого набора β, β ∈ δi , в силу (4.2), получим:ψ g1 (β), .
. . , gp (β) = ψ αi,1 , . . . , αi,i−1 , g(β) ⊕ αi,i , αi,i+1 , . . . , αi,p = g(β).Следовательно, множество G представляет собой ψ-УМ порядка m, которое будем называтьстандартным ψ-УМ, связанным с разбиением ∆.Приведём пример стандартного ψ-УМ для функции ψ(y1 , . . . , yp ) = y1 yt+1 ∨ y2 yt+2 ∨ . . . ∨∨ yt y2t , где p = 2t, связанного с разбиением куба B m на последовательные отрезки δ1 , . . .
, δpдлины s1 , . . . , sp соответственно, где s1 + · · · + sp = 2m . Если при этом константы в (4.2)выбрать так, что αi,j = 1 только тогда, когда |i − j| = t, то соответствующее стандартноеe порядка m будет иметь вид (4.3), где G(j) состоит из таких ФАЛ g, g ∈ P2 (m),ψ-УМ Gдля которых g(α) = 1 при α ∈ δi , если |i − j| = t, и g(α) = 0 на остальных отрезках δi ,e имеет мощность t(2s0 + 2s00 ), еслиза исключением δj . Заметим, что полученное ψ-УМ G|s1 | = · · · = |st | = s0 и st+1 = · · · = |s2t | = s00 , где t(s0 + s00 ) = 2m .Используем построенные выше стандартные ψ-УМ для синтеза СФЭ в базисе Б, Б == {Ei }bi=1 . В силу полноты базиса Б в UФБ существуют формулы F& , F∨ и F¬ , реализующиеФАЛ x1 · x2 , x1 ∨ x2 и x1 соответственно, которыми мы будем заменять ФЭ базиса Б0 присинтезе схем на основе конъюнктивных и дизъюнктивных представлений.Теорема 4.1 (ср.
[3]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её СФЭ Σf ,Σf ∈ UCБ , такая, что2nL(Σf ) 6 ρБn5 log n + O(1)1+n.(4.4)Доказательство. Найдём среди ФЭ базиса Б, Б = {Ei }bi=1 , элемент Ej , на котором достигается приведённый вес ρj = ρБ (см. §1), то естьρj =Lj= min ρi = ρБ .kj − 1 ki >2(4.5)§4.13Пусть, далее, m, s, t, p — натуральные числа такие, чтоp = t(kj − 1) + 1,2m2mkj 66p<+ (kj − 1),ss(4.6)(4.7)а Π = (π1 , . . . , πp ) — такое разбиение куба B m на последовательные отрезки, что|πi | = si 6 s.(4.8)Построим из t ФЭ Ej бесповторную формулу Ft с p входами, которая имеет вид квазиполного l-ярусного, l = dlogk pe, дерева и реализует ФАЛ ψ(y1 , . .
. , yp ). Пусть G, G ⊆ P2 (m), —стандартное ψ-УМ порядка m, связанное с разбиением Π, для которого в силу (4.6)–(4.8)|G| = λ 6 p · 2s .(4.9)Искомая СФЭ Σf строится, как обычно, на основе разложения ФАЛ f (x1 , . . . , xn ) попеременным x00 = (xq+1 , . . . , xn )f (x0 , x00 ) =_Kσ00 (x00 ) · fσ00 (x0 ),(4.10)σ 00 ∈B n−qгде q = m, x0 = (x1 , . . . , xq ), а fσ00 (x0 ) = f (x0 , σ 00 ). При этом для реализации каждой ФАЛfσ00 (x0 ), σ 00 ∈ B n−q , используется её представлениеfσ00 (x0 ) = ψ(gσ00 ,1 , .
. . , gσ00 ,p ),(4.11)где ФАЛ gσ00 ,1 , . . . , gσ00 ,p берутся из множества G.→−Для системы ФАЛ G построим реализующую её СФЭ ΣG , ΣG ∈ UCБ , сложности не болеечем c · p · 2m+s путём моделирования формулами в «базисе» F& , F∨ , F¬ π-схем, полученых врезультате «вложения» в структуру контактного дерева совершенных ДНФ ФАЛ из G.Пусть, далее, СФЭ Σ0 содержит СФЭ ΣG в качестве подсхемы и для каждого σ 00 , σ 00 ∈∈ B n−q , реализует ФАЛ fσ00 (x0 ) в соответствии с (4.11), используя для этого формулу Ft .Схема Σf представляет собой суперпозицию вида Σf = Σ0 (Σ00 ), где СФЭ Σ00 — мультиплексорпорядка (n−q) от БП x00 , и реализует ФАЛ f в соответствии с (4.10). Сложность построеннойСФЭ Σf , Σf ∈ UCБ , с учётом (4.5)–(4.9) будет удовлетворять неравенствуL(Σf ) 6 Lj · t · 2n−m + O 2n−m + p · 2s + p · 2s/2+m ,(4.12)из которого приm = q = d2 log ne ,s = dn − 5 log neи при значениях остальных параметров, определённых из (4.6)–(4.7), следует (4.4).Теорема доказана.Следствие.LCБ (n) ∼ ρБ2n.n(4.13)14Глава 1.bf , Σb f ∈ UИКС ,Теорема 4.2.
Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её ИКС ΣБтакая, чтоnb f ) 6 ρ̂Б 2L(Σn5 log n + O(1)1+n.(4.14)Доказательство. Найдём среди ФПЭ базиса Б, Б = {Ki }bi=1 , элемент Kj , для которогоρ̂j = ρ̂Б (см. §2), то естьρ̂j =Lj= min ρ̂i = ρ̂Б .kj + 1 16i6b(4.15)Пусть, далее, m, s, t, p — натуральные числа такие, чтоp = t(kj + 1),2m2mkj 66p<+ kj ,ss(4.16)(4.17)а Π = (π1 , . . .
, πp ) — такое разбиение куба B m на последовательные отрезки, что|πi | = si 6 s.(4.18)b t над базисом Б представляет собой «звезду» из t управляемых непеПусть (t, 1)-КС Fресекающимися наборами БП y (1) , . . . , y (t) длины kj контактов Kj . При этом центр звездыb t , а её концевые вершины — проводящими входами Fb t , помеченнымиявляется выходом КС F(0)(0)b t реализует ФАЛразличными БП набора y (0) = (y1 , .
. . , yt ). Таким образом, КС Fb 1 , . . . , yp ) = y (0) · ϕj y (1) ∨ . . . ∨ yt(0) · ϕj y (t) .ψ(y1bb стандартное ψ-УМОбозначим через Gпорядка m, построенное на основе разбиения Πтак, что для любого набора (g (1) , . . . , g (t) ), составленного из ФАЛ G и связанного с наборомБП y = (y (1) , . . . , y (t) ) и любого набора α = (α(1) , . . . , α(t) ) значений БП y не более одной изФАЛ ϕj g (i) (α(i) ) , где i = 1, . . .
, t, обращается в 1.b f аналогично тому, как строилась СФЭ Σf при доказательстве теоПостроим ИКС Σремы 4.1, на основе разложений (4.10) и (4.11) с использованием ФАЛ ψb вместо ФАЛ ψ,b t вместо формулы Ft и множества Gb вместо множества G.ИКС Fb G построенаb по-прежнему удовлетворяет (4.9) и пусть (1, λ)-КС ΣЗаметим, что λ = |G|из контактов базиса Б, моделирующих замыкающий и размыкающий контакты стандартногоb и имеет сложностьбазиса (см. §2), реализует систему из ФАЛ множества Gb G 6 λ · 2m+1 .L Σbb для любой ФАЛ g(x0 )Заметим также, что в силу ψ-универсальностимножества ФАЛ Gсправедливо представлениеg x0 = ψb g1 , .
. . , gp(4.19)b для всех j, j = 1, . . . , p. Для реализации данного представления достаточногде gj ∈ Gb t присоединить к выходам КС Σb G в соответствии с (4.19), причёмвходы y1 , . . . , yp КС Fуказанная реализация является корректной суперпозицией соответствующих схем в силуотмеченных выше свойств ортогональности ФАЛ из G, подставляемых вместо БП из y.§5.15b 0 от БП x0 содержит в качестве подсхемы КС Σb G и реализует каждуюПусть ИКС ΣФАЛ fσ00 (x0 ), σ 00 ∈ B n−q , на одном из своих 2n−q выходов согласно (4.19), используя дляb t , входы которой присоединены к выходам Σb G соответствующим образом.этого схему Fb f содержит ИКС Σb 0 в качестве подсхемы и представляет собой результатИскомая ИКС Σкорректной суперпозиции вида Σf = Σ00 (Σ0 ), где Σ00 — (2n−q , 1)-КС, моделирующая в базиb0 все Б контактное дерево от БП x00 , входы (листья) которого присоединены к выходам Σсоответствии с (4.10).Сложности ИКС Σ0 и КС Σ00 удовлетворяют неравенствамL Σ0 6 L ΣG + 2n−q · t,L Σ00 6 2n−q+1и, следовательно,L Σf 6 Lj · 2n−q · t + O 2n−q + O 2s + t · 2q+s/2 .Оценка (4.14) получается из последнего неравенства при тех же значениях параметров, что и в теореме 4.1, при которых, начиная с достаточно большого n, выполнены всенеобходимые соотношения.Теорема доказана.Следствие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
