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

Ïðè ýòîì òîæäåñòâó t : F0 = F00 ,ãäå F0 è F00 ôîðìóëû èç UΦÁ , áóäåò ñîîòâåòñòâîâàòü òîæäåñòâî t : F0 ∼ F00 , ãäå F0 è F00 ñîîòâåòñòâóþùèå F0 è F00ñõåìû èç UCÁ , ÿâëÿþùååñÿ ¾ñõåìíûì¿ àíàëîãîì òîæäåñòâà t.Ìíîæåñòâî ÑÔÝ âèäà F, ãäå F ∈ F ⊆ UΦÁ , áóäåì îáîçíà÷àòü÷åðåç F, à ñèñòåìó òîæäåñòâ âèäà t, ãäå t ∈ τ , à τ ñèñòåìàòîæäåñòâ äëÿ UΦÁ , ÷åðåç τ . Òàê, íà ðèñ. 5.1a è 5.1b ïðèâåΠKäåíû òîæäåñòâà tM& è t1,& , ÿâëÿþùèåñÿ ñõåìíûìè àíàëîãàìè1Ïîä äóáëèðîâàíèåì (ñíÿòèåì) âûõîäà zi ÑÔÝ ïîíèìàåòñÿ íàíåñåíèå íà âåðøèíó ñ ïîìåòêîé zi åùå îäíîé âûõîäíîé ÁÏ (ñîîòâåòñòâåííîóäàëåíèå ñ íå¼ ïîìåòêè zi )42Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìx21x2x+1x2•+••+22+++1 22 2++2••¬∼ ¬ •+++ &1 ++ 2+• ∨¬ ••2z1z1x1x2••• ¬&•yz1a)•{∨x1∼ z•1b)ΠKÐèñ.

5.1: òîæäåñòâà tM& è t1,&ÏKââåäåííûõ âûøå ôîðìóëüíûõ òîæäåñòâ tM& è t1,& .Íà ðèñ. 5.2a è 5.2b ïîêàçàíû òîæäåñòâîtBEiè òîæäåñòâîtCE,i∈iEi[1, b], ñîîòâåòñòâåííî, à íà ðèñ. 5.2c òîæäåñòâîtCâõ . Çàìåòèì, ÷òî ïðèìåíåíèå òîæäåñòâà ñíÿòèÿ ðàâíîñèëüíî âûïîëíåíèþ îïåðàöèè óäàëåíèÿ âèñÿ÷åé âåðøèíûñîîòâåòñòâóþùåãî òèïà (ñì. Ÿ7). Çàìåòèì òàêæå, ÷òî òîæCCäåñòâà tBEi , tEi , tâõ íå ÿâëÿþòñÿ àíàëîãàìè ôîðìóëüíûõ òîæäåñòâ è ïîëîæèì b bCτÁB = tBτÁC = tCEi i=1 ,Ei i=1 ∪ tâõ .âåòâëåíèÿäëÿ ôóíêöèîíàëüíîãî ýëåìåíòàñíÿòèÿñíÿòèÿâõîäàÎ÷åâèäíî, ÷òî ñ ïîìîùüþ ýòèõ òîæäåñòâ ìîæíî èçáàâèòüñÿîò âñåõ âèñÿ÷èõ âåðøèí è âñåõ âíóòðåííèõ âåòâëåíèé, èìåþùèõñÿ â ÑÔÝ.

Ñëåäîâàòåëüíî, äëÿ ëþáîé ÑÔÝ Σ, Σ ∈ UCÁ,ñóùåñòâóåò ÝÏ âèäà Σ |⇒ F, ãäå F ôîðìóëà (ñèñòåìà{τ C ,τ B }UΦ .ôîðìóë) èç Áb îäíîêðàòíîå ÝÏ äëÿ ôîðìóë èçÏóñòü, äàëåå, F 7→ FtUΦÁ , ãäå òîæäåñòâî t èìååò âèät : F0 (x1 , . . . , xn ) = F00 (x1 , . . . , xn ) ,Ÿ5.43Ïðåîáðàçîâàíèÿ íà îñíîâå òîæäåñòâx*1 . . . xki•*•****1 ** ki** *ϕi •z1 , z2x:$1xki. . . •$$ :: $$ ::: ∼ 1 $$ ::: ki$$ :: :$ ϕi •ki 1 :• ϕi•$ :z1z2a)x*1 . . . xki•*•**** ** ** *ϕi •∼x1 .

. . xk i••x1•b)∼ ∅c)Ðèñ. 5.2: òîæäåñòâà âåòâëåíèÿ, ñíÿòèÿ ÔÝ è ñíÿòèÿ âõîäàb ïîëó÷àåòñÿ èç ôîðìóëû F çàìåíîé ïîäôîðà ôîðìóëà F0ìóëû F (F1 , . . . , Fn ) ôîðìóëîé F00 (F1 , . . . , Fn ). Ñîïîñòàâèìýòîìó ÝÏ ¾ìîäåëèðóþùåå¿ åãî îäíîêðàòíîå ÝÏ ÑÔÝ âèb (ñì. ðèñ. 5.3). Çàìåòèì, ÷òî â òîì ñëó÷àå, êîãäàäà F 7→ Σtôîðìóëû F0 è F00 ÿâëÿþòñÿ áåñïîâòîðíûìè ôîðìóëàìè, àb ñîâïàäàÁÏ x1 , . . .

, xn èõ ñóùåñòâåííûìè ÁÏ, ÑÔÝ Σ00åò ñ ÑÔÝ F .  îñòàëüíûõ ñëó÷àÿõ èç ïîäôîðìóëû âèäàF0 (F1 , . . . , Fn ) ôîðìóëû F íåîáõîäèìî ñ ïîìîùüþ òîæäåñòâτÁB ñôîðìèðîâàòü ñíà÷àëà ïîäñõåìó F0 (F1 , . . . , Fn ), à çàòåìb ìîãóò ïîÿâèòüñÿïðèìåíèòü òîæäåñòâî t. Ïðè ýòîì â ÑÔÝ Σâèñÿ÷èå âåðøèíû èëè âíóòðåííèå ¾âåòâëåíèÿ¿, è òîãäà äëÿb íåîáõîäèìî ïðîâåñòè ÝÏ âèäà Σb.b êFb |⇒ Fïåðåõîäà îò Σ{τ C ,τ B }b , ãäå F, Fb ∈ UΦ ,Ñëåäîâàòåëüíî, äëÿ ëþáîãî ÝÏ âèäà F |⇒ FÁτ44Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì888888 8888 8888Fn 88Fn 88 88F1 88 88F1 88 88 88 88 88 88 88 @@ . . .88 @@ .

. .~~~~ 88 @@@88 @@@→−~~~~t88 88@88 88@~~~~~~88 88F0 88 88F00 88 88 88 88 88 88 88 88 88 88 bFΣÐèñ. 5.3: ìîäåëèðîâàíèå ÝÏ ôîðìóë ñ ïîìîùüþ ÝÏ ÑÔÝñóùåñòâóåò ìîäåëèðóþùåå åãî ÝÏ âèäàFbF.|⇒{Á}τ ,τ B ,τ CÁÍà ðèñ. 5.4 ïîêàçàíî ÝÏ ÑÔÝ èç UC , êîòîðîå ìîäåëèðóåòÝÏ (3.1) äëÿ ôîðìóë èç UΦ :x1 (x2 x3 ∨ x2 ∨ x3 ) 7→ x1 (x2 x3 ∨ x2 · x3 ) 7→ x1 .tM&tΠK1,&Èç îïèñàííîãî âûøå ñïîñîáà ¾ìîäåëèðîâàíèÿ¿ ÝÏ ôîðìóë ñ ïîìîùüþ ÝÏ ÑÔÝ, à òàêæå ñïîñîáà ïåðåõîäà îò ôîðìóë ê ÑÔÝ è îáðàòíî íà îñíîâå ÝÏ ñ ïîìîùüþ òîæäåñòâτÁB , τÁC âûòåêàåò ñïðàâåäëèâîñòü ñëåäóþùåãî óòâåðæäåíèÿ.Åñëè τ êîíå÷íàÿïîëíàÿ ñèñòåìàòîæΦCBäåñòâ äëÿ ÝÏ ôîðìóë èç UÁ , òî τ , τ , τ êîíå÷íàÿïîëíàÿ ñèñòåìà òîæäåñòâ äëÿ ÝÏ ÑÔÝ èç UCÁ .Ñèñòåìà òîæäåñòâ τ îñí, τ B, τ C ÊÏÑÒäëÿ ÝÏ ÑÔÝ èç UC.Òåîðåìà 5.1.Ñëåäñòâèå.Ðàññìîòðèì äàëåå âîïðîñû ñòðóêòóðíîãî ìîäåëèðîâàíèÿôîðìóë â ðàçëè÷íûõ áàçèñàõ.

Ïóñòü ïîìèìî áàçèñà Á =Ÿ5.45Ïðåîáðàçîâàíèÿ íà îñíîâå òîæäåñòâx1•x2x3•x1•¬ •#& •{••¬•#∨ −→x2& •u•) &•••{#→¬ −tB&∨••{&z1••tM&&x1x3•∨z1x2x3••&•{#• ¬ −−→−→tB&tΠK1,&•&•{x1 x2• •z1x3•&•}!⇒τC•x1z1∨z1Ðèñ. 5.4: ïðèìåð ìîäåëèðîâàíèÿ ÝÏ ôîðìóë ñ ïîìîùüþ ÝÏÑÔÝ46Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì= {ϕi }bi=1 ó íàñ èìååòñÿ äðóãîé êîíå÷íûé ïîëíûéáàçèñb0000ΦÁ = {ϕi }i=1 , è ïóñòü ôîðìóëà Φi x1 , .

. . , xki0 èç UÁ0 , ãäåki0 > ki , ðåàëèçóåò ÔÀË ϕi , i = 1, . . . , b. Çàìåòèì, ÷òî âñëó÷àå ki0 > ki ÁÏ xki +1 , . . . , xki0 ÿâëÿþòñÿ ôèêòèâíûìè ÁÏôîðìóëû Φ0i . ÏîëîæèìΦ0 = Φ01 , . . . , Φ0b ,Π0 = Π01 , . . . , Π0b ,ãäå Π0i òîæäåñòâî âèäà ϕi = Φ0i , i = 1, . . . , b, è ôîðìóëû èçΦ0 (òîæäåñòâà èç Π0 ) áóäåì íàçûâàòü(ñîîòâåòñòâåííî)ÁÁ0 .0Äëÿ ôîðìóëû F, F ∈ UΦÁ , îáîçíà÷èì ÷åðåç Π (F) ôîðìó0ëó íàä áàçèñîì Á , êîòîðàÿ ïîëó÷àåòñÿ èç F çàìåíîé êàæäîé0åå ïîäôîðìóëû âèäà ϕi (F1 , .

. . , Fki ) ôîðìóëîé Φi F1 , . . . , Fki , xki +1 , . . . , xki0 ,òî åñòü ÿâëÿåòñÿ ðåçóëüòàòîì ïîäñòàíîâêè ôîðìóëû Fj âìåñòî ÁÏ xj â ôîðìóëó Φ0i äëÿ âñåõ j, j = 1, . . . , ki . Ïåðåõîä îòôîðìóëû F ê ôîðìóëå Π0 (F) áóäåì íàçûâàòüFÁ00Φ èëè, èíà÷å,Π0 .Çàìåòèì, ÷òî ýòîò ïåðåõîä ÿâëÿåòñÿ ñïåöèàëüíûì ÝÏ âèäàôîðìóëàìèòîæäåñòâàìè ïåðåõîäà îò áàçèñà ê áàçèñóñòðóêòóðíûììîäåëèðîâàíèåì ôîðìóëû â áàçèñå íà îñíîâå ôîðìóëïåðåõîäàíà îñíîâå òîæäåñòâ ïåðåõîäàF |⇒ Π0 (F)Π0äëÿ ôîðìóë íàä áàçèñîì Á ∪ Á0 . Îòñþäà ñëåäóåò, â ÷àñòíîñòè, ÷òî â ðåçóëüòàòå óêàçàííîãî ñòðóêòóðíîãî ìîäåëèðîâàíèÿ îáåèõ ÷àñòåé òîæäåñòâà t, ÿâëÿþùèõñÿ ôîðìóëàìè èç0ΦUΦÁ , ïîëó÷àåòñÿ òîæäåñòâî t äëÿ ôîðìóë èç UÁ0 , êîòîðîå0ìû áóäåì îáîçíà÷àòü ÷åðåç Π (t).

Ìíîæåñòâî ôîðìóë âèäà0Π0 (F), ãäå F ∈ F ⊆ UΦÁ , áóäåì îáîçíà÷àòü ÷åðåç Π (F), à0ìíîæåñòâî òîæäåñòâ âèäà Π (t), ãäå t ∈ τ òîæäåñòâî íàä0UΦÁ , ÷åðåç Π (τ ).Ðàññìîòðèì òåïåðü âîïðîñû ìîäåëèðîâàíèÿ ÝÏ ôîðìóëâ áàçèñå Á ñ ïîìîùüþ ÝÏ ôîðìóë áàçèñà Á0 . Ïóñòü Φ0 =Ÿ5.Ïðåîáðàçîâàíèÿ íà îñíîâå òîæäåñòâ47(Φ01 , . . . , Φ0b ) ñèñòåìà ôîðìóë ïåðåõîäà îò áàçèñà Á ê áàçèñó Á0 , à Π0 = (Π01 , . . . , Π0b ) ñèñòåìà òîæäåñòâ ïåðåõîäà,ñâÿçàííàÿ ñ Φ0 . Çàìåòèì, ÷òî ëþáîå ÝÏ äëÿ ôîðìóë èç UΦÁ,èìåþùåå âèäbF |⇒ F,(5.1)τìîæåò áûòü ¾ïðîìîäåëèðîâàíî¿ ñ ïîìîùüþ ÝÏ äëÿ ôîðìóëèç UΦÁ0 âèäàb 0,F0 |⇒ F(5.2)τ0b 0 = Π0 (F)b è τ 0 = Π0 (τ ).

Äåéñòâèòåëüíî,ãäå F0 = Π0 (F), Fïóñòü ÝÏ (5.1) ÿâëÿåòñÿ îäíîêðàòíûì ÝÏ íà îñíîâå òîæäåñòâà t, t ∈ τ , êîòîðîå èìååò âèät : A (x1 , . . . , xq ) = B (x1 , . . . , xq ) ,b ïîëó÷àåòñÿ â ðåçóëüòàòå çàìåíû ïîäôîðè ïóñòü ôîðìóëà Fìóëû A (F1 , . . . , Fq ) ôîðìóëû F ôîðìóëîé B (F1 , . . . , Fq ). Òîãäà òîæäåñòâî t0 = Π0 (t) èìååò âèät0 : A0 (x1 , . . . , x1 ) = B (x1 , . . . , xq ) ,b 0 ìîæåò áûòüãäå A0 = Π0 (A) è B0 = Π0 (B), à ôîðìóëà F0ïîëó÷åíà èç ôîðìóëûF â ðåçóëüòàòå çàìåíû åå ïîäôîðìóëû A0 F10 , . . . , Fq0 , ãäå Fj0 = Π0 (Fj ) äëÿ âñåõ j, j ∈ [1, q],ôîðìóëîé B0 F10 , .

. . , Fq0 . Ìîäåëèðîâàíèå êðàòíîãî ÝÏ âèäà (5.1) ñ ïîìîùüþ êðàòíîãî ÝÏ âèäà (5.2) îñóùåñòâëÿåòñÿïóòåì ïîñëåäîâàòåëüíîãî ìîäåëèðîâàíèÿ îäíîêðàòíûõ ÝÏ,ñîñòàâëÿþùèõ ÝÏ (5.1).Îïèñàííîå âûøå ìîäåëèðîâàíèå ïîçâîëÿåò âûïîëíÿòü ÝÏäëÿ òåõ ýêâèâàëåíòíûõôîðìóë èç UΦÁ0 , êîòîðûå ïðèíàäëå0Φæàò ìíîæåñòâó Π UÁ , òî åñòü ÿâëÿþòñÿ ¾ìîäåëÿìè¿ ôîð0ìóë èç UΦÁ , íà îñíîâå ñèñòåìû òîæäåñòâ Π (τ ), ÿâëÿþùèõñÿ ¾ìîäåëÿìè¿ òîæäåñòâ èç τ . Äëÿ òîãî ÷òîáû ïðîâîäèòü48Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÝÏ äëÿ ïðîèçâîëüíûõ ôîðìóë èç UΦÁ0 ñ èñïîëüçîâàíèåì ñè0ñòåìû òîæäåñòâ Π (τ ), âûáåðåì êàêóþ-ëèáî ñèñòåìó ôîðìóë ïåðåõîäà Φ = (Φ1 , .

. . , Φb0 ) îò áàçèñà Á0 ê áàçèñó Áè ðàññìîòðèì ñâÿçàííóþ ñ íåé ñèñòåìó òîæäåñòâ ïåðåõîäà Π = (Π1 , . . . , Πb0 ). Ïóñòü Π̌ ñèñòåìà òîæäåñòâ âèäàΠ̌ = Π0 (Π) äëÿ ÝÏ ôîðìóë èç UΦÁ0 , êîòîðàÿ ïîëó÷àåòñÿ â ðåçóëüòàòå ñòðóêòóðíîãî ìîäåëèðîâàíèÿ ïðàâûõ ÷àñòåé òîæäåñòâ èç Π íà îñíîâå ñèñòåìû òîæäåñòâ Π0 .

Äëÿ ïðîèçâîëüíîé ôîðìóëû F0 , F0 ∈ UΦÁ0 , ïîëîæèìΠ̌ F0 = Π0 (Π (F))è çàìåòèì, ÷òîF0 |⇒ F̌0 = Π̌ F0 ,F̌0 ∈ Π0 UΦÁ .Π̌ ñèëó ñêàçàííîãî âûøå, îòñþäà âûòåêàåò ñïðàâåäëèâîñòüñëåäóþùåãî óòâåðæäåíèÿ.Ïóñòü τ ÊÏÑÒ äëÿÝÏ ôîðìóë èç , à è ñèñòåìû òîæäåñòâ äëÿïåðåõîäà îò áàçèñà ê áàçèñó è îò áàçèñà Á0 ê áàçèñó Áñîîòâåòñòâåííî. Òîãäà ñèñòåìà òîæäåñòâ {Π0 (τ ) , Π0 (Π)}ÿâëÿåòñÿ ÊÏÑÒ äëÿ ÝÏ ôîðìóë èç UΦÁ .Òåîðåìà 5.2(òåîðåìà ïåðåõîäà).UΦΠ0ΠÁÁÁ0Èç ñèñòåìû òîæäåñòâ τ îñí äëÿ ÝÏ ôîðìóëèç UΦ (ñì. Ÿ3) óêàçàííûì â òåîðåìå ñïîñîáîì ìîæíî ïîëó÷èòü ÊÏÑÒ äëÿ ÝÏ ôîðìóë â ëþáîì áàçèñå Á.Ñëåäñòâèå.Àíàëîãè÷íûì îáðàçîì íà îñíîâå òåîðåìû 5.1 ðåøàþòñÿâîïðîñû ïîñòðîåíèÿ ÊÏÑÒ äëÿ ÝÏ ÑÔÝ â ïðîèçâîëüíîìáàçèñå.Ÿ6.Ÿ6Êîíòàêòíûå ñõåìû èπ -ñõåìû,îöåíêà èõ ÷èñëà49Êîíòàêòíûå ñõåìû è π -ñõåìû, îöåíêà èõ ÷èñëà.

Îñîáåííîñòè ôóíêöèîíèðîâàíèÿ ìíîãîïîëþñíûõ ñõåìÐàññìîòðèì êëàññ êîíòàêòíûõ ñõåì, â êîòîðûõ ðåàëèçàöèÿÔÀË îñóùåñòâëÿåòñÿ íå ñ ïîìîùüþ ïðåîáðàçîâàíèÿ âõîäíûõ çíà÷åíèé â âûõîäíûå, êàê ýòî ïðîèñõîäèò, íàïðèìåð, âñõåìàõ èç ôóíêöèîíàëüíûõ ýëåìåíòîâ (ñì. Ÿ7), à â ðåçóëüòàòå ïåðåäà÷è çíà÷åíèé ïî ðåáðàì ãðàôà, ïðîâîäèìîñòüþêîòîðîãî ¾óïðàâëÿþò¿ âõîäíûå ÁÏ. Ðåáðî èëè äóãà ãðàôà ñïîìåòêîé xi (xi ) íàçûâàåòñÿ(ñîîòâåòñòâåííî) êîíòàêòîì ÁÏ xi (ñì. ðèñ.

6.1).çàìûêàþùèìðàçìûêàþùèìxivssuvsa)xisuvsb)xσisu-c)Ðèñ. 6.1: òèïû êîíòàêòîâxq ivqqq?a)xq iquvqq 6qqub)Ðèñ. 6.2: ôèçè÷åñêàÿ èíòåðïðåòàöèÿ êîíòàêòîâÑ÷èòàåòñÿ, ÷òî êîíòàêò âèäà xσi , σ ∈ {0, 1}, ïðîâîäèòòîãäà è òîëüêî òîãäà, êîãäà xi = σ , ïðè÷åì îðèåíòèðîâàííûé êîíòàêò, òî åñòü êîíòàêò, ñâÿçàííûé ñ äóãîé, ïðîâîäèòòîëüêî â ñîîòâåòñòâóþùåì íàïðàâëåíèè.Ñ òî÷êè çðåíèÿ óïðàâëåíèÿ ïðîâîäèìîñòüþ íåîðèåíòèðîâàííûé ðàçìûêàþùèé (çàìûêàþùèé) êîíòàêò ÁÏ xi ôóíê-50Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìöèîíèðóåò êàê p-ÌÎÏ (ñîîòâåòñòâåííî n-ÌÎÏ) òðàíçèñòîð,íà çàòâîð êîòîðîãî ïîñòóïàåò ÁÏ xi (ñì.

ðèñ. 6.2a è 6.2b), ààíàëîãè÷íûé îðèåíòèðîâàííûé êîíòàêò êàê ÌÎÏ-òðàíçèñòîðñîîòâåòñòâóþùåãî òèïà ñ äèîäîì Øîòòêè [17, 23]. Êðîìå òîãî, îðèåíòèðîâàííûé êîíòàêò âèäà xσi , èäóùèé èç âåðøèíûv â âåðøèíó u (ñì. ðèñ. 6.1c), ÷àñòî ðàññìàòðèâàþò êàê êîìàíäó óñëîâíîãî ïåðåõîäà èç v â u, êîòîðûé âûïîëíÿåòñÿ,åñëè xi = σ .Ñåòü Σ ñ âõîäàìè a01 , . . .