OK-metodichka-2010-part1 (1132792), страница 4
Текст из файла (страница 4)
Íà ðèñ. 3.1bïðèâåäåíà äëÿ íàãëÿäíîñòè ¾ðàçâåðòêà¿ ìíîæåñòâà Ng0 èñîñòàâëÿþùèõ åãî ìàêñèìàëüíûõ ãðàíåé óêàçàííîé ÔÀË g 0 .Ëåãêî âèäåòü, ÷òî ñîêðàùåííàÿ ÄÍÔ ÝÊ èëè ÝÄ ñîâïàäàåòñ íåé ñàìîé.×òîáû ñäåëàòü ïîñòðîåíèå ñîêðàùåííîé ÄÍÔ äëÿ ÔÀËf, f ∈ P2 (n), áîëåå íàãëÿäíûì, ÷àñòî èñïîëüçóþò åå ïðåäñòàâëåíèå â âèäå, òî åñòü â âèäå òàáëèöû Π2,2 (f ),â êîòîðîé íàáîðû (10) è (11) ïåðåñòàâëåíû, à ïðîòèâîïîëîæíûå ñòîðîíû îòîæäåñòâëåíû ïî òèïó ¾òîðà¿. Çàìåòèì, ÷òîëþáîå ðåáðî êóáà B 4 ñîîòâåòñòâóåò äâóì ñîñåäíèì êëåòêàìóêàçàííîé òàáëèöû, à ëþáîé êâàäðàò â B 4 ëèáî êâàäðàòó,ñîñòàâëåííîìó èç ÷åòûðåõ ñîñåäíèõ êëåòîê òàáëèöû, ëèáîåå ñòðîêå èëè ñòîëáöó.
Íà ðèñ. 3.2 ïðèâåäåíà êàðòà Êàðíî ÔÀË g 0 (x1 , x2 , x3 , x4 ) è óêàçàíû âñå ìàêñèìàëüíûå ãðàíèýòîé ÔÀË.êàðòû ÊàðíîÏóñòü A0 è A00 ñîêðàùåííûå ÄÍÔ ÔÀËè ñîîòâåòñòâåííî, à íåïðèâîäèìàÿ ÄÍÔ A ïîëó÷àåòñÿ èç ôîðìóëû A0 · A00 â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîêè ïðèâåäåíèÿ ïîäîáíûõ. Òîãäà A ñîêðàùåííàÿ ÄÍÔ ÔÀËf = f 0 · f 00 .Òåîðåìà 3.1.f0f 0026Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûe1` @@@@ β4β0β53 `c N@`3c`N50 `c @ @@@ @ N40@ @@@@0 α6N@α1`c `@@N70 @`c2 c` α2c``N60@α7@@@@@ @ N10 @@@ @@α@5@`c@`c`c @c`α4β0@ α3@@ x x2 3 x4 x@11@I 6@`c a)e0β` 3 = (1011)N30α3 ` = (0001)α2 = (1001) `N70N20β0 = (1000) `` α0 = e0N10α1 = (1100) `` α7 = (0011)N40` α4 = (0010) ` β4 = (0111)N60`α5 = (0100)N50`β5 = (1110)` α6 = (0110)b)Ðèñ.
3.1: ¾ãåîìåòðèÿ¿ ñîêðàùåííîé ÄÍÔ ÔÀË g 03.Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿÐèñ. 3.2: êàðòà Êàðíî ÔÀË g 02728Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÄîêàçàòåëüñòâî. Äîñòàòî÷íî äîêàçàòü, ÷òî â A âõîäèò ëþ-áàÿ ïðîñòàÿ èìïëèêàíòà ÔÀË f . Ïóñòü ÝÊ K ÿâëÿåòñÿ ïðîñòîé èìïëèêàíòîé ÔÀË f è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ èìïëèêàíòîé êàê ÔÀË f 0 , òàê è ÔÀË f 00 . Èç ñâîéñòâ ñîêðàùåííûõ ÄÍÔ âûòåêàåò, ÷òî â A0 è A00 íàéäóòñÿ ÝÊ K 0 è K 00ñîîòâåòñòâåííî, êîòîðûå èìïëèöèðóþòñÿ ÝÊ K .
Òàêèì îáe,ðàçîì, â ÄÍÔ A âîéäåò èìïëèöèðóåìàÿ ÔÀË K 0 · K 00 ÝÊ Kêîòîðàÿ ïîëó÷èòñÿ â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ â ôîðìóëå A0 · A00 . Çàìåòèì, ÷òî ïðè ýòîìÝÊ K èìïëèöèðóåò ÔÀË K 0 ·K 00 è, ñëåäîâàòåëüíî, èìïëèöèe .
Ïîñêîëüêó ÝÊ Ke ÿâëÿåòñÿ èìïëèêàíòîé ÔÀË fðóåò ÝÊ Ke = K , òàê êàêè, îäíîâðåìåííî, èìïëèöèðóåòñÿ ÝÊ K , òî KK ïðîñòàÿ èìïëèêàíòà ÔÀË f .Òåîðåìà äîêàçàíà.Åñëè íåïðèâîäèìàÿ ÄÍÔ A ïîëó÷àåòñÿ èç ÊÍÔÔÀË f â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ, òî A ñîêðàùåííàÿ ÄÍÔ ÔÀË f .Ñëåäñòâèå.BÏðèìåíÿÿ ñëåäñòâèå èç òåîðåìû 3.1 ê ÔÀË g 0 , ïîêàçàííîé íà ðèñ. 3.1-3.2, ïîëó÷èì (ñðàâíèòå ñ (3.1))D = (x1 ∨ x2 ∨ x4 )·(x1 ∨ x2 ∨ x3 ∨ x4 )·(x1 ∨ x2 ∨ x3 ∨ x4 ) == (x2 ∨ x4 ∨ x1 x3 ) · (x1 ∨ x2 ∨ x3 ∨ x4 ) == x3 x4 ∨ x1 x4 ∨ x1 x2 ∨ x2 x3 ∨ x2 x4 ∨ x1 x3 ∨ x2 x4 .Ñëåäóþùèé ìåòîä (ìåòîä Áëåéêà [6]) ïîçâîëÿåò ïîëó÷àòü ñîêðàùåííóþ ÄÍÔ ÔÀË f èç ïðîèçâîëüíîé ÄÍÔ ýòîéÔÀË ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé íà îñíîâåòîæäåñòâà îáîáùåííîãî ñêëåèâàíèÿ:x1 x2 ∨ x1 x3 = x1 x2 ∨ x1 x3 ∨ x2 x3 .Ëþáàÿ ÄÍÔ A0 , êîòîðóþ ìîæíî ïîëó÷èòü èç ÄÍÔ Aïóòåì ôîðìèðîâàíèÿ â íåé ñ ïîìîùüþ òîæäåñòâ àññîöèàòèâíîñòè è êîììóòàòèâíîñòè ïîäôîðìóë âèäà xi K 0 ∨ xi K 00 ,3.Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿ29ïðèìåíåíèÿ ê ýòèì ïîäôîðìóëàì òîæäåñòâà îáîáùåííîãîñêëåèâàíèÿxi K 0 ∨ xi K 00 = xi K 0 ∨ xi K 00 ∨ K 0 K 00(3.2)è ïîñëåäóþùåãî ïðèâåäåíèÿ ïîäîáíûõ, íàçûâàåòñÿ ðàñøèðåíèåì ÄÍÔ A.
Ðàñøèðåíèå A0 ÄÍÔ A ñ÷èòàåòñÿ ñòðîãèì, åñ-ëè A0 ñîäåðæèò ÝÊ, íå ÿâëÿþùóþñÿ èìïëèêàíòîé íè îäíîéÝÊ èç A. Çàìåòèì, ÷òî ñîêðàùåííàÿ ÄÍÔ íå èìååò ñòðîãèõðàñøèðåíèé è ÷òî â ðåçóëüòàòå ïîñòðîåíèÿ ïîñëåäîâàòåëüíûõ ñòðîãèõ ðàñøèðåíèé è ïðèâåäåíèÿ ïîäîáíûõ èç ëþáîéÄÍÔ ìîæíî ïîëó÷èòü íåïðèâîäèìóþ ÄÍÔ, êîòîðàÿ íå èìååò ñòðîãèõ ðàñøèðåíèé.Íåïðèâîäèìàÿ ÄÍÔ ÿâëÿåòñÿ ñîêðàùåííîéÄÍÔ òîãäà è òîëüêî òîãäà, êîãäà îíà íå èìååò ñòðîãèõðàñøèðåíèé.Äîêàçàòåëüñòâî.
Äîñòàòî÷íî óáåäèòüñÿ â òîì, ÷òî íåïðèÒåîðåìà 3.2.âîäèìàÿ ÄÍÔ A, íå èìåþùàÿ ñòðîãèõ ðàñøèðåíèé, ñîäåðæèò âñå ïðîñòûå èìïëèêàíòû ðåàëèçóåìîé åþ ÔÀË f . ÏóñòüX (n) = {x1 , . . . , xn } ìíîæåñòâî ÁÏ ÄÍÔ A, à K ïðîñòàÿ èìïëèêàíòà f , êîòîðàÿ íå âõîäèò â A. Ðàññìîòðèì ìíîæåñòâî K, ñîñòîÿùåå èç âñåõ òåõ ýëåìåíòàðíûõ êîíúþíêöèéîò ÁÏ X (n), êîòîðûå ÿâëÿþòñÿ èìïëèêàíòàìè f , íî íå ÿâëÿþòñÿ èìïëèêàíòàìè íè îäíîé ÝÊ èç A.
Çàìåòèì, ÷òî ìíîæåñòâî K íå ïóñòî, òàê êàê ñîäåðæèò ÝÊ K â ñèëó åå ñâîéñòâ,è ÷òî K íå ìîæåò ñîäåðæàòü ÝÊ ðàíãà n, ïîñêîëüêó ëþáàÿαn1ÝÊ âèäà xα1 · · · xn , ãäå α = (α1 , . . . , αn ) ∈ Nf , ÿâëÿåòñÿ èìïëèêàíòîé òîé ÝÊ èç A, êîòîðàÿ îáðàùàåòñÿ â 1 íà íàáîðå α.Ïóñòü, äàëåå, k ÝÊ ìàêñèìàëüíîãî ðàíãà â K, ïðè÷åì,êàê áûëî îòìå÷åíî, R (k) < n, è ïóñòü áóêâû íåêîòîðîé ÁÏxi , 1 6 i 6 n, íå âõîäÿò â k . Òîãäà, â ñèëó âûáîðà ÝÊ k èñâîéñòâ ÄÍÔ A, ÝÊ âèäà xi · k (âèäà xi · k ) äîëæíà áûòü èìïëèêàíòîé íåêîòîðîé ÝÊ âèäà xi ·K 0 (ñîîòâåòñòâåííî xi ·K 00 )30Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûèç A, ãäå ÝÊ K 0 è K 00 ñîñòîÿò èç áóêâ ÝÊ k . Ñëåäîâàòåëüe ðàâíîé K 0 · K 00 , à ÝÊíî, ÝÊ k ÿâëÿåòñÿ èìïëèêàíòîé ÝÊ KeK , â ñâîþ î÷åðåäü, ÿâëÿåòñÿ èìïëèêàíòîé íåêîòîðîé ÝÊ èçA.
Äåéñòâèòåëüíî, ÄÍÔ A íå èìååò ñòðîãèõ ðàñøèðåíèé èe , ïîïîýòîìó ñîäåðæèò ÝÊ, êîòîðàÿ èìïëèöèðóåòñÿ ÝÊ K000ëó÷àþùåéñÿ èç ïîäôîðìóëû xi K ∨ xi K â ðåçóëüòàòå ýêâèâàëåíòíîãî ïðåîáðàçîâàíèÿ (3.2). Òàêèì îáðàçîì, ÝÊ kÿâëÿåòñÿ èìïëèêàíòîé íåêîòîðîé ÝÊ èç A è íå ìîæåò âõîäèòü â K. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò, ÷òî ÝÊ Kâõîäèò â A.Òåîðåìà äîêàçàíà.Èç ëþáîé ÄÍÔ A ÔÀË f ìîæíî ïîëó÷èòü ñîêðàùåííóþ ÄÍÔ ýòîé ÔÀË â ðåçóëüòàòå ïîñòðîåíèÿ ïîñëåäîâàòåëüíûõ ñòðîãèõ ðàñøèðåíèé è ïðèâåäåíèÿ ïîäîáíûõ äî ïîëó÷åíèÿ íåïðèâîäèìîé ÄÍÔ, íå èìåþùåé ñòðîãèõðàñøèðåíèé.Ñëåäñòâèå.Âîçüìåì äëÿ ïðèìåðà â êà÷åñòâå ÄÍÔ A ñîâåðøåííóþÄÍÔ ÔÀË ãîëîñîâàíèÿ H (x1 , x2 , x3 ), êîòîðàÿ èìååò âèäA (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 .Ïðèìåíÿÿ ê A ìåòîä Áëåéêà, ïîëó÷èì:A = (x1 x2 x3 ∨ x1 x2 x3 ) ∨ x1 x2 x3 ∨ x1 x2 x3 == x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 = (x2 x3 ∨ x2 x1 x3 ) ∨ x1 x2 x3 == x2 x3 ∨ x1 x3 ∨ x1 x2 x3 = x2 x3 ∨ (x3 x1 ∨ x3 x1 x2 ) == x2 x3 ∨ x1 x3 ∨ x1 x2 .
(3.3)4.4Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ31Òóïèêîâûå ÄÍÔ, ÿäðî è ÄÍÔ ïåðåñå÷åíèåòóïèêîâûõ. ÄÍÔ Êâàéíà è ÄÍÔ ñóììà òóïèêîâûõ, êðèòåðèé âõîæäåíèÿ ïðîñòûõ èìïëèêàíò â òóïèêîâûå ÄÍÔ, åãî ëîêàëüíîñòüÁóäåì ãîâîðèòü, ÷òî ÄÍÔ A, ðåàëèçóþùàÿ ÔÀË f , ÿâëÿåòñÿÄÍÔ, åñëè f 6= A0 äëÿ ëþáîé ÄÍÔ A0 , ïîëó÷åííîé èç A â ðåçóëüòàòå óäàëåíèÿ íåêîòîðûõ áóêâ èëè öåëûõ ÝÊ. Èç îïðåäåëåíèÿ âûòåêàåò, ÷òî â òóïèêîâóþ ÄÍÔA ÔÀË f ìîãóò âõîäèòü òîëüêî ïðîñòûå èìïëèêàíòû ýòîéÔÀË, è ÷òî A ÿâëÿåòñÿ íåïðèâîäèìîé ÄÍÔ. Ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ òóïèêîâàÿ ÄÍÔ A ÔÀË f çàäàåò òóïèêîâîå (ñì. 1) ïîêðûòèå ìíîæåñòâà Nf ìàêñèìàëüíûìèãðàíÿìè ÔÀË f è îáðàòíî.Ïîñòðîåíèå âñåõ èëè íåêîòîðûõ òóïèêîâûõ ÄÍÔ äëÿ çàäàííîé ÔÀË f ÿâëÿåòñÿ, îáû÷íî, ïðîìåæóòî÷íûì ýòàïîìïðè ïîñòðîåíèè() ÄÍÔ ÔÀË f ,òî åñòü ÄÍÔ, êîòîðàÿ èìååò ìèíèìàëüíûé ðàíã (ñîîòâåòñòâåííî äëèíó) ñðåäè âñåõ ÄÍÔ, ðåàëèçóþùèõ f .
Ýòî ñâÿçàíî ñ òåì, ÷òî ìèíèìàëüíàÿ ÄÍÔ îáÿçàòåëüíî ÿâëÿåòñÿòóïèêîâîé, à ñðåäè êðàò÷àéøèõ ÄÍÔ âñåãäà åñòü òóïèêîâàÿ.Ïðè ïîñòðîåíèè òóïèêîâûõ ÄÍÔ ÔÀË f áûâàåò ïîëåçíîçíàòü ÄÍÔ(ÄÍÔ ∩T ) ÔÀË f , òîåñòü äèçúþíêöèþ âñåõ òåõ ðàçëè÷íûõ ïðîñòûõ èìïëèêàíòýòîé ÔÀË, êîòîðûå âõîäÿò â ëþáóþ òóïèêîâóþ ÄÍÔ ÔÀËf.Íàáîð α, α ∈ B n , íàçûâàåòñÿÔÀË f (x1 , . . . , xn ),åñëè α ∈ Nf è α âõîäèò òîëüêî â îäíó ìàêñèìàëüíóþ ãðàíüÔÀË f . Ïðè ýòîì ãðàíü NK , ÿâëÿþùàÿñÿ ìàêñèìàëüíîéãðàíüþ ÔÀË f è ñîäåðæàùàÿ òî÷êó α, ñ÷èòàåòñÿÔÀË f , à ñîâîêóïíîñòü âñåõ ðàçëè÷íûõ ÿäðîâûõ ãðàíåé ÔÀË f íàçûâàåòñÿÔÀË f .òóïèêîâîéìèíèìàëüíîé êðàò÷àéøåéïåðåñå÷åíèå òóïèêîâûõÿäðîâîé òî÷êîéãðàíüþÿäðîâîéÿäðîì32Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÄèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà ∩T ÔÀËf ñîñòîèò èç òåõ ïðîñòûõ èìïëèêàíò ÔÀË f , êîòîðûåñîîòâåòñòâóþò ÿäðîâûì ãðàíÿì ýòîé ÔÀË.Äîêàçàòåëüñòâî.
Ïóñòü òóïèêîâàÿ ÄÍÔ A ÔÀË f (x1, . . . , xn)Ëåììà 4.1.íå âêëþ÷àåò â ñåáÿ ïðîñòóþ èìïëèêàíòó K , êîòîðàÿ ñîîòâåòñòâóåò ÿäðîâîé ãðàíè NK ÔÀË f , ñîäåðæàùåé ÿäðîâóþòî÷êó α ýòîé ÔÀË. Ïîñêîëüêó âñå îòëè÷íûå îò K ïðîñòûåèìïëèêàíòû ÔÀË f îáðàùàþòñÿ â 0 íà íàáîðå α, òî ÄÍÔA òàêæå áóäåò ðàâíà 0 íà ýòîì íàáîðå è, ñëåäîâàòåëüíî,f (α) = 0. Ïîëó÷åííîå ïðîòèâîðå÷èå ñ òåì, ÷òî α ∈ Nf , äîêàçûâàåò íåîáõîäèìîñòü âêëþ÷åíèÿ ÝÊ K â ëþáóþ òóïèêîâóþ ÄÍÔ ÔÀË f .Ïóñòü òåïåðü ïðîñòàÿ èìïëèêàíòà K ÔÀË f ñîîòâåòñòâóåò ãðàíè NK , êîòîðàÿ íå âõîäèò â ÿäðî ÔÀË f .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
