OK-metodichka-2010-part1 (1132792), страница 5
Текст из файла (страница 5)
Ïðè ýòîìêàæäàÿ òî÷êà ãðàíè NK ïîêðûâàåòñÿ õîòÿ áû îäíîé îòëè÷íîé îò NK ìàêñèìàëüíîé ãðàíüþ ÔÀË f . Ñëåäîâàòåëüíî,âñå îòëè÷íûå îò NK ìàêñèìàëüíûå ãðàíè ÔÀË f îáðàçóþò ïîêðûòèå ìíîæåñòâà Nf , èç êîòîðîãî ìîæíî âûäåëèòüòóïèêîâîå ïîäïîêðûòèå, ñîîòâåòñòâóþùåå òóïèêîâîé ÄÍÔÔÀË f , íå ñîäåðæàùåé ÝÊ K .Ëåììà äîêàçàíà.Èñõîäÿ èç ¾ãåîìåòðè÷åñêèõ¿ ñîîáðàæåíèé ìîæíî íàõîäèòü âñå èëè íåêîòîðûå òóïèêîâûå ÄÍÔ äëÿ ÔÀË îò íåáîëüøîãî ÷èñëà ÁÏ. Òàê, íàïðèìåð, ñîêðàùåííàÿ ÄÍÔ (3.3)äëÿ ÔÀË ¾ãîëîñîâàíèÿ¿ H (x1 , x2 , x3 ) ÿâëÿåòñÿ åäèíñòâåííîé òóïèêîâîé ÄÍÔ ýòîé ÔÀË, ÔÀË g (x1 , x2 , x3 ) (ñì.
ðèñ.2.1a è (2.10)) èìååò ïÿòü òóïèêîâûõ ÄÍÔ A1 = K1 ∨ K3 ∨ K5 ,A3 = K1 ∨ K2 ∨K4 ∨ K5 ,A2 = K2 ∨ K4 ∨ K6 ,A4 = K2 ∨ K3 ∨ K5 ∨ K6 ,A5 = K3 ∨ K4 ∨ K6 ∨ K1 ,(4.1)(4.2)4.Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ33à ó ÔÀË g 0 (x1 , x2 , x3 , x4 ) (ñì. ðèñ. 3.1-3.2 è (3.1)) èìåþòñÿäâå òóïèêîâûå ÄÍÔ A01 = K10 ∨ K30 ∨ K40 ∨ K50 ,A02 = K20 ∨ K30 ∨ K40 ∨ K50 . (4.3)Ïðè ýòîì ÄÍÔ A1 , A2 â (4.1) è ÄÍÔ A01 , A02 â (4.3) ÿâëÿþòñÿ ìèíèìàëüíûìè è, îäíîâðåìåííî, êðàò÷àéøèìè ÄÍÔÔÀË g è ÔÀË g 0 ñîîòâåòñòâåííî.Ïðè ïîñòðîåíèè òóïèêîâûõ ÄÍÔ ÔÀË f íàðÿäó ñ ÄÍÔïåðåñå÷åíèå òóïèêîâûõ ïîëåçíî çíàòü ÄÍÔ(ÄÍÔ ΣT ) ÔÀË f , òî åñòü äèçúþíêöèþ âñåõ òåõ ðàçëè÷íûõ ïðîñòûõ èìïëèêàíò ýòîé ÔÀË, êîòîðûå âõîäÿò âõîòÿ áû â îäíó òóïèêîâóþ ÄÍÔ ÔÀË f .
Çàìåòèì, ÷òî ÄÍÔ∩T ÔÀË f â îáùåì ñëó÷àå íå ðåàëèçóåò ñàìó ÔÀË f , à âíåêîòîðûõ ñëó÷àÿõ è, â ÷àñòíîñòè, â ñëó÷àå ÔÀË g (ñì. âûøå), ìîæåò áûòü ïóñòîé.  òî æå âðåìÿ ÄÍÔ ΣT ÔÀË fâñåãäà ðåàëèçóåò ýòó ÔÀË, ñîäåðæèòñÿ â åå ñîêðàùåííîé èìîæåò ñ íåé ñîâïàäàòü, êàê ýòî èìååò ìåñòî â ñëó÷àå ÔÀËg èëè â ñëó÷àå ÔÀË ¾ãîëîñîâàíèÿ¿.Áóäåì íàçûâàòü ÔÀË, åñëè âñå åå ìàêñèìàëüíûå ãðàíè ÿâëÿþòñÿ ÿäðîâûìè. Èç ëåììû 4.1 ñëåäóåò, ÷òîñîêðàùåííàÿ ÄÍÔ ÿäðîâîé ÔÀË ÿâëÿåòñÿ åå åäèíñòâåííîéòóïèêîâîé ÄÍÔ. Ïðèìåðîì ÿäðîâîé ÔÀË ÿâëÿåòñÿ ÔÀËãîëîñîâàíèÿ (3.3) (ñì. òàêæå 6).Äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà, ïîëó÷àþùàÿñÿ èçñîêðàùåííîé ÄÍÔ ÔÀË f óäàëåíèåì òåõ ÝÊ K , äëÿ êîòîðûõ ãðàíü NK ïîêðûâàåòñÿ ÿäðîì ÔÀË f , íî íå âõîäèò âíåãî, íàçûâàåòñÿýòîé ÔÀË.
Èç îïðåäåëåíèéñëåäóåò, ÷òî ÄÍÔ Êâàéíà ÔÀË f âêëþ÷àåò â ñåáÿ ÄÍÔ ΣTýòîé ÔÀË è ñîäåðæèòñÿ â åå ñîêðàùåííîé ÄÍÔ. Çàìåòèì,÷òî äëÿ ÔÀË g 00 (x1 , x2 , x3 ), ïîêàçàííîé íà ðèñ. 4.1, åå ñîêðàùåííàÿ ÄÍÔ èìååò âèä g 00 = x2 x3 ∨ x1 x2 ∨ x1 x3 , òî åñòüîòëè÷àåòñÿ îò ÄÍÔ Êâàéíà, êîòîðàÿ ÿâëÿåòñÿ åäèíñòâåííîéòóïèêîâîé ÄÍÔ ýòîé ÔÀË è èìååò âèä g 00 = x2 x3 ∨ x1 x3 . Âñóììà òóïèêî-âûõÿäðîâîéÄÍÔ Êâàéíà34Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû(111)`@@`c`@c`@@@@`@`c@`c@ x2x3x@1@I`@6(000)Ðèñ.
4.1: ¾ãåîìåòðèÿ¿ ñîêðàùåííîé ÄÍÔ ÔÀË g 00òî æå âðåìÿ äëÿ ÔÀË g 0 , ïîêàçàííîé íà ðèñ. 3.1, ÄÍÔ Êâàéíà ñîâïàäàåò ñ ñîêðàùåííîé ÄÍÔ ýòîé ÔÀË è îòëè÷àåòñÿîò åå ÄÍÔ ΣT , êîòîðàÿ (ñì. âûøå) ðàâíàK10 ∨ K20 ∨ K30 ∨ K40 ∨ K50 .Äëÿ ÔÀË f (x1 , . . . , xn ) è íàáîðà α, α ∈ Nf , îáîçíà÷èì÷åðåç Πα (f ) ìíîæåñòâî âñåõ ïðîõîäÿùèõ ÷åðåç α ìàêñèìàëüíûõ ãðàíåé ÔÀË f , êîòîðîå ìû áóäåì íàçûâàòüfα. Òî÷êó α, α ∈ Nf , áóäåì íàçûâàòüf , åñëè íàéäåòñÿ òî÷êà β, β ∈ Nf ,äëÿ êîòîðîé èìååò ìåñòî ñòðîãîå âêëþ÷åíèå Πβ (f ) ⊂ Πα (f ).Óêàçàííîå âêëþ÷åíèå îçíà÷àåò, ÷òî ëþáàÿ ìàêñèìàëüíàÿãðàíü ÔÀË f , ïðîõîäÿùàÿ ÷åðåç òî÷êó β , ïðîõîäèò è ÷åðåçòî÷êó α, ïðè÷åì åñòü òàêàÿ ìàêñèìàëüíàÿ ãðàíü ÔÀË f , êîòîðàÿ ïðîõîäèò ÷åðåç òî÷êó α, íî íå ïðîõîäèò ÷åðåç òî÷êóβ .
Ëåãêî âèäåòü, ÷òî äëÿ ëþáîé ðåãóëÿðíîé òî÷êè α ÔÀËf âñåãäà íàéäåòñÿ òàêàÿ íåðåãóëÿðíàÿ òî÷êà β, β ∈ Nf , äëÿêîòîðîé Πβ (f ) ⊂ Πα (f ).Èç îïðåäåëåíèé ñëåäóåò, ÷òî ëþáàÿ íåÿäðîâàÿ òî÷êà ÿäðîâîé ãðàíè ðåãóëÿðíà, è ïîýòîìó òî÷êè αi , i ∈ [1, 7], ÔÀËg 0 , ïîêàçàííîé íà ðèñ. 3.1, ÿâëÿþòñÿ åå ðåãóëÿðíûìè òî÷êà-ÔÀË ÷åðåç òî÷êóãóëÿðíîé òî÷êîé ÔÀËïó÷êîìðå-4.Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ35ìè. Êðîìå òîãî, â ñèëó âêëþ÷åíèÿ Πβ0 (g 0 ) ⊂ Πα0 (g 0 ), òî÷êàα0 òîæå ÿâëÿåòñÿ ðåãóëÿðíîé òî÷êîé ýòîé ÔÀË.Ãðàíü NK ÔÀË f íàçûâàåòñÿýòîéÔÀË, åñëè âñå òî÷êè NK ðåãóëÿðíû.
Çàìåòèì, ÷òî ãðàíü,êîòîðàÿ íå âõîäèò â ÿäðî, íî ïîêðûâàåòñÿ èì, ÿâëÿåòñÿ ðåãóëÿðíîé. Çàìåòèì òàêæå, ÷òî äëÿ ÔÀË g 0 , ïîêàçàííîé íàðèñ. 3.1, ãðàíè N60 è N70 , êîòîðûå íå âõîäÿò â ÄÍÔ ΣT , ÿâëÿþòñÿ ðåãóëÿðíûìè, òàê êàê ñîñòîÿò èç ðåãóëÿðíûõ òî÷åê.ðåãóëÿðíîé ãðàíüþÏðîñòàÿ èìïëèêàíòà KÔÀË f âõîäèò â ÄÍÔ òîãäà è òîëüêî òîãäà, êîãäàãðàíü NK íå ÿâëÿåòñÿ ðåãóëÿðíîé ãðàíüþ ýòîé ÔÀË.Äîêàçàòåëüñòâî. Ïóñòü α1, . . .
, αs âñå ðåãóëÿðíûå òî÷êèÒåîðåìà 4.1(ñð. [27, 6, 22, 10]).ΣTÔÀË f . Òîãäà äëÿ êàæäîãî j, j = 1, . . . , s, â ñèëó ðåãóëÿðíîñòè òî÷êè αj , íàéäåòñÿ íåðåãóëÿðíàÿ òî÷êà βj ÔÀË f ,îáëàäàþùàÿ òåì ñâîéñòâîì, ÷òî ëþáàÿ ìàêñèìàëüíàÿ ãðàíüÔÀË f , ïðîõîäÿùàÿ ÷åðåç òî÷êó βj , ïðîõîäèò è ÷åðåç òî÷êó αj .
Ñëåäîâàòåëüíî, ëþáàÿ ñèñòåìà ìàêñèìàëüíûõ ãðàíåé ÔÀË f , ïîêðûâàþùàÿ òî÷êè β1 , . . . , βs , ¾àâòîìàòè÷åñêè¿ ïîêðîåò âñå òî÷êè α1 , . . . , αs . Òàêèì îáðàçîì, ãðàíüNK , ñîñòîÿùàÿ èç ðåãóëÿðíûõ òî÷åê, íå ìîæåò âõîäèòü âòóïèêîâîå ïîêðûòèå ìíîæåñòâà Nf ìàêñèìàëüíûìè ãðàíÿìè, è ïîýòîìó ÝÊ K íå ìîæåò âõîäèòü â ÄÍÔ ΣT ÔÀË f .Ïóñòü òåïåðü NK íåðåãóëÿðíàÿ ãðàíü ÔÀË f , êîòîðàÿ ñîäåðæèò íåðåãóëÿðíóþ òî÷êó α, è ïóñòü Nf \ NK == {β1 , . . . , βq }. Èç íåðåãóëÿðíîñòè òî÷êè α ñëåäóåò, ÷òî äëÿëþáîãî j, j = 1, . .
. , q , ïó÷îê Πβj (f ) íå ìîæåò áûòü ñòðîãî âëîæåí â ïó÷îê Πα (f ). Êðîìå òîãî, ðàâåíñòâî Πβj (f ) == Πα (f ) òîæå íåâîçìîæíî, òàê êàê NK ∈ Πα (f ) \ Πβj (f ),è ïîýòîìó â Πβj (f ) íàéäåòñÿ ãðàíü NKj , êîòîðàÿ ïðîõîäèò÷åðåç òî÷êó βj , íî íå ïðîõîäèò ÷åðåç òî÷êó α. Ñëåäîâàòåëüíî, èç ïîêðûòèÿ ìíîæåñòâà Nf ìàêñèìàëüíûìè ãðàíÿìèNK , NK1 , . . . , NKq íåëüçÿ óäàëèòü ãðàíü NK , òàê êàê òîëüêî îíà ïîêðûâàåò â íåì òî÷êó α. Òàêèì îáðàçîì, ëþáîå òó-36Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûïèêîâîå ïîêðûòèå ìíîæåñòâà Nf , ÿâëÿþùååñÿ ïîäïîêðûòèåì óêàçàííîãî ïîêðûòèÿ, áóäåò ñîîòâåòñòâîâàòü òóïèêîâîéÄÍÔ, ñîäåðæàùåé ÝÊ K .Òåîðåìà äîêàçàíà.Êîñíåìñÿ, äàëåå, âîïðîñà î ëîêàëüíîì õàðàêòåðå ðàññìîòðåííûõ âûøå êðèòåðèåâ âõîæäåíèÿ ïðîñòûõ èìïëèêàíòÔÀË f â åå ÄÍÔ ∩T è ÄÍÔ ΣT (ñì.
[27, 21, 22, 16]). Äëÿêàæäîé ìàêñèìàëüíîé ãðàíè N ÔÀË f (x1 , . . . , xn ) ïîëîæèìS0 (N, f ) = {N}, à çàòåì èíäóêöèåé ïî r, r = 1, 2, . . ., îïðåäåëèì ìíîæåñòâî Sr (N, f ) êàê ìíîæåñòâî âñåõ òåõ ìàêñèìàëüíûõ ãðàíåé ÔÀË f , êîòîðûå èìåþò íåïóñòîå ïåðåñå÷åíèåõîòÿ áû ñ îäíîé ãðàíüþ èç Sr−1 (N, f ). Ïðè ýòîì ìíîæåñòâîSr (N, f ) áóäåì íàçûâàòürNf.Äîêàæåì, ÷òî âîïðîñ î âõîæäåíèè ïðîñòîé èìïëèêàíòû K ÔÀË f â ÄÍÔ ∩T (ÄÍÔ ΣT ) ýòîé ÔÀË ìîæíî ðåøèòü, ðàññìàòðèâàÿ îêðåñòíîñòü S1 (NK , f ) (ñîîòâåòñòâåííîS2 (NK , f )). Äåéñòâèòåëüíî, ãðàíü NK ÿâëÿåòñÿ ÿäðîâîé ãðàíüþ ÔÀË f òîãäà è òîëüêî òîãäà, êîãäà îíà íå ïîêðûâàåòñÿâñåìè îñòàëüíûìè ìàêñèìàëüíûìè ãðàíÿìè ýòîé ÔÀË. Ïîñêîëüêó ãðàíè, íå âõîäÿùèå â S1 (NK , f ), íå èìåþò îáùèõòî÷åê ñ NK , ãðàíü NK ÿâëÿåòñÿ ÿäðîâîé òîãäà è òîëüêî òîãäà, êîãäà îíà íå ïîêðûâàåòñÿ âñåìè îñòàëüíûìè ãðàíÿìèèç S1 (NK , f ).
Èç òåîðåìû 4.1 ñëåäóåò, ÷òî ÝÊ K íå âõîäèò â ÄÍÔ ΣT ÔÀË f òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîé òî÷êè α èç NK íàéäåòñÿ òî÷êà β , β ∈ Nf , äëÿ êîòîðîéΠβ (f ) ⊂ Πα (f ). Çàìåòèì, ÷òî âñå ãðàíè ïó÷êà Πα (f ) âõîäÿòâ S1 (NK , f ), à âñå ãðàíè ïó÷êà Πβ (f ), åñëè Πα (f )∩Πβ (f ) 6=∅, â S2 (NK , f ). Ñëåäîâàòåëüíî, ïðîâåðêó ãðàíè NK íà ðåãóëÿðíîñòü ìîæíî îñóùåñòâèòü íà îñíîâå àíàëèçà åå îêðåñòíîñòè ïîðÿäêà 2. Ëåãêî ïîêàçàòü, ÷òî ðàññìîòðåíèå îêðåñòíîñòè ïîðÿäêà 2 äîñòàòî÷íî äëÿ ïðîâåðêè ãðàíè NK íà ååâõîæäåíèå â ÄÍÔ Êâàéíà ÔÀË f .
Åñëè æå âñå ÿäðîâûå ãðà-ôóíêöèèîêðåñòíîñòüþ ïîðÿäêà ãðàíè5.37Ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔíè ÔÀË f âûäåëåíû è ¾ïîìå÷åíû¿ (äëÿ ýòîãî, êàê óæå ãîâîðèëîñü, äîñòàòî÷íî ðàññìîòðåòü èõ îêðåñòíîñòè ïîðÿäêà1), òî íåâõîæäåíèå ÝÊ K â ÄÍÔ Êâàéíà ÔÀË f ðàâíîñèëüíî ïîêðûòèþ ãðàíè NK îòëè÷íûìè îò íåå ¾ïîìå÷åííûìè¿ãðàíÿìè èç îêðåñòíîñòè S1 (NK , f ).5Îñîáåííîñòè ÄÍÔ ëèíåéíûõ è ìîíîòîííûõôóíêöèé. Ôóíêöèÿ ïîêðûòèÿ, òàáëèöà Êâàéíà è ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔëèíåéíî çàâèñèò îòëèíåéíîé ÁÏÁóäåì ãîâîðèòü, ÷òî ÔÀË f (x1 , .
. . , xn )xi , èëè, èíà÷å, ÷òî ÁÏ xi ÿâëÿåòñÿÔÀËf , åñëè f (α) 6= f (β) äëÿ ëþáûõ ñîñåäíèõ ïî ÁÏ xi íàáîðîâα è β êóáà B n . Ïðè ýòîì äëÿ ÔÀË f èìååò ìåñòî ðàâåíñòâîÁÏf (x1 , . . . , xn ) = xi ⊕ f (x1 , . . . , xi−1 , 0, xi+1 , . . . , xn ) ,êîòîðîå ðàâíîñèëüíî ëèíåéíîñòè ÁÏ xi ÔÀË f , à çíà÷èòÔÀË ÿâëÿåòñÿ ëèíåéíîé òîãäà è òîëüêî òîãäà, êîãäà îíàëèíåéíî çàâèñèò îò âñåõ ñâîèõ ñóùåñòâåííûõ ÁÏ.Çàìåòèì, ÷òî åñëè ÔÀË f ëèíåéíî çàâèñèò îò ÁÏ xi , òîâ ëþáóþ èìïëèêàíòó ýòîé ÔÀË âõîäèò îäíà èç áóêâ xi , xi .Ðàññìîòðèì äàëåå êëàññ ìîíîòîííûõ ÔÀË è íåêîòîðûåñâÿçàííûå ñ íèì äðóãèå êëàññû ôóíêöèé.
Íàïîìíèì, ÷òîÔÀË f (x1 , . . . , xn ) íàçûâàåòñÿ, åñëè f (α) 6 f (β)näëÿ ëþáûõ íàáîðîâ α è β êóáà B òàêèõ, ÷òî α 6 β . Áóäåìãîâîðèòü, ÷òî ÔÀË f (x1 , . . . , xn )xi , èëè, èíà÷å, ÁÏ xi ÿâëÿåòñÿÁÏ ÔÀËf , åñëè íåðàâåíñòâî f (α) 6 f (β) âûïîëíÿåòñÿ äëÿ ëþáûõñîñåäíèõ ïî ÁÏ xi íàáîðîâ α è β êóáà B n òàêèõ, ÷òî α 6 β .Ëåãêî âèäåòü, ÷òî ìîíîòîííàÿ ÔÀË ìîíîòîííî çàâèñèò îòâñåõ ñâîèõ ÁÏ è îáðàòíî.Äîêàæåì, ÷òî åñëè ÔÀË f (x1 , . . . , xn ) ìîíîòîííî çàâèñèò îò ÁÏ xi , òî íè îäíà èç åå ïðîñòûõ èìïëèêàíò íå ìîæåò ñîäåðæàòü áóêâó xi . Äåéñòâèòåëüíî, ïóñòü èìïëèêàíòàÁÏìîíîòîííîéìîíîòîííî çàâèñèò îòìîíîòîííîé38Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûK 0 ÔÀË f ñîäåðæèò áóêâó xi è, ñëåäîâàòåëüíî, äëÿ ãðàíèNK 0 = Γγ 0 , ãäå γ 0 ∈ ([0, 2])n è γ 0 hii = 0, èìååò ìåñòî âêëþ÷åíèå NK 0 ⊆ Nf . Òîãäà, â ñèëó ìîíîòîííîé çàâèñèìîñòè ÔÀËf îò ÁÏ xi , èìåþò ìåñòî âêëþ÷åíèÿNK 00 = Γγ 00 ⊆ Nfè NK = Γγ = NK 0 ∪ NK 00 ⊆ Nf ,ãäå íàáîð γ 00 (íàáîð γ ) ïîëó÷àåòñÿ èç íàáîðà γ 0 çàìåíîé 0 â iîì ðàçðÿäå íà 1 (ñîîòâåòñòâåííî 2).
Ïîñëåäíåå èç ýòèõ âêëþ÷åíèé îçíà÷àåò, ÷òî ÝÊ íå ÿâëÿåòñÿ ïðîñòîé èìïëèêàíòîéÔÀË f , òî åñòü ïðîñòàÿ èìïëèêàíòà ìîíîòîííîé ïî ÁÏ xiÔÀË íå ìîæåò ñîäåðæàòü áóêâû xi . Îòñþäà ñëåäóåò, ÷òî ëþáàÿ ïðîñòàÿ èìïëèêàíòà îòëè÷íîé îò 0 ìîíîòîííîé ÔÀË ÿâëÿåòñÿ ìîíîòîííîé ÝÊ, òî åñòü íå ñîäåðæèò îòðèöàíèé ÁÏ.×àñòíûì ñëó÷àåì ìîíîòîííîé çàâèñèìîñòè ÔÀË f îòÁÏ xi ÿâëÿåòñÿ() çàâèñèìîñòü f îò xi , êîãäà f = xi · g (ñîîòâåòñòâåííî f = xi ∨ g ),ãäå ÔÀË g ïîëó÷àåòñÿ èç f ïîäñòàíîâêîé êîíñòàíòû 1 (ñîîòâåòñòâåííî 0) âìåñòî ÁÏ xi . Ïðè ýòîì â ñëó÷àå êîíúþíêòèâíîé çàâèñèìîñòè áóêâà xi âõîäèò â ëþáóþ èìïëèêàíòóÔÀË f , à â ñëó÷àå äèçúþíêòèâíîé çàâèñèìîñòè áóêâà xiíå âõîäèò íè â îäíó ïðîñòóþ èìïëèêàíòó ÔÀË f îòëè÷íóþîò xi . Áóäåì ãîâîðèòü, ÷òî ÔÀË f (x1 , . . . , xn )(,) çàâèñèò îò ÁÏ xi , åñëèÔÀË f (x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
