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

Ïîýòîìó îïòèìèçàöèÿ ïîäîáíûõ ôîðìóë ïî ãëóáèíåÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì ¾ðàñïàðàëëåëèâàíèÿ¿ âû÷èñëåíèé.Ôîðìóëû èç UΦ ìîæíî îïòèìèçèðîâàòü òàêæå ïî ÷èñëóîòðèöàíèé ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé íà îñíîâå òîæäåñòâìóëûýêâèâàëåíòíûì ïðåîáðàçîâàíèåì (ÝÏ) ôîð-ïîäîáíûìètM& : (x1 · x2 ) = x1 ∨ x2 ,tM∨: (x1 ∨ x2 ) = x1 · x2 ,tM¬ : (x1 ) = x1 òîæäåñòâ äå Ìîðãàíà äëÿ êîíúþíêöèè, äèçúþíêöèè èîòðèöàíèÿ ñîîòâåòñòâåííî, à òàêæå ïðåîáðàçîâàíèé ïîäîáèÿ. Òîæäåñòâî tM¬ èñïîëüçóåòñÿ ïðè ýòîì äëÿ óñòðàíåíèÿ22Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìíåñêîëüêèõ ïîñëåäîâàòåëüíûõ âõîæäåíèé ÔÑ ¬ â îïòèìèMçèðóåìîé ôîðìóëå, à òîæäåñòâà tM& , t∨ äëÿ âûïîëíåíèÿïåðåõîäàF0 = F1 ◦ · · · ◦ Ft = (F1 · · · Ft ),ãäå (◦, ) ∈ {(&, ∨), (∨, &)} è t > 2, âî âñåõ åå ìàêñèìàëüíûõ ïî âêëþ÷åíèþ ïîäôîðìóëàõ âèäà F0 , ôîðìèðóåìûõ ñïîìîùüþ ïðåîáðàçîâàíèé ïîäîáèÿ.Ôîðìóëà, â êîòîðîé âñå ÔÑ ¬ âñòðå÷àþòñÿ òîëüêî íàäÁÏ, íàçûâàåòñÿ.

Ëåãêî âèäåòü, ÷òî ñ ïîìîùüþ òîæäåñòâ äå Ìîðãàíà ëþáóþ ôîðìóëó èç UΦ ìîæíî ïðåîáðàçîâàòü â ôîðìóëó ñ ïîäíÿòûìèîòðèöàíèÿìè. Çàìåòèì, ÷òî ïðåîáðàçîâàíèÿ ïîäîáèÿ è ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóë íà îñíîâå òîæäåñòâ äåÌîðãàíà íå èçìåíÿþò ðàíã ýòèõ ôîðìóë è, ñëåäîâàòåëüíî,÷èñëî ÔÑ {&, ∨} â íèõ.Îïðåäåëèì àëüòåðíèðîâàíèå Alt (F) ôîðìóëû F ñ ïîäíÿòûìè îòðèöàíèÿìè êàê ìàêñèìàëüíîå ÷èñëî èçìåíåíèéòèïîâ ÔÑ & è ∨ â öåïÿõ äåðåâà, ñîîòâåòñòâóþùåãî ôîðìóëåF. Çàìåòèì, ÷òî àëüòåðíèðîâàíèå ÝÊ èëè ÝÄ ðàâíî íóëþ,à àëüòåðíèðîâàíèå ëþáîé (îòëè÷íîé îò ÝÊ è ÝÄ) ÄÍÔ èëèÊÍÔ ðàâíî 1.ôîðìóëîé ñ ïîäíÿòûìè îòðèöàíèÿìèÒåîðåìà 2.1.öàíèÿìè èçêàÿ,÷òîÄëÿ ëþáîé ôîðìóëû F ñ ïîäíÿòûìè îòðèñóùåñòâóåò ïîäîáíàÿ åé ôîðìóëà F̌ òà-UΦD F̌ 6 dlog (L (F) + 1)e + Alt (F) .Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî(2.6)ïðîâåäåì èíäóêöèåé ïîðàíãó ôîðìóëû F.

Åñëè R (F) = 1, òî ôîðìóëà F èìååò âèäF = xσi , σ ∈ B , è ñàìà óäîâëåòâîðÿåò íåðàâåíñòâó (2.6).Ïóñòü íåðàâåíñòâî (2.6) ñïðàâåäëèâî äëÿ ëþáîé ïîäôîðìóëû F0 òàêîé, ÷òî R(F0 ) 6 r − 1, ãäå r > 2, è ïóñòü ôîðìóëàF èìååò ðàíã r è àëüòåðíèðîâàíèå a. Ïðåäñòàâèì ôîðìóëóŸ2.23Ôîðìóëû, èõ îïòèìèçàöèÿ ïî ãëóáèíåF â âèäå:F = Φ (F1 , . . . , Ft ) ,ãäå t > 2, ôîðìóëà Φ(y1 , . .

. , yt ) ïðè íåêîòîðîì ◦, ◦ ∈ {&, ∨},èìååò âèä y1 ◦ . . . ◦ yt , àëüòåðíèðîâàíèå ïîäôîðìóë F1 , . . .. . . , Ft ôîðìóëû F íå áîëüøå, ÷åì a0 , ãäå a0 = max{0, (a − 1)},à èõ ðàíã íå ïðåâîñõîäèò (r − 1). Ïîëîæèìd = dlog (L (F) + 1)e + a − a0è di = dlog (L (Fi ) + 1)e ,ãäå i = 1, . . . , t, à çàòåì äëÿ êàæäîé ôîðìóëû Fi ïîñòðîèìïî èíäóêòèâíîìó ïðåäïîëîæåíèþ ïîäîáíóþ åé ôîðìóëó F̌iòàêóþ, ÷òîD F̌i 6 di + a0 .Çàìåòèì, ÷òî ïðè ýòîìtX(2.7)2di 6 2d .i=1Äåéñòâèòåëüíî, åñëè a − a0 = 1, òî2d > 2 (L (F) + 1) =tX2 (L (Fi ) + 1) >i=1tX2di ,i=1à åñëè a = a0 = 0, òî F = xσ1 1 ◦ · · · ◦ xσt t è, ñëåäîâàòåëüíî,tXi=12di =tX(L (xσi i ) + 1) = L (F) + 1 6 2d .i=1Çàìåòèì òàêæå,÷òî ïåðåíóìåðàöèåé ôîðìóë F̌i , i = 1, .

. . , t,ìîæíî äîáèòüñÿ âûïîëíåíèÿ íåðàâåíñòâ:d1 > d2 > · · · > dt .(2.8)24Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÏóñòü òåïåðü Φ0 ôîðìóëà âèäà y1 ◦ · · · ◦ y2d , êîòîðîé ñîîòâåòñòâóåò ïîëíîå äâîè÷íîå d-ÿðóñíîå äåðåâî, à ôîðìóëà Φ00 ïîëó÷àåòñÿ èç Φ0 óäàëåíèåì ïîñëåäíèõ q , ãäå q =2d − 2d1 − · · · − 2dt è q > 0 â ñèëó (2.7), âõîæäåíèé ÁÏâìåñòå ñ òåìè ÔÑ, êîòîðûå ñ íèìè ñâÿçàíû.

 ñèëó (2.8)ïåðâûå 2d1 âõîæäåíèé ÁÏ â Φ00 ñîñòàâëÿþò ïîäôîðìóëó Φ1 ,êîòîðîé ñîîòâåòñòâóåò ïîëíîå äâîè÷íîå d1 -ÿðóñíîå äåðåâî,ñîäåðæàùåå 2d1 âõîæäåíèé ÁÏ â Φ00 , ñëåäóþùèå 2d2 âõîæäåíèé ÁÏ â Φ00 ïîäôîðìóëó Φ2 , êîòîðîé ñîîòâåòñòâóåòïîëíîå äâîè÷íîå d2 -ÿðóñíîå äåðåâî, è òàê äàëåå, âïëîòü äîïîñëåäíèõ 2dt âõîæäåíèé ÁÏ â Φ00 , ñîñòàâëÿþùèõ ïîäôîðìóëó Φt , êîòîðîé ñîîòâåòñòâóåò ïîëíîå äâîè÷íîå dt -ÿðóñíîåäåðåâî.Îáîçíà÷èì ÷åðåç F̌ ôîðìóëó, êîòîðàÿ ïîëó÷àåòñÿ èç Φ00çàìåíîé ïîäôîðìóëû Φi íà ôîðìóëó F̌i , i = 1, .

. . , t. Çàìåòèì, ÷òî F̌ ïîäîáíà F, èìååò ãëóáèíó íå áîëüøå,÷åìd + a0 = dlog (L (F) + 1)e + a,è ïîýòîìó óäîâëåòâîðÿåò íåðàâåíñòâó (2.6).Òåîðåìà äîêàçàíà.Äëÿ ëþáîé ÝÊ èëè ÝÄ K ñóùåñòâóåò ïîäîáíàÿ ôîðìóëà Ǩ òàêàÿ, ÷òîÑëåäñòâèå 1.D Ǩ = dlog (L(K) + 1)e ,(2.9)êîòîðàÿ, â ñèëó ëåììû 2.1, ìèíèìàëüíà ïî ãëóáèíå.Äëÿ ëþáîé ÄÍÔ èëè ÊÍÔ A ñóùåñòâóåòïîäîáíàÿ åé ôîðìóëà Ǎ òàêàÿ, ÷òîÑëåäñòâèå 2.D Ǎ 6 dlog (L (A) + 1)e + 1.Çàìå÷àíèå.

Äîêàçàòåëüñòâî òåîðåìû äàåò èíäóêòèâíûé ìåòîä îïòèìèçàöèè ôîðìóë ñ ïîäíÿòûìè îòðèöàíèÿìè ïî ãëóáèíå ñ ïîìîùüþ ïðåîáðàçîâàíèé ïîäîáèÿ.Ÿ3.Ÿ3Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóë25Çàäà÷à ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ñõåìíà ïðèìåðå ôîðìóë. Ïîëíîòà ñèñòåìû îñíîâíûõ òîæäåñòâ äëÿ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ôîðìóë áàçèñà {&, ∨, ¬}Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ (ÝÏ), òî åñòü ïðåîáðàçîâàíèÿ, íå èçìåíÿþùèå ôóíêöèîíèðîâàíèÿ ñõåì, èãðàþò âàæíóþ ðîëü ïðè ðåøåíèè ðàçëè÷íûõ çàäà÷ òåîðèè óïðàâëÿþùèõ ñèñòåì è, â ÷àñòíîñòè, çàäà÷è ñèíòåçà ñõåì (ñì. Ÿ1 ãëàâû3). Ñëåäóÿ [30], èçëîæèì ðÿä âîïðîñîâ ÝÏ ñõåì èç îñíîâíûõêëàññîâ è ðàññìîòðèì ñíà÷àëà ïîíÿòèÿ, ñâÿçàííûå ñ ýêâèâàëåíòíûìè ïðåîáðàçîâàíèÿìè ñõåì íà îñíîâå òîæäåñòâ íàïðèìåðå ôîðìóë íàä áàçèñîì Á.

Íàïîìíèì, ÷òî íåêîòîðûåÝÏ ôîðìóë áàçèñà Á0 óæå èñïîëüçîâàëèñü äëÿ ðàñêðûòèÿñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ ïðè ïîñòðîåíèè ñîêðàùåííîéÄÍÔ (ñì. Ÿ3 ãëàâû 1), à òàêæå ïðè îïòèìèçàöèè ôîðìóë ïîãëóáèíå (ñì. Ÿ2).Îäíîêðàòíîå ÝÏ ôîðìóëû F â ôîðìóëó F̌ ñ ïîìîùüþòîæäåñòâà t (ñì. Ÿ2) áóäåì çàïèñûâàòü â âèäå îäíîêðàòíîée â ðåçóëüâûâîäèìîñòè âèäà F 7→ F̌. Àíàëîãè÷íîå ÝÏ F â Ftòàòå ïðèìåíåíèÿ îäíîãî èç òîæäåñòâ ñèñòåìû τ (íåñêîëüêèõïîñëåäîâàòåëüíûõ ïðèìåíåíèé òîæäåñòâ èç τ ) áóäåì çàïèñûâàòü â âèäå îäíîêðàòíîé (ñîîòâåòñòâåííî êðàòíîé) âûâîe (ñîîòâåòñòâåííî F |⇒ Fe ). Ïðè ýòîìäèìîñòè âèäà F 7→ Fττñ÷èòàåòñÿ, ÷òî òîæäåñòâîeet: F=Fâûâîäèòñÿ èç ñèñòåìû òîæäåñòâ τ , è ýòîò ôàêò çàïèñû-âàåòñÿ â âèäå âûâîäèìîñòè τ 7→ et èëè τ |⇒ et â çàâèñèìîñòèîò ÷èñëà èñïîëüçîâàííûõ ïåðåõîäîâ.

Çàìåòèì, ÷òî â ñèëóe ñëåäóåò îáðàòíàÿîáðàòèìîñòè ÝÏ èç âûâîäèìîñòè F |⇒ Fτe |⇒ F. Ñèñòåìà òîæäåñòâ τ íàçûâàåòñÿâûâîäèìîñòü Fτïîëíîé26Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìäëÿ ÝÏ ôîðìóë íàä Á, åñëè äëÿ ëþáûõ äâóõ ýêâèâàëåíòíûõôîðìóë F0 è F00 íàä Á èìååò ìåñòî âûâîäèìîñòü F0 |⇒ F00 .τÐàññìîòðèì, â ÷àñòíîñòè, ñèñòåìó τ , êîòîðàÿ ñîñòîèò èçòîæäåñòâ äå Ìîðãàíà è òîæäåñòâàtÏK1,& : x1 (x2 ∨ x2 ) = x1 , òîæäåñòâà ïîäñòàíîâêè êîíñòàíòû 1 = x2 ∨ x2 â êîíúþíêöèþ (ñì. òîæäåñòâà (2.2) èç ãëàâû 1).

Ïðèìåð ÝÏ ôîðìóë èçUΦ ñ ïîìîùüþ ñèñòåìû òîæäåñòâ τ äàåò ñëåäóþùàÿ öåïî÷êàâûâîäèìîñòåé:x1 (x2 x3 ∨ x2 ∨ x3 ) 7→ x1 (x2 x3 ∨ x2 · x3 ) 7→ x1 .tM&tΠK1,&(3.1)Äàëåå áóäåì ðàññìàòðèâàòü òîëüêî ôîðìóëû íàä áàçèñîìÁ0 , íàçûâàÿ èõ ïðîñòî ôîðìóëàìè.

Çàìåòèì, ÷òî èìåþò ìåñòî (ñì., â ÷àñòíîñòè, Ÿ2 ãëàâû 1, à òàêæå Ÿ2) ñëåäóþùèåòîæäåñòâà àññîöèàòèâíîñòètA◦ : x1 ◦ (x2 ◦ x3 ) = (x1 ◦ x2 ) ◦ x3 ,òîæäåñòâà êîììóòàòèâíîñòètK◦ : x1 ◦ x2 = x2 ◦ x2è òîæäåñòâà îòîæäåñòâëåíèÿ ÁÏtOΠ: x ◦ x = x,◦ãäå ◦ ∈ {&, ∨}, òîæäåñòâà äèñòðèáóòèâíîñòè ¾◦¿ îòíîñèòåëüíî ¾¿tD◦, : x1 ◦ (x2 x3 ) = (x1 ◦ x2 ) (x1 ◦ x3 )è òîæäåñòâà (¾ïðàâèëà¿) äå ÌîðãàíàtM¬ : (x1 ) = x1 ,tM◦ : (x1 ◦ x2 ) = (x1 ) (x2 ) ,Ÿ3.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóë27ãäå (◦, ) ∈ {(&, ∨) , (∨, &)}, òîæäåñòâà ïîäñòàíîâêè êîíñòàíò1ΠKtΠK0,& : x1 (x2 · x2 ) = x2 · x2 , t1,& : x1 (x2 ∨ x2 ) = x1 ,tΠK0,∨ : x1 ∨ x2 · x2 = x1 ,tΠK1,∨ : x1 ∨ (x2 ∨ x2 ) = x2 ∨ x2 ,à òàêæå òîæäåñòâî ïîãëîùåíèÿt Π : x1 ∨ x1 x2 = x1 ,òîæäåñòâî îáîáùåííîãî ñêëåèâàíèÿtOC : x1 x2 ∨ x1 x3 = x1 x2 ∨ x1 x3 ∨ x2 x3è äðóãèå.Äîêàæåì, ÷òî MMtM& , t¬ |⇒ t∨è K M t& , τ|⇒ tK∨ ,M Mãäå τ M = tM& , t¬ , t∨ .

Äåéñòâèòåëüíî,x1 ∨ x2 |⇒ x1 ∨ x2 7→ (x1 ) · (x2 ) 7→ x1 · x2tM&tM¬tM¬èx1 ∨ x2 7→ x1 ∨ x2 7→ x1 · x2 7→ x2 · x1 |⇒ x2 ∨ x1 .tM¬tM∨tK&MtM& , t¬Àíàëîãè÷íûì îáðàçîì äîêàçûâàåòñÿ, ÷òî OΠ M MtA|⇒ tA|⇒ tOΠ,∨ , t& , τ∨&, τDΠKMt&,∨ , τ M |⇒ tD|⇒ tΠKσ,∨ ,∨,& è tσ,& , τ1 îòëè÷èå îò òîæäåñòâ (2.1)(2.2) ãëàâû 1 äàííûå òîæäåñòâà ïîäñòàíîâêè êîíñòàíò îðèåíòèðîâàíû íà áàçèñ Á0 , ãäå ðîëü êîíñòàíòû 0(êîíñòàíòû 1) èãðàåò ôîðìóëà âèäà xi · xi (ñîîòâåòñòâåííî xi ∨ xi ).28Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìãäå σ ∈ {0, 1}.

Çàâåðøàÿ ïðèìåðû âûâîäèìîñòåé, äîêàæåì,÷òî ΠK DK OΠt1,& , t&,∨ , tA|⇒ tΠ .∨ , t∨ , t∨Äåéñòâèòåëüíî,x1 ∨ x1 x2 7→ x1 (x2 ∨ x2 ) ∨ x1 x2 7→ x1 ((x2 ∨ x2 ) ∨ x2 )tΠK1,&tD&,∨|⇒ x1 ((x2 ∨ x2 ) ∨ x2 ) 7→ x1 (x2 ∨ x2 ) 7→ x1 .KtA∨ ,t∨tOΠ∨tΠK1,&ÏîëîæèìΠK ΠKM A K OΠ Dτ îñí = tM& , t¬ , t& , t& , t& , t&,∨ , t1,& , t0,& ,Aτ A = tA& , t∨ ,Kτ K = tK& , t∨ ,OΠ,τ OΠ = tOΠ& , t∨DDDτ = t&,∨ , t∨,& ,ΠKΠK ΠK ΠKτ= tΠK0,& , t1,& , t0,∨ , t1,∨ ,τeîñí = τ M , τ A , τ K , τ OΠ , τ D , τ ΠK , tΠ .ñèñòåìîé îñíîâíûõ òîæäåñòâðàñøèðåííîé ñèñòåìîé îñíîâíûõ òîæ-Ñèñòåìó τ îñí áóäåì íàçûâàòü,îñíà ñèñòåìó τe.

Ðàññìîòðåííûå âûøå ïðèìåðû âûâîäèìîñòåé äîêàçûâàþò ñëåäóþùåå óòâåðæäåíèå.äåñòâËåììà 3.1.Ñèñòåìà τeîñí âûâîäèìà èç ñèñòåìû τ îñí.Ïîêàæåì òåïåðü, ÷òî ñ ïîìîùüþ ÝÏ íà îñíîâå ñèñòåìûòîæäåñòâ τ îñí èç ëþáîé ôîðìóëû ìîæíî ïîëó÷èòü ñîâåðøåííóþ ÄÍÔ èëè ôîðìóëó x1 x1 . Ââåäåì äëÿ ýòîãî íåêîòîðûå ïîíÿòèÿ, õàðàêòåðèçóþùèå ôîðìóëû, ïîÿâëÿþùèåñÿíà ïðîìåæóòî÷íûõ ýòàïàõ óêàçàííîãî ÝÏ. ÏðîèçâîëüíóþŸ3.29Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóëêîíúþíêöèþ áóêâ, ñîäåðæàùóþ, â îáùåì ñëó÷àå, ïîâòîðÿþùèåñÿ èëè ïðîòèâîïîëîæíûå áóêâû, áóäåì íàçûâàòüÝÊ (ÎÝÊ), à äèçúþíêöèþ òàêèõ êîíúþíêöèé, ñîäåðæàùóþ, â îáùåì ñëó÷àå, ïîâòîðÿþùèåñÿ ¾ñëàãàåìûå¿, îáîáùåííîé ÄÍÔ (ÎÄÍÔ).

Îáû÷íóþ ÝÊ (ÄÍÔ) è ôîðìóëóx1 · x1 áóäåì ñ÷èòàòüÎÝÊ (ñîîòâåòñòâåííîÎÄÍÔ), à ñîâåðøåííóþ ÄÍÔ è ôîðìóëó x1 · x1ÎÄÍÔ. Íàïîìíèì (ñì. Ÿ2), ÷òî ôîðìóëà,â êîòîðîé âñå ÔÑ ¬ ïðèìåíÿþòñÿ òîëüêî ê ÁÏ è íåò äâóõïîñëåäîâàòåëüíî ïðèìåíÿåìûõ ÔÑ ¬, íàçûâàåòñÿ ôîðìóëîéñ ïîäíÿòûìè îòðèöàíèÿìè.Ïóñòü ôîðìóëà F (x1 , . . . , xn ) ðåàëèçóåò ÔÀË f (x1 , .