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

. , zm ).Íîìåð ν(α) íàáîðà α = (α1 , . . . , αn ) èç B n ñ÷èòàåòñÿαn1ÝÊ (ÝÄ) ðàíãà n îò ÁÏ X (n) âèäà xα1 · · ·xn (ñîîòα1nâåòñòâåííî x1 ∨. . .∨xαn ), ìíîæåñòâî âñåõ òàêèõ ÔÀË îáîçíà÷àåòñÿ Qn (ñîîòâåòñòâåííî Jn ), à ñèñòåìà èç âñåõ óêàçàííûõÔÀË, óïîðÿäî÷åííûõ ïî èõ íîìåðàì, íàçûâàåòñÿ(ñîîòâåòñòâåííî)−→n îò ÁÏ x1 , . .

. , xn è îáîçíà÷àåòñÿ ÷åðåç Qn (ñîîòâåò−→ñòâåííî Jn ). Ôóíêöèÿ âèäàíî-ìåðîìêîíúþíêäèçúþíêòèâíûì äåøèôðàòîðîìòèâíûìïîðÿäêàµn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =_xα1 1 · · · xαnn yν(α)α=(α1 ,...,αn )ìóëüòèïëåêñîðíîé ôóíêöèåé, èëè, èíà÷å, ìóëüòèïëåêñîðîì ïîðÿäêà n, à ïåðåìåííûå x = (x1, . .

. , xn) (y =(y0 , . . . , y2 −1 )) ñ÷èòàþòñÿ àäðåñíûìè (ñîîòâåòñòâåííî èíôîðìàöèîííûìè ) ÁÏ ìóëüòèïëåêñîðà µn.íàçûâàåòñÿnÌóëüòèïëåêñîðíóþ ÔÀË ïîðÿäêà (n − q) , 0 6 q < n, îòàäðåñíûõ ÁÏ x00 = (xq+1 , . . . , xn ) è èíôîðìàöèîííûõ ÁÏ y =(y0 , . . . , y2n−q −1 ) ÷àñòî èñïîëüçóþò äëÿ ðàçëîæåíèÿ ïðîèçâîëüíîé ÔÀË f (x1 , . . .

, xn ) ïî ÁÏ x00 (ñì. ðàçëîæåíèå Øåííîíà (2.5) èç Ÿ2 ãëàâû 1).Ñõåìó, êîòîðàÿ ðåàëèçóåò ñèñòåìó ÔÀË Qn (Jn , µn ) áóäåì íàçûâàòü(ñîîòâåòñòâåííî,)n. Ñõåìû,ðåàëèçóþùèå ðàâíûå ñèñòåìû ôóíêöèé, íàçûâàþòñÿäåøèôðàòîðîìäèçúþíêòèâíûì äåøèôðàòîðîì ìóëüòèïëåêñîðîì ïîðÿäêàýêâè-16Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìâàëåíòíûìè. Ïðåäïîëàãàåòñÿ, ÷òî èçîìîðôíûå ñõåìû âñåãäà ýêâèâàëåíòíû, è ïîýòîìó äëÿ ëþáîãî êîíå÷íîãî ìíîæåñòâà ñõåì U âûïîëíÿåòñÿ íåðàâåíñòâîkUk 6 |U| ,(1.7)ãäå kUk ÷èñëî ïîïàðíî íå ýêâèâàëåíòíûõ ñõåì â U.Ÿ2Ôîðìóëû, èõ ñòðóêòóðà, ýêâèâàëåíòíîñòü èñïîñîáû çàäàíèÿ. Îïòèìèçàöèÿ ïîäîáíûõ ôîðìóë ïî ãëóáèí堟1 ãëàâû 1 äàíî èíäóêòèâíîå îïðåäåëåíèå ôîðìóëû è ðåàëèçóåìîé åþ ôóíêöèè. Íàïîìíèì åãî è ðàññìîòðèì ñïîñîáïðåäñòàâëåíèÿ ôîðìóë àëãåáðû ëîãèêè ñ ïîìîùüþ îðèåíòèðîâàííûõ óïîðÿäî÷åííûõ äåðåâüåâ.Ïóñòü, ïî-ïðåæíåìó, X = {x1 , x2 , . . .

, xn , . . . } ñ÷åòíûéóïîðÿäî÷åííûé àëôàâèò âõîäíûõ ÁÏ è ïóñòü Á == {ϕ1 , ϕ2 , . . . , ϕb } áàçèñ, ãäå ÔÀË ϕi , i = 1, . . . , b, çàâèñèòîò ki , ki > 1, ÁÏ è ÿâëÿåòñÿ ñóùåñòâåííîé ÔÀË, åñëè ki > 2.Ïðåäïîëàãàåòñÿ, ÷òî Á ïîëíûé áàçèñ (ñì. Ÿ1 ãëàâû 1) èäîïóñêàåòñÿ, â îáùåì ñëó÷àå, íàëè÷èå â íåì ðàâíûõ ÔÀË.×àùå âñåãî ìû áóäåì èìåòü äåëî ñ áàçèñîì Á0 = {&, ∨, ¬}.Ëþáàÿ ïåðåìåííàÿ xj èç X ñ÷èòàåòñÿ0 èëè, èíà÷å,Á, êîòîðàÿ ðåàëèçóåò ôóíêöèþ xj .

Åñëè i ∈ [1, b] è äëÿ êàæäîãîj, j ∈ [1, ki ], îïðåäåëåíà ôîðìóëà Fj ãëóáèíû qj íàä Á, êîòîðàÿ ðåàëèçóåò ÔÀË fj , òî çàïèñü F âèäàôîðìóëîé ãëóáèíûòðèâèàëüíîé ôîðìóëîé íàä áàçèñîìF = ϕi (F1 , . . . , Fki )ÿâëÿåòñÿ(2.1)ôîðìóëîé ãëóáèíû q íàä Á, ãäåq = max {q1 , . . . , qki } + 1,êîòîðàÿ ðåàëèçóåò ôóíêöèþ f âèäà f = ϕi (f1 , . . . , fki ).(2.2)Ÿ2.Ôîðìóëû, èõ îïòèìèçàöèÿ ïî ãëóáèíå17Âñå çàïèñè, ïîëó÷åííûå â ðåçóëüòàòå óêàçàííîãî èíäóêòèâíîãî ïîñòðîåíèÿ, è òîëüêî îíè ñ÷èòàþòñÿÁ. Ïðè ýòîì ôîðìóëû, ïîëó÷åííûå â ïðîöåññå èíäóêòèâíîãî ïîñòðîåíèÿ ôîðìóëû F, íàçûâàþòñÿ åå, à òå ïîäôîðìóëû F1 , . . . , Fki , èç êîòîðûõ íà ïîñëåäíåì øàãå èíäóêòèâíîãî ïîñòðîåíèÿ ñòðîèòñÿ ôîðìóëà F âèäà (2.1), ñ÷èòàþòñÿ ååïîäôîðìóëàìè.Çàìåòèì, ÷òî çàïèñü ïîäôîðìóëû F0 ôîðìóëû F ÿâëÿåòñÿ ÷àñòüþ çàïèñè F, ïðè÷¼ì êàæäàÿ òàêàÿ ÷àñòü ñ÷èòàåòñÿF0 â F èëè, èíà÷å,0F ôîðìóëû F, à ÷èñëî óêàçàííûõ ÷àñòåé íàçûâàåòñÿF0 â F.

Ïîä() ôîðìóëû Fïîíèìàåòñÿ ÷èñëî âõîæäåíèé â íåå ôóíêöèîíàëüíûõ ñèìâîëîâ (ñîîòâåòñòâåííî ñèìâîëîâ ïåðåìåííûõ), êîòîðîå îáîçíà÷àåòñÿ ÷åðåç L (F) (ñîîòâåòñòâåííî R (F)).Íàïîìíèì, ÷òî ¾ãðàôè÷åñêè¿ ñîâïàäàþùèå ôîðìóëû ñ÷èòàþòñÿ, à ôîðìóëû F0 è F00 , ðåàëèçóþùèå ðàâ000íûå ôóíêöèè f è f , íàçûâàþòñÿèëè, èíà÷å,. Ïðè ýòîì ðàâåíñòâî âèäà t : F0 = F00 ñ÷èòàåòAñÿ. ×åðåç tKϕ è tϕ áóäåì îáîçíà÷àòü òîæäåñòâîêîììóòàòèâíîñòè è òîæäåñòâî àññîöèàòèâíîñòè äëÿ ÔÀËϕ (x1 , x2 ), ãäå ϕ ∈ {x1 · x2 , x1 ∨ x2 , x1 ⊕ x2 , x1 ∼ x2 }(ñì. Ÿ2ãëàâû 1).Ìíîæåñòâî âñåõ ôîðìóë íàä áàçèñîì Á áóäåì îáîçíà÷àòüΦΦ÷åðåç UΦÁ è ïîëîæèì UÁ0 = U .

Èíäóêöèåé ïî ãëóáèíå ëþáîé ôîðìóëå ãëóáèíû q íàä Á ìîæíî ñîïîñòàâèòü óïîðÿäî÷åííîå îðèåíòèðîâàííîå êîðíåâîå äåðåâî ãëóáèíû q , êàæäîìó ëèñòó êîòîðîãî ïðèïèñàíà ÁÏ èç X, à êàæäîé âíóòðåííåéâåðøèíå ôóíêöèîíàëüíûé ñèìâîë (ÔÑ) èç Á. Ôîðìóëå xjãëóáèíû 0 ñîïîñòàâèì ¾òðèâèàëüíîå¿ äåðåâî ñ åäèíñòâåííîé âåðøèíîé, ÿâëÿþùåéñÿ êîðíåì è ëèñòîì îäíîâðåìåííî,êîòîðîé ïðèïèñàíà ÁÏ xj (ñì. ðèñ.

2.1a). Ôîðìóëå F âèäà (2.1) ñîïîñòàâèì äåðåâî D ãëóáèíû q , îïðåäåëÿåìîé ðàâåíñòâîì (2.2), è ñ êîðíåì v , ïîêàçàííîå íà ðèñ. 2.1b, ãäåôîðìóëàìè íàäïîäôîð-áàçèñîììóëàìèãëàâíûìèâõîæäåíèåìâèäàêðàòíîñòüþèçîìîðôíûìèâàëåíòíûìèòîæäåñòâîìïîçèöèîííîé ïîäôîðìóëîéñëîæíîñòüþ ðàíãîìðàâíûìèýêâè-18Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìDj , j = 1, . . . , ki äåðåâî ãëóáèíû qj ñ êîðíåì vj , êîòîðîåñîîòâåòñòâóåò ôîðìóëå Fj .•xjD1...Dki•<v1 <<<<• vki<1 << ki< ϕ• iva)b)Ðèñ. 2.1: ïðåäñòàâëåíèå ôîðìóëû äåðåâîìÇàìåòèì, ÷òî ôîðìóëà F ïî ñîïîñòàâëåííîìó åé äåðåâóD âîññòàíàâëèâàåòñÿ îäíîçíà÷íî ñ òî÷íîñòüþ äî èçîìîðôèçìà, è ÷òî ïðè ýòîì ïîääåðåâüÿ äåðåâà D âçàèìíîîäíîçíà÷íîñîïîñòàâëÿþòñÿ ïîçèöèîííûì ïîäôîðìóëàì ôîðìóëû F.

Íàðèñ. 2.2a ïîêàçàíî äåðåâî, ñîîòâåòñòâóþùåå ôîðìóëå((x1 ∨ x2 ) ∨ x3 ) ∨ (x3 (x1 ∨ x2 ) ∨ x1 x2 ) ,(2.3)êîòîðàÿ ÿâëÿåòñÿ ôîðìóëîé ãëóáèíû 4 íàä áàçèñîì Á0 è{0,2,3}ðåàëèçóåò ÔÀË s3.Äëÿ óäîáñòâà áóäåì ñ÷èòàòü, ÷òî â UΦÁ âõîäÿò íå òîëüêîîòäåëüíûå ôîðìóëû, íî è óïîðÿäî÷åííûå ñèñòåìû (íàáîðû)ôîðìóë íàä áàçèñîì Á, ÷òî êàæäàÿ òàêàÿ ñèñòåìà ðåàëèçóåòíàáîð, ñîñòîÿùèé èç ÔÀË, ðåàëèçóåìûõ åå ôîðìóëàìè, è÷òî ýòîé ñèñòåìå ôîðìóë ñîîòâåòñòâóåò ñèñòåìà èç äåðåâüåâ,ñîïîñòàâëåííûõ åå ôîðìóëàì.Çàìåòèì, ÷òî ðàíã R (F) ôîðìóëû F ðàâåí ÷èñëó ëèñòüåâñâÿçàííîãî ñ íåé äåðåâà D, åå ñëîæíîñòü L(F) ðàâíà ÷èñëóîñòàëüíûõ âåðøèí D, à åå ãëóáèíà D (F) ãëóáèíå åãî êîðíÿ. Çàìåòèì òàêæå, ÷òî ïîðÿäîê âõîæäåíèÿ ÁÏ â çàïèñüŸ2.x41x2x1x2••44•44 44 44x43 1 4 2 x41x21 4 2 x3••44•••4•444 ∨44 ∨ 444 441 4 21 4 21 4 2•44•44oo•44o∨ 44& 44 ooo o &1 41 4 oo 2•4oo•wo¬ 444ooo ∨o4o1 4 oo 2•wo•419Ôîðìóëû, èõ îïòèìèçàöèÿ ïî ãëóáèíå∨xO41x2•4OO oo•4441 2 o44ooOoOOO1 2o 4 O 44344oo 1 4•44 2 OO4•'44 ox•woo•o444o∨∨44& 44oo4 444 2 4•wo1ooo1 4• 22 4444 1 & 1 ∨••44∨ 444 ¬2 4 1•a)z1 ∨b)Ðèñ.

2.2: ïðåäñòàâëåíèå ôîðìóëû (2.3) äåðåâîì èêâàçèäåðåâîìôîðìóëû F ïðè åå ïðîñìîòðå ñëåâà íàïðàâî ñîîòâåòñòâóåò ïîñëåäîâàòåëüíîñòè ïîÿâëåíèÿ ÁÏ íà ëèñòüÿõ ñâÿçàííîãî ñ íåé äåðåâà,ïðîñìàòðèâàåìûõ â ¾åñòåñòâåííîì¿ ïîðÿäêå(ñì. Ÿ1).Ðàññìîòðèì òåïåðü íåêîòîðûå ñîîòíîøåíèÿ ìåæäó ïàðàìåòðàìè ôîðìóë íàä áàçèñîì Á0 . Çàìåòèì, ÷òî ïðåäñòàâëÿÿôîðìóëû äåðåâüÿìè, òàêèå ñîîòíîøåíèÿ ìîæíî äîêàçûâàòüáîëåå ïðîñòûì è íàãëÿäíûì ñïîñîáîì.Ëåììà 2.1.âåíñòâàÄëÿ ôîðìóëû F,F ∈ UΦ, âûïîëíÿþòñÿ íåðà-R (F) = L&,∨ (F) + 1 6 L (F) + 1 6 2D(F) ,(2.4)ãäå L&,∨ (F) ÷èñëî ÔÑ & è ∨ â ôîðìóëå F.Äîêàçàòåëüñòâî.

Ñðàâíèâàÿ ÷èñëî ðåáåð, âõîäÿùèõ â âåð-øèíû äåðåâà (ôîðìóëû) F ñ ÷èñëîì ðåáåð, âûõîäÿùèõ èçåãî âåðøèí, ïîëó÷èì|E (F)| = 2L&,∨ (F) + L¬ (F) = L (F) + R (F) − 1,20Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìãäå L¬ (F) ÷èñëî ÔÑ ¬ â ôîðìóëå F, îòêóäà ñëåäóåò, ÷òîR (F) = L&,∨ (F) + 1.Âòîðîå èç ñîîòíîøåíèé (2.4) ëåãêî óñòàíàâëèâàåòñÿ èíäóêöèåé ïî D (F).Ëåììà äîêàçàíà.Ñëåäñòâèå.D (F) > dlog (L (F) + 1)e .(2.5)Äëÿ òîãî ÷òîáû âûäåëèòü íàáîð x = (xi1 , . .

. , xin ), êîòîðûé ñîñòîèò èç âñåõ ðàçëè÷íûõ ÁÏ àëôàâèòà X, âñòðå÷àþùèõñÿ â ôîðìóëå F è ïåðå÷èñëåííûõ â ïîðÿäêå âîçðàñòàíèÿ èõ íîìåðîâ, áóäåì çàïèñûâàòü åå â âèäå F = F (x). Ïðèýòîì ôîðìóëó, êîòîðàÿ ïîëó÷àåòñÿ èç F â ðåçóëüòàòå çàìåíûêàæäîãî âõîæäåíèÿ ÁÏ xij , j = 1, . . . , n, ôîðìóëîé Fj áóäåìñ÷èòàòüFjxij , j = 1, . . . , nF è áóäåì îáîçíà÷àòü åå ÷åðåçF (F1 , . . .

, Fn ). Çàìåòèì, ÷òî ôîðìóëà F (F1 , . . . , Fn ) ðåàëèçóåò ÔÀË f (f1 , . . . , fn ), ãäå ÔÀË f (ÔÀË fj ) ÔÀË, ðåàëèçóåìàÿ ôîðìóëîé F (ñîîòâåòñòâåííî Fj , j = 1, . . . , n). Îòñþäà ñëåäóåò, ÷òî åñëè óêàçàííóþ ïîäñòàíîâêó ïðèìåíèòüê îáåèì ÷àñòÿì òîæäåñòâà t : F0 = F00 , ãäå F0 = F0 (x) èF00 = F00 (x), ìû ïîëó÷èì òîæäåñòâîðåçóëüòàòîì ïîäñòàíîâêè ôîðìóëû âìåñòî ÁÏ, â ôîðìóëób0 = Fb 00 ,bt: Fb 0 = F0 (F1 , .

. . , Fn ) è Fb 00 = F00 (F1 , . . . , Fn ), êîòîðîå íàãäå Fçûâàåòñÿt.Èç îïðåäåëåíèé ñëåäóåò, ÷òî äëÿ ôîðìóë èìååò ìåñòî òàêíàçûâàåìûé ïðèíöèï ýêâèâàëåíòíîé çàìåíû. Ýòî îçíà÷àåò,b 0 (âèäà Fb 00 ) ôîð÷òî åñëè ïîçèöèîííóþ ïîäôîðìóëó âèäà Fìóëû F çàìåíèòü, ó÷èòûâàÿ òîæäåñòâî bt, ýêâèâàëåíòíîé åéïîäñòàíîâêîé äëÿ òîæäåñòâàŸ2.Ôîðìóëû, èõ îïòèìèçàöèÿ ïî ãëóáèíå21b 00 (ñîîòâåòñòâåííî Fb 0 ), òî ïîëó÷åííàÿ â ðåçóëüòàôîðìóëîé Fòå òàêîé çàìåíû ôîðìóëà F̌ áóäåò ýêâèâàëåíòíà ôîðìóëå F.Óêàçàííûé ïåðåõîä îò ôîðìóëû F ê ôîðìóëå F̌ íàçûâàåòñÿ(îäíîêðàòíûì)F íà îñíîâå òîæäåñòâà t, à ïîñëåäîâàòåëüíîñòü îäíîêðàòíûõ ÝÏ ôîðìóëû F, âûïîëíÿåìûõ íà îñíîâå òîæäåñòâèç ñèñòåìû τ , ñ÷èòàåòñÿ å¼ (ìíîãîêðàòíûì) ÝÏ íà îñíîâåýòîé ñèñòåìû.Ôîðìóëû èç UΦ , ïîëó÷àþùèåñÿ äðóã èç äðóãà ýêâèâàKëåíòíûìè ïðåîáðàçîâàíèÿìè íà îñíîâå òîæäåñòâ tK& è t∨ ,AA. Ëåãêîà òàêæå òîæäåñòâ t& è t∨ , íàçûâàþòñÿâèäåòü, ÷òî ïîäîáíûå ôîðìóëû ïîëó÷àþòñÿ äðóã èç äðóãàïåðåñòàíîâêîé àðãóìåíòîâ è èçìåíåíèåì ïîðÿäêà âûïîëíåíèÿ îäíîòèïíûõ äâóìåñòíûõ áàçèñíûõ îïåðàöèé, îáðàçóþùèõ ñîîòâåòñòâóþùóþ ìíîãîìåñòíóþ îïåðàöèþ, è ïîýòîìóìîãóò îòëè÷àòüñÿ äðóã îò äðóãà òîëüêî ãëóáèíîé.Çàìåòèì, ÷òî ñëîæíîñòü õàðàêòåðèçóåò âðåìÿ âû÷èñëåíèÿ ôîðìóëû íà îäíîì ïðîöåññîðå, à ãëóáèíà âðåìÿ åå ïàðàëëåëüíîãî âû÷èñëåíèÿ íà íåîãðàíè÷åííîì ÷èñëå ïðîöåññîðîâ.