OK-metodichka-2010-part3 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 4

Çàìåòèì, ÷òî óêàçàííûéìóëüòèïëåêñîð ïîëó÷àåòñÿ ïðè ðàçëîæåíèè ÔÀË µn ñíà÷àëà ïî àäðåñíûì, à çàòåì ïî èíôîðìàöèîííûì ÁÏ.  òîæå âðåìÿ, êîíòàêòíûé ìóëüòèïëåêñîð ïîðÿäêà n, ïîñòðîåííûé ïî ìåòîäó êàñêàäîâ ïðè ðàçëîæåíèè ÔÀË µn ñíà÷àëàŸ3. Ìåòîä êàñêàäîâ äëÿ ÊÑ è ÑÔÝ25x1x1x4•x41 º³¹´¸·µ¶x3 ⊕ x4•x3x2x1x3x4x4•x3º³¹´¸·µ¶ f2•x2 (x3 ⊕ x4 )x3 x4•x2x2 ∨ x3 x4•x2x1º³¹´¸·µ¶ f1Ðèñ. 3.1: ïðèìåð ÊÑ ñ ïîìå÷åííûìè âåðøèíàìè,ïîñòðîåííîé ìåòîäîì êàñêàäîâx1x1x4••x2º³¹´¸·µ¶ f2•x31 º³¹´¸·µ¶x3x1x4•x3x2•x2•x1º³¹´¸·µ¶ f1Ðèñ. 3.2: ïðèìåð ÊÑ, ïîñòðîåííîé ìåòîäîì êàñêàäîâ26Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìx1•¬ •²x/4x3•/•//²²//²² ²//²/?º ¬¬ •¨²²²•??? ÄÄÄ??ÄÄÄÄ??Ä&ÄÄ ??&?ÂÄ•/ÂÄÄ/•//²² ²// ²²// ²²∨/¨²ºJ²• JJJJJJJJJJ∨J&J•Ä$²²²•ÂIJ²²² ²²²&&²²²&²²²&•/ÂÄ /•Â/¨²/•)¨²•ÄÂ////²²²²²²// ²²// ²²//∨²²//∨²²/º¨²²/¨²º ²••²²f2f1x2•Ðèñ.

3.3: ÑÔÝ äëÿ ñèñòåìû ÔÀË F , ïîñòðîåííàÿ ìåòîäîìêàñêàäîâx2Gw•ww• GGGwwwwGwwGGG wwwww1 º³¹´¸·µ¶wGGG x1 x2 wwwwGGGGx2GGGGGG www xGGG•ww2•x1......xn−1w•GGGGww GGGxGnGGwGGGG wwwº³¹´¸·µ¶wGxn−1 ww GGxn−1 x ww `nn wGGwwwGwwww xn−1 GG•www•w•GGÐèñ. 3.4: ñõåìà Êàðäî äëÿ ëèíåéíîé ôóíêöèè `nŸ3. Ìåòîä êàñêàäîâ äëÿ ÊÑ è ÑÔÝ27ïî èíôîðìàöèîííûì, à çàòåì ïî àäðåñíûì ÁÏ, ñîäåðæèòÊÄ ïîðÿäêà 2n îò èíôîðìàöèîííûõ ÁÏ è ïîýòîìó èìååònñëîæíîñòü íå ìåíüøå, ÷åì 22 +1 . Ýòî ïîêàçûâàåò, ÷òî âûáîð¾ïðàâèëüíîãî¿ ïîðÿäêà ïåðåìåííûõ ïðè ðàçëîæåíèè ÔÀËìîæåò ñóùåñòâåííî óìåíüøèòü ñëîæíîñòü ÊÑ, ïîñòðîåííîéïî ìåòîäó êàñêàäîâ.Ó÷èòûâàÿ âñå ñêàçàííîå âûøå, äîïîëíèì ëåììû 1.3 è 1.4ñëåäóþùèì óòâåðæäåíèåì.Ëåììà 3.1. Äëÿ ëþáîãî íàòóðàëüíîãî n è σ ∈ B âûïîëíÿþòñÿ íåðàâåíñòâà:KL(`σn )¹ º1,6 4n − 4 +n¡→¢−nLK P 2 (n) 6 2 · 22 .Ðàññìîòðèì, â çàêëþ÷åíèå, ìåòîä Øåííîíà äëÿ ñèíòåçà ÊÑ è ÑÔÝ (ñì.

[32, 14]), êîòîðûé ïîçâîëÿåò óñòàíîâèòüïîðÿäîê ðîñòà ôóíêöèé Øåííîíà LK (n) è LC (n) (ñì. Ÿ2).Ìåòîä Øåííîíà çàêëþ÷àåòñÿ â âûáîðå íåêîòîðîãî ïàðàìåòðà q, 1 6 q 6 n, è ïîñòðîåíèè ñõåìû Σf , ðåàëèçóþùåéïðîèçâîëüíóþ ÔÀË f (x1 , . . . , xn ) íà îñíîâå åå ðàçëîæåíèÿïî ÷àñòè ïåðåìåííûõ (ñì. ðàâåíñòâî (2.5) èç ãë. 1):_¡¢¡ ¢σq+1f x0 , x00 =xq+1· · · xσnn · fσ00 x0 ,(3.4)σ 00 =(σq+1 ,...,σn )ãäå x0 = (x1 , . . . , xq ) , x00 = (xq+1 , . .

. , xn ) è fσ00 (x0 ) == f (x0 , σ 00 ) ïðè âñåõ σ 00 , σ 00 ∈ B n−q . Ïðè ýòîì ñõåìà Σf ïðåäñòàâëÿåò ñîáîé êîððåêòíóþ ñóïåðïîçèöèþ âèäà Σ00 (Σ0 ), ãäåΣ00 ìóëüòèïëåêñîð ïîðÿäêà (n − q) îò àäðåñíûõ ÁÏ x00 ,èíôîðìàöèîííûå âõîäû êîòîðîãî ïðè âûïîëíåíèè óêàçàííîé ñóïåðïîçèöèè ïðèñîåäèíÿþòñÿ ê âûõîäàì óíèâåðñàëüíîãî ìíîãîïîëþñíèêà Σ0 ïîðÿäêà q îò ÁÏ x0 â ñîîòâåòñòâèèñ (3.4).Ïîëàãàÿq = blog (n − 2 log n)c ,28Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìïîñòðîèì äëÿ ÔÀË f (x1 , . . . , xn ) óêàçàííûì âûøå ñïîñîáîìÊÑ (ÑÔÝ â áàçèñå Á0 ) Σf , ãäå Σ00 (2n−q , 1)-ÊÄ ïîðÿäêà(n − q) èç Ÿ6 ãëàâû 2 (ñîîòâåòñòâåííî ôîðìóëà Fn−q èç ëåììû 1.4), à Σ0 óíèâåðñàëüíûé ìíîãîïîëþñíèê èç ëåììû 3.1(ñîîòâåòñòâåííî ëåììû 1.3). Êîððåêòíîñòü ïîñòðîåííîé ñóïåðïîçèöèè â ñëó÷àå ÊÑ îáåñïå÷èâàåòñÿ ðàçäåëèòåëüíîñòüþÊÄ.

Äëÿ ñëîæíîñòè ïîëó÷åííîé ñõåìû Σf áóäóò ñïðàâåäëèâû îöåíêèµ n¶2n+22qL (Σf ) 6 2 · 22 + 2 · 2n−q 6+O,n − 2 log nn2åñëè Σf ∈ UK , è2qL (Σf ) 6 2n−q+4·28 · 2n6+On − 2 log nµ2nn2¶,åñëè Σf ∈ UC . Òàêèì îáðàçîì, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 3.1. Äëÿ ôóíêöèé Øåííîíà LK (n) è LC (n) âûïîëíåíû ñîîòíîøåíèÿ:LK (n) .

42n,nLC (n) . 82n.nŸ4 Ðåãóëÿðíûå ðàçáèåíèÿ åäèíè÷íîãî êóáà è ìîäåëèðîâàíèå ôóíêöèé ïåðåìåííûìè. Ñèíòåçñõåì äëÿ íåêîòîðûõ äåøèôðàòîðîâ è ìóëüòèïëåêñîðîâ.Ìíîæåñòâî δ, δ ⊆ B q , íàçûâàåòñÿ m-ðåãóëÿðíûì ìíîæåñòâîì íàáîðîâ êóáà B q , åñëè m < q, |δ| = 2m è âñå ïðåôèêñû1 äëèíû m íàáîðîâ èç δ ðàçëè÷íû. Çàìåòèì, ÷òî mðåãóëÿðíîìó ìíîæåñòâó δ, δ ⊆ B q , ìîæíî âçàèìíîîäíîçíà÷íî ñîïîñòàâèòü ñèñòåìó ÔÀË ψ = (ψ1 , .

. . , ψq−m ) èç P2q−m (m)1Äëÿ ñëîâà (íàáîðà) α âèäà α = βγ ñëîâî β (γ ) ñ÷èòàåòñÿ åãî ïðåôèêñîì (ñîîòâåòñòâåííî ñóôôèêñîì ).Ÿ4. Ðåãóëÿðíûå ðàçáèåíèÿ åäèíè÷íîãî êóáà29òàê, ÷òî íàáîð α = (β, γ), ãäå β ∈ B m è γ ∈ B q−m , ïðèíàäëåæèò δ òîãäà è òîëüêî òîãäà, êîãäà ψ (β) = γ . Çàìåòèì òàêæå, ÷òî ëþáàÿ ÔÀË g, g ∈ P2 (q), ñîâïàäàåò íàm-ðåãóëÿðíîì ìíîæåñòâå íàáîðîâ δ, δ ⊆ B q , ñ íåêîòîðîéÔÀË èç P2 (m), åñëè ðàññìàòðèâàòü P2 (m) êàê ìíîæåñòâîâñåõ ÔÀË èç P2 (q) ñ íåñóùåñòâåííûìè ÁÏ xm+1 , . . . , xq . Ïðèýòîì ëþáàÿ ÔÀË èç ñâÿçàííîé ñ δ ñèñòåìû ôóíêöèé ñîâïàäàåò íà δ ñ ñîîòâåòñòâóþùåé ÁÏ êóáà B q .Äëÿ íàáîðîâ β = (β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 èíâåðòèðîâàíèåì íåêîòîðûõ ÔÀË.Ëåììà 4.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 =30Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìδ1 ⊕ α, ãäå ν(α) = i − 1, äëÿ âñåõ i, i = 1, . . . , 2q−m .

Èç ïîñòðîåíèÿ ñèñòåìû ìíîæåñòâ ∆ = (δ1 , . . . , δ2q−m ) ñëåäóåò, ÷òîêàæäîå èç íèõ îáëàäàåò òðåáóåìûì ñâîéñòâàìè, ñâÿçàííûìèñ ìîæåëèðîâàíèåì ÔÀË èç g ñ ïîìîùüþ ÁÏ.Ïîêàæåì òåïåðü, ÷òî ∆ ïîêðûòèå êóáà B q . Äëÿ ýòîãîâîçüìåì ïðîèçâîëüíûé íàáîð èç B q âèäà (β, γ), ãäå β ∈ B mè γ ∈ B q−m , à ïî íåìó íàéäåì â ìíîæåñòâå δ íàáîð âèäà(β, γb), êîòîðûé èìååòñÿ â δ â ñèëó m-ðåãóëÿðíîñòè ýòîãîìíîæåñòâà. Ñëåäîâàòåëüíî,(β, γ) = (β, γ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 .Ëåììà äîêàçàíà.Ëåììà 4.2 (ñð. [14]). Äëÿ n = 1, 2, 3, . . . âûïîëíÿþòñÿ íåðàâåíñòâൠn¶³−→ ´2,LÊ Q n 6 2n + Onµ n¶³→ ´2Ê −n+1LJn 62+O.n(4.1)(4.2)Äîêàçàòåëüñòâî. Âûáåðåì ïàðàìåòðû m, q è λ òàê, ÷òîλ = 2m ,q = m + λ è q 6 n,Ÿ4. Ðåãóëÿðíûå ðàçáèåíèÿ åäèíè÷íîãî êóáà31à çàòåì ðàññìîòðèì m-ðåãóëÿðíîå ìíîæåñòâî íàáîðîâ δ1 êóáà B q îò ÁÏ x0 = (x1 , . . . , xq ), ñâÿçàííîå ñ ñèñòåìîé ÔÀË−→Q m (x1 , . .

. , xm ), êîòîðàÿ ñîñòîèò èç âñåõ ÝÊ âèäà xσ1 1 · · · xσmm ,ãäå ν(σ1 , . . . , σm ) = j − 1, j ∈ [1, λ].Ïîñòðîèì äëÿ ýòîé ñèñòåìû ïî ëåììå 4.1 ðàçáèåíèå ∆ =(δ1 , . . . , δ2q−m ) êóáà B q è çàìåòèì, ÷òî ëþáàÿ ÝÊ K(x0 ) =σxσ1 1 · · · xq q , ãäå σ 0 = (σ1 , . .

. , σq ) ∈ δi , ñîâïàäàåò íà ìíîæåñòâå−→δi ñ îäíîé èç ÝÊ ñèñòåìû Q m , òî åñòü ñîâïàäåò íà íåì ñα 0áóêâîé xj σ0 , ãäå m + 1 6 jσ0 6 q, ασ0 ∈ B . Çàìåòèì, ÷òî âσñèëó óêàçàííûõ âûøå ñâîéñòâ ðàçáèåíèÿ ∆ ëþáàÿ ÝÊ K =xσ1 1 · · · xσnn , ãäå σ 0 = (σ1 , . . . , σq ) ∈ δi , 1 6 i 6 2λ , ìîæåò áûòüïðåäñòàâëåíà â âèäåαK = χi (x0 ) · xj σ0 · Kσ00 (x00 ),0(4.3)σãäå x00 = (xq + 1, . . .

, xn ), σ 00 = (σq+1 , . . . , σn ).Ïóñòü, äàëåå, (1, 2λ )-ÊÑ Σ0 ðåàëèçóåò ñòðîêó èç ÔÀË−→χ = (χ1 , . . . , χ2λ ),£ ãäå ¤χi (x0 ) õàðàêòåðèñòè÷åñêàÿ ÔÀËìíîæåñòâà δi , i ∈ 1, 2λ , è ïîëó÷àåòñÿ â ðåçóëüòàòå îòîæäåñòâëåíèÿ âõîäîâ ó ñõåì Σ1 , . . . , Σ2λ , ãäå π -ñõåìà Σi , i ∈[1, 2λ ], ïîñòðîåíà ïî ëåììå 1.2 äëÿ ÔÀË χi , ïðè÷åì âûõîäîìΣi ñ÷èòàåòñÿ êîðåíü ñîîòâåòñòâóþùåãî ÊÄ (ñì. ðèñ. 4.1).−→(&)Èñêîìàÿ (1, 2n )-ÊÑ Σn ðåàëèçóåò êàæäóþ ÝÊ èç Q mâ ñîîòâåòñòâèè ñ (4.3), èìååò âèä, ïîêàçàííûé íà ðèñ.

4.1, èÿâëÿåòñÿ ÊÊÑ.Ïîëàãàÿm = dlog ne − 2,ïîëó÷èì, ÷òîλ = 2m 6n,2q = m + λ 6 n.(&)Ïðè ýòîì ñëîæíîñòü ïîñòðîåííîé (1, 2n )-ÊÑ Σn , ÿâëÿþùåéñÿ êîíòàêòíûì äåøèôðàòîðîì ïîðÿäêà n, óäîâëåòâîðÿ-32Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÐèñ. 4.1: ê äîêàçàòåëüñòâó ëåììû 4.2åò íåðàâåíñòâàì:µ n¶³´2(&)n−mn−m+1qnL Σn6 λ2+2+ q2 6 2 + O,nèç êîòîðûõ âûòåêàåò íåðàâåíñòâî (4.1).(∨)Èñêîìàÿ (1, 2n )-ÊÑ Σn , ÿâëÿþùàÿñÿ äèçúþíêòèâíûìêîíòàêòíûì äåøèôðàòîðîì ïîðÿäêà n, ñëîæíîñòü êîòîðîãîóäîâëåòâîðÿåò îöåíêå (4.2), ïîëó÷àåòñÿ â ðåçóëüòàòå ïåðå(&)õîäà îò ÊÊÑ Σn ê èíâåðñíîé ÊÊÑ â ñîîòâåòñòâèè ñ ëåììîé 10.1 ãëàâû 2.Ëåììà äîêàçàíà.Ÿ4.

Ðåãóëÿðíûå ðàçáèåíèÿ åäèíè÷íîãî êóáà33Ñëåäñòâèå. Îöåíêè ëåììû 4.2 è ñëåäñòâèÿ èç ëåììû 2.2äàþò àñèìïòîòè÷åñêîå ðàâåíñòâî³→− ´LÊ Q n ∼ 2nËåììà 4.3. Äëÿ n = 1, 2, . . . âûïîëíÿþòñÿ íåðàâåíñòâàµπnL (µn ) 6 2 · 2 + O2nn¶µCn, L (µn ) 6 2 · 2 + O2nn¶,D(µn ) 6 n + 6,ïðè÷åì ñóùåñòâóåò òàêàÿ ðåàëèçóþùàÿ ÔÀË µn è áåñïîb n ñ ïîäíÿòûìèâòîðíàÿ ïî èíôîðìàöèîííûì ÁÏ ôîðìóëà Fîòðèöàíèÿìè, ãëóáèíà êîòîðîé óäîâëåòâîðÿåò ïîñëåäíåìóèç íèõ, àëòåðíèðîâàíèå íå áîëüøå 3, à ñëîæíîñòü íå ïðåâîñõîäèò 7 · 2n .Äîêàçàòåëüñòâî.

Èñêîìàÿ π -ñõåìà Σn ïîëó÷àåòñÿ â ðåçóëü(&)òàòå ïðèñîåäèíåíèÿ ê êàæäîìó èç âûõîäîâ (1, 2n )-ÊÑ Σn ,ïîñòðîåííîé ïðè äîêàçàòåëüñòâå ëåììû 4.2, êîíòàêòà ñîîòâåòñòâóþùåé åìó èíôîðìàöèîííîé ÁÏ è îòîæäåñòâëåíèÿêîíöåâûõ âåðøèí âñåõ òàêèõ êîíòàêòîâ â âûõîäíóþ âåðøèíó Σn . Èñêîìàÿ ÑÔÝ Sn ïîëó÷àåòñÿ èç ôîðìóëû ñ ïîäíÿòûìè îòðèöàíèÿìè Fn , êîòîðàÿ ìîäåëèðóåò π -ñõåìó Σn(ñì. Ÿ6 ãë. 2), â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèé ïðèâåäåíèÿ (ñì. Ÿ1) äëÿ âåðøèí, ñîîòâåòñòâóþùèõ ÔÝ ¬.Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà ëåììû íà îñíîâå ðàçáèåíèÿ ∆, ââåäåííîãî â ëåììå 4.2, è ïðåäñòàâëåíèÿ (4.3) ïîñòðîèì äëÿ ÔÀË µn ôîðìóëó F̃n ñëåäóþùèì îáðàçîìF̃n (x1 , . .

. , xn , y0 , . . . , y2n −1 ) =λ__ α 0(4.4)¡ 0¢Ai x & & Jσ00 (x00 ) ∨=xj σ0 yν(σ0 ,σ00 ) i=1σ 00 ∈B n−qσ 0 ∈δiσ34Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìãäå Ai ñîâåðøåííàÿ ÄÍÔ ÔÀË χi , i = 1, . . . , λ, è Jσ00 (x00 ) =K σ00 (x00 ). Ëåãêî âèäåòü, ÷òî F̃n ðåàëèçóåò ìóëüòèïëåêñîðíóþÔÀË µn , áåñïîâòîðíà ïî ÁÏ y0 , . .

. , y2n −1 è ÷òî Alt (F̃n ) 6 3.Ïóñòü, äàëåå, ôîðìóëà F̌n ïîëó÷àåòñÿ â ðåçóëüòàòå îïòèìèçàöèè ôîðìóëû F̃n ïî ãëóáèíå. Òîãäà ïðèl ³ n ´mn > 3 è m = log3b n áóäóò óäîâëåòâîðÿòü óñëîâèÿì ëåìñëîæíîñòü è ãëóáèíà Fìû. Äåéñòâèòåëüíî, åñëè1 n > 6, òî q 6 n − m è, ñëåäîâàòåëüíî,³ ´¡¡¢¢e n = 2q−m q · 2m + 2n−q (n − q) + 2m+1 6R F6 2n+1 + n · 2n−m 6 2n+1 + 3 · 2n = 5 · 2n .Ïðè ýòîì, î÷åâèäíî,L¬ (F̃n ) 6´1³R(F̃n ) − 2n 6 2n+12è, òàêèì îáðàçîì,L(F̃n ) 6 R(F̃n ) + L¬ (Fn ) − 1 6 7 · 2n − 1,bn ) 6îòêóäà â ñèëó ñëåäñòâèÿ 1 èç òåîðåìû 2.1 ñëåäóåò, ÷òî D(Fn + 6.Ëåììà äîêàçàíà.Ñëåäñòâèå.n + 1 6 D(µn ) 6 n + 6.1Ñëó÷àé n 6 5 ðàññìàòðèâàþòñÿ îòäåëüíî.Ÿ5. Ìåòîä Ëóïàíîâà ñèíòåçà ÑÔÝ35Ÿ5 Äèçúþíêòèâíî-óíèâåðñàëüíûå ìíîæåñòâàôóíêöèé.