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

, a0p è âûõîäàìè a001 , . . . , a00q , â êîòîðîé âñå ðåáðà (äóãè) ïîìå÷åíû ïåðåìåííûìè x1 , . . . , xn èëèèõ îòðèöàíèÿìè x1 , . . . , xn , íàçûâàåòñÿ (p, q)(ÊÑ)x1 , . . . , xn è îáîçíà÷àåòñÿ Σ == Σ (x1 , . . . , xn ) èëè Σ = Σ x1 , .

. . , xn ; a01 , . . . , a0p ; a001 , . . . , a00q .Ïðè ýòîì ÷èñëî êîíòàêòîâ íàçûâàåòñÿÊÑ Σè îáîçíà÷àåòñÿ ÷åðåç L (Σ). Íà ðèñ. 6.3ac ïîêàçàíû íåêîòîðûå êîíêðåòíûå ÊÑ îò ÁÏ x1 , x2 , x3 ñ âõîäîì a1 è âûõîäàìèa2 , a3 .Ïóñòü Σ ÊÑ îò ÁÏ X (n) è α = (α1 , . . . , αn ) íàáîð èç B n . Îïðåäåëèì ñåòü Σ|α êàê ñåòü, ïîëó÷àþùóþñÿèç Σ â ðåçóëüòàòå óäàëåíèÿ âñåõ ðåáåð (äóã) ñ ïîìåòêàìèxα1 1 , . . . , xαnn , òî åñòü ðåáåð, êîòîðûå íå ïðîâîäÿò íà íàáîðå α, è ñíÿòèÿ ïîìåòîê ñ îñòàëüíûõ ðåáåð Σ.

Äëÿ âåðøèív è u ÊÑ Σ ââåäåìvu êàê ÔÀË gv,u (x1 , . . . , xn ), êîòîðàÿ ðàâíà 1 íàíàáîðå α = (α1 , . . . , αn ) ∈ B n òîãäà è òîëüêî òîãäà, êîãäàâ ñåòè Σ|α ñóùåñòâóåò (v − u)-öåïü, òî åñòü òîãäà è òîëüêî òîãäà, êîãäà â Σ èìååòñÿ öåïü èç ïðîâîäÿùèõ íà íàáîðåα êîíòàêòîâ âèäà xα1 1 , . . . , xαnn , èäóùàÿ èç v â u. Áóäåì ãîâîðèòü òàêæå, ÷òî ÔÀË gv,u ÿâëÿåòñÿuv , èëè, èíà÷å,v u. Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî äëÿíàõîæäåíèÿ ÔÀË gv,u (x1 , .

. . , xn ) äîñòàòî÷íî ïðîñìîòðåòüâñå íàáîðû α, α ∈ B n , è äëÿ êàæäîãî èç íèõ âûÿñíèòü íàëè÷èå èëè îòñóòñòâèå â Σ öåïè, ñîñòîÿùåé èç ïðîâîäÿùèõìîéîò ÁÏ-êîíòàêòíîé ñõå-ñëîæíîñòüþê âåðøèíåôóíêöèþ ïðîâîäèìîñòè îò âåðøèíûìîñòè âåðøèíû èç âåðøèíûìåæäó âåðøèíàìè èôóíêöèåé äîñòèæèðåàëèçóåòñÿŸ6.Êîíòàêòíûå ñõåìû èπ -ñõåìû,vs3sx1x1x1s v1x2 v2x2s v1v2 sa2a1x151îöåíêà èõ ÷èñëàa1x1x2v4sx3sa)C2C1sa2C3b)a1 svsx1x1sx2sx3s a3x1x2x3x1x2x3sx2sx3sa2c)Ðèñ. 6.3: íåêîòîðûå ÊÑ îò ÁÏ x1 , x2 , x3íà íàáîðå α êîíòàêòîâ, êîòîðàÿ èäåò èç v â u. Òàê, ïðîñìàòðèâàÿ âñå íàáîðû çíà÷åíèé ÁÏ x1 , x2 , ìîæíî óáåäèòüñÿ âòîì, ÷òî ÔÀË ïðîâîäèìîñòè gv1 ,v2 (x1 , x2 ) â ÊÑ Σ, ïîêàçàííîé íà ðèñ.

6.3a, ðàâíà x1 ⊕ x2 , à ÔÀË ïðîâîäèìîñòè gv3 ,v4ðàâíà 0.Áóäåì ñ÷èòàòü, ÷òî â êàæäîé âåðøèíå (1, m)-ÊÑ Σ(x1 , . . . , xn ; a1 ; a2 , . . . , am+1 )ðåàëèçóåòñÿ ÔÀË ïðîâîäèìîñòè îò âõîäà a1 ê ýòîé âåðøèíå è ÷òî Σ ðåàëèçóåò ñèñòåìó ÔÀË F = (f1 , . . . , fm ), ãäåfj ÔÀË ïðîâîäèìîñòè îò a1 ê âûõîäó ñ ïîìåòêîé aj+1 ,j ∈ [1, m].

Ïðè ýòîì, î÷åâèäíî, â âåðøèíå a1 ðåàëèçóåòñÿ52Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÔÀË 1, êîòîðóþ â äàëüíåéøåì ïî óìîë÷àíèþ áóäåì èñïîëüçîâàòü â êà÷åñòâå ïîìåòêè åäèíñòâåííîãî âõîäà (1, m)-ÊÑ.Òàê, ÊÑ, èçîáðàæåííûå íà ðèñ. 6.3a, 6.3b è 6.3c, ðåàëèçóþòÔÀË x1 ⊕x2 , H (x1 , x2 , x3 ) è íàáîð ÔÀË (x1 ⊕ x2 ⊕ x3 , x1 ⊕ x2 ⊕ x3 ⊕ 1)ñîîòâåòñòâåííî. Íà ðèñ.

6.4a ïîêàçàíà (1, 2n )-ÊÑ D (x1 , . . . , xn ; 1; a0 , . . . , a2n −1 ),êîòîðàÿ íàçûâàåòñÿ (1, 2n )nîò ÁÏ X (n). Ëåãêî âèäåòü, ÷òî â âûõîäíîé âåðøèíå ai ,i = 0, . . . 2n − 1, ýòîãî êîíòàêòíîãî äåðåâà (ÊÄ) ðåàëèçóåòñÿ ÝÊ âèäà xσ1 1 · · · xσnn , ãäå ν (σ1 , . . . , σn ) = (i − 1), è ÷òîÔÀË ïðîâîäèìîñòè ìåæäó ëþáûìè åãî âûõîäàìè ðàâíà 0.Òàêèì îáðàçîì, (1, 2n )-ÊÄ ïîðÿäêà n ÿâëÿåòñÿ äåøèôðàòîðîì ïîðÿäêà n, òî åñòü ñõåìîé, ðåàëèçóþùåé ñèñòåìó Qn èçâñåõ ÝÊ ðàíãà n îò ÁÏ X (n).Ñõåìû Σ0 è Σ00 ñ÷èòàþòñÿ, êàê îáû÷íî,, åñëè èçîìîðôíû ñîîòâåòñòâóþùèå èì ãðàôû, è, åñëè îíè ðåàëèçóþò ðàâíûå ñèñòåìû ÔÀË.

Èçîìîðôíûå ÊÑ, î÷åâèäíî, ýêâèâàëåíòíû.Äëÿ ìíîæåñòâà C , ñîñòîÿùåãî èç êîíòàêòîâ âèäà xσi11 , . . . , xσirrâ ÊÑ Σ, îïðåäåëèì åãîK (C) èσ1J (C) êàê ÔÀË âèäà xi1 · · · xσirr èxσi11 ∨. . .∨xσirr ñîîòâåòñòâåííî. Ïðè ýòîì ìíîæåñòâî C íàçûâàåòñÿ(), åñëè K (C) 6= 0 (J (C) 6= 1),è(ñîîòâåòñòâåííî) â ïðîòèâíîì ñëó÷àå. Çàìåòèì, ÷òî â ðåçóëüòàòå ïðèâåäåíèÿ ïîäîáíûõ (ñì. Ÿ4)îòëè÷íàÿ îò 0 ÔÀË K (C) è îòëè÷íàÿ îò 1 ÔÀË J (C) ìîãóòáûòü ïðåîáðàçîâàíû â ÝÊ è ÝÄ ñîîòâåòñòâåííî. Î÷åâèäíî,òàêæå, ÷òî-êîíòàêòíûì äåðåâîì ïîðÿäêàèçîìîðôíûìèýêâèâàëåíò-íûìèôóíêöèþ îòäåëèìîñòèôóíêöèþ ïðîâîäèìîñòèïðîâîäÿùèì îòäåëèìûìíóëåâûìåäèíè÷íûìK C 0 > K (C)è J C 0 6 J (C) ,åñëè C 0 ⊆ C .Èç ââåäåííûõ îïðåäåëåíèé (ñì.

òàêæå Ÿ1) ñëåäóåò, ÷òîÔÀË g , ðåàëèçóåìàÿ ÊÑ Σ (x1 , . . . , xn ; a1 ; a2 ), îáðàùàåòñÿ â 1(îáðàùàåòñÿ â 0) íà íàáîðå α, α ∈ B n , òîãäà è òîëüêî òîãäà,Ÿ6.Êîíòàêòíûå ñõåìû èπ -ñõåìû,îöåíêà èõ ÷èñëà53ss• a0sssKsK•sKKKxn KK•axnss•ssssOsx1 sss• OOOOsx2 OO•ss1 •sKKKKK xo2oooo•x1 KKo•KoKKKKx2 KKx2•1...ai•/ xσ1 . . . xσnn1ss• a2n −2sssKsK•sKKKxn KK a n•xn2 −1a)a0 •KKK xnKKKKs•ssssa1 •ss xn•KKK xKK2KKo•KKK x1ooKKoox2oKKo•s• aOs• OO x2sOOO ssOs•ss x1ssssx2ss•a2n −2 •KKK xnKKKKs•ssssxnsa2n −1 •sb)Ðèñ. 6.4: (1, 2n )- è (2n , 1)- êîíòàêòíûå äåðåâüÿ ïîðÿäêà n54Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìêîãäà â Σ ñóùåñòâóåò ìíîæåñòâî êîíòàêòîâ C , îáðàçóþùååïðîñòóþ ïðîâîäÿùóþ (a1 − a2 )-öåïü (ñîîòâåòñòâåííî òóïèêîâîå îòäåëèìîå (a1 |a2 ))-ñå÷åíèå), äëÿ êîòîðîãî K (C) = 1(ñîîòâåòñòâåííî J (C) = 0) íà íàáîðå α.

Òàêèì îáðàçîì,g (x1 , . . . , xn ) = K (C1 ) ∨ . . . ∨ K (Ct ) == J (S1 ) & . . . &J (Sr ) , (6.1)ãäå C1 , . . . , Ct è S1 , . . . , Sr âñå ïðîñòûå ïðîâîäÿùèå (a1 − a2 )öåïè è âñå òóïèêîâûå îòäåëèìûå (a1 |a2 )-ñå÷åíèÿ ÊÑ Σ.Çàìåòèì, ÷òî ïåðâàÿ èç ôîðìóë (6.1) ìîæåò áûòü ïðåîáðàçîâàíà â ÄÍÔ, à âòîðàÿ â ÊÍÔ, â ðåçóëüòàòå ïðèâåäåíèÿ ïîäîáíûõ (ñì. Ÿ3), åñëè g 6≡ 0 è g 6≡ 1 ñîîòâåòñòâåííî.Òàê, â ÊÑ, ïîêàçàííîé íà ðèñ. 6.3b, èìåþòñÿ òðè ïðîñòûåïðîâîäÿùèå öåïè C1 , C2 è C3 , êîòîðûå èäóò èç a1 â a2 . ÏðèýòîìK (C1 ) = x1 x2 x3 , K (C2 ) = x1 x2 x1 = x1 x2 , K (C3 ) = x1 x3è, ñëåäîâàòåëüíî,g (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 ∨ x1 x3 == x1 x2 ∨ x2 x3 ∨ x3 x1 = H (x1 , x2 , x3 ) .Ðàññìîòðèì òåïåðü ïàðàëëåëüíî-ïîñëåäîâàòåëüíûå èëè,èíà÷å, π -ñõåìû, êîòîðûå ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì ÊÑ.Ïðîñòåéøåé π -ñõåìîé ñ÷èòàåòñÿ ëþáàÿ (1, 1)-ÊÑ, êîòîðàÿ ñîñòîèò èç îäíîãî êîíòàêòà, ñîåäèíÿþùåãî ïîëþñà (ñì.

ðèñ. 6.6a).Åñëè π -ñõåìû Σ1 è Σ2 óæå îïðåäåëåíû, òî (1, 1)-ÊÑ Σ0 (Σ00 ),êîòîðàÿ ïîëó÷àåòñÿ â ðåçóëüòàòå èõ ïàðàëëåëüíîãî (ñîîòâåòñòâåííî ïîñëåäîâàòåëüíîãî) ñîåäèíåíèÿ (ñì. ðèñ. 6.6b è 6.6c)òîæå ÿâëÿåòñÿ π -ñõåìîé. Çàìåòèì, ÷òî ïðè ýòîì âõîä (âûõîä) Σ0 ÿâëÿåòñÿ ðåçóëüòàòîì îòîæäåñòâëåíèÿ âõîäîâ (ñîîòâåòñòâåííî âûõîäîâ) Σ1 è Σ2 , òîãäà êàê âõîäîì Σ00 ÿâëÿåòñÿŸ6.Êîíòàêòíûå ñõåìû èπ -ñõåìû,a1 îöåíêà èõ ÷èñëà55 a2C1Cta)a1 •···S1 a2•Spb)Ðèñ. 6.5: ÊÑ, ìîäåëèðóþùèå ÄÍÔ è ÊÍÔâõîä Σ1 , âûõîäîì Σ00 âûõîä Σ2 , à âûõîä Σ1 îòîæäåñòâëÿåòñÿ ñ âõîäîì Σ2 è ñòàíîâèòñÿ âíóòðåííåé âåðøèíîé Σ00 .Ëåãêî âèäåòü, ÷òî π -ñõåìà, ïîêàçàííàÿ íà ðèñ. 6.6a, ðåàëèçóåò ÔÀË xσi , à π -ñõåìû Σ0 è Σ00 (ñì.

ðèñ. 6.6b è 6.6c) ÔÀË f1 ∨ f2 è f1 &f2 ñîîòâåòñòâåííî, ãäå f1 è f2 ÔÀË,ðåàëèçóåìûå π -ñõåìàìè Σ1 è Σ2 ñîîòâåòñòâåííî.Ëþáîé π-ñõåìå Σ ìîæíî ñîïîñòàâèòü ýêâèâàëåíòíóþ åé ôîðìóëó F èç UΦ ñ ïîäíÿòûìè îòðèöàíèÿìèòàêóþ, ÷òî R (F) = L (Σ) è îáðàòíî.Äîêàçàòåëüñòâî. Ïîñòðîèì ôîðìóëó F èíäóêöèåé ïî ñòðî-Ëåììà 6.1.åíèþ π -ñõåìû Σ. Åñëè Σ ïðîñòåéøàÿ π -ñõåìà âèäà xσi , òîïîëîæèì F = xσi . Åñëè π -ñõåìàì Σ1 è Σ2 óæå ñîïîñòàâëåíû ôîðìóëû F1 è F2 ñ ïîäíÿòûìè îòðèöàíèÿìè, òî π -ñõåìåΣ0 (Σ00 ), ïîëó÷àþùåéñÿ â ðåçóëüòàòå ïàðàëëåëüíîãî (ñîîòâåòñòâåííî ïîñëåäîâàòåëüíîãî) ñîåäèíåíèÿ Σ1 è Σ2 , ñîïîñòàâèì ôîðìóëó F0 = F1 ∨ F2 (ñîîòâåòñòâåííî F00 = F1 &F2 ).Ïðè ýòîìR F0 = R F00 = R (F1 ) + R (F2 )56Ãëàâà 2.a1 xσiÎñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì a2Σ0:a1 Σ1 a2Σ2a)b)Σ00 : a1 Σ1•Σ2 a2c)Ðèñ. 6.6: ê îïðåäåëåíèþ π -ñõåìûè, ñëåäîâàòåëüíî, ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ,R F0 = R F00 = L (Σ1 ) + L (Σ2 ) = L (Σ) .Àíàëîãè÷íûì îáðàçîì, èíäóêöèåé ïî ñòðîåíèþ ôîðìóëû Fñ ïîäíÿòûìè îòðèöàíèÿìè ìîæíî íàéòè ýêâèâàëåíòíóþ åéπ -ñõåìó Σ òàêóþ, ÷òî L (Σ) = R (F).Ëåììà äîêàçàíà.Íà ðèñ 6.7a ïîêàçàíà π -ñõåìà, êîòîðàÿ ðåàëèçóåò ÔÀËH (x1 , x2 , x3 ) è ñîîòâåòñòâóåò ôîðìóëå:H (x1 , x2 , x3 ) = x1 (x2 ∨ x3 ) ∨ x2 x3 ,à íà ðèñ.

6.7b π -ñõåìà, êîòîðàÿ ïîñòðîåíà íà îñíîâå êîíòàêòíîãî äåðåâà è ðåàëèçóåò ÔÀË µn ìóëüòèïëåêñîðíóþŸ6.Êîíòàêòíûå ñõåìû èπ -ñõåìû,îöåíêà èõ ÷èñëàt•ttx2tttttttx3tt aa1 JtJJtt 2JJ xttx3 ttJJ 2JJtJJtttJJ tt•tx1a)x2 oooo•oooR oRo•oRox1 ooRRRoox2 RR•a1 OoOoOx2 lll•OOlllx1 OOOllO• OOOOOx2 OOO•?xn oooo• ??o??oo??ooOO•OOOO??O??y0xn OOO• OOOOO ???OOO ??O ?y1 OOOO??OO? aoo o 2y2n −2ooooo ooo oooooy2n −1xn oooo•ooooOoO•OOOOxn OOO•b)Ðèñ. 6.7: ïðèìåðû π -ñõåì5758Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÔÀË ïîðÿäêà n, â ñîîòâåòñòâèè ñ ôîðìóëîéµn (x1 , .

. . , xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · ·  .σ1 ∈Bσ2 ∈Bσn ∈BÑõåìà, ìîäåëèðóþøàÿ ñîâåðøåííóþ ÄÍÔ ÔÀË f , íàçûâàåòñÿÊÑ äëÿ ýòîé ÔÀË.Áóäåì íàçûâàòü (1, m)-ÊÑ, åñëè âñå èçîëèðîâàííûå âåðøèíû Σ ÿâëÿþòñÿ åå ïîëþñàìè, à âñå êîíòàêòûè îñòàëüíûå âåðøèíû Σ ïðèíàäëåæàò ïðîñòûì ïðîâîäÿùèìb , êîöåïÿì, ñîåäèíÿþùèì åå âõîä è âûõîäû.

Ïðè ýòîì ÊÑ Σòîðàÿ ïîëó÷àåòñÿ èç ÊÑ Σ óäàëåíèåì ¾ëèøíèõ¿, òî åñòü íåïðèíàäëåæàùèõ öåïÿì óêàçàííîãî âèäà, íåïîëþñíûõ âåðøèí è êîíòàêòîâ, ÿâëÿåòñÿ ýêâèâàëåíòíîé Σ ïðèâåäåííîéb 6 L (Σ). Çàìåòèì, ÷òî ïðèâåäåííàÿ ÊÑÊÑ òàêîé, ÷òî L(Σ)íå ñîäåðæèò ïåòåëü, à ïðèâåäåííàÿ ÊÑ, íå ðåàëèçóþùàÿ íóëåâûõ ÔÀË, ÿâëÿåòñÿ ñâÿçíûì ãðàôîì. Òàê, ÊÑ, ïîêàçàííàÿ íà ðèñ. 6.3c, íå ÿâëÿåòñÿ ïðèâåäåííîé, à ñîîòâåòñòâóþùàÿ åé ïðèâåäåííàÿ ÊÑ ïîëó÷àåòñÿ èç íåå óäàëåíèåì âåðøèíû v .Ðàññìîòðèì òåïåðü íåêîòîðûå îöåíêè ÷èñëà êîíòàêòíûõñõåì ðàçëè÷íûõ òèïîâ. Ïóñòü UK è Uπ ìíîæåñòâî âñåõ ÊÑèç íåîðèåíòèðîâàííûõ êîíòàêòîâ è ìíîæåñòâî âñåõ π -ñõåìñîîòâåòñòâåííî.

Åñëè UA îäèí èç óêàçàííûõ êëàññîâ ñõåì,òî ÷åðåç UA (L, n) áóäåì îáîçíà÷àòü ìíîæåñòâî ïðèâåäåííûõ(1, 1)-ñõåì Σ èç UA îò ÁÏ X (n), äëÿ êîòîðûõ L (Σ) 6 L. Äëÿëþáîãî ìíîæåñòâà ñõåì U â ñîîòâåòñòâèè ñ Ÿ1 ÷åðåç |U| è kUkáóäåì ïî-ïðåæíåìó îáîçíà÷àòü ÷èñëî ïîïàðíî íå èçîìîðôíûõ è ïîïàðíî íå ýêâèâàëåíòíûõ ñõåì â U ñîîòâåòñòâåííî.Ïðè ýòîì äëÿ ëþáîãî èç ââåäåííûõ âûøå ìíîæåñòâ ñõåìíåðàâåíñòâî (1.7) áóäåò âûïîëíÿòüñÿ.êàíîíè÷åñêîéïðèâåäåííîéŸ6.Êîíòàêòíûå ñõåìû èËåììà 6.2.íåðàâåíñòâîπ -ñõåìû,îöåíêà èõ ÷èñëà59Ïðè ëþáûõ íàòóðàëüíûõ L è n âûïîëíÿåòñÿkUπ (L, n)k 6 (12n)L .(6.2)Äîêàçàòåëüñòâî.  ñèëó ëåììû 6.1, äîñòàòî÷íî äîêàçàòü,÷òî ÷èñëî ïîïàðíî íå ýêâèâàëåíòíûõ ôîðìóë F (x1 , .

. . , xn )ñ ïîäíÿòûìè îòðèöàíèÿìè íàä áàçèñîì Á0 , äëÿ êîòîðûõR (F) 6 L, íå ïðåâîñõîäèò (16n)L . Äëÿ ýòîãî ñîïîñòàâèìôîðìóëå F óêàçàííîãî âèäà ôîðìóëó F0 èç UΦ{&,∨} îò ÁÏx1 , . . . , x2n , êîòîðàÿ ïîëó÷àåòñÿ èç F çàìåíîé êàæäîé ååïîäôîðìóëû xi , i ∈ [1, n], ôîðìóëîé xi+n è äëÿ êîòîðîé,â ñèëó çàìå÷àíèÿ ê ëåììå 2.1,L F0 = R (F) − 1 6 L − 1.Ïðè òàêîì ñîïîñòàâëåíèè íåýêâèâàëåíòíûå ôîðìóëû ïåðåõîäÿò â íåýêâèâàëåíòíûå, è ïîýòîìó ÷èñëî ïîïàðíî íå ýêâèâàëåíòíûõ ôîðìóë ðàññìàòðèâàåìîãî âèäà íå áîëüøå, ÷åì ΦU{&,∨} (L − 1, 2n), îòêóäà, â ñèëó çàìå÷àíèÿ ê ëåììå 4.2,ñëåäóåò (6.2).Ëåììà äîêàçàíà.Ëåììà 6.3.íåðàâåíñòâîÏðè ëþáûõ íàòóðàëüíûõ L è n âûïîëíÿåòñÿ KU (L, n) 6 (8nL)L .Äîêàçàòåëüñòâî. Âîçüìåìïðîèçâîëüíóþ ÊÑ Σ== Σ(x1 , . .