Lectionc1 (1132950), страница 6
Текст из файла (страница 6)
Ëåãêî ïîêàçàòü, ÷òî ðàññìîòðåíèå îêðåñòíîñòè ïîðÿäêà2 äîñòàòî÷íî äëÿ ïðîâåðêè ãðàíè NK íà åå âõîæäåíèå âÄÍÔ Êâàéíà ÔÀË f . Åñëè æå âñå ÿäðîâûå ãðàíè ÔÀË fâûäåëåíû è ¾ïîìå÷åíû¿ (äëÿ ýòîãî, êàê óæå ãîâîðèëîñü,äîñòàòî÷íî ðàññìîòðåòü èõ îêðåñòíîñòè ïîðÿäêà 1), òî íåâõîæäåíèåÝÊ K â ÄÍÔ Êâàéíà ÔÀË f ðàâíîñèëüíî ïîêðûòèþ ãðàíèNK îòëè÷íûìè îò íåå ¾ïîìå÷åííûìè¿ ãðàíÿìè èç îêðåñòíîñòèS1 (NK ; f ).5.537Îñîáåííîñòè ÄÍÔÎñîáåííîñòè ÄÍÔ äëÿ ôóíêöèéèç íåêîòîðûõ êëàññîâ.Òåîðåìà Þ.
È. Æóðàâëåâàî ÄÍÔ ñóììà ìèíèìàëüíûõÐàññìîòðèì îñîáåííîñòè ¾ïîâåäåíèÿ¿ è ñâÿçàííûå ñ íèìèîñîáåííîñòè ÄÍÔ äëÿ ôóíêöèé èç íåêîòîðûõ êëàññîâ. Íàïîìíèì,÷òî ÔÀË âèäàf (x1 ; : : : ; xn ) = 1 x1 n xn 0èçP2 (n),ãäå0 ; : : : ; n áóëåâû êîíñòàíòû, íàçûâàåòñÿëèíåéíîé ÔÀË è çàìåòèì, ÷òî ñóùåñòâåííûìè ÁÏ ýòîé ÔÀËÿâëÿþòñÿ òå è òîëüêî òå ÁÏ xi èç ìíîæåñòâà X (n), äëÿêîòîðûõ ¾êîýôôèöèåíò¿ i ðàâåí 1. Çàìåòèì òàêæå, ÷òîÔÀË `n = x1 xn è `n = x1 xn 1 ÿâëÿþòñÿåäèíñòâåííûìè ñóùåñòâåííûìè ëèíåéíûìè ÔÀË â P2 (n).Áóäåì ãîâîðèòü, ÷òî ÔÀË f (x1 ; : : : ; xn )xi , èëè, èíà÷å, ÷òî ÁÏ xi ÿâëÿåòñÿÔÀËf , åñëè f () 6= f ( ) äëÿ ëþáûõ ñîñåäíèõ ïî ÁÏ xi íàáîðîâ è êóáà B n . Ïðè ýòîì ðàçëîæåíèå ÔÀË f ïî ÁÏ xi (ñì.(2.5)) ïåðåõîäèò â ðàâåíñòâîÁÏëèíåéíî çàâèñèò îòëèíåéíîé ÁÏf (x1 ; : : : ; xn ) = xi f (x1 ; : : : ; xi 1 ; 0; xi+1 ; : : : ; xn ) ; (5.1)êîòîðîå ðàâíîñèëüíî ëèíåéíîñòè ÁÏ xi ÔÀË f , à çíà÷èòÔÀË ÿâëÿåòñÿ ëèíåéíîé òîãäà è òîëüêî òîãäà, êîãäà îíàëèíåéíî çàâèñèò îò âñåõ ñâîèõ ñóùåñòâåííûõ ÁÏ.
Íà ñàìîìäåëå äëÿ ëèíåéíîñòè ÔÀË f äîñòàòî÷íî, ÷òîáû îíà ëèíåéíîçàâèñåëà îò âñåõ ñâîèõ ñóùåñòâåííûõ ÁÏ, êðîìå îäíîé. Ýòîëåãêî äîêàçàòü èíäóêöèåé ïî ÷èñëó ñóùåñòâåííûõ ÁÏ ÔÀËf , èñïîëüçóÿ òîò ôàêò, ÷òî âñå ÔÀË èç P2 (1) ÿâëÿþòñÿëèíåéíûìè, â êà÷åñòâå áàçèñà èíäóêöèè è ïðèìåíÿÿ ðàâåíñòâî(5.1) äëÿ îáîñíîâàíèÿ èíäóêòèâíîãî ïåðåõîäà.Çàìåòèì, ÷òî åñëè âî ìíîæåñòâå Nf ÔÀË f (x1 ; : : : ; xn )íåò ñîñåäíèõ ïî íåêîòîðîé ÁÏ xi íàáîðîâ, òî â êàæäóþ38Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûèìïëèêàíòó K ÔÀË f îáÿçàòåëüíî âõîäèò îäíà èç áóêâÁÏ xi . Äåéñòâèòåëüíî, åñëè K íå ñîäåðæèò áóêâ ÁÏ xi , òîäëÿ ëþáîãî íàáîðà èç NK è ñîñåäíåãî ñ íèì ïî ÁÏ xiíàáîðà áóäóò âûïîëíÿòüñÿ ðàâåíñòâà K () = K ( ) = 1.Ñëåäîâàòåëüíî, f () = f ( ) = 1, òàê êàê K èìïëèêàíòàf , à ýòî ïðîòèâîðå÷èò ñâîéñòâàì ìíîæåñòâà Nf .
Óêàçàííîåñâîéñòâî âûïîëíÿåòñÿ, â ÷àñòíîñòè, åñëè ÔÀË f ëèíåéíîçàâèñèò îò ÁÏ xi , òàê êàê ïðè ýòîì f () 6= f ( ) äëÿ ëþáûõñîñåäíèõ ïî ÁÏ xi íàáîðîâ è .Çàìåòèì, äàëåå, ÷òî åñëè âî ìíîæåñòâå Nf ÔÀË f (x1 ; : : : ; xn )âîîáùå íåò ñîñåäíèõ íàáîðîâ, òî îíà èìååò åäèíñòâåííóþÄÍÔ îò ÁÏ X (n) ñâîþ ñîâåðøåííóþ ÄÍÔ. Äåéñòâèòåëüíî,ðàíã ëþáîé èìïëèêàíòû K ÔÀË f â ýòîì ñëó÷àå ðàâåí n,à ñîîòâåòñòâóþùàÿ åé ãðàíü NK ñîñòîèò èç îäíîãî íàáîðàêóáà B n .
Ñëåäîâàòåëüíî, ëþáàÿ ÄÍÔ A ÔÀË f âêëþ÷àåò âñåáÿ jNf j ÝÊ ðàíãà n, òî åñòü ÿâëÿåòñÿ åå ñîâåðøåííîé ÄÍÔ.Î÷åâèäíî, ÷òî åñëè âî ìíîæåñòâå Nf åñòü ñîñåäíèå íàáîðû,òî ñîâåðøåííàÿ ÄÍÔ ÔÀË f óæå íå áóäåò åäèíñòâåííîéÄÍÔ ýòîé ÔÀË. Òàêèì îáðàçîì, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.Ñîâåðøåííàÿ ÄÍÔ ÔÀË f èç P2 (n) ÿâëÿåòñÿåå åäèíñòâåííîé ÄÍÔ îò ÁÏ X (n) òîãäà è òîëüêî òîãäà,êîãäà âî ìíîæåñòâå Nf íåò ñîñåäíèõ íàáîðîâ.Ñëåäñòâèå. Ñîâåðøåííàÿ ÄÍÔ ëèíåéíîé ñóùåñòâåííîé ÔÀËÿâëÿåòñÿ åäèíñòâåííîé ÄÍÔ ýòîé ÔÀË îò åå ñóùåñòâåííûõÁÏ.Ëåììà 5.1.Ðàññìîòðèì òåïåðü êëàññ ìîíîòîííûõ ÔÀË è íåêîòîðûåñâÿçàííûå ñ íèì äðóãèå êëàññû ôóíêöèé. Íàïîìíèì, ÷òîÔÀË f (x1 ; : : : ; xn ) íàçûâàåòñÿ, åñëè f () 6 f ( )näëÿ ëþáûõ íàáîðîâ è êóáà B òàêèõ, ÷òî 6 .
Áóäåìãîâîðèòü, ÷òî ÔÀË f (x1 ; : : : ; xn )xi , èëè, èíà÷å, ÁÏ xi ÿâëÿåòñÿÁÏ ÔÀËf , åñëè íåðàâåíñòâî f () 6 f ( ) âûïîëíÿåòñÿ äëÿ ëþáûõñîñåäíèõ ïî ÁÏ xi íàáîðîâ è êóáà B n òàêèõ, ÷òî 6 .ÁÏìîíîòîííîéìîíîòîííî çàâèñèò îòìîíîòîííîé5.39Îñîáåííîñòè ÄÍÔËåãêî âèäåòü, ÷òî ìîíîòîííàÿ ÔÀË ìîíîòîííî çàâèñèò îòâñåõ ñâîèõ ÁÏ è îáðàòíî.Äîêàæåì, ÷òî åñëè ÔÀË f (x1 ; : : : ; xn ) ìîíîòîííî çàâèñèòîò ÁÏ xi , òî íè îäíà èç åå ïðîñòûõ èìïëèêàíò íå ìîæåòñîäåðæàòü áóêâó xi . Äåéñòâèòåëüíî, ïóñòü èìïëèêàíòà K 0ÔÀË f ñîäåðæèò áóêâó xi è, ñëåäîâàòåëüíî, äëÿ ãðàíè NK 0 =0n0 0 , ãäå 2 ([0; 2]) è 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 ; : : : ; xi 1 ; xi ; xi+1 ; : : : ; xn )çàâèñèò îò xi ìîíîòîííî (ñîîòâåòñòâåííî êîíúþíêòèâíî, äèçúþíêòèâíî).Î÷åâèäíî, ÷òî âñå îñîáåííîñòè ÄÍÔ, õàðàêòåðíûå äëÿ ÔÀËñ òîé èëè èíîé ìîíîòîííîé çàâèñèìîñòüþ îò ÁÏ ðàñïðîñòðàíÿþòñÿíà ÔÀË ñ àíàëîãè÷íîé èíìîíîòîííîé çàâèñèìîñòüþ ïîñëåèíâåðòèðîâàíèÿ ñîîòâåòñòâóþùèõ ÁÏ.êîíúþíêòèâíàÿ äèçúþíêòèâíàÿèíìîíîòîííî èíêîíúþíêòèâíî èíäèçúþíêòèâíî40Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÑîïîñòàâèì êàæäîìó íàáîðó èç B n , ìîíîòîííóþ ÝÊK+ îò ÁÏ X (n), ñîñòîÿùóþ èç òåõ è òîëüêî òåõ áóêâ xj ,j 2 [1; n], äëÿ êîòîðûõ hj i = 1, è çàìåòèì, ÷òî êàæäàÿìîíîòîííàÿ ÝÊ îò ÁÏ X (n) ìîæåò áûòü ïðåäñòàâëåíà âóêàçàííîì âèäå.
Ëåãêî âèäåòü òàêæå, ÷òî ãðàíü, ñîîòâåòñòâóþùàÿÝÊ K+ , ãäå = (1 ; : : : ; n ) 2 B n , èìååò âèä , ãäå =(2 1 ; : : : ; 2 n ). Íàáîð , 2 B n , íàçûâàåòñÿìîíîòîííîé ÔÀË f , f 2 P2 (n), åñëè 2 Nf èf ( ) = 0 äëÿ ëþáîãî îòëè÷íîãî îò íàáîðà òàêîãî, ÷òî 6 . Ìíîæåñòâî âñåõ íèæíèõ åäèíèö ìîíîòîííîé ÔÀË fáóäåì îáîçíà÷àòü ÷åðåç Nf+ . ñèëó ââåäåííûõ îïðåäåëåíèé, K+ () = 1 òîãäà è òîëüêîòîãäà, êîãäà > , îòêóäà ñëåäóåò, ÷òî íàáîð ÿâëÿåòñÿåäèíñòâåííîé íèæíåé åäèíèöåé ÝÊ K+ è ÷òî ÝÊ K+0 èìïëèöèðóåòÝÊ K+00 òîãäà è òîëüêî òîãäà, êîãäà 0 > 00 . Îòñþäà âûòåêàåòòàêæå, ÷òî ÝÊ K+ ÿâëÿåòñÿ ïðîñòîé èìïëèêàíòîé ìîíîòîííîéÔÀË f òîãäà è òîëüêî òîãäà, êîãäà 2 Nf+ , è ÷òî íàáîð ÿâëÿåòñÿ ïðè ýòîì ÿäðîâîé òî÷êîé ÔÀË f .
Òàêèì îáðàçîì,äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.íèæíåéåäèíèöåéÑîêðàùåííàÿ ÄÍÔ A ìîíîòîííîé ÔÀË f , f 2 P2 (n),ÿâëÿåòñÿ åäèíñòâåííîé òóïèêîâîé ÄÍÔ ýòîé ÔÀË è èìååòâèä:_Ëåììà 5.2.A (x1 ; : : : ; xn ) = 2Nf+K+ (x1 ; : : : ; xn ) :Ïðè ýòîì âñå íàáîðû èç Nf+ ÿâëÿþòñÿ ÿäðîâûìè òî÷êàìèÔÀË f .Ñëåäñòâèå. Ìîíîòîííàÿ ÔÀË ÿâëÿåòñÿ ÿäðîâîé ÔÀË.Ôóíêöèÿ f (x1 ; : : : ; xn ) íàçûâàåòñÿ öåïíîé (öèêëè÷åñêîé )ôóíêöèåé äëèíû t, åñëè åå ñîêðàùåííàÿ ÄÍÔ ñ ¾ãåîìåòðè÷åñêîé¿òî÷êè çðåíèÿ ïðåäñòàâëÿåò ñîáîé öåïü (ñîîòâåòñòâåííî öèêë)èç t ïîñëåäîâàòåëüíî ñîåäèíåííûõ ðåáåð N1 ; N2 ; : : : ; Nt êóáà5.1N12N2``t+1``Nt`a)Ðèñ.
5.1: ìíîæåñòâîBn41Îñîáåííîñòè ÄÍÔ3N11Ntt2N2````3Nt 1`b)Nfäëÿ öåïíîé è öèêëè÷åñêîé ÔÀËf(ñì. ðèñ. 5.1a è 5.1b). Çàìåòèì, ÷òî öèêëè÷åñêàÿ ÔÀËäëèíû t ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäà t > 6 ÷åòíîå ÷èñëî, à öåïíàÿ ÔÀË äëèíû t ïðè ëþáîì t > 1.Ïðèìåð öåïíîé ÔÀË äëèíû 3 äàåò ÔÀË g 00 , ïîêàçàííàÿ íàðèñ. 4.1, à ÔÀË g (ñì. ðèñ. 2.1a) ÿâëÿåòñÿ öèêëè÷åñêîé ÔÀËäëèíû 6.Èç òåîðåìû 4.1 ñëåäóåò, â ÷àñòíîñòè, ÷òî äëÿ ëþáîé öåïíîéÔÀË äëèíû íå ìåíüøå 4 è ëþáîé öèêëè÷åñêîé ÔÀË ÄÍÔT ñîâïàäàåò ñ ñîêðàùåííîé ÄÍÔ. Ïðè ýòîì öåïíàÿ ÔÀËf íå÷åòíîé äëèíû t = 2k 1 > 3 èìååò åäèíñòâåííóþ ìèíèìàëüíóþ ÄÍÔ, êîòîðàÿ ñîâïàäàåò ñ åå ÄÍÔ M è ñîîòâåòñòâóåòïîêðûòèþ (ñì. ðèñ. 5.1a) N1 [N3 [: : :[Nt äëèíû k .
Äåéñòâèòåëüíî,ìíîæåñòâî Nf â äàííîì ñëó÷àå ñîñòîèò èç 2k íàáîðîâ è íåìîæåò áûòü ïîêðûòî (k 1) ðåáðîì. Êðîìå òîãî, ïîêðûòèåìíîæåñòâà Nf , ñîñòîÿùåå èç k ðåáåð, íå ìîæåò âêëþ÷àòü âñåáÿ ðåáðà ñ îáùèìè âåðøèíàìè è äîëæíî ñîäåðæàòü ÿäðîâûåðåáðà N1 è Nt ÔÀË f . Ëåãêî âèäåòü, ÷òî òîëüêî ïîêðûòèåN1 [ N3 [ : : : [ Nt îáëàäàåò âñåìè ýòèìè ñâîéñòâàìè. Òàêèìîáðàçîì, äëÿ öåïíîé ÔÀË íå÷åòíîé äëèíû t, t > 5, ÄÍÔT íå ñîâïàäàåò ñ ÄÍÔ M .42Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûNn 1n 1n = e1`Nn`n+1`2N12n 2N2n 2``12n 1```e0Ðèñ.
5.2: öåïíàÿ ÔÀË äëèíû(2n 2) â êóáå B nÏðè ëþáîì n 2 N; n > 3, âP2 (n) ñóùåñòâóþò ÔÀË f 0 è f 00 , èìåþùèå îáùóþ ïðîñòóþèìïëèêàíòó K , êîòîðàÿ âõîäèò â ÄÍÔ M îäíîé, íî íåâõîäèò â ÄÍÔ M äðóãîé èç ýòèõ ÔÀË è äëÿ êîòîðîéSn 3 (NK ; f 0 ) = Sn 3 (NK ; f 00 ).Òåîðåìà 5.1 (ñð. [6, 22, 10]).Äîêàçàòåëüñòâî. Äîñòàòî÷íî ïîñòðîèòü â P2 (n) öåïíóþ ôóíêöèþ÷åòíîé äëèíû t = 2k > 2n 2 > 4. Äåéñòâèòåëüíî, åñëèóêàçàííàÿ ÔÀË f íàéäåíà, à åå ìíîæåñòâî Nf ñîîòâåòñòâóåòðèñ.
5.1a, òî, ïîëàãàÿfNf 0 = Nf n f1 gèNf 00 = Nf n ft+1 g ;ïîëó÷èì öåïíûå ÔÀË f 0 è f 00 íå÷åòíîé äëèíû 2k 1 òàêèå,÷òî êàæäîå ðåáðî Ni ; ãäå i = 2; : : : ; t 1, âõîäèò â ÄÍÔ Mîäíîé èç íèõ, íî íå âõîäèò â ÄÍÔ M äðóãîé. Ïðè ýòîì,6.Ôóíêöèÿ ïîêðûòèÿ. Ãðàäèåíòíîå ïîêðûòèå43î÷åâèäíî, Sk 2 (Nk ; f 0 ) = Sk 2 (Nk ; f 00 ) è, ñëåäîâàòåëüíî, èñêîìàÿÝÊ K ñîîòâåòñòâóåò ðåáðó Nk .Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà âîçüìåì â êà÷åñòâå föåïíóþ ÔÀË äëèíû 2n 2, ó êîòîðîé ìíîæåñòâî Nf ñîñòîèòèç âñåõ íàáîðîâ i = (1; : : : ; 1; 0; : : : ; 0), ãäå i 2 [1; n], è íàáîðîâ| {z } | {z }in in+i = i , i 2 [1; n), à ðåáðî ñ íîìåðîì j; j 2 [1; 2n 2],èìååò âèä Nj = fj ; j +1 g (ñì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
