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

Ðàññìîòðèì ñíà÷àëà ñëó÷àé, êîãäà a = 1è log q > 1.  ýòîì ñëó÷àå íåðàâåíñòâî (2.11) ñëåäóåò èç òîãî,÷òî ëåâàÿ ÷àñòü (2.10) ìîíîòîííî âîçðàñòàåò ïî y , è äëÿy 0 = (1 + ε)log q,log log qãäålog log log q,log (e log q)ñïðàâåäëèâû ñîîòíîøåíèÿε=y 0 log y 0 =log q(log log q − log log log q + log e ln (1 + ε)) 6log log qµ¶log log log qε log e6 log q (1 + ε) 1 −+=log log qlog log q¡¢= log q (1 + ε) (1 − ε) = log q 1 − ε2 6 log q.= (1 + ε)Çàìåòèì, ÷òî â ñëó÷àå a > 0 íåðàâåíñòâî (2.10) ýêâèâàëåíòíî íåðàâåíñòâó(ay)ay > q a ,è ïîýòîìó íåðàâåíñòâî (2.11) ïîëó÷àåòñÿ èç íåðàâåíñòâà y > y 0â ðåçóëüòàòå çàìåíû y íà ay è log q íà a log q , åñëè âûïîëíåíîóñëîâèå a log q > 1.Íåðàâåíñòâî (2.12) â ñëó÷àå a > 1 ïîëó÷àåòñÿ â ðåçóëüòàòå ëîãàðèôìèðîâàíèÿ íåðàâåíñòâà ay > q è äåëåíèÿ îáåèõ÷àñòåé ïîëó÷åííîãî íåðàâåíñòâà íà log a.Ëåììà äîêàçàíà.Ÿ2. Íèæíèå îöåíêè19Òåîðåìà 2.1.

Äëÿ íåêîòîðîé ïîñëåäîâàòåëüíîñòè ε=ε(n),n = 1, 2, . . ., òàêîé, ÷òî ε (n) > 0 ïðè n > n0 è ε (n) ñòðåìèòñÿ ê 0 ïðè n ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè, âûïîëíÿþòñÿ íåðàâåíñòâà2n,n2nLΦ (n) > (1 − ε (n)),log n2nLK (n) > (1 − ε (n)) ,n2nLπ (n) > (1 − ε (n)).log nLC (n) > (1 + ε (n))(2.13)(2.14)(2.15)(2.16)Äîêàçàòåëüñòâî. Íåðàâåíñòâà (2.13)(2.16) âûâîäÿòñÿ èç ñîîòâåòñòâóþùåãî ðàññìàòðèâàåìîìó êëàññó ñõåì U ñ ôóíêöèîíàëîì ñëîæíîñòè L íåðàâåíñòâà (2.6)(2.9) íà îñíîâå ìîùíîñòíîãî ðàâåíñòâà (2.4) ñ èñïîëüçîâàíèåì ëåììû 2.3, ãäånq = 22 , è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π .Äåéñòâèòåëüíî, ïîäñòàâëÿÿ óêàçàííûå çíà÷åíèÿ â (2.11) ïî-20Ãëàâà 3.

Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìëó÷èìC1) L (n) >>2) LΦ (n) >3) LK (n) >>µ¶2nlog(n + 3)1+−n>n+3n+5µ¶(2.17)log n − 3 − o(1)2n1+nnµ¶n3 + o(1)2n21−(2.18)−1>log n + 3log nlog nµ¶2nlog(n + 3 + log n)1+>n + 3 + log nn + 5 + log nµ¶(2.19)3 + o(1)2n1−nnÑëåäîâàòåëüíî, íåðàâåíñòâî (2.13) ((2.14), (2.15)) áóäåòñïðàâåäëèâî äëÿ äîñòàòî÷íî áîëüøèõ n ïðè ε (n) = log nn−4(ñîîòâåòñòâåííî ε (n) = log4 n , ε (n) = n4 ).Àíàëîãè÷íûì îáðàçîì óñòàíàâëèâàåòñÿ ñïðàâåäëèâîñòü(2.16) ïðè ε (n) = log5 n .Òåîðåìà äîêàçàíà.Ñëåäñòâèå 1.LC (n) &2n,n2n2n, LK (n) &,log nn2nLπ (n) &.log nLΦ (n) &Ñëåäñòâèå 2. Íèæíèå îöåíêè (2.13)(2.16) ïðè óêàçàííûõâ äîêàçàòåëüñòâå çíà÷åíèÿõ ε(n) ñïðàâåäëèâû äëÿ ñëîæíîñòè ïî÷òè âñåõ ÔÀË f, f ∈ P2 (n), ïðè èõ ðåàëèçàöèè âñîîòâåòñòâóþùèõ êëàññàõ ñõåì.nÄåéñòâèòåëüíî, çàìåíà âåëè÷èíû q = 22 âåëè÷èíîé q =1 2nïðè ïîëó÷åíèè îöåíîê (2.17)(2.19) ñ ïîìîùüþ ëåìn2ìû 2.3 ïîâëèÿåò òîëüêî íà ó÷àñòâóþùèå â èõ ïîñëåäíèõŸ3.

Ìåòîä êàñêàäîâ äëÿ ÊÑ è ÑÔÝ21íåðàâåíñòâàõ ôóíêöèè âèäà o(1). Ïðè ýòîì, â ñèëó (2.5),b ïðàâàÿ ÷àñòü ñîîòâåòñòâóþùåãî íåðàâåíãäå δ = n1 , à Ψñòâà (2.13)(2.15), âíîâü ïîëó÷åííàÿ îöåíêà áóäåò ñïðàâåäëèâà äëÿ ïî÷òè âñåõ ÔÀË f, f ∈ P2 (n). Ñïðàâåäëèâîñòüíèæíåé îöåíêè (2.16) äëÿ ïî÷òè âñåõ ÔÀË óñòàíàâëèâàåòñÿàíàëîãè÷íî.Àíàëîãè÷íûì îáðàçîì íà îñíîâå (2.12) è ëåììû 4.3 ãëàâû 2 äîêàçûâàåòñÿ ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 2.2. Äëÿ n = 1, 2, . . . ñïðàâåäëèâî íåðàâåíñòâîD(n) > n − log log n + o(1).(2.20)Çàìå÷àíèå. Îöåíêà (2.20) ñïðàâåäëèâà äëÿ ãëóáèíû D(f )ïî÷òè âñåõ ÔÀË f , f ∈ P2 (n).Ÿ3 Ìåòîä êàñêàäîâ äëÿ êîíòàêòíûõ ñõåì èñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ.Ìåòîä ØåííîíàÏðèâåäåííûå ⠟1 ïðîñòåéøèå ìåòîäû ñèíòåçà ïîçâîëÿþòñòðîèòü ôîðìóëû è π -ñõåìû, ñïåöèôèêà êîòîðûõ íå äîïóñêàåò ìíîãîêðàòíîãî èñïîëüçîâàíèÿ ¾ïðîìåæóòî÷íûõ ðåçóëüòàòîâ¿.

Ìåòîä êàñêàäîâ [20] ÿâëÿåòñÿ äîñòàòî÷íî ïðîñòûì èâ òî æå âðåìÿ äîâîëüíî ýôôåêòèâíûì ìåòîäîì ñèíòåçà êàêÊÑ, òàê è ÑÔÝ, êîòîðûé ïîçâîëÿåò ýòî äåëàòü. Îí ñâÿçàíñ ïîñëåäîâàòåëüíûì ðàçëîæåíèåì çàäàííûõ ÔÀË ïî ÁÏ èðåêóðñèâíûì ïîñòðîåíèåì ñõåìû, ðåàëèçóþùåé ýòè ÔÀË.Ìåòîä êàñêàäîâ ïîçâîëÿåò ïî ïðîèçâîëüíîé çàäàííîé ñèñòåìå ôóíêöèé àëãåáðû ëîãèêè F = (f1 , . . . , fm ), F ∈ P2m (n),ñòðîèòü (1, m)-ÊÑ ΣF , ΣF ∈ UK , è ÑÔÝ UF , UF ∈ UC , êîòîðûå ðåàëèçóþò F . Áóäåì ñ÷èòàòü, ÷òî âñå ÔÀË f1 , f2 , . . . , fmñèñòåìû F ðàçëè÷íû, îòëè÷íû îò êîíñòàíò, è äëÿ êàæäîéÁÏ xi , 1 6 i 6 n, ñðåäè íèõ åñòü ÔÀË, ñóùåñòâåííî çàâèñÿùàÿ îò xi .22Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÐàçëîæèì ÔÀË f1 , f2 , .

. . , fm ñíà÷àëà ïî ÁÏ x1 , ïîòîì ïîÁÏ x2 è òàê äàëåå. Ïðè ýòîì ïîñòðîèì ïîñëåäîâàòåëüíîñòèb i , ñîñòîÿùèõ èç ÔÀË îò ÁÏ xi , xi+1 , . . . , xn ,ìíîæåñòâ Gi è Gãäå i = 1, 2, . . . , n, òàêèå, ÷òî1. Gi ñîñòîèò èç âñåõ ðàçëè÷íûõ ÔÀË g (xi , . . . , xn ) âèäàg = fj (σ1 , . . .

, σi−1 , xi , xi+1 , . . . , xn ) ,ãäå 1 6 j 6 m, (σ1 , . . . , σi−1 ) ∈ B i−1 ;b i ñîñòîèò èç âñåõ ðàçëè÷íûõ ôóíêöèé g, g ∈ Gi , êî2. Gòîðûå ñóùåñòâåííî çàâèñÿò îò xi .Ëåãêî âèäåòü, ÷òîG1 = {f1 , . . . , fm } ,b n ⊆ {xn , xn } ,Gb1 , . . . , Gb n íå ïóñòû è ïîïàðíî íå ïåðåñåà ìíîæåñòâà ÔÀË Gêàþòñÿ.b i , ãäå 1 6 i 6 n,Çàìåòèì, ÷òî ëþáóþ ÔÀË g, g ∈ Gìîæíî ïðåäñòàâèòü (ñì. Ÿ10 ãëàâû 2) â âèäåg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 ,(3.1)ãäå gσ = g (σ, xi+1 , .

. . , xn ), è, ñëåäîâàòåëüíî, gσ ∈ Ǧi+1 ∪{0, 1} äëÿ âñåõ σ, σ ∈ B . Åñëè ïðè ýòîì äëÿ íåêîòîðîãîσ, σ ∈ B , ÔÀË gσ ðàâíà 0, òî âìåñòî (3.1) áóäåì èñïîëüçîâàòü ðàçëîæåíèåg = xσi gσ ,(3.2)ãäå gσ ∈ Ǧi+1 ∪ {1}.Ñ ïîìîùüþ îïåðàöèé ïðèñîåäèíåíèÿ îäíîãî èëè äâóõïðîòèâîïîëîæíûõ êîíòàêòîâ (ñì. Ÿ10 ãë.

2) ïîñòðîèì ÊÊÑ→−b1 ∪ . . . ∪ Gbn .Σ̌F , êîòîðàÿ ðåàëèçóåò ñèñòåìó ÔÀË G F , ãäå GF = GÏðè ýòîì äëÿ êàæäîãî i, i = n, (n − 1), . . . , 1, êàæäàÿ ÔÀËb i , ðåàëèçóåòñÿ ñîãëàñíî (3.1) ((3.2)) íà âûõîäå v , êîg, g ∈ Gòîðûé ïðè α = 0, 1 (ñîîòâåòñòâåííî α = σ ) ñîåäèíåí êîíòàêòîì âèäà xαi ñ òåì âûõîäîì vα , ãäå ðåàëèçóåòñÿ ÔÀ˟3.

Ìåòîä êàñêàäîâ äëÿ ÊÑ è ÑÔÝ23gα = g (α, xi+1 , . . . , xn ) òàê, êàê ýòî ïîêàçàíî íà ðèñ. 10.1a(ñîîòâåòñòâåííî ðèñ. 10.1b) ãëàâû 2.Äëÿ ïîëó÷åíèÿ èñêîìîé ÊÑ ΣF äîñòàòî÷íî ¾ñíÿòü¿ ïîìåòêè ñ òåõ âûõîäíûõ âåðøèí ÊÑ Σ̌F , â êîòîðûõ ðåàëèçóþòñÿ ÔÀË, îòëè÷íûå îò f1 , . . . , fm .Àíàëîãè÷íûì îáðàçîì ïî ìåòîäó êàñêàäîâ ñòðîèòñÿ è−→ÑÔÝ ǓF , ðåàëèçóþùàÿ ñèñòåìó ÔÀË G F , ñ òîé ëèøü ðàçíèöåé, ÷òî:1.

ñíà÷àëà ðåàëèçóþòñÿ âñå ÔÀË âèäà xi , 1 6 i 6 n,êîòîðûå âñòðå÷àþòñÿ â ÊÑ ΣF ;2. äëÿ âñåõ i, i = (n − 1) , . . . , 1, ðàçëîæåíèå (3.1), ãäåb i è g0 , g1 ∈ Ǧi+1 , ðåàëèçóåòñÿ òàê, êàê ïîêàçàíîg ∈Gíà ðèñ. 10.2a ãëàâû 2, à ðàçëîæåíèå (3.2), ïðèìåíÿåìîåâ ñëó÷àå gσ = 0 (ðàçëîæåíèåg = xσi ∨ gσ xσi = xσi ∨ gσ(3.3)â ñëó÷àå gσ = 1), òàê, êàê ïîêàçàíî íà ðèñ.

10.2b(ñîîòâåòñòâåííî 10.2c ãëàâû 2);3. êàæäàÿ ÔÀË âèäà gσ xσi , èñïîëüçóåìàÿ â ïðåäûäóùåìïóíêòå ïðè ðåàëèçàöèè ðàçëîæåíèé âèäà (3.1) èëè (3.2)äëÿ ðàçëè÷íûõ ÔÀË g , ðåàëèçóåòñÿ òîëüêî îäèí ðàç.Êàê è â ñëó÷àå ÊÑ, ÑÔÝ UF , ðåàëèçóþùàÿ ñèñòåìó ÔÀË Fè ïîñòðîåííàÿ ïî ìåòîäó êàñêàäîâ, ïîëó÷àåòñÿ èç ÑÔÝ ǓFâ ðåçóëüòàòå ¾ñíÿòèÿ¿ òåõ âûõîäîâ, â êîòîðûõ ðåàëèçóþòñÿÔÀË, îòëè÷íûå îò ÔÀË èç F .Ïóñòü, íàïðèìåð, F = (f1 , f2 ), ãäåf1 = x1 x2 (x3 ⊕ x4 ) ∨ x1 (x2 ∨ x3 x4 ) ,f2 = x1 (x3 ⊕ x4 ) ∨ x1 x4 .24Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÒîãäà:b 1 = G1 = {f1 , f2 } ;Gb 2 = {x2 (x3 ⊕ x4 ) , x2 ∨ x3 x4 } , G2 = Gb 2 ∪ {x3 ⊕ x4 , x4 } ;Gb 3 = {x3 ⊕ x4 , x3 x4 } ,b 3 ∪ {x4 } ;GG3 = Gb 4 = {x4 , x4 } .GÍà ðèñ.

3.1 ïîêàçàíà ïîñòðîåííàÿ äëÿ äàííîé ñèñòåìû ÔÀËÊÑ Σ̌F , âåðøèíû êîòîðîé ïîìå÷åíû ñîïîñòàâëåííûìè èìÔÀË, íà ðèñ. 3.2 ñîîòâåòñòâóþùàÿ åé ÊÑ ΣF , à íà ðèñ. 3.3 ÑÔÝ UF .Äðóãèì ïðèìåðîì ÊÑ, ïîñòðîåííîé ïî ìåòîäó êàñêàäîâäëÿ ëèíåéíîé ÔÀË `n , ãäå n > 2, ÿâëÿåòñÿ èçâåñòíàÿ ñõåìà Êàðäî [31], ïîêàçàííàÿ íà ðèñ. 3.4. Çàìåòèì, ÷òî ýòà ÊÑèìååò ñëîæíîñòü (4n − 4) è ÿâëÿåòñÿ ìèíèìàëüíîé.  òî æåâðåìÿ ÑÔÝ, ïîñòðîåííàÿ äëÿ `n , n > 2, ïî ìåòîäó êàñêàäîâèìååò ñëîæíîñòü (7n − 9) è íå ÿâëÿåòñÿ ìèíèìàëüíîé, òàêêàê èìååò áîëüøóþ ñëîæíîñòü ïî ñðàâíåíèþ ñî ñõåìîé Σ⊕nñëîæíîñòè (4n − 4), ïîêàçàííîé íà ðèñ. 9.1 ãëàâû 2.

Àíàëîãè÷íûå îöåíêè ñïðàâåäëèâû äëÿ ÔÀË `n (ñì. ëåììó 1.4).Ïðè ïîñòðîåíèè ïî ìåòîäó êàñêàäîâ (1, 2n )-ÊÑ, ðåàëèçó−→þùåé ñèñòåìó ôóíêöèé àëãåáðû ëîãèêè Q n , ìû ïîëó÷èìêîíòàêòíîå äåðåâî ïîðÿäêà n, ïîêàçàííîå íà ðèñ. 6.4a èçŸ6 ãëàâû 2. Êàê áóäåò ïîêàçàíî ⠟4 ýòî ÊÄ íå ÿâëÿåòñÿìèíèìàëüíûì êîíòàêòíûì äåøèôðàòîðîì.Àíàëîãè÷íûì îáðàçîì ñ ïîìîùüþ ìåòîäà êàñêàäîâ ìîæíî ïîñòðîèòü êîíòàêòíûé óíèâåðñàëüíûé ìíîãîïîëþñíèê ñëîæníîñòè íå áîëüøå, ÷åì 2 · 22 , à òàêæå êîíòàêòíûé ìóëüòèïëåêñîð ïîðÿäêà n è ñëîæíîñòè 3 · 2n − 2, ïîêàçàííûé íàðèñ. 6.6b ãëàâû 2 (ñì. ëåììó 1.4).