Теормин (2012) (1133351)
Текст из файла
Òåîðåòè÷åñêèé ìèíèìóì ïî êóðñóÎñíîâû êèáåðíåòèêèÑîçäàí ïî ëåêöèÿì Ëîæêèíà Ñ.À. â 2012 ãîäóÍåîôèöèàëüíûé òåîðåòè÷åñêèé ìèíèìóì, ñîñòàâëåííûé ñòóäåíòàìè ËÒÏ ÀÑÂÊ.Èñïîëüçóéòå íà ñâîé ñòðàõ è ðèñê. Ëèöåíçèÿ CC-BY-NC.Àâòîðû:Êàãàíîâ Â. Þ.Êîðîë¼â À. Ê.è äðóãèå11j äëÿ êîòîðûõ a ≤ j ≤ b, ãäå a, b öåëûå, íàçûâàåòñÿ[a, b].[a1 , a2 ), [a2 , a3 ), . . ., ãäå a1 < a2 < a3 < . . . < an íàçûâàþòñÿ ïîñëåäîâà-Ìíîæåñòâî âñåõ öåëûõ ÷èñåëîòðåçêîìè îáîçíà÷àåòñÿ ÷åðåçÎòðåçêè âèäàòåëüíûìè.äëèíîé (âûñîòîé)×èñëî ñòîëáöîâ (ñòðîê) ìàòðèöû M íàçûâàåòñÿ ååÍàáîðïîêðûòèåðàíã (äëèíà).(a1 , a2 , .
. . , an )ïîêðûòèÿ, n Ðàçáèåíèå ìíîæåñòâàñîîòâåòñòâåííî.a = a1 ∪ a2 ∪ . . . ∪ an . aiêîìïîíåíòûïîêðûòèå èç íåïåðåñåêàþùèõñÿ ìíîæåñòâ.Ïîêðûòèå, â êîòîðîì íè îäíà èç êîìïîíåíò íå ñîäåðæèòñÿ â äðóãîé êîìïîíåíòå (â îáúåäèíåíèè îñòàëüíûõ êîìïîíåíò) ñ÷èòàåòñÿíåïðèâîäèìûì (òóïèêîâûì)ñîîòâåòñòâåííî.f , îïðåäåëåííóþ íà ìíîæåñòâå An è ïðèíèìàþùóþ çíà÷åíèÿ èç ìíîæåñòâà D(ìíîæåñòâà A) áóäåì íàçûâàòü n-àðíîé (n-ìåñòíîé) ôóíêöèåé èç ìíîæåñòâà A âî ìíîæåñòâî D (ñîîòâåòñòâåííî íàä ìíîæåñòâîì A) îò ïåðåìåííûõ x.ÔóíêöèþÎòíîøåíèå, îáëàäàþùåå ñâîéñòâàìè ðåôëåêñèâíîñòè, òðàíçèòèâíîñòè è àíòèñèììåòðè÷íîñòè, áóäåì, êàê îáû÷íî, íàçûâàòü îòíîøåíèåìÅñëèt÷àñòè÷íîãî ïîðÿäêà. îòíîøåíèå ÷àñòè÷íîãî ïîðÿäêà íà ìíîæåñòâåA,òî ïàðó(A, t)áóäåì íàçûâàòü÷àñòè÷íî óïîðÿäî÷åííûì ìíîæåñòâîì.Åñëè ëþáûå äâà ýëåìåíòàÏîäAñðàâíèìû, òîäèñêðåòíîé ôóíêöèåéAëèíåéíî óïîðÿäî÷åííîå ìíîæåñòâî.ïîíèìàþò, îáû÷íî, îòîáðàæåíèå îäíîãî êîíå÷íîãî ìíîæå-[0, k), ãäå k ≥ 2 íàçûâàåòñÿ ôóíêöèåé k -çíà÷íîék = 2 àëãåáðû ëîãèêè) à ìíîæåñòâî âñåõ òàêèõ ôóíêöèé îáîçíà÷àåòñÿ ÷åðåçñòâà â äðóãîå.
Òàê, ôóíêöèÿ íàä îòðåçêîìëîãèêè,( ïðèPk .Ïåðåìåííàÿxiíàçûâàåòñÿíåñóùåñòâåííîé ïåðåìåííîéäëÿ ëþáûõ îòëè÷àþùèõñÿ òîëüêî ïîxiíàçûâàåòñÿÔóíêöèÿfxiíàáîðîâñóùåñòâåííîé ïåðåìåííîéαèβèçôóíêöèèf.ñóùåñòâåííî (íåñóùåñòâåííî) çàâèñèò îò ïåðåìåííîé(ñîîòâåòñòâåííî íåñóùåñòâåííàÿ) ïåðåìåííàÿ ôóíêöèèfôóíêöèè f åñëè f (a) = f (b)An .  ïðîòèâíîì ñëó÷àå ïåðåìåííàÿxi , åñëè xi ñóùåñòâåííàÿf.cóùåñòâåííàÿ ôóíêöèÿ, åñëè îíà ñóùåñòâåííîxj ôîðìóëà ãëóáèíû 0 íàäçàâèñèò îò âñåõ ñâîèõ ïåðåìåííûõ.Ëþáàÿ ïåðåìåííàÿìíîæåñòâîì áàçèñíûõ ôóíêöèé Á,èíäóêòèâíî ãëóáèíà ðàñòåò, âñå ïîëó÷åííûå â ðåçóëüòàòå èíäóêòèâíîãî ïîñòðîåíèÿ çàïèñè ôîðìóëûíàä Á.Âñå ôîðìóëû, ïîëó÷åííûå íà ýòàïå èíäóêöèè ïîäôîðìóëû.Ñëîæíîñòü (ðàíã)ïîäôîðìóëû,íà ïîñëåäíåì ãëàâíûåôîðìóëû ÷èñëî âõîæäåíèé â íåå ôóíêöèîíàëüíûõ ñèìâîëîâ (ñèì-âîëîâ ïåðåìåííûõ).ÔîðìóëûF00F0èF 00 ,ðåàëèçóþùèå ðàâíûå ôóíêöèè, íàçûâàþòñÿýêâèâàëåíòíûìè.
F 0 =òîæäåñòâî.Ìíîæåñòâî âñåõ ôóíêöèé, ðåàëèçóåìûõ íàä Á ÌíîæåñòâîÁàçèñïîëíîå,çàìûêàíèå ìíîæåñòâàåñëè åãî çàìûêàíèå ñîâïàäàåò ñ êîíå÷íîå ïîëíîå âPaÁ.Pa .ìíîæåñòâî.2ÌíîæåñòâîíàçûâàþòBn,ãäåB = 0, 1åäèíè÷íûì êóáîìÍàáîðû, íàõîäÿùèåñÿ íàðÿäå ñîñåäíèå(ïîi-éíàçûâàåòñÿñôåðîén ∈ N,òî åñòü ìíîæåñòâî íàáîðîâ äëèíûnèç 0 è 1, îáû÷íîãèïåðêóáîì ðàçìåðíîñòè n.ðàññòîÿíèè n ïðîòèâîïîëîæíûå, îòëè÷àþùèåñÿèëèâ îäíîì ðàç-ïåðåìåííîé).Ìíîæåñòâî íàáîðîâ êóáàα,èBn,íàõîäÿùèõñÿ íà ðàññòîÿíèè(ñîîòâåòñòâåííîøàðîì)2ðàäèóñàtt(íå áîëüøå, ÷åìñ öåíòðîìα.t)îò íàáîðàÍà ìíîæåñòâå Bn îáû÷íûì îáðàçîì ââåäåì îòíîøåíèå ÷àñòè÷íîãî ïîðÿäêà ≤ òàêîå, ÷òîα = (α1 , . . .
, αn ) ≤ β = (β1 , . . . , βn ) òîãäà è òîëüêî òîãäà, êîãäà αi ≤ βi ïðè âñåõ i. Íàáîðûñâÿçàííûå ýòèì îòíîøåíèåì íàçûâàþòñÿñðàâíèìûìè.y = (y1 , . . . , yn ) äëèíû n íàä ìíîæåñòâîì [0, 2] ÷åðåç Γy îáîçíà÷èì ìíîæåñòâînâñåõ òåõ íàáîðîâ α = (α1 , . . . , αn ) êóáà B , äëÿ êîòîðûõ αi = yi ïðè âñåõ i, ÷òî yi 6= 2. Γy nãðàíü êóáà B , êîëè÷åñòâî 2 â íàáîðå = (n − r) ðàçìåðíîñòü ãðàíè, r ðàíã.ÔÀË f îäíîçíà÷íî îïðåäåëÿåòñÿ ñâîèì õàðàêòåðèñòè÷åñêèì ìíîæåñòâîì, êîòîðîåñîñòîèò èç âñåõ íàáîðîâ α òàêèõ, ÷òî f (α) = 1, è îáîçíà÷àåòñÿ ÷åðåç Nf .Ôóíêöèè xi è x̄i áóäåì íàçûâàòü áóêâàìè ÁÏ xi . Êîíúþíêöèÿ (äèçúþíêöèÿ) r , 1 ≤ r ≤ n,áóêâ ðàçëè÷íûõ ÁÏ èç ìíîæåñòâà X(n) íàçûâàåòñÿ ýëåìåíòàðíîé êîíúþíêöèåé (ñîîòâåòñòâåííî ýëåìåíòàðíîé äèçúþíêöèåé) ðàíãà r îò áóëåâûõ ïåðåìåííûõ X(n).Äëÿ íàáîðàÄèçúþíêöèÿ ðàçëè÷íûõ ýëåìåíòàðíûõ êîíúþíêöèé äèçúþíêòèâíàÿ íîðìàëüíàÿôîðìà.Êîíúþíêöèÿ ðàçëè÷íûõ ýëåìåíòàðíûõ äèçúþíêöèé ôîðìà.Ñîâåðøåííà,êîíúþíêòèâíàÿ íîðìàëüíàÿåñëè åå ÝÊ (ÝÄ) ñóùåñòâåííî çàâèñÿò îò îäíèõ è òåõ æå ÁÏ, à èõ ðàíã ÷èñëî ÁÏ.×èñëî ÝÊ (ÝÄ) Ëåììà.äëèíàÄÍÔ (ÊÍÔ).Ñîâåðøåííàÿ ÄÍÔ ÔÀËf, f ∈ P2 (n),ÿâëÿåòñÿ åäèíñòâåííîé ÄÍÔ îò ÁÏêîòîðàÿ ðåàëèçóåò ýòó ÔÀË, òîãäà è òîëüêî òîãäà, êîãäà âî ìíîæåñòâåNfX(n),íåò ñîñåäíèõíàáîðîâ.Ýòàïû äîêàçàòåëüñòâà.
Âîñïîëüçîâàòüñÿ òåì, ÷òî ó ýòîé ÔÀË íåò ãðàíåé ðàçìåðíîñòèáîëåå 0.Ñëåäñòâèå.Ñîâåðøåííûå ÄÍÔ ÔÀË ln , ¯ln ÿâëÿþòñÿ åäèíñòâåííûìè ÄÍÔ ýòèõ ÔÀË îòÁÏ X(n).3f 0 èìïëèöèðóåò ÔÀË f 00 , èëè, èíà÷å, ÔÀË f 00 ïîãëîùàåò ÔÀË f 0 , åñëè Nf 0 ⊆ Nf 00 ,000åñòü èìïëèêàöèÿ (f → f ) òîæäåñòâåííî ðàâíà 1.Ýëåìåíòàðíàÿ êîíúþíêöèÿ, êîòîðàÿ èìïëèöèðóåò ÔÀË f , íàçûâàåòñÿ èìïëèêàíòîé ýòîéÔÀËòîÔÀË.ÄÍÔ âèäàf (x1 , .
. . , xn )=K1 ∨ . . . ∨ Ks = Uáóäåì íàçûâàòüíåïðèâîäèìîé,âåòñâóþùåå åé ïîêðûòèå ÿâëÿåòñÿ íåïðèâîäèìûì, òî åñòü íè îäíà èç ãðàíåéåñëè ñîîò-NK1 , . . . , NKsíåñîäåðæèòñÿ íè â îäíîé èç äðóãèõ ãðàíåé ïîêðûòèÿ. Íà ÿçûêå èìïëèöèðóåìîñòè ýòî îçíà÷àåò, ÷òî íè îäíà èç ÝÊKi , iÈìïëèêàíòà Ê ÔÀËf∈ [1, s],íå ÿâëÿåòñÿ èìïëèêàíòîé ÝÊíàçûâàåòñÿïðîñòîé èìïëèêàíòîéùàåòñÿ íèêàêîé äðóãîé îòëè÷íîé îò íåå èìïëèêàíòîé ÔÀËÄèçúþíêöèÿ âñåõ ïðîñòûõ èìïëèêàíò ÔÀËÒåîðåìà. Ïóñòü U 0fKj ,ãäåj ∈ [1, s]èi 6= j .ýòîé ÔÀË, åñëè îíà íå ïîãëî-f.íàçûâàåòñÿ ååñîêðàùåííîéÄÍÔ.U 00 ñîêðàùåííûå ÄÍÔ ÔÀË f 0 è f 00 ñîîòâåòñòâåííî, à íåïðèâîäèìàÿ000ÄÍÔ U ïîëó÷àåòñÿ èç ôîðìóëû U ·U â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ.000Òîãäà U ñîêðàùåííàÿ ÄÍÔ ÔÀË f = f · f .Ýòàïû äîêàçàòåëüñòâà. Äîêàæåì, ÷òî â U âõîäèò ëþáàÿ ïðîñòàÿ èìïëèêàíòà f .
∀K 000000000ïðîñòîé èìïëèêàíòû f : K èìïëèêàíòà f è f .  U , U åñòü K , K , êîòîðûå èìïëèöèðó000000þòñÿ K .  U âîéäåò èìïëèöèðóåìàÿ K · K ÝÊ K̄ . K èìïëèöèðóåò K · K , ñëåäîâàòåëüíî,è K̄ . K̄ îäíîâðåìåííî èìïëèêàíòà f è èìïëèöèðóåòñÿ K ⇒ K̄ = K . Ñëåäñòâèå. Åñëè íåïðèâîäèìàÿ ÄÍÔ U ïîëó÷àåòñÿ èç ÊÍÔ B ÔÀË f â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ, òî U ñîêðàùåííàÿ ÄÍÔ ÔÀË f .0Ëþáàÿ ÄÍÔ U , êîòîðóþ ìîæíî ïîëó÷èòü èç ÄÍÔ U ïóòåì ôîðìèðîâàíèÿ â íåé ñ ïîìî000ùüþ òîæäåñòâ àññîöèàòèâíîñòè è êîììóòàòèâíîñòè ïîäôîðìóë âèäà xi K ∨ x̄i K , ïðèìåíåíèÿ0000000 00ê ýòèì ïîäôîðìóëàì òîæäåñòâà îáîáùåííîãî ñêëåèâàíèÿ xi K ∨ x̄i K = xi K ∨ x̄i K ∨ K Kè ïîñëåäóþùåãî ïðèâåäåíèÿ ïîäîáíûõ, íàçûâàåòñÿ ðàñøèðåíèåì ÄÍÔ U .00Ðàñøèðåíèå U ÄÍÔ U ñ÷èòàåòñÿ ñòðîãèì, åñëè U ñîäåðæèò ÝÊ, íå ÿâëÿþùóþñÿ èìïëèêàíòîé íè îäíîé ÝÊ èç U .è3Òåîðåìà.Íåïðèâîäèìàÿ ÄÍÔ ÿâëÿåòñÿ ñîêðàùåííîé ÄÍÔ òîãäà è òîëüêî òîãäà, êîãäàîíà íå èìååò ñòðîãèõ ðàñøèðåíèé.Ýòàïû äîêàçàòåëüñòâà.
Äîêàæåì, ÷òî, åñëè ÄÍÔ íåïðèâîäèâàÿ è íå èìååò ñòðîãèõ ðàñ-f . Ðàññìîòðèì ÝÊ k ìàêñèìàëüíîãî ðàíãàU . Ïîñêîëüêó åå ðàíã ñòðîãî ìåíüøå ÷èñëà âñåõ áóêâ, íàéäåòñÿ xi , íå âõîäÿùàÿ â íåå. Ðàññìîòðèì000000ÝÊ âèäà xi · k (x̄i · k). Îíè ñóòü èìïëèêàíòû íåêîòîðûõ xi · K (x̄i · K ); K , K ñîñòîÿò èç áóêâ0 00k . Ïî îáîáùåííîìó ñêëåèâàíèþ, îíà åùå è èìïëèêàíòà K K = K̃ , êîòîðàÿ ñàìà èìïëèêàíòàíåêîòîðîé ÝÊ èç ôîðìóëû. Ïðîòèâîðå÷èå, ò.ê. ïîëó÷èëîñü, ÷òî k èìëèêàíòà íåêîòîðîé ÝÊøèðåíèé, òî îíà ñîäåðæèò âñå ïðîñòûå èìïëèêàíòûf,èç ìíîæåñòâà òåõ èìïëèêàíòêîòîðûå íå ÿâëÿþòñÿ èìïëèêàíòàìè íè îäíîé ÝÊ èçèç ôîðìóëû.Ñëåäñòâèå.Èç ëþáîé ÄÍÔUÔÀËfìîæíî ïîëó÷èòü ñîêðàùåííóþ ÄÍÔ ýòîé ÔÀËâ ðåçóëüòàòå ïîñòðîåíèÿ ïîñëåäîâàòåëüíûõ ñòðîãèõ ðàñøèðåíèé è ïðèâåäåíèÿ ïîäîáíûõ äîïîëó÷åíèÿ íåïðèâîäèìîé ÄÍÔ, íå èìåþùåé ñòðîãèõ ðàñøèðåíèé.4U,ÄÍÔU 0,ðåàëèçóþùàÿ ÔÀËïîëó÷åííîé èçUf,òóïèêîâîéÿâëÿåòñÿÄÍÔ, åñëèf 6= U 0äëÿ ëþáîé ÄÍÔâ ðåçóëüòàòå óäàëåíèÿ íåêîòîðûõ áóêâ èëè öåëûõ ÝÊ.Ìèíèìàëüíàÿ (êðàò÷àéøàÿ)ÄÍÔ ÔÀËf ÄÍÔ, êîòîðàÿ èìååò ìèíèìàëüíàÿ ðàíã(ñîîòâåòñòâåííî äëèíó) ñðåäè âñåõ ÄÍÔ, ðåàëèçóþùèõÏåðåñå÷åíèå òóïèêîâûõÄÍÔ ÔÀËff.
äèçúþíêöèÿ âñåõ ðàçëè÷íûõ ïðîñòûõ èìïëè-f.α, α ∈ B n , íàçûâàåòñÿ ÿäðîâîé òî÷êîé ÔÀË f (x1 , . . . , xn ), åñëè α ∈ Nf è α âõîäèòòîëüêî â îäíó ìàêñèìàëüíóþ ãðàíü ÔÀË f . Ïðè ýòîì ãðàíü Nk , ÿâëÿþùàÿñÿ ìàêñèìàëüíîéãðàíüþ ÔÀË f è ñîäåðæàùàÿ òî÷êó α, ñ÷èòàåòñÿ ÿäðîâîé ãðàíüþ ÔÀË f , à ñîâîêóïíîñòüâñåõ ðàçëè÷íûõ ÿäðîâûõ ãðàíåé ÔÀË f íàçûâàåòñÿ ÿäðîì ÔÀË f .Ëåììà. ÄÍÔ ∩T ÔÀË f ñîñòîèò èç òåõ ïðîñòûõ èìïëèêàíò ÔÀË f , êîòîðûå ñîîòâåò-êàíò ýòîé ÔÀË, êîòîðûå âõîäÿò â ëþáóþ òóïèêîâóþ ÄÍÔ ÔÀËÍàáîðñòâóþò ÿäðîâûì ãðàíÿì ýòîé ÔÀË.Ýòàïû äîêàçàòåëüñòâà. Ïóñòü â òóïèêîâîé íåò èìïëèêàíòû, ñîîòâåòñòâóþùåé ÿäðîâîéãðàíè.
Òîãäàf =0íà ÿäðîâîé òî÷êå (âåäü ïîëó÷èëàñü íåïîêðûòàÿ ÿäðîâàÿ òî÷êà). Çíà÷èò,ïðîñòàÿ èìïëèêàíòà, ïîêðûâàþùàÿ ÿäðîâóþ òî÷êó, âõîäèò âî âñå òóïèêîâûå ÄÍÔ. Òåïåðü,ïóñòüK ïðîñòàÿ èìïëèêàíòàf,íå âõîäÿùàÿ â ÿäðî. Çíà÷èò, åñòü äðóãèå èìïëèêàíòû, êî-òîðûå ïîêðûâàþò åå åäèíèöû, íàéäåòñÿ òàêàÿ òóïèêîâàÿ ÄÍÔ, â êîòîðîéâûäåëèòü òóïèêîâîå ïîäïîêðûòèå, íå ñîäåðæàùååÑóììà òóïèêîâûõfÄÍÔ ÔÀËK ),ÿäðîâîé,NKf.åñëè âñå åå ìàêñèìàëüíûå ãðàíè ÿâëÿþòñÿ ÿäðîâûìè.ÄÍÔ, ïîëó÷àþùàÿñÿ èç ñîêðàùåííîé ÄÍÔ ÔÀËãðàíüíå áóäåò (ìîæíî äèçúþíêöèÿ âñåõ òåõ ðàçëè÷íûõ ïðîñòûõ èìïëèêàíòýòîé ÔÀË, êîòîðûå âõîäÿò õîòÿ áû â îäíó òóïèêîâóþ ÄÍÔ ÔÀËÔÀË ÿâëÿåòñÿKâ ïåðåñå÷åíèè åå íå áóäåò.ïîêðûâàåòñÿ ÿäðîì ÔÀËf,fóäàëåíèåì òåõ ÝÊíî íå âõîäèò â íåãî, íàçûâàåòñÿK,äëÿ êîòîðûõÄÍÔ ÊâàéíàýòîéÔÀË.Ïó÷îê ÔÀË f ÷åðåç òî÷êó αìàëüíûõ ãðàíåé ÔÀËÒî÷êàα, α ∈ N ,Πα (f )ðåãóëÿðíîé òî÷êîéÿâëÿåòñÿäëÿ êîòîðîé èìååò ìåñòî ñòðîãîå âêëþ÷åíèåÃðàíüNKÔÀËf ìíîæåñòâî âñåõ ïðîõîäÿùèõ ÷åðåçαìàêñè-f.íàçûâàåòñÿÔÀË f ,Πβ (f ) ⊂ Πα (f ).ðåãóëÿðíîé ãðàíüþåñëè íàéäåòñÿ òî÷êàβ, β ∈ Nf ,ýòîé ÔÀË, åñëè âñå òî÷êèNKðåãó-ëÿðíû.Òåîðåìà.ãðàíüNKÏðîñòàÿ èìïëèêàíòàÝòàïû äîêàçàòåëüñòâà.èç âñåõβKÔÀËfâõîäèò â ÄÍÔΣTòîãäà è òîëüêî òîãäà, êîãäàíå ÿâëÿåòñÿ ðåãóëÿðíîé ãðàíüþ ýòîé ÔÀË.ïîêðîåò âñåα.∀ðåãóëÿðíîé òî÷êèαíàéäåòñÿ íåðåãóëÿðíàÿβ.Ñèñòåìà ãðàíåéÏðîòèâîðå÷èå ñ òóïèêîâîñòüþ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
