Lectionc1 (1132950), страница 4
Текст из файла (страница 4)
Ïóñòüf (x1 ; : : : ; xn ) = K1 _ : : : _ Ks = A;f (x1 ; : : : ; xn ) = J1 Jt = B;(3.1)(3.2)ãäå K1 ; : : : ; Ks (J1 ; : : : ; Jt ) ðàçëè÷íûå ÝÊ (ñîîòâåòñòâåííîÝÄ) îò ÁÏ x1 ; : : : ; xn . Èç (2.1), (2.2) ñëåäóåò, ÷òî ïðåäñòàâëåíèÿ(3.1) è (3.2) ýêâèâàëåíòíû ñëåäóþùèì ïîêðûòèÿì ìíîæåñòâNf è N f ãðàíÿìè êóáà B nNf = NK1 [ : : : [ NKs ;N f = N J1 [ : : : [ N Jt :(3.3)(3.4)Òàê, ïðåäñòàâëåíèåg (x1 ; x2 ; x3 ) = K1 _ : : : _ K6 ;ãäå(3.5)N g = f(000) ; (111)g èK1 = x1 x3 ;K4 = x1 x3 ;K2 = x2 x3 ;K5 = x2 x3 ;K3 = x1 x2 ;K6 = x1 x2 ;ñîîòâåòñòâóåò ïîêðûòèþ Ng = N1 [ : : : [ N6 , ãäå Ni = NKi ïðèâñåõ i = 1; : : : ; 6 (ñì. ðèñ.
2.1a). Çàìåòèì, ÷òî ñîâåðøåííûåÄÍÔ è ÊÍÔ ÔÀË f èç (2.4) çàäàþò ïîêðûòèå ìíîæåñòâ Nfè N f ñîîòâåòñòâåííî ãðàíÿìè ðàçìåðíîñòè 0. Ïðèíèìàÿ âîâíèìàíèå óêàçàííóþ âûøå ãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ,ìû íå áóäåì â äàëüíåéøåì äåëàòü ñóùåñòâåííûõ ðàçëè÷èéìåæäó ÝÊ Ki è ñîîòâåòñòâóþùåé åé ãðàíüþ NKi , à òàêæåìåæäó ÄÍÔ âèäà (3.1) è ñîîòâåòñòâóþùèì åé ïîêðûòèåì (3.3).24Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÐàññìîòðèì òåïåðü íåêîòîðûå ñïåöèàëüíûå âèäû ÄÍÔ,èõ ¾ãåîìåòðè÷åñêóþ¿ èíòåðïðåòàöèþ è ñïîñîáû ïîñòðîåíèÿ.Áóäåì ãîâîðèòü, ÷òî ÔÀË f 0ÔÀË f 00 , èëè,000èíà÷å, ÔÀË fÔÀË f , åñëè Nf 0 Nf 00 , òî åñòü000èìïëèêàöèÿ (f ! f ) òîæäåñòâåííî ðàâíà 1. Ýëåìåíòàðíàÿêîíúþíêöèÿ, êîòîðàÿ èìïëèöèðóåò ÔÀË f , íàçûâàåòñÿýòîé ÔÀË. Çàìåòèì, ÷òî îòíîøåíèå èìïëèöèðóåìîñòè ÿâëÿåòñÿîòíîøåíèåì ÷àñòè÷íîãî ïîðÿäêà è ÷òî f 0 èìïëèöèðóåò f 00òîãäà è òîëüêî òîãäà, êîãäà f 00 = f 0 _ f 00 èëè f 0 = f 0 f 00 . Îòñþäà ñëåäóåò, â ÷àñòíîñòè, ÷òî ÝÊ K 0 èìïëèöèðóåòÝÊ K 00 òîãäà è òîëüêî òîãäà, êîãäà ìíîæåñòâî áóêâ K 00ñîäåðæèòñÿ âî ìíîæåñòâå áóêâ K 0 , òî åñòü K 0 = K 00 K äëÿíåêîòîðîé ÝÊ K , íå èìåþùåé îáùèõ áóêâ ñ ÝÊ K 00 .
Ýòîîçíà÷àåò, ÷òî â äàííîì ñëó÷àå ÝÊ K 0 ìîæåò áûòü ¾óñòðàíåíà¿èç ÄÍÔ K 00 _ K 0 ñ ïîìîùüþ òîæäåñòâà ïîãëîùåíèÿ (2.3) (ñì.2).Äèçúþíêòèâíóþ íîðìàëüíóþ ôîðìó A âèäà (3.1) áóäåìíàçûâàòü, åñëè ñîîòâåòñòâóþùåå åé ïîêðûòèåÿâëÿåòñÿ íåïðèâîäèìûì (ñì. 1), òî åñòü íè îäíà èç ãðàíåéNK1 ; : : : ; NKs íå ñîäåðæèòñÿ íè â îäíîé èç äðóãèõ ãðàíåéïîêðûòèÿ (3.3). Íà ¾ÿçûêå èìïëèöèðóåìîñòè¿ ýòî îçíà÷àåò,÷òî íè îäíà èç ÝÊ Ki ; i 2 [1; s], íå ÿâëÿåòñÿ èìïëèêàíòîéÝÊ Kj , ãäå j 2 [1; s] è i 6= j . Çàìåòèì, ÷òî ñ ïîìîùüþòîæäåñòâà ïîãëîùåíèÿ (2.3) (ñì. 2) èç ëþáîé ÄÍÔ A ìîæíîb.ïîëó÷èòü íåïðèâîäèìóþ ÄÍÔ AÈìïëèêàíòà K ÔÀË f íàçûâàåòñÿýòîé ÔÀË, åñëè îíà íå ïîãëîùàåòñÿ íèêàêîé äðóãîé îòëè÷íîéîò íåå èìïëèêàíòîé ÔÀË f .
Èç îïðåäåëåíèé è îòìå÷åííûõâûøå ôàêòîâ ñëåäóåò, ÷òî â ïðîñòóþ èìïëèêàíòó ÔÀË f íåâõîäÿò áóêâû íåñóùåñòâåííûõ ÁÏ ýòîé ÔÀË è ÷òî èç ëþáîéèìïëèêàíòû ÔÀË f ìîæíî ïîëó÷èòü åå ïðîñòóþ èìïëèêàíòóóäàëåíèåì íåêîòîðûõ áóêâ. Ïîñëåäíåå îçíà÷àåò, ÷òî ëþáàÿèìïëèêàíòà ÔÀË f èìïëèöèðóåò íåêîòîðóþ ïðîñòóþ èìïëèêàíòóf.ïîãëîùàåòèìïëèöèðóåòèìïëèêàíòîéíåïðèâîäèìîéïðîñòîé èìïëèêàíòîé3.Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿ25Äèçúþíêöèÿ âñåõ ïðîñòûõ èìïëèêàíò ÔÀË f íàçûâàåòñÿååÄÍÔ. Çàìåòèì, ÷òî ñîêðàùåííàÿ ÄÍÔ ÔÀËf ÿâëÿåòñÿ íåïðèâîäèìîé ÄÍÔ è ÷òî åé ñîîòâåòñòâóåò ïîêðûòèåìíîæåñòâà Nf âñåìè ìàêñèìàëüíûìè ïî âêëþ÷åíèþ ãðàíÿìèìíîæåñòâà Nf ýòîé ÔÀË, êîòîðûå ìû áóäåì íàçûâàòü ïðîñòîÔÀË f . Óêàçàííîå ñîîòâåòñòâèåïîçâîëÿåò ñòðîèòü ñîêðàùåííóþ ÄÍÔ íà îñíîâå ¾ãåîìåòðè÷åñêèõ¿ñîîáðàæåíèé.
Òàê, â ñîîòâåòñòâèè ñ ðèñ. 2.1 ïðàâàÿ ÷àñòü(3.5) ÿâëÿåòñÿ ñîêðàùåííîé ÄÍÔ ÔÀË g , à èç ðèñ. 3.1aâûòåêàåò, ÷òî ñîêðàùåííàÿ ÄÍÔ ÔÀË g 0 (x1 ; x2 ; x3 ; x4 ), äëÿêîòîðîé eg0 = (1111 1011 1101 1010), èìååò âèäñîêðàùåííîéìàêñèìàëüíûìè ãðàíÿìèg0 = K10 _ : : : _ K70 ;(3.6)ãäå K10 = x3 x4 , K20 = x2 x3 , K30 = x2 x4 , K40 = x1 x3 , K50 == x2 x4 , K60 = x1 x4 , K70 = x1 x2 , ïðè÷åì ÝÊ Ki0 ; i = 1; : : : ; 7,ñîîòâåòñòâóåò ãðàíè Ni0 = NKi0 íà ðèñ.
3.1a. Íà ðèñ. 3.1bïðèâåäåíà äëÿ íàãëÿäíîñòè ¾ðàçâåðòêà¿ ìíîæåñòâà Ng0 èñîñòàâëÿþùèõ åãî ìàêñèìàëüíûõ ãðàíåé óêàçàííîé ÔÀË g 0 .Ëåãêî âèäåòü, ÷òî ñîêðàùåííàÿ ÄÍÔ ÝÊ èëè ÝÄ ñîâïàäàåòñ íåé ñàìîé.×òîáû ñäåëàòü ïîñòðîåíèå ñîêðàùåííîé ÄÍÔ äëÿ ÔÀËf; f 2 P2 (n), áîëåå íàãëÿäíûì, ÷àñòî èñïîëüçóþò åå ïðåäñòàâëåíèåâ âèäå, òî åñòü â âèäå òàáëèöû 2;2 (f ), â êîòîðîéíàáîðû (10) è (11) ïåðåñòàâëåíû, à ïðîòèâîïîëîæíûå ñòîðîíûîòîæäåñòâëåíû ïî òèïó ¾òîðà¿. Çàìåòèì, ÷òî ëþáîå ðåáðîêóáà B 4 ñîîòâåòñòâóåò äâóì ñîñåäíèì êëåòêàì óêàçàííîéòàáëèöû, à ëþáîé êâàäðàò â B 4 ëèáî êâàäðàòó, ñîñòàâëåííîìóèç ÷åòûðåõ ñîñåäíèõ êëåòîê òàáëèöû, ëèáî åå ñòðîêå èëèñòîëáöó. Íà ðèñ. 3.2 ïðèâåäåíà êàðòà Êàðíî ÔÀË g 0 (x1 ; x2 ; x3 ; x4 )è óêàçàíû âñå ìàêñèìàëüíûå ãðàíè ýòîé ÔÀË.êàðòû ÊàðíîÏóñòü A0 è A00 ñîêðàùåííûå ÄÍÔ ÔÀË f 0è f 00 ñîîòâåòñòâåííî, à íåïðèâîäèìàÿ ÄÍÔ A ïîëó÷àåòñÿèç ôîðìóëû A0A00 â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ.
Òîãäà A ñîêðàùåííàÿ ÄÍÔ ÔÀË f = f 0 f 00.Òåîðåìà 3.1.26Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû1 @@@4053 N3 @@N50 @@ @@@@0N4@ @@@0@6N0@70@1 @N2 2 @N6@@ @@ 7@@0N1@@@@@ @5 @@ 3@40@@@ x2 x3 x4 x@1I@@61e``c`c``c`c`c`c``c`c`c``c`c`ce0a)3 = (1011)N303 = (0001)`2 = (1001)0 = (1000)1 = (1100)``N20``N10`N700 = e0N605 = (0100)N505 = (1110)````7 = (0011)N404 = (0010)`4 = (0111)6 = (0110)`b)Ðèñ.
3.1: ¾ãåîìåòðèÿ¿ ñîêðàùåííîé ÄÍÔ ÔÀËg03.Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿÐèñ. 3.2: êàðòà Êàðíî ÔÀËg02728Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÄîêàçàòåëüñòâî. Äîñòàòî÷íî äîêàçàòü, ÷òî â A âõîäèò ëþáàÿïðîñòàÿ èìïëèêàíòà ÔÀË f . Ïóñòü ÝÊ K ÿâëÿåòñÿ ïðîñòîéèìïëèêàíòîé ÔÀË f è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ èìïëèêàíòîéêàê ÔÀË f 0 , òàê è ÔÀË f 00 . Èç ñâîéñòâ ñîêðàùåííûõ ÄÍÔâûòåêàåò, ÷òî â A0 è A00 íàéäóòñÿ ÝÊ K 0 è K 00 ñîîòâåòñòâåííî,êîòîðûå èìïëèöèðóþòñÿ ÝÊ K .
Òàêèì îáðàçîì, â ÄÍÔ Ae , êîòîðàÿ ïîëó÷èòñÿâîéäåò èìïëèöèðóåìàÿ ÔÀË K 0 K 00 ÝÊ Kâ ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ âôîðìóëå A0 A00 . Çàìåòèì, ÷òî ïðè ýòîì ÝÊ K èìïëèöèðóåòe . ÏîñêîëüêóÔÀË K 0 K 00 è, ñëåäîâàòåëüíî, èìïëèöèðóåò ÝÊ KeÝÊ K ÿâëÿåòñÿ èìïëèêàíòîé ÔÀË f è, îäíîâðåìåííî, èìïëèöèðóåòñÿe = K , òàê êàê K ïðîñòàÿ èìïëèêàíòà ÔÀË f .ÝÊ K , òî KÒåîðåìà äîêàçàíà.Åñëè íåïðèâîäèìàÿ ÄÍÔ A ïîëó÷àåòñÿ èç ÊÍÔB ÔÀË f â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ, òî A ñîêðàùåííàÿ ÄÍÔ ÔÀË f .Ñëåäñòâèå.Ïðèìåíÿÿ ñëåäñòâèå èç òåîðåìû 3.1 ê ÔÀË g 0 , ïîêàçàííîéíà ðèñ. 3.1-3.2, ïîëó÷èì (ñðàâíèòå ñ (3.6))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ïóòåì ôîðìèðîâàíèÿ â íåé ñ ïîìîùüþ òîæäåñòâ àññîöèàòèâíîñòè3.Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿ29è êîììóòàòèâíîñòè ïîäôîðìóë âèäà xi K 0 _xi K 00 , ïðèìåíåíèÿê ýòèì ïîäôîðìóëàì òîæäåñòâà îáîáùåííîãî ñêëåèâàíèÿxi K 0 _ xi K 00 = xi K 0 _ xi K 00 _ K 0 K 00(3.7)ðàñøèðåíèåìñòðîãèìè ïîñëåäóþùåãî ïðèâåäåíèÿ ïîäîáíûõ, íàçûâàåòñÿÄÍÔ A.
Ðàñøèðåíèå A0 ÄÍÔ A ñ÷èòàåòñÿ, åñëè A0ñîäåðæèò ÝÊ, íå ÿâëÿþùóþñÿ èìïëèêàíòîé íè îäíîé ÝÊèç A. Çàìåòèì, ÷òî ñîêðàùåííàÿ ÄÍÔ íå èìååò ñòðîãèõðàñøèðåíèé è ÷òî â ðåçóëüòàòå ïîñòðîåíèÿ ïîñëåäîâàòåëüíûõñòðîãèõ ðàñøèðåíèé è ïðèâåäåíèÿ ïîäîáíûõ èç ëþáîé ÄÍÔìîæíî ïîëó÷èòü íåïðèâîäèìóþ ÄÍÔ, êîòîðàÿ íå èìååò ñòðîãèõðàñøèðåíèé.Íåïðèâîäèìàÿ ÄÍÔ ÿâëÿåòñÿ ñîêðàùåííîéÄÍÔ òîãäà è òîëüêî òîãäà, êîãäà îíà íå èìååò ñòðîãèõðàñøèðåíèé.Äîêàçàòåëüñòâî. Äîñòàòî÷íî óáåäèòüñÿ â òîì, ÷òî íåïðèâîäèìàÿÒåîðåìà 3.2.ÄÍÔ A, íå èìåþùàÿ ñòðîãèõ ðàñøèðåíèé, ñîäåðæèò âñåïðîñòûå èìïëèêàíòû ðåàëèçóåìîé åþ ÔÀË f . Ïóñòü X (n) =fx1; : : : ; xng ìíîæåñòâî ÁÏ ÄÍÔ A, à K ïðîñòàÿ èìïëèêàíòàf , êîòîðàÿ íå âõîäèò â A.
Ðàññìîòðèì ìíîæåñòâî K, ñîñòîÿùååèç âñåõ òåõ ýëåìåíòàðíûõ êîíúþíêöèé îò ÁÏ X (n), êîòîðûåÿâëÿþòñÿ èìïëèêàíòàìè f , íî íå ÿâëÿþòñÿ èìïëèêàíòàìèíè îäíîé ÝÊ èç A. Çàìåòèì, ÷òî ìíîæåñòâî K íå ïóñòî,òàê êàê ñîäåðæèò ÝÊ K â ñèëó åå ñâîéñòâ, è ÷òî K íåìîæåò ñîäåðæàòü ÝÊ ðàíãà n, ïîñêîëüêó ëþáàÿ ÝÊ âèäàx1 1 xnn , ãäå = (1 ; : : : ; n ) 2 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 30Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûK 00 ) èç A, ãäå ÝÊ K 0 è K 00 ñîñòîÿò èç áóêâ ÝÊ k. Ñëåäîâàòåëüíî,e ðàâíîé K 0 K 00 , à ÝÊÝÊ k ÿâëÿåòñÿ èìïëèêàíòîé ÝÊ KeK , â ñâîþ î÷åðåäü, ÿâëÿåòñÿ èìïëèêàíòîé íåêîòîðîé ÝÊèç A.
Äåéñòâèòåëüíî, ÄÍÔ A íå èìååò ñòðîãèõ ðàñøèðåíèée,è ïîýòîìó ñîäåðæèò ÝÊ, êîòîðàÿ èìïëèöèðóåòñÿ ÝÊ K000ïîëó÷àþùåéñÿ èç ïîäôîðìóëû xi K _xi K â ðåçóëüòàòå ýêâèâàëåíòíîãîïðåîáðàçîâàíèÿ (3.7). Òàêèì îáðàçîì, ÝÊ 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.8)4Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
