Lectionc1 (1132950), страница 3
Текст из файла (страница 3)
2.1:`b)B 3 è B 4 , ïðèìåðû ãðàíåéòîãäà è òîëüêî òîãäà, êîãäà i 6 i ïðè âñåõ i 2 [1; n]. Ïðèýòîì ñ÷èòàåòñÿ, ÷òî < , åñëè 6 è 6= , à íàáîðû; èç B n , äëÿ êîòîðûõ 6 èëè 6 ( è ),íàçûâàþòñÿ(ñîîòâåòñòâåííî).ñðàâíèìûìèíåñðàâíèìûìèÄëÿ íàáîðà = (1 ; : : : ; n ) äëèíû n íàä ìíîæåñòâîì[0; 2] ÷åðåç îáîçíà÷èì ìíîæåñòâî âñåõ òåõ íàáîðîâ == (1 ; : : : ; n ) êóáà B n , äëÿ êîòîðûõ i = i ïðè âñåõ i 2[1; n] òàêèõ, ÷òî i 6= 2.
Ìíîæåñòâî íàçûâàåòñÿêóáà B n , ÷èñëî (n r), ðàâíîå ÷èñëó "2" â íàáîðå , ñ÷èòàåòñÿýòîé ãðàíè, à ÷èñëî r åå. Çàìåòèì,÷òî óêàçàííàÿ ãðàíü ïðåäñòàâëÿåò ñîáîé ïîäêóá ðàçìåðíîñòè(n r) êóáà B n è ñîñòîèò èç 2n r íàáîðîâ, îòëè÷àþùèõñÿäðóã îò äðóãà òîëüêî â òåõ ðàçðÿäàõ, â êîòîðûõ ðàñïîëîæåíûñèìâîëû "2" íàáîðà .
 ÷àñòíîñòè, ãðàíü ðàçìåðíîñòè 0ïðåäñòàâëÿåò ñîáîé âåðøèíó êóáà, ãðàíü ðàçìåðíîñòè 1 åãî ðåáðî, ãðàíü ðàçìåðíîñòè 2 êâàäðàò, è òàê äàëåå. Òàê,íà ðèñ. 2.1 â êóáå B 3 âûäåëåíû ðåáðà N1 ; : : : ; N6 , à â êóáå B 4âûäåëåíû ãðàíè (0010) ; (0200) ; (0221) è (1222) ðàçìåðíîñòåéãðàíüþðàçìåðíîñòüþðàíãîì16Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûx1 0 x1 x1 10 0 1 0 11 0 0 1 1a)x2 & _ 0 0 0 0 11 0 1 1 00 0 1 1 01 1 1 0 1x10011! j #110111101000b)ef(00)(11)(01)(10)(0001)(0111)(0110)(1001)(1101)(1110)(1000)íàçâàíèå ôóíêöèè f "0" (êîíñòàíòà íóëü) "1" (êîíñòàíòà åäèíèöà) òîæäåñòâåííàÿ ôóíêöèÿ îòðèöàíèå êîíúþíêöèÿ (óìíîæåíèå) äèçúþíêöèÿ ñóììà ïî ìîäóëþ 2 ýêâèâàëåíòíîñòü èìïëèêàöèÿ øòðèõ Øåôôåðà ñòðåëêà Ïèðñàc)Ðèñ. 2.2:P2 (1) è ¾îñíîâíûå¿ ÔÀË èç P2 (2)2.Ãèïåðêóá è ôóíêöèè àëãåáðû ëîãèêè170, 1, 2 è 3 ñîîòâåòñòâåííî.
Ëåãêî âèäåòü, ÷òî ãðàíü ðàíãà(n r) â êóáå B n , ãäå = (; 2; : : : ; 2) è 2 B n r , ñîîòâåòñòâóåòîòðåçêó êóáà äëèíû 2r , à ìíîæåñòâî âñåõ ãðàíåé óêàçàííîãîâèäà îáðàçóåò ðàçáèåíèå B n íà ïîñëåäîâàòåëüíûå îòðåçêè.Áóäåì, êàê îáû÷íî, ïðåäïîëàãàòü, ÷òî ó íàñ èìååòñÿ ñ÷åòíûéóïîðÿäî÷åííûé àëôàâèò áóëåâûõ ïåðåìåííûõ (ÁÏ) X = fx1 ; x2 ; : : : ; xn ; : : : g,è áóäåì ðàññìàòðèâàòü ôóíêöèè àëãåáðû ëîãèêè (ÔÀË),èëè, èíà÷å, áóëåâû ôóíêöèè îò ïåðåìåííûõ èç X, à ìíîæåñòâîâñåõ òàêèõ ôóíêöèé áóäåì îáîçíà÷àòü ÷åðåç P2 (X), èëè P2 .Áóäåì ïðåäïîëàãàòü òàêæå, ÷òî êàæäûé ðàññìàòðèâàåìûén-ìåðíûéêóáèìååòâèäBn=n= B (X ), ãäå ìíîæåñòâî ïåðåìåííûõ X = fxj1 ; : : : ; xjn g X è j1 < < jn , ïðè÷åì ïåðåìåííàÿ xji äëÿ âñåõ i 2[1; n] ñâÿçàíà ñ i-ì ðàçðÿäîì êóáà B n (X ).
Ìíîæåñòâî âñåõôóíêöèé àëãåáðû ëîãèêè f (xj1 ; : : : ; xjn ), îòîáðàæàþùèõ êóáB n (X ) â B , áóäåì îáîçíà÷àòü ÷åðåç P2 (X ), à åãî m-þ äåêàðòîâóñòåïåíü, òî åñòü ìíîæåñòâî ñèñòåì âèäà F = (f1 ; : : : ; fm ),ñîñòîÿùèõ èç m òàêèõ ôóíêöèé, ÷åðåç P2m (X ). Êàê ïðàâèëî,ìû áóäåì âûäåëÿòü èç X ìíîæåñòâî ÁÏ X (n) = fx1 ; : : : ; xn g,ãäå n 2 N, áóäåì ñîïîñòàâëÿòü åìó íàáîð ÁÏ x(n) == (x1 ; : : : ; xn ) è áóäåì ðàññìàòðèâàòü ìíîæåñòâî ÔÀË P2 (n) =P2 (X (n)), à òàêæå åãî ñòåïåíè P2m (n) = P2m (X (n)).Äëÿ çàäàíèÿ ÔÀË f èç P2 (n) ìîæíî èñïîëüçîâàòü åånòàáëèöó çíà÷åíèé, òî åñòü ìàòðèöó M èç ìíîæåñòâà B 2 ;n+1 ,i-ÿ ñòðîêà, i 2 [1; 2n ], êîòîðîé èìååò âèäM hi; [1; n + 1]i = (; f ()) ;ãäå () = i 1.
Ïðè ýòîì ñòîëáåö M h[1; 2n ] ; n + 1i, îäíîçíà÷íîçàäàþùèé ÔÀË f , ñ÷èòàåòñÿ åå ñòîëáöîì çíà÷åíèé è îáû÷íîçàïèñûâàåòñÿ â âèäå òðàíñïîíèðîâàííîé ñòðîêè, îáîçíà÷àåìîén÷åðåç ef . Îòñþäà ñëåäóåò, â ÷àñòíîñòè, ÷òî jP2 (n)j = 22 .Íà ðèñ. 2.2a (2.2b) ïðèâåäåíû òàáëèöû âñåõ (ñîîòâåòñòâåííî¾îñíîâíûõ¿) ÔÀË îò ÁÏ x1 (ñîîòâåòñòâåííî x1 ; x2 ), à íàðèñ. 2.2c ïåðå÷èñëåíû ñòîëáöû çíà÷åíèé ef è íàçâàíèÿ äëÿ18Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûâñåõ óêàçàííûõ ÔÀË.
Ñòîëáåö çíà÷åíèé ÔÀË f èç P2 (n)ïðè ëþáîì k 2 [1; n) ìîæíî çàïèñàòü â âèäå ïðÿìîóãîëüíîékn k , i-ÿ ñòðîêàòàáëèöû (ìàòðèöû) äëèíû 2 è âûñîòû 2nkêîòîðîé, i 2 1; 2, èìååò âèäefD(i 1) 2k ; i2kiE:õàðàêòåðèñòè÷åñêèìÊðîìå òîãî, ÔÀË f îäíîçíà÷íî îïðåäåëÿåòñÿ ñâîèì, êîòîðîå ñîñòîèò èç âñåõ íàáîðîâ 2 B n òàêèõ,÷òî f () = 1, è îáîçíà÷àåòñÿ ÷åðåç Nf , à òàêæå åãî äîïîëíåíèåìN f = Nf = B n nNf . Çàìåòèì, ÷òî ÔÀË f ÿâëÿåòñÿ õàðàêòåðèñòè÷åñêîéôóíêöèåé ìíîæåñòâà Nf .Íà ðèñ. 2.3a ïîêàçàíà òàáëèöà çíà÷åíèé ÔÀË òðåõ ïåðåìåííûõH (x1 ; x2 ; x3 ), êîòîðàÿ íàçûâàåòñÿ ôóíêöèåé, íàðèñ. 2.3b ïðèâåäåíû ïðÿìîóãîëüíûå òàáëèöû åå çíà÷åíèé, àíà ðèñ. 2.3c âûïèñàíû íàáîðû ìíîæåñòâ NH è N H .Íåòðóäíî óáåäèòüñÿ â òîì, ÷òî áèíàðíûå îïåðàöèè &, _, óäîâëåòâîðÿþò îáû÷íûì ¾àëãåáðàè÷åñêèì¿ òîæäåñòâàìàññîöèàòèâíîñòè è êîììóòàòèâíîñòè, à îïåðàöèÿ &, êðîìåòîãî, òîæäåñòâàì äèñòðèáóòèâíîñòè îòíîñèòåëüíî _ è ,ñ ïîìîùüþ êîòîðûõ ìîæíî ðàñêðûâàòü ñêîáêè1 .
Çàìåòèì,òàêæå, ÷òî èìåþò ìåñòî ñëåäóþùèå òîæäåñòâà ïðèâåäåíèÿïîäîáíûõìíîæåñòâîìãîëîñîâàíèÿx 0 = x x = x x = 0; x _ 1 = x _ x = x x = 1;x x = x _ x = x _ 0 = x 0 = x 1 = x;x1 _ x1 x2 = x1 ;(2.1)(2.2)(2.3)ïîñëåäíåå èç êîòîðûõ íàçûâàåòñÿ ¾òîæäåñòâîì ïîãëîùåíèÿ¿.1ÏðèçàïèñèôîðìóëíàäP2 (2)áóäåìïðèìåíÿòüîáû÷íûåñîãëàøåíèÿ î ¾ñèëå¿ îïåðàöèé, â ñîîòâåòñòâèè ñ êîòîðûìè ÔÀË:ñèëüíåå ÔÀË&,à ÔÀË&ñèëüíåå âñåõ îñòàëüíûõ ÔÀË îòäâóõ ÁÏ. Êðîìå òîãî, âíåøíèå ñêîáêè è ñêîáêè, çàäàþùèå ïîðÿäîêìíîãîêðàòíîãî âûïîëíåíèÿ îäíîé è òîé æå áèíàðíîé àññîöèàòèâíîéîïåðàöèè&; _; ; , áóäåì, êàê ïðàâèëî, îïóñêàòü.2.Ãèïåðêóá è ôóíêöèè àëãåáðû ëîãèêèx100001111x200110011x3 H0 01 00 01 10 01 10 11 1a)x1001l x3x2l0110001x2l x3x1l0110110 0 1 10 1 0 10 0 0 10 1 1 1b)NH = f(011) ; (101) ; (110) ; (111)gN H = f(000) ; (001) ; (010) ; (100)gc)Ðèñ.
2.3: ôóíêöèÿ ãîëîñîâàíèÿ1920Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÐàññìîòðèì íåêîòîðûå ôîðìóëû ¾àëãåáðàè÷åñêîãî¿ òèïàíàä ìíîæåñòâîìÁ0= fx1 x2 ; x1 _ x2 ; x1 g :áóêâàìèÔóíêöèè xi è xi áóäåì íàçûâàòüÁÏ xi è, êàê îáû÷íî,áóäåì ñ÷èòàòü, ÷òî x0i = xi ; x1i = xi . Êîíúþíêöèÿ (äèçúþíêöèÿ)r; 1 6 r 6 n, áóêâ ðàçëè÷íûõ ÁÏ èç ìíîæåñòâà X (n)íàçûâàåòñÿ(ñîîòâåòñòâåííî)rX (n).
Èç (2.1),r1(2.2) ñëåäóåò, ÷òî ýëåìåíòàðíàÿ êîíúþíêöèÿ (ÝÊ) K = xi1 xirè ýëåìåíòàðíàÿ äèçúþíêöèÿ (ÝÄ) J = xi11 _ : : : _ xirr , ãäå1 6 i1 < < ir 6 n, ÿâëÿþòñÿ õàðàêòåðèñòè÷åñêèìèÔÀË ãðàíè NK = è åå äîïîëíåíèÿ NJ = B n n , ãäåíàáîð èç ([0; 2])n îáëàäàåò òåì ñâîéñòâîì, ÷òî hip i = pïðè âñåõ p 2 [1; r] è hii = 2 â îñòàëüíûõ ñëó÷àÿõ. Òàê,ýëåìåíòàðíûå êîíúþíêöèè x1 x2 x3 x4 , x1 x3 x4 , x1 x4 è x1 ðàíãà4, 3, 2 è 1 ñîîòâåòñòâåííî îò ÁÏ x1 ; x2 ; x3 ; x4 ÿâëÿþòñÿõàðàêòåðèñòè÷åñêèìè ÔÀË ãðàíåé êóáà B 4 , ïîêàçàííûõ íàðèñ.
2.1b. Áóäåì ñ÷èòàòü, ÷òî êîíñòàíòà 1 (êîíñòàíòà 0) ÿâëÿåòñÿýëåìåíòàðíîé êîíúþíêöèåé (ñîîòâåòñòâåííî ýëåìåíòàðíîéäèçúþíêöèåé) ðàíãà 0. Çàìåòèì, ÷òî ëþáàÿ îòëè÷íàÿ îòx1 x2 è x1 x2 ñóùåñòâåííàÿ ÔÀË îò ÁÏ x1 ; x2 ÿâëÿåòñÿëèáî ÝÊ, ëèáî ÝÄ ðàíãà 2.Äèçúþíêöèÿ ðàçëè÷íûõ ýëåìåíòàðíûõ êîíúþíêöèé íàçûâàåòñÿ(ÄÍÔ), à êîíúþíêöèÿðàçëè÷íûõ ýëåìåíòàðíûõ äèçúþíêöèé (ÊÍÔ). Ïðè ýòîì ÄÍÔ (ÊÍÔ) ñ÷èòàåòñÿ,åñëè âñå åå ÝÊ (ñîîòâåòñòâåííî ÝÄ) ñóùåñòâåííî çàâèñÿò îòîäíèõ è òåõ æå ÁÏ, à èõ ðàíã ðàâåí ÷èñëó ýòèõ ÁÏ.
×èñëîÝÊ (ÝÄ) â ÄÍÔ (ñîîòâåòñòâåííî ÊÍÔ) A íàçûâàåòñÿ ååè îáîçíà÷àåòñÿ ÷åðåç (A). Ëþáóþ ÔÀË f (x1 ; : : : ; xn ),îòëè÷íóþ îò êîíñòàíòû, ìîæíî ïðåäñòàâèòü â âèäå åå ñîâåðøåííûõýëåìåíòàðíîé êîíúþíêöèåéäèçúþíêöèåé ðàíãà îò áóëåâûõ ïåðåìåííûõäèçúþíêòèâíîé íîðìàëüíîé ôîðìîéôîðìîéäëèíîéýëåìåíòàðíîéêîíúþíêòèâíîé íîðìàëüíîéñîâåðøåííîé2.21Ãèïåðêóá è ôóíêöèè àëãåáðû ëîãèêèÄÍÔ è ÊÍÔ ñëåäóþùèì îáðàçîì:f (x1 ; : : : ; xn ) =_x1 1 : : : xnn =(1 ;:::;n )2Nf^=x1 1 _ : : : _ xnn :(1 ;:::;n )2N f(2.4)Òàê, ñîâåðøåííàÿ ÄÍÔ ÔÀË g (x1 ; x2 ; x3 ), äëÿ êîòîðîé N gf(000) ; (111)g, (ñì. ðèñ.
2.1a) èìååò âèä=g (x1 ; x2 ; x3 ) == x1 x2 x3 _ x1 x2 x3 _ x1 x2 x3 _ x1 x2 x3 _ x1 x2 x3 _ x1 x2 x3 :Çàìåòèì, ÷òî ëþáóþ ÔÀË f èç P2 (n), îòëè÷íóþ îò êîíñòàíòû0, ìîæíî ïðåäñòàâèòü åå ñîâåðøåííîé ÄÍÔ âèäà (2.4), àÔÀË f 0 ôîðìóëîé x1 x1 .
Ñëåäîâàòåëüíî, ëþáàÿ ÔÀËèç P2 ìîæåò áûòü ðåàëèçîâàíà ôîðìóëîé íàä Á0 , è ïîýòîìóìíîæåñòâî Á0 ÿâëÿåòñÿ áàçèñîì P2 .Íîìåð () íàáîðà = (1 ; : : : ; n ) èç B n ñ÷èòàåòñÿ1 xn (ñîîòâåòñòâåííîÝÊ (ÝÄ) ðàíãà n îò ÁÏ X (n) âèäà xn1x1 1 _: : :_xnn ), à ñèñòåìà èç âñåõ òàêèõ ÔÀË, óïîðÿäî÷åííûõïî èõ íîìåðàì, íàçûâàåòñÿ(ñîîòâåòñòâåííî)n îò ÁÏ x1 ; : : : ; xnè îáîçíà÷àåòñÿ ÷åðåç Qn (ñîîòâåòñòâåííî Jn ). Ôóíêöèÿ âèäàíîìåðîìêîíúþíêòèâíûìäèçúþíêòèâíûì äåøèôðàòîðîì ïîðÿäêàn (x1 ; : : : ; xn ; y0 ; : : : ; y2n 1 ) =_=(1 ;:::;n )x1 1 xnn y ()ìóëüòèïëåêñîðíîé ôóíêöèåéìóëüòèïëåêñîðîìïîðÿäêààäðåñíûìèèíôîðìàöèîííûìèíàçûâàåòñÿ, èëè, èíà÷å,n, à ïåðåìåííûå x = (x1 ; : : : ; xn ) (y = (y0 ; : : : ; y2n 1 ))ñ÷èòàþòñÿ(ñîîòâåòñòâåííî)ÁÏ ìóëüòèïëåêñîðà n .Ìóëüòèïëåêñîðíóþ ÔÀË ïîðÿäêà (n q ) ; 0 6 q < n, îòàäðåñíûõ ÁÏ x00 = (xq+1 ; : : : ; xn ) è èíôîðìàöèîííûõ ÁÏ y =22Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû(y0 ; : : : ; y2n q 1 ) ÷àñòî èñïîëüçóþò äëÿ ðàçëîæåíèÿ ïðîèçâîëüíîéÔÀË f (x1 ; : : : ; xn ) ïî ÁÏ x00 , êîòîðîå îáîáùàåò ñîâåðøåííóþÄÍÔ (2.4) ñëåäóþùèì îáðàçîì:_f x0 ; x00 =00 =(q+1 ;:::;n )q+1 xnn f00 x0 =xq+1= nqx00 ; fe0 x0 ; : : : ; fe1 x0 ;(2.5)x0 = (x1 ; : : : ; xq ) è f00 (x0 ) = f (x0 ; 00 ).
Çàìåòèì, ÷òî ïðèq = 0 âñå ¾îñòàòî÷íûå¿ ÔÀË f00 (x0 ) ÿâëÿþòñÿ êîíñòàíòàìè.ãäåÏðåäñòàâëåíèå (2.5), â ñâîþ î÷åðåäü, ìîæíî îáîáùèòüñëåäóþùèì îáðàçîì. Ïóñòü = (1 ; : : : ; p ) ðàçáèåíèåêóáà B n , à i ; i 2 [1; p], õàðàêòåðèñòè÷åñêàÿ ÔÀË êîìïîíåíòûi è ïóñòü (x; y1 ; : : : ; yp ) =p_i=1 i (x)yi =p^( i (x) _ yi );i=1(2.6)x = (x1 ; : : : ; xn ), òàê íàçûâàåìàÿ ìóëüòèïëåêñîðíàÿôóíêöèÿ ðàçáèåíèÿ . Òîãäà ëþáóþ ÔÀË f èç P2(n) ìîæíîãäåïðåäñòàâèòü â âèäåf (x) =p_i=1gi (x) i (x) = (x; g1 (x); : : : ; gp (x));(2.7)ãäå gi ; i 2 [1; p], ïðîèçâîëüíàÿ ÔÀË èç P2 (n), ñîâïàäàþùàÿñ f íà i .
Çàìåòèì, ÷òî äëÿ ðàçëîæåíèÿ ÔÀË ìîæíî èñïîëüçîâàòüêàê äèçúþíêòèâíûå âàðèàíòû ïðåäñòàâëåíèé (2.5), (2.7), òàêè êîíúþíêòèâíûå âàðèàíòû ýòèõ ïðåäñòàâëåíèé, ñâÿçàííûåñ êîíúþíêòèâíûì ðàçëîæåíèåì (2.6).3.3Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿ23Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ÄÍÔ.Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû ååïîñòðîåíèÿÏðåäñòàâëåíèå ÔÀË â âèäå ÄÍÔ èëè ÊÍÔ èìååò ïðîñòóþãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
