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

. . , xn ).Äîêàæåì ñóùåñòâîâàíèå ÝÏ âèäàîáîá-ùåííîéêàíîíè÷åñêîéíîíè÷åñêîéñîâåðøåííûìèF |⇒ F0τMbF00 |⇒ F|⇒{KtD&,∨ ,t&êà-}τ ΠΠeF,|⇒{ΠΠtD&,∨ ,τ(3.2)}ãäå τ ΠΠ = τ A , τ K , τ ΠK , τ OΠ , tΠ , F0 ôîðìóëà ñ ïîäíÿòûbèFe êàíîíèìè îòðèöàíèÿìè, F00 îáîáùåííàÿ ÄÍÔ, à F÷åñêàÿ è ñîâåðøåííàÿ ÎÄÍÔ ÔÀË f ñîîòâåòñòâåííî. Äåéñòâèòåëüíî,, òî åñòü ïåðåõîä îò F ê F0â (3.2) (ñì. Ÿ2) ìîæíî îñóùåñòâèòü ïðèìåíåíèåì òîæäåñòâMMtM¬ , t& è t∨ ê ïîäôîðìóëàì âèäà (F1 ), (F1 · F2 ) è (F1 ∨ F2 )ñîîòâåòñòâåííî äî òåõ ïîð, ïîêà âñå òàêèå ïîäôîðìóëû íåáóäóò ¾óñòðàíåíû¿. Ïåðåõîä îò F0 ê F00 â (3.2), êîòîðûé íàçûâàåòñÿ n, îñóùåñòâëÿåòñÿ ïðèìåíåíèåìoDKòîæäåñòâ t&,∨ , t& ê ïîäôîðìóëàì âèäà F1 · (F2 ∨ F3 ) èëè(F1 ∨ F2 ) · F3 äî òåõ ïîð, ïîêà îíè âñòðå÷àþòñÿ â ïðåîáðàçóåìîé ôîðìóëå.b â (3.2), êîòîðûé íàçûâàåòñÿÏåðåõîä îò F00 ê F, âûïîëíÿåòñÿ â òðè ýòàïà.

Íà ïåðâîì ýòàïå êàæäàÿ ÎÝÊ K 00 èç ÎÄÍÔ F00 ïðåîáðàçóåòñÿâ êàíîíènoOΠΠKK , à÷åñêóþ ÎÝÊ K ñ ïîìîùüþ òîæäåñòâ t& , t0,& , tA,t& &ïîäíÿòèå îòðèöàíèéðàñêðûòèåì ñêîáîêäåíèåì ïîäîáíûõïðèâå-30Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìòàêæå òîæäåñòâà(3.3)xi · xi = x1 · x1 ,êîòîðîå âûâîäèòñÿ èç íèõ ñëåäóþùèì îáðàçîì:xi · xi 7→ (x1 · x1 ) · (xi · xi ) 7→ (xi · xi ) · (x1 · x1 ) 7→ x1 · x1 .tΠK0,&tK&tΠK0,&bÍà âòîðîì ýòàïå ïîëó÷åííàÿ ôîðìóëà F̌ ïðåîáðàçóåòñÿ â Fïóòåì ¾óñòðàíåíèÿ¿ ïîâòîðíûõ âõîæäåíèé ðàâíûõ ýëåìåíòàðíûõ êîíúþíêöèé èëè ïîäôîðìóë x1 · x1 ñ ïîìîùüþ òîæäåñòâ τ A , τ K , tOΠè, â ñëó÷àå f 6≡ 0, ïîñëåäóþùåãî¾óñòðà∨ A K ΠKíåíèÿ¿ ÎÝÊ x1 · x1 ñ ïîìîùüþ òîæäåñòâ t∨ , t∨ , t0,∨ .Çàìåòèì, ÷òî ïåðâûå äâà ýòàïà ïðèâåäåíèÿ ïîäîáíûõ,íà êîòîðûõ ïðîèñõîäèò ïðèâåäåíèå ïîâòîðåíèé ÁÏ â ÎÝÊ èb . Îäíàêî, äëÿ óìåíüÝÊ, óæå äàþò íàì èñêîìóþ ôîðìóëó Føåíèÿ ÷èñëà øàãîâ â ïîñëåäóþùèõ ÝÏ ìîæíî âûïîëíèòüòðåòèé ýòàï ïðèâåäåíèÿ ïîäîáíûõ ýòàï ïðèâåäåíèÿ ïîãëîùåíèé ÝÊ.

Íà êàæäîì øàãå ýòîãîýòàïà â ïîëó÷åííîéÄÍÔ ñ ïîìîùüþ òîæäåñòâ τ A , τ K âûäåëÿåòñÿ ïîäôîðìóëà âèäà K 00 ∨ K 00 · K , ãäå K 00 è K íåêîòîðûå ÝÊ, à çàòåìÝÊ K 00 · K ¾óñòðàíÿåòñÿ¿ ñ ïîìîùüþ ÝÏK 00 ∨ K 00 · K 7→ K 00 .tΠÇàìåòèì òàêæå, ÷òî ðàñêðûòèå ñêîáîê è ðàçëè÷íûå ýòàïûïðèâåäåíèÿ ïîäîáíûõ ìîæíî ÷åðåäîâàòü äðóã ñ äðóãîì ïðèb.ÝÏ ïîäôîðìóë ôîðìóëû F0 èëè ôîðìóë F00 , FbeÏåðåõîä îò F ê F â (3.2) âûïîëíÿåòñÿ â äâà ýòàïà. Ñíà÷àb , êîòîðàÿ èìååò ðàíã r, ãäå r = n − q <b èç Fëà êàæäàÿ ÝÊ Kn, è íå ñîäåðæèò áóêâ ÁÏ xi1 , . . . , xiq , ïðèâîäèòñÿ ê åå ñîe îò ÁÏ X (n) â ðåçóëüòàòå ñëåäóþùåãîâåðøåííîé ÄÍÔ KÝÏ:b |⇒ Kb (xi ∨ xi ) · · · xiq ∨ xiq |⇒ K.eK11tΠK1,&tD&,∨Ÿ3.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóë31Çàòåì â ïîëó÷åííîé ÎÄÍÔ óñòðàíÿþòñÿ ïîâòîðíûå âõîæäåíèÿ ñëàãàåìûõ òàê, êàê ýòî äåëàëîñü ðàíåå ïðè ïåðåõîäåb , è â ðåçóëüòàòå ìû ïðèõîäèì ê ñîâåðøåííîé ÎÄÍÔîò F̌ ê Fe .

Òàêèì îáðàçîì, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.FËþáóþ ôîðìóëó F (x1, . . . , xn), ðåàëèçóþùóþÔÀË f , ñ ïîìîùüþ ÝÏ íà îñíîâå ñèñòåìû òîæäåñòâ τ îñíìîæíî ïðåîáðàçîâàòü â ñîâåðøåííóþ ÎÄÍÔ ÔÀË f îò ÁÏX (n).Ëåììà 3.2.Ðàññìîòðèì îïèñàííûå âûøå ÝÏ íà ïðèìåðå ôîðìóëûF = (x1 ∨ x2 ) · (x1 · x3 ) · (x2 ∨ x3 ) ,äëÿ êîòîðîéF 7→ (x1 ∨ x2 ) · (x1 ∨ x3 ) · (x2 ∨ x3 )tM&F0|⇒{bFx1 x2 x3 ∨ x1 x2 ∨ x1 x2 x3 ∨ x2 x3ΠΠ \tΠtD&,∨ ,τ|⇒= F0 ,b= F̌ = F,}x1 x2 ∨ x2 x3b 0,=Fx1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3e= F.{τ A ,τ K ,tΠ }b0F|⇒{ΠΠtD&,∨ ,τ}Ñèñòåìà τ îñí ïîëíàÿ ñèñòåìà òîæäåñòâ.Äîêàçàòåëüñòâî.

Ïóñòü F0 è F00 ýêâèâàëåíòíûå ôîðìóëû,Òåîðåìà 3.1.ðåàëèçóþùèå ðàâíûå ÔÀË f 0 è f 00 ñîîòâåòñòâåííî, à íàáîðx (n) = x ñîäåðæèò âñå ðàçëè÷íûå ÁÏ, âñòðå÷àþùèåñÿ â F0e ñîâåðøåíè F00 . Ïóñòü, äàëåå, ÔÀË f (x) ðàâíà f 0 è f 00 , à Fíàÿ ÎÄÍÔ ÔÀË f îò ÁÏ X (n).  ñèëó ëåììû 3.2, èìååòìåñòî ÝÏe |⇒ F00 ,F0 |⇒ Fτ îñíêîòîðîå äîêàçûâàåò òåîðåìó.τ îñí32Ÿ4Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÑõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ. Îöåíêà ÷èñëà ôîðìóë è ñõåì â áàçèñå {&, ∨, ¬}Ðàññìîòðèì òåïåðü áîëåå îáùóþ ïî ñðàâíåíèþ ñ ôîðìóëàìè ìîäåëü ìîäåëü ñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ(ÑÔÝ), â êîòîðîé ïîñëåäîâàòåëüíîñòü îïåðàöèé ñóïåðïîçèöèè áàçèñíûõ ÔÀË çàäàåòñÿ ñ ïîìîùüþ îðèåíòèðîâàííîãîàöèêëè÷åñêîãî ãðàôà, îáîáùàþùåãî äåðåâî, è ãäå âîçìîæíîìíîãîêðàòíîå èñïîëüçîâàíèå ïðîìåæóòî÷íûõ ðåçóëüòàòîâ.Ïî ñóùåñòâó ÑÔÝ ïîëó÷àåòñÿ èç ñèñòåìû äåðåâüåâ (ñèñòåìû ôîðìóë) â ðåçóëüòàòå îòîæäåñòâëåíèÿ íåêîòîðûõ èçîìîðôíûõ ïîääåðåâüåâ (ñîâïàäàþùèõ ïîäôîðìóë).Ïóñòü Z ñ÷åòíûé óïîðÿäî÷åííûé àëôàâèò (âûõîäíûõ)ÁÏ, êîòîðûé íå èìååò îáùèõ ÁÏ ñ àëôàâèòîì X.

Ñîïîñòàâèì êàæäîìó ôóíêöèîíàëüíîìó ñèìâîëó (ÔÑ) ϕi , i =1, . . . , b, ôóíêöèîíàëüíûé ýëåìåíò (ÔÝ) Ei , èìåþùèé ki âõîäîâ, ïðè÷åì âõîäó ñ íîìåðîì j ñîîòâåòñòâóåò j -ÿ ÁÏ xj ÔÀËϕi , ãäå j = 1, . . . , ki , è îäèí âûõîä, íà êîòîðîì ýòà ÔÀË ðåàëèçóåòñÿ (ñì. ðèñ. 4.1a). Óïðîùåííûé âàðèàíò èçîáðàæåíèÿÔÝ Ei â âèäå âåðøèíû ãðàôà ñ ïîìåòêîé ϕi , â êîòîðóþ âõîäÿò ki óïîðÿäî÷åííûõ, òî åñòü ïðîíóìåðîâàííûõ ÷èñëàìè1, . .

. , ki äóã, ïîêàçàí íà ðèñ. 4.1b. Ïðè ýòîì ïðåäïîëàãàåòñÿ,÷òî äóãà ñ íîìåðîì j, 1 6 j 6 ki , ñîîòâåòñòâóåò j -ìó âõîäó ÔÝ Ei .  äàëüíåéøåì ìû, êàê ïðàâèëî, íå áóäåì äåëàòüðàçëè÷èé ìåæäó ôóíêöèîíàëüíûì ñèìâîëîì ϕi è ôóíêöèîíàëüíûì ýëåìåíòîì Ei .Ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ íàäáàçèñîì Á íàçûâàåòñÿ îðèåíòèðîâàííàÿ àöèêëè÷åñêàÿ óïî-Îïðåäåëåíèå.ðÿäî÷åííàÿ ñåòü Σ, âõîäíàÿ âûáîðêà êîòîðîé ñîñòîèò èç âñåõèñòîêîâ Σ, à âåðøèíû ïîìå÷åíû ñëåäóþùèì îáðàçîì:1. êàæäîìó âõîäó (âûõîäó) Σ ñîïîñòàâëåíà ÁÏ èç X (ñîîòâåòñòâåííî Z), ÿâëÿþùàÿñÿ ïîìåòêîé ñâÿçàííîé ñíèì âåðøèíû, ïðè÷åì ðàçëè÷íûì âõîäàì (âûõîäàì)Ÿ4.33ÑÔÝ, îöåíêà ÷èñëà ôîðìóë è ñõåìx*1 . .

. xki•*•x1 . . . xki••Ei 11 1111 ϕi 11 11 a)Ei**** 1 ** ki** *•ϕib)Ðèñ. 4.1: ôóíêöèîíàëüíûé ýëåìåíò Eiñîïîñòàâëåíû ðàçëè÷íûå ÁÏ, à óïîðÿäî÷åííîñòü âåðøèí âî âõîäíîé è âûõîäíîé âûáîðêàõ Σ îïðåäåëÿåòñÿóïîðÿäî÷åííîñòüþ ñîïîñòàâëåííûõ èì ÁÏ;2. êàæäàÿ îòëè÷íàÿ îò èñòîêà âåðøèíà v ñõåìû Σ ïîìå÷åíà ÔÑ ϕi , ãäå ki = d+Σ (v).Çàìåòèì, ÷òî â îáùåì ñëó÷àå âåðøèíû â âûõîäíîé âûáîðêå ÑÔÝ ìîãóò ïîâòîðÿòüñÿ, òî åñòü îäíîé è òîé æå âûõîäíîé âåðøèíå ìîæåò áûòü ñîïîñòàâëåíî íåñêîëüêî ÁÏ èçZ. Åñëè ìíîæåñòâî X = {xi1 , . . . , xin } (Z = {zj1 , .

. . , zjm }) ñîñòîèò èç âñåõ âõîäíûõ (ñîîòâåòñòâåííî âûõîäíûõ) ÁÏ ÑÔÝΣ, ïåðå÷èñëåííûõ â ïîðÿäêå âîçðàñòàíèÿ èõ íîìåðîâ â àëôàâèòå X (ñîîòâåòñòâåííî Z), òî, â ñîîòâåòñòâèè ñ Ÿ1, áóäåìçàïèñûâàòü ÑÔÝ Σ â âèäå Σ = Σ (X; Z) èëè Σ = Σ (x; z),ãäå x = (xi1 , . . .

, xin ) è z = (zj1 , . . . , zjm ) íàáîðû ÁÏ, ñîîòâåòñòâóþùèå ìíîæåñòâàì X è Z .Ñõåìà Σ, êîòîðàÿ ïîëó÷àåòñÿ èç äåðåâà D, ñâÿçàííîãî ñôîðìóëîé F èç UΦÁ , â ðåçóëüòàòå îòîæäåñòâëåíèÿ ëèñòüåâ ñîäèíàêîâûìè ïîìåòêàìè è ïðèïèñûâàíèÿ åãî êîðíþ âûõîäíîé ÁÏ èç Z, íàçûâàåòñÿF. Çàìåòèì, ÷òî óêàçàííîå êâàçèäåðåâî Σ îäíîçíà÷íî îïðåäåëÿåò ôîðìóëó F è ÿâëÿåòñÿ ÑÔÝ íàä áàçèñîìôîðìóëåêâàçèäåðåâîì, ñîîòâåòñòâóþùèì34Ãëàâà 2.xG1x2Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìGG www• 2wwGG1ww GGx3*•{w * w2 1 G•G# ∨GG ww•GGww& **wG2**ww GGG 2w*w{11 •#•2 * ∨** &1** 1•4•¬∨ 4444 2 44 1• ∨•Gz1a)x#S1xk•2SSSkkkkk ##11 ukkk S1S1 ) 11& 11∨ x311#S## SSSS kkkk•SkSkSk#11 ukk 1S1 ) 11& 11∨ 11nnjjj11 vnnn 11 ujjjj11∨ 11¬ 1:1:::: 11 11∨ 1•# SSSz1b)Ðèñ.

4.2: ÑÔÝ, ïîëó÷åííàÿ èç êâàçèäåðåâà íà ðèñ. 2.2bÁ. Èç ýòîãî êâàçèäåðåâà ïóòåì ¾îòîæäåñòâëåíèÿ¿ (íàëîæåíèÿ) åãî èçîìîðôíûõ êâàçèïîääåðåâüåâ ìîæíî ïîëó÷àòü èäðóãèå ÑÔÝ, çàäàþùèå ôîðìóëó F. Íà ðèñ. 2.2b ïîêàçàíîêâàçèäåðåâî íàä áàçèñîì Á0 ñ âõîäíûìè ÁÏ x1 , x2 , x3 è âûõîäíîé ÁÏ z1 , êîòîðîå ïîëó÷åíî èç äåðåâà, ñîïîñòàâëåííîãîôîðìóëå (2.3) è èçîáðàæåííîãî íà ðèñ. 2.2a.

Íà ðèñ. 4.2aïðèâåäåíà ÑÔÝ, ïîëó÷åííàÿ èç äàííîãî êâàçèäåðåâà â ðåçóëüòàòå îòîæäåñòâëåíèÿ äâóõ åãî èçîìîðôíûõ êâàçèïîääåðåâüåâ, à íà ðèñ. 4.2b äàíî áîëåå ¾íàãëÿäíîå¿ èçîáðàæåíèåýòîé ÑÔÝ â âèäå ñèñòåìû ñîåäèíåííûõ ñîîòâåòñòâóþùèìîáðàçîì ÔÝ.Îáîçíà÷èì ÷åðåç UCÁ ìíîæåñòâî âñåõ ÑÔÝ íàä áàçèñîìCCÁ, è ïóñòü U = UÁ0 . Çàìåòèì, ÷òî ñèñòåìà êâàçèäåðåâüåâñ îáùèìè âõîäàìè, ñîîòâåòñòâóþùàÿ ñèñòåìå ôîðìóë íàäáàçèñîì Á, ÿâëÿåòñÿ ÑÔÝ íàä Á, åñëè âûõîäàì ýòèõ êâà-Ÿ4.ÑÔÝ, îöåíêà ÷èñëà ôîðìóë è ñõåì35çèäåðåâüåâ ïðèïèñàíû ðàçëè÷íûå âûõîäíûå ÁÏ.

 ñâÿçè ñýòèì ôîðìóëû íàä Á è èõ ñèñòåìû áóäåì ñ÷èòàòü ÷àñòíûìñëó÷àåì ÑÔÝ íàä Á, ïîëàãàÿ, ÷òî èìååò ìåñòî âêëþ÷åíèåCCΦUΦÁ ⊆ UÁ . Çàìåòèì òàêæå, ÷òî ÑÔÝ Σ, Σ ∈ UÁ , âõîäèò â UÁòîãäà è òîëüêî òîãäà, êîãäà âñå ñòîêè Σ, è òîëüêî îíè, ÿâëÿþòñÿ åå âûõîäàìè, à èç êàæäîé âåðøèíû Σ, îòëè÷íîé îòåå âõîäîâ è âûõîäîâ, èñõîäèò îäíà äóãà.Îïðåäåëèì òåïåðü ôóíêöèîíèðîâàíèå ÑÔÝ Σ == Σ (x1 , . . .

, xn ; z1 , . . . , zm ) íàä áàçèñîì Á. Ñíà÷àëà èíäóêöèåé ïî q, q = 0, 1, . . ., îïðåäåëèì äëÿ êàæäîé âåðøèíûv ãëóáèíû q â ñõåìå Σ ðåàëèçóåìóþ â íåé ôîðìóëó Fv =Fv (x1 , . . . , xn ) ãëóáèíû q íàä áàçèñîì Á. Åñëè q = 0, òî åñòüv âõîä Σ, ïîëîæèì Fv = xj , ãäå xj âõîäíàÿ ÁÏ, ñîïîñòàâëåííàÿ âåðøèíå v . Ïóñòü òåïåðü v âåðøèíà ãëóáèíûq, q > 1, ñõåìû Σ, êîòîðàÿ èìååò ïîìåòêó ϕi è â êîòîðóþâõîäèò ki äóã, ïðè÷åì äóãà ñ íîìåðîì j, 1 6 j 6 ki , èñõîäèòèç âåðøèíû vj ãëóáèíû qj , ãäå óæå ðåàëèçîâàíà ôîðìóëàFj = Fvj ãëóáèíû qj , à äëÿ ÷èñåë q, q1 , .