Lectionc1 (1132950), страница 2
Текст из файла (страница 2)
Êàê èçâåñòíî(ñì., íàïðèìåð, [27]), aa!a (a 1) (a n + 1)==;nn! (a n)!n!(1.1)à ÷èñëî ñî÷åòàíèé ñ (âîçìîæíûìè) ïîâòîðåíèÿìè äëèíûèç A ðàâíî a+nn 1 .Èíäóêöèåé ïî n ëåãêî ïîêàçàòü, ÷òîn! > n n3;n(1.2)à èç ôîðìóëû Ñòèðëèíãà [25] ñëåäóåò, ÷òî1n! n np2n:(1.3)ea(n)1Àñèìïòîòè÷åñêîå ðàâåíñòâî a (n) b (n) îçíà÷àåò, ÷òî lim b(n) = 1,n!1òî åñòüa (n) = (1 + o (1)) b (n) :10Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÈç (1.1) è (1.2) âûòåêàåò, â ÷àñòíîñòè, íåðàâåíñòâî an63ann;(1.4)à èç (1.1) è (1.3) àñèìïòîòè÷åñêîå ðàâåíñòâî1n2nn+1 p22n:(1.5)Íàïîìíèì òåïåðü íåêîòîðûå ïîíÿòèÿ, ñâÿçàííûå ñ ôóíêöèÿìèè îòíîøåíèÿìè.
Ïóñòü x = (x1 ; : : : ; xn ), ãäå ïåðåìåííàÿ xiïðîáåãàåò çíà÷åíèÿ èç ìíîæåñòâà A è ñâÿçàíà ñ i-é êîìïîíåíòîé,i 2 [1; n], äåêàðòîâîé ñòåïåíè An . Ôóíêöèþ f , îïðåäåëåííóþíà ìíîæåñòâå An è ïðèíèìàþùóþ çíà÷åíèÿ èç ìíîæåñòâà D(ìíîæåñòâà A), áóäåì íàçûâàòü n, èëè, èíà÷å, nAD (ñîîòâåòñòâåííîA) îò ïåðåìåííûõ x è áóäåì ïðåäñòàâëÿòüåå â âèäå2-ìåñòíîéàðíîé ôóíêöèåé èç ìíîæåñòâà âî ìíîæåñòâîíàä ìíîæåñòâîì-! D (ñîîòâåòñòâåííî f : An ! A) :Ïðè ýòîì â ñëó÷àå D = B = f0; 1g ôóíêöèÿ f ñ÷èòàåòñÿf = f (x) ; f : Anîòíîøåíèåì íàä ìíîæåñòâîì A, à çàïèñü f (a) (f (a)), ãäå2 An, îçíà÷àåò, ÷òî êîìïîíåíòû íàáîðà aa = (a1 ; : : : ; an )íàõîäÿòñÿ (ñîîòâåòñòâåííî íå íàõîäÿòñÿ) â îòíîøåíèè f , òîåñòü f (a) = 1 (ñîîòâåòñòâåííî f (a) = 0).Äëÿ áèíàðíûõ îòíîøåíèé, òî åñòü îòíîøåíèé îò äâóõïåðåìåííûõ, îáû÷íûì îáðàçîì îïðåäåëÿþòñÿ ñâîéñòâà ðåôëåêñèâíîñòè,òðàíçèòèâíîñòè, ñèììåòðè÷íîñòè è àíòèñèììåòðè÷íîñòè.
Îòíîøåíèå,îáëàäàþùåå ñâîéñòâàìè ðåôëåêñèâíîñòè, ñèììåòðè÷íîñòè èòðàíçèòèâíîñòè, áóäåì, êàê îáû÷íî, íàçûâàòü îòíîøåíèåì1×åðåçdebc)(îáîçíà÷àåòñÿáëèæàéøååêñâåðõó(ñîîòâåòñòâåííî ñíèçó) öåëîå ÷èñëî2Ôóíêöèþîò ïåðåìåííûõ 1 2 áóäåì, êàê îáû÷íî, ïðåäñòàâëÿòüfâ âèäå(x1 fx2 ).x ;x1.11Îñíîâíûå ïîíÿòèÿýêâèâàëåíòíîñòè. Íàïîìíèì, ÷òî îòíîøåíèå ýêâèâàëåíòíîñòè , çàäàííîå íà ìíîæåñòâå A, ïîðîæäàåò ðàçáèåíèå ýòîãîìíîæåñòâà íà êëàññû -ýêâèâàëåíòíîñòè ìàêñèìàëüíûåïî âêëþ÷åíèþ ïîäìíîæåñòâà ìíîæåñòâà A, ñîñòîÿùèå èçïîïàðíî -ýêâèâàëåíòíûõ ýëåìåíòîâ.
Ïðèìåðîì îòíîøåíèÿýêâèâàëåíòíîñòè ÿâëÿåòñÿ îòíîøåíèåíàn000ìíîæåñòâå A , â êîòîðîì ñëîâà è íàõîäÿòñÿ òîãäà èòîëüêî òîãäà, êîãäà 00 ìîæíî ïîëó÷èòü èç 0 â ðåçóëüòàòåïåðåñòàíîâêè áóêâ. Çàìåòèì, ÷òî êëàññàìè ýêâèâàëåíòíîñòèïî ýòîìó îòíîøåíèþ ÿâëÿþòñÿ ñî÷åòàíèÿ ñ ïîâòîðåíèÿìè.Îòíîøåíèå, îáëàäàþùåå ñâîéñòâàìè ðåôëåêñèâíîñòè, òðàíçèòèâíîñòèè àíòèñèììåòðè÷íîñòè, áóäåì, êàê îáû÷íî, íàçûâàòü îòíîøåíèåì. Åñëè îòíîøåíèå ÷àñòè÷íîãî ïîðÿäêàíà ìíîæåñòâå A, òî ïàðó (A; ) áóäåì íàçûâàòü.  òîì ñëó÷àå, êîãäà â ÷àñòè÷íîóïîðÿäî÷åííîì ìíîæåñòâå (A; ) ëþáûå äâà ýëåìåíòà a0 èa00 èç A ñðàâíèìû, òî åñòü ëèáî a0 a00 , ëèáî a00 a0 , ïàðó(A; ) áóäåì ñ÷èòàòü.Ïðåäïîëàãàåòñÿ, ÷òî âñå ýëåìåíòû êîíå÷íîãî ëèíåéíî óïîðÿäî÷åííîãîìíîæåñòâà (A; ), ãäå jAj = t, ïðîíóìåðîâàíû ÷èñëàìè îòðåçêà[0; t) òàê, ÷òî äëÿ ëþáûõ a0 è a00 èç A íîìåð a0 íå áîëüøå,÷åì íîìåð a00 òîãäà è òîëüêî òîãäà, êîãäà a0 a00 .Ïîä äèñêðåòíîé ôóíêöèåé ïîíèìàþò, îáû÷íî, îòîáðàæåíèåîäíîãî êîíå÷íîãî ìíîæåñòâà â äðóãîå.
Òàê, ôóíêöèÿ íàäîòðåçêîì [0; k ), ãäå k > 2, íàçûâàåòñÿk(ïðè k = 2 ), à ìíîæåñòâî âñåõòàêèõ ôóíêöèé îáîçíà÷àåòñÿ ÷åðåç Pk . Äèñêðåòíûå ôóíêöèè,êàê ïðàâèëî, ìîãóò áûòü îïèñàíû òàáëèöàìè. Òàê, áèíàðíàÿôóíêöèÿ f (x1 ; x2 ) èç êîíå÷íîãî ëèíåéíî óïîðÿäî÷åííîãî ìíîæåñòâàA = fa1 ; : : : ; am g â êîíå÷íîå ìíîæåñòâî D ìîæåò áûòü çàäàíàìàòðèöåé M; M 2 Dm;m , ãäå M hi; j i = f (ai ; aj ) ïðè âñåõ i; jèç îòðåçêà [1; m], è îáðàòíî.Ïóñòü X = fx1 ; x2 ; : : : ; xn ; : : : g ñ÷åòíûé óïîðÿäî÷åííûéàëôàâèò ïåðåìåííûõ íàä ìíîæåñòâîì A è ïóñòü PA = PA (X)ïåðåñòàíîâî÷íîñòè÷àñòè÷íîãî ïîðÿäêàóïîðÿäî÷åííûì ìíîæåñòâîì÷àñòè÷íîëèíåéíî óïîðÿäî÷åííûì ìíîæåñòâîìëîãèêèàëãåáðû ëîãèêèôóíêöèåé -çíà÷íîé12Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû ìíîæåñòâî âñåõ ôóíêöèé íàä A îò ïåðåìåííûõ èç X.
Ïåðåìåííàÿxi ; i 2 [1; n], íàçûâàåòñÿf (x1 ; : : : ; xn ) èç PA , åñëè f () = f ( ) äëÿ ëþáûõ îòëè÷àþùèõñÿòîëüêî ïî xi íàáîðîâ è èç An .  ïðîòèâíîì ñëó÷àåïåðåìåííàÿ xi íàçûâàåòñÿïåðåìåííîé ôóíêöèèf . Ñ÷èòàåòñÿ, ÷òî ôóíêöèÿ f ñóùåñòâåííî (íåñóùåñòâåííî)çàâèñèò îò ïåðåìåííîé xi , åñëè xi ñóùåñòâåííàÿ (ñîîòâåòñòâåííîíåñóùåñòâåííàÿ) ïåðåìåííàÿ ôóíêöèè f . Íåñóùåñòâåííàÿïåðåìåííàÿ íå âëèÿåò íà çíà÷åíèå ôóíêöèè, ïîýòîìó, êàêîáû÷íî, ðàâåíñòâî ôóíêöèé áóäåì ðàññìàòðèâàòü ñ òî÷íîñòüþäî äîáàâëåíèÿ èëè èçúÿòèÿ íåñóùåñòâåííûõ ïåðåìåííûõ.Ïðè ýòîì äâå ôóíêöèè ñ÷èòàþòñÿ, åñëè îíè èìåþòîäíè è òå æå ñóùåñòâåííûå ïåðåìåííûå è îäèíàêîâûì îáðàçîìîòîáðàæàþò äåêàðòîâó ñòåïåíü A, ñâÿçàííóþ ñ èõ ñóùåñòâåííûìèïåðåìåííûìè, â A.
Áóäåì ãîâîðèòü, ÷òî f ôóíêöèÿ, åñëè îíà ñóùåñòâåííî çàâèñèò îò âñåõ ñâîèõ ïåðåìåííûõ.Ïðåäïîëàãàåòñÿ, ÷òî ó íàñ èìååòñÿ ñ÷åòíûé àëôàâèò ôóíêöèîíàëüíûõñèìâîëîâ (ÔÑ) äëÿ îáîçíà÷åíèÿ ôóíêöèé èç PA è ÷òî âPA âûäåëåíî ¾áàçèñíîå¿ ìíîæåñòâî Á. Äàäèì èíäóêòèâíîåîïðåäåëåíèå ôîðìóëû íàä Á è ðåàëèçóåìîé åþ ôóíêöèè,êîòîðîå, â îòëè÷èå îò [27], íåÿâíî ïðåäïîëàãàåò íàëè÷èå â Áôóíêöèè, òîæäåñòâåííî ðàâíîé ïåðåìåííîé. Çàìåòèì, ÷òî ññîäåðæàòåëüíîé òî÷êè çðåíèÿ ôîðìóëà ïðåäñòàâëÿåò ñîáîéñëîâî, ïîñòðîåííîå èç ÔÑ ¾áàçèñíûõ¿ ôóíêöèé, ñèìâîëîâïåðåìåííûõ è ¾ðàçäåëèòåëåé¿, êîòîðîå çàäàåò ïîñëåäîâàòåëüíîñòüâûïîëíåíèÿ îïåðàöèé ñóïåðïîçèöèè.Ëþáàÿ ïåðåìåííàÿ xj èç X ñ÷èòàåòñÿ0Á, êîòîðàÿ ðåàëèçóåò ôóíêöèþ xj .
Åñëè' (x1 ; : : : ; xk ) 2 Á è äëÿ êàæäîãî i; i 2 [1; k], îïðåäåëåíàôîðìóëà Fi ãëóáèíû qi íàä ìíîæåñòâîì Á, êîòîðàÿ ðåàëèçóåòôóíêöèþ fi èç PA , òî çàïèñü F âèäàíåñóùåñòâåííîé ïåðåìåííîé ôóíêöèèñóùåñòâåííîéðàâíûìèñóùåñòâåííàÿíàä ìíîæåñòâîìôîðìóëîé ãëóáèíûF = ' (F1 ; : : : ; Fk )(1.6)ÿâëÿåòñÿ ôîðìóëîé ãëóáèíû q = max fq1 ; : : : ; qk g + 1 íàä Á,2.13Ãèïåðêóá è ôóíêöèè àëãåáðû ëîãèêèêîòîðàÿ ðåàëèçóåò ôóíêöèþ f âèäà f = ' (f1 ; : : : ; fk ). Âñåçàïèñè, ïîëó÷åííûå â ðåçóëüòàòå óêàçàííîãî èíäóêòèâíîãîïîñòðîåíèÿ, è òîëüêî îíè ñ÷èòàþòñÿÁ. Ïðè ýòîì ôîðìóëû, ïîëó÷åííûå â ïðîöåññå èíäóêòèâíîãîïîñòðîåíèÿ ôîðìóëû F, íàçûâàþòñÿ åå, à òåïîäôîðìóëû F1 ; : : : ; Fk , èç êîòîðûõ íà ïîñëåäíåì øàãå èíäóêòèâíîãîïîñòðîåíèÿ ñòðîèòñÿ ôîðìóëà F âèäà (1.6), ñ÷èòàþòñÿ ååïîäôîðìóëàìè. Ïîä() ôîðìóëûF ïîíèìàåòñÿ ÷èñëî âõîæäåíèé â íåå ÔÑ (ñîîòâåòñòâåííîñèìâîëîâ ïåðåìåííûõ), êîòîðîå îáîçíà÷àåòñÿ ÷åðåç L (F) (ñîîòâåòñòâåííîR (F)).Ôîðìóëû F0 è F00 , ðåàëèçóþùèå ðàâíûå ôóíêöèè f 0 è00f , íàçûâàþòñÿèëè, èíà÷å,.
Ïðèýòîì ðàâåíñòâî âèäà t : F0 = F00 ñ÷èòàåòñÿ.Îáû÷íûì îáðàçîì ââîäÿòñÿ òîæäåñòâà, õàðàêòåðèçóþùèåñâîéñòâà êîììóòàòèâíîñòè, àññîöèàòèâíîñòè è äèñòðèáóòèâíîñòèáèíàðíûõ ôóíêöèé èç PA .Ìíîæåñòâî âñåõ ôóíêöèé, ðåàëèçóåìûõ ôîðìóëàìè íàäÁ, íàçûâàåòñÿìíîæåñòâà Á. Ïðè ýòîì ìíîæåñòâîÁ ñ÷èòàåòñÿ, åñëè åãî çàìûêàíèå ñîâïàäàåò ñ PA . Âäàëüíåéøåì ëþáîå êîíå÷íîå ïîëíîå â PA áàçèñíîå ìíîæåñòâîÁ áóäåì íàçûâàòü. Ïðè ýòîì, â îòëè÷èå îò [27], â Áìîãóò ïðèñóòñòâîâàòü ÔÀË, ïðè óäàëåíèè êîòîðûõ îñòàâøååñÿìíîæåñòâî ïðîäîëæàåò áûòü ïîëíûì.ôîðìóëàìè íàä ìíîæåñòâîìïîäôîðìóëàìèãëàâíûìèñëîæíîñòüþ ðàíãîìðàâíûìèýêâèâàëåíòíûìèòîæäåñòâîìçàìûêàíèåìïîëíûìáàçèñîì2Ãèïåðêóá è ôóíêöèè àëãåáðû ëîãèêè.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû èñâÿçàííûå ñ íèìè ðàçëîæåíèÿ ôóíêöèéÌíîæåñòâî B n , ãäå B = f0; 1g è n 2 N, òî åñòü ìíîæåñòâîíàáîðîâ äëèíû n èç 0 è 1, îáû÷íî íàçûâàþòèëèðàçìåðíîñòè n.
Îòíîøåíèå ïåðåñòàíîâî÷íîñòèðàçáèâàåò êóá B n íà êëàññû ýêâèâàëåíòíîñòè (ñî÷åòàíèÿ)B0n ; B1n ; : : : ; Bnn ; ãäå Bin ; i 2 [0; n], òàê íàçûâàåìûé i-éêóáîìãèïåðêóáîìåäèíè÷íûì14Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûñëîé êóáà B n , òî åñòü ìíîæåñòâî íàáîðîâ ñ i åäèíèöàìè, è,nnî÷åâèäíî, jBi j = i .Íà ìíîæåñòâå B n ââåäåì îòíîøåíèå ëåêñèêîãðàôè÷åñêîãîëèíåéíîãî ïîðÿäêà, êîòîðîå çàäàåòñÿ âçàèìíî îäíîçíà÷íûìîòîáðàæåíèåì (íóìåðàöèåé) : B n ! [0; 2n ) òàêèì, ÷òî (1 ; : : : ; n ) =nXi=1i 2n i :Çàìåòèì, ÷òî äâîè÷íàÿ çàïèñü ÷èñëà () ; 2 B n , äîïîëíåííàÿñëåâà íóëÿìè äî íàáîðà äëèíû n, ñîâïàäàåò ñ .
Àíàëîãè÷íûìîáðàçîì ââîäèòñÿ ëåêñèêîãðàôè÷åñêèé ïîðÿäîê íà ìíîæåñòâå([0; k))n ïðè k > 2. Ìíîæåñòâî íàáîðîâ, ÿâëÿþùååñÿ îáðàçîìîòðåçêà [a; b], ãäå [a; b] [0; 2n ), ïðè îòîáðàæåíèè 1 , íàçûâàåòñÿBn.Äëÿ íàáîðîâ ; èç B n ÷åðåç (; ) îáîçíà÷àåòñÿ òàêíàçûâàåìîå ðàññòîÿíèå Õýììèíãà ìåæäó íèìè, òî åñòü ÷èñëîòåõ ðàçðÿäîâ, â êîòîðûõ îíè îòëè÷àþòñÿ äðóã îò äðóãà. Ïðèýòîì íàáîðû, íàõîäÿùèåñÿ íà ðàññòîÿíèè n, íàçûâàþòñÿà íàáîðû, îòëè÷àþùèåñÿ òîëüêî â îäíîì (i-ì) ðàçðÿäå, ñ÷èòàþòñÿ(ñîîòâåòñòâåííîi).Ïðè ãåîìåòðè÷åñêîì èçîáðàæåíèè êóáà B n íà ïëîñêîñòè âåðøèíûi-ãî ñëîÿ îáû÷íî ðàñïîëàãàþòñÿ íà îäíîì è òîì æå ãîðèçîíòàëüíîìóðîâíå íàä âåðøèíàìè (i 1)-ãî ñëîÿ, i = 1; : : : ; n, à ñîñåäíèåâåðøèíû ñîåäèíÿþòñÿ îòðåçêàìè ïðÿìûõ (ñì. ðèñ.
2.1). Ìíîæåñòâîíàáîðîâ êóáà B n , íàõîäÿùèõñÿ íà ðàññòîÿíèè t (íå áîëüøå,÷åì t) îò íàáîðà , íàçûâàåòñÿ(ñîîòâåòñòâåííî)t. Çàìåòèì, ÷òî i-é ñëîé êóáà B n ÿâëÿåòñÿñôåðîé ðàäèóñà i ñ öåíòðîì â íàáîðå e0 = (0; : : : ; 0) è ñôåðîéðàäèóñà (n i) ñ öåíòðîì â íàáîðå e1 = (1; : : : ; 1).Íà ìíîæåñòâå B n îáû÷íûì îáðàçîì ââåäåì îòíîøåíèå÷àñòè÷íîãî ïîðÿäêà 6 òàêîå, ÷òîîòðåçêîì êóáàïðîòèâîïîëîæíûìè,ñîñåäíèìè ïî -é ïåðåìåííîéñîñåäíèìèðàäèóñà ñ öåíòðîìñôåðîé = (1 ; : : : ; n ) 6 = (1 ; : : : ; n )øàðîì2.15Ãèïåðêóá è ôóíêöèè àëãåáðû ëîãèêèB3(1111)@ @@@@@@@@@ @@@ @@@@@@@@x x x 1x @@I@6(0000)B4(111)@@(110) NN@ (011)@@(101)N @ (010) @ NN@ (001)(100) N @@@@(000)``c2c`3(1222)`c`1`4`c65c`c`````c`(0200)1````````(0221)(0010)432`a)Ðèñ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
