Частично упорядоченные множества (1127207), страница 3
Текст из файла (страница 3)
ìíîæåñòâà P = h P, 6 i∅ 6= Q ⊆ P ⇒ dim(Q) 6 dim(P), ïðè óäàëåíèè 1-ãîýëåìåíòà åãî ðàçìåðíîñòü óìåíüøàåòñÿ íå áîëåå, ÷åì íà 1;dim(P + Q) = max dim(P), dim(Q) , åñëè õîòÿ áûîäíî èç ìíîæåñòâ íå ÿâëÿåòñÿ öåïüþ è dim(P + Q) = 2;dim(P × Q) 6 dim(P) + dim(Q);dim(P) 6 |P|/2 ïðè |P| > 4 (òåîðåìà Õèðàãó÷è).Òåîðåìà (¾êîìïàêòíîñòè¿)ÏóñòüP òàêîå ÷.ó.
ìíîæåñòâî, ÷òî ëþáîå åãî êîíå÷íîå ÷.ó.ïîäìíîæåñòâî èìååò ðàçìåðíîñòü, íå ïðåâîñõîäÿùóþÒîãäàwp1 :d.dim(P) 6 d.n4c1nc21−6 dim(P) 61−, n = |P|.log n4log nÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿd-íåñâîäèìûå ÷.ó. ìíîæåñòâàÎïðåäåëåíèå×.ó. ìíîæåñòâî P íàçûâàåòñÿ d-íåñâîäèìûì äëÿ íåêîòîðîãîd > 2, åñëè dim(P) = d è dim(P 0 ) < d äëÿ ëþáîãîñîáñòâåííîãî ÷.ó. ïîäìíîæåñòâà P 0 ⊂ P .... íåñâîäèìûå ìíîæåñòâà:2 äâóõýëåìåíòíàÿ àíòèöåïü (åäèíñòâåííîå);3 s3 , sh, shd + ... îïèñàíû, ðåãóëÿðíû è õîðîøî èçó÷åíû;4 äîñòàòî÷íî ÷àñòî âñòðå÷àþòñÿ è âåñüìà ïðè÷óäëèâû;t St (åäèíñòâåííîå 2t-ýëåìåíòíîå) + ...;êàæäîå t-íåñâîäèìîå ÷.ó.
ìíîæåñòâî ÿâëÿåòñÿ÷.ó. ïîäìíîæåñòâîì íåêîòîðîãî (t + 1)-íåñâîäèìîãî.46 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿ4-íåñâîäèìîå ÷.ó. ìíîæåñòâî[[[◦◦' '◦ ''A'A ◦A''A'A''' '''AAA AA'A'' '''' AA A'◦◦◦ [◦ [[◦◦◦47 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿÏðîáëåìà Íîãèíàπ(d, n) ìîùíîñòè ìíîæåñòâàd-íåñâîäèìîãî n-ýëåìåíòíîãî ÷.ó.Êàêîâî íàèáîëüøåå çíà÷åíèåìàêñèìàëüíûõ ýëåìåíòîâìíîæåñòâà ïðèd > 4?Äàííàÿ ïðîáëåìà äî ñèõ ïîð îñòà¼òñÿ îòêðûòîé.Óòâåðæäåíèåπ(d, n) 6 n − d .48 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÇàäà÷è c ðåøåíèÿìèÐàçäåëû1Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó.
ìíîæåñòâ2Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè3Ëèíåàðèçàöèÿ4Çàäà÷è c ðåøåíèÿìè5Ìîäåëè Êðèïêå49 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÇàäà÷è c ðåøåíèÿìèÂîïðîñ ×ÓÌ-1: Åñòü ëè ðàçíèöà ìåæäó óòâåðæäåíèÿìè×.ó. ìíîæåñòâî ñîäåðæèò (à) áåñêîíå÷íóþ öåïü è(á) öåïü, äëèíà êîòîðîé áîëüøå íàïåð¼ä çàäàííîãî ÷èñëà?Îòâåò:◦ [h[[ NhhNN◦NhhNhNN◦ h...◦◦NNNN◦ ◦ [[ ◦ ◦ AAA[ AAAA◦50 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÇàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-2Ïðèâåäèòå ïðèìåð ÷.ó.ì., èìåþùåãî â òî÷íîñòè îäèíìàêñèìàëüíûé ýëåìåíò è íå èìåþùåãî íàèáîëüøåãî.Ðåøåíèå....◦◦...•51 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà52 / 85Çàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-3 ÷.ó. ìíîæåñòâåh N, | iäëÿ ïîäìíîæåñòâàíàéòè1AM ;2AO ;3sup A ;4inf A .Ðåøåíèå.1AM = { 36n | n = 1, 2, . . . } ;2AO = { 1, 2, 3, 6 };3sup A = ÍÎÊ (12, 18) = 36 ;4inf A = ÍÎÄ (12, 18) = 6.A = {12, 18}ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÇàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-4Ðàçëîæèòü â ïåðåñå÷åíèå ìèíèìàëüíîãî êîëè÷åñòâà öåïåé ÷.ó.ìíîæåñòâîPc14c2hhhbbhhh4444haa4441212Ðåøåíèå.P = [ a1 , b1 , a2 , c1 , b2 , c2 ] ∩ [ a2 , b2 , a1 , c2 , b1 , c1 ] .53 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÇàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-51Ñêîëüêî ñóùåñòâóåò ÷àñòè÷íûõ ïîðÿäêîâ íà ìíîæåñòâå{ a, b, c }?2Ñêîëüêî ñðåäè íèõ íåèçîìîðôíûõ?3Ñêîëüêî ñðåäè íèõ ëèíåéíûõ ïîðÿäêîâ?54 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà55 / 85Çàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-5...Ðåøåíèå. Íåèçîìîðôíûõ òð¼õýëåìåíòíûõ ïîðÿäêîâ 5:òðèâèàëüíûé, 3 è◦◦◦◦◦[[[ ◦Îíè ïîðîæäàþò ïîðÿäêè íà { a, b, c }:òðèâèàëüíûé 1,öåïü 3 6,2 + 1 6,Z3 è äâîéñòâåííûé ê íåìó ïî 3Âñåãî 19[[[◦◦◦ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà56 / 85Çàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-6Ïîñòðîéòå ÷.ó. ìíîæåñòâàI(1)èI(2)âñåõ èíòåðâàëîâáóëåâûõ åäèíè÷íûõ êóáîâ ðàçìåðíîñòåé1è2.Ðåøåíèå.Áóëåâ åäèíè÷íûé êóáîâ ðàçìåðíîñòè n ñîäåðæèò 3n ðàçëè÷íûõèíòåðâàëîâ, ïðè ýòîì èìååòñÿ Cnk 2k èíòåðâàëîâ ðàçìåðíîñòèk, k = 0, 1, . . . , n.I(1):(0)(−)[[(1)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà57 / 85Çàäà÷è c ðåøåíèÿìèÇàäà÷à ×ÓÌ-6...I(2) = I(1) × I(1)(äâîéíûìè ëèíèÿìè ïîêàçàíû ýêçåìïëÿðû I(1)):(−−)[[[[AAA [ A[AAA(1−)(−1)(−0)(0−)[[[[[[AAAA[[AAAAAA [[ AAAA [[(11)(10)(01)(00)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÌîäåëè ÊðèïêåÐàçäåëû1Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ2Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè3Ëèíåàðèçàöèÿ4Çàäà÷è c ðåøåíèÿìè5Ìîäåëè Êðèïêå58 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà59 / 85Ìîäåëè ÊðèïêåÈíòóèöèîíèñòñêîå èñ÷èñëåíèå âûñêàçûâàíèé ÈÈÂ: ôîðìóëûÏðèìåíåíèå ÷.ó. ìíîæåñòâ â ìàòåìàòè÷åñêîé ëîãèêå ìîäåëèÊðèïêå êàê îáùåãî ñïîñîáà óñòàíîâëåíèÿ èñòèííîñòè ôîðìóëëîãè÷åñêèõ èñ÷èñëåíèé.Çàôèêñèðóåì ìíîæåñòâàV ar = { x, y, . . . }ëîãè÷åñêèõ ïåðåìåííûõàòîìàðíûõ âûñêàçûâàíèé;Φ = { ¬, N, ∨, } ñèìâîëîâëîãè÷åñêèõ ñâÿçîê.Îïðåäåëåíèåíàä ìíîæåñòâîì Φ ëîãè÷åñêèõ ñâÿçîê íàçûâàåòñÿëèáî íåêîòîðàÿ ëîãè÷åñêàÿ ïåðåìåííàÿ (àòîìàðíàÿ ôîðìóëà),ëèáî îäíî èç çíàêîñî÷åòàíèé âèäà (¬A), (AN B), (A ∨ B) èëè(A B) (ìîëåêóëÿðíàÿ ôîðìóëà), ãäå A è B ôîðìóëû.ÔîðìóëîéA ìíîæåñòâî âñåõ ëîãè÷åñêèõ ôîðìóë.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÌîäåëè ÊðèïêåÈBÂ: ýêîíîìèÿ ñêîáîê è èñòèííîñòíûå çíà÷åíèÿÄëÿ ñîêðàùåíèÿ çàïèñè ôîðìóë ïðèíèìàþò ñîãëàøåíèÿ ïðàâèëà ýêîíîìèè ñêîáîê è ïðèîðèòåòà ñâÿçîê: âíåøíèå ñêîáêèó ôîðìóë îïóñêàþòñÿ è ñèëà ñâÿçîê óáûâàåò â ïîðÿäêå,óêàçàííîì ïðè èõ ââåäåíèè âûøå (> ¾ñèëüíåå¿)¬ >N > ∨ >Êàæäàÿ ëîãè÷åñêàÿ ïåðåìåííàÿ ìîæåò ïðèíèìàòü, âîîáùåãîâîðÿ, ñ÷¼òíîå ìíîæåñòâî èñòèííîñòíûõ çíà÷åíèé{ 0, 1, .
. . , }. Ïåðâîå çíà÷åíèå 0 íàçîâ¼ì âûäåëåííûì.Íåôîðìàëüíî âûäåëåííîå çíà÷åíèå ñèìâîëèçèðóåò ¾èñòèíó¿(È), à îñòàëüíûå ðàçëè÷íûå ñèòóàöèè îòñóòñòâèÿèñòèííîñòè: íåîïðåäåë¼ííîñòü âûñêàçûâàíèÿ, ðàçëè÷íûåôîðìû åãî ¾ëîæíîñòè¿ (Ë) è ò.ä.
 êëàññè÷åñêîé ëîãèêåìíîæåñòâî èñòèííîñòíûõ çíà÷åíèé ñóæàåòñÿ äî äâóõ: { È, Ë } èâûäåëåííîå È.60 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà61 / 85Ìîäåëè ÊðèïêåÈÈÂ: àêñèîìûÑëåäóþùèå ôîðìóëû íàçîâ¼ì12345678910ñõåìàìè àêñèîìÈÈÂ:A (B A);(A (B C)) ((A B) (A C));AN B A;AN B B ;A (B (AN B));A A ∨ B;B A ∨ B;(A C) ((B C) (A ∨ B C));¬ A (A B);(A B) ((A ¬B) ¬A).È ïîëó÷àþòñÿ ïðè ïîäñòàíîâêå â ñõåìûêîíêðåòíûõ ôîðìóë âìåñòî ìåòàñèìâîëîâ A, B è C .ÀêñèîìûÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÌîäåëè ÊðèïêåÈÈÂ: ïðàâèëî âûâîäà è âûâîäèìûå ôîðìóëû ÈÈ èìååòñÿ åäèíñòâåííîå ïðàâèëî âûâîäà, îáîçíà÷àåìîåMP (ëàò. modus ponens, ïðàâèëî îòäåëåíèÿ), ïîçâîëÿþùåå èçôîðìóë A è A B ïîëó÷èòü ôîðìóëó B :A, A B ` BÔîðìóëà A íàçûâàåòñÿ âûâîäèìîé, åñëè íàéä¼òñÿ êîíå÷íàÿïîñëåäîâàòåëüíîñòü ôîðìóë A1 , .
. . , Al òàêàÿ, ÷òî Al = A èêàæäûé ýëåìåíò ïîñëåäîâàòåëüíîñòèëèáî ÿâëÿåòñÿ àêñèîìîé,ëèáî ïîëó÷åí ïî ïðàâèëóôîðìóë.MPèç êàêèõ-òî äâóõ ïðåäûäóùèõÂûâîäèìîñòü ôîðìóëû A çàïèñûâàåòñÿ êàê ` A, â ñëó÷àåîòñóòñòâèÿ âûâîäà ïèøóò 6` A.62 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÌîäåëè ÊðèïêåÈÈÂ: ïðèìåð âûâîäà ôîðìóëûÏðèâåä¼ì âûâîä ôîðìóëû x ∨ y y ∨ x.Äëÿ óäîáñòâà ôîðìóëû âûâîäà áóäåì ïèñàòü äðóã ïîä äðóãîì,íóìåðóÿ èõ è äàâàÿ êðàòêèå êîììåíòàðèè ïî èõ ïîëó÷åíèþ.(1)x y∨x ïîäñòàíîâêà â ñõåìó 7(2)yy∨x ïîäñòàíîâêà â ñõåìó 6(3)(x y ∨ x) ((y y ∨ x) (x ∨ y y ∨ x)) ïîäñòàíîâêà â àêñèîìó 8: A 7→ x, B 7→ y , C 7→ y ∨ x(4)(y y ∨ x) (x ∨ y y ∨ x)(5)x∨yy∨x ïî MP èç (1) è (3) ïî MP èç (2) è (4)Íàïîìèíàíèå:» A A ∨ B;¼ B A ∨ B;½ (A C) ((B C) (A ∨ B C)).63 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÌîäåëè ÊðèïêåÈÈÂ: âûâîäèìîñòü èç ìíîæåñòâà ôîðìóëÏóñòü Γ êîíå÷íîå ìíîæåñòâî ôîðìóë.Ôîðìóëà B íàçûâàåòñÿ âûâîäèìîé èç ìíîæåñòâà ôîðìóë Γ(ñèìâîëè÷åñêè Γ ` B ), åñëè íàéä¼òñÿ êîíå÷íàÿïîñëåäîâàòåëüíîñòü ôîðìóë B1 , .
. . , Bl òàêàÿ, ÷òî Bl = B èêàæäûé ýëåìåíò ýòîé ïîñëåäîâàòåëüíîñòèëèáî ÿâëÿåòñÿ àêñèîìîé,ëèáî ïðèíàäëåæèò Γ,ëèáî ïîëó÷åí ïî ïðàâèëó MP èç êàêèõ-òî äâóõ ïðåäûäóùèõôîðìóë.Ôàêò âûâîäèìîñòè Γ ` B íå èçìåíèòñÿ, åñëè âìåñòîìíîæåñòâà Γ âçÿòü êîíúþíêöèþ ñîñòàâëÿþùèõ åãî ôîðìóë,òàê ÷òî ìîæíî ðàññìàòðèâàòü òîëüêî îäíîýëåìåíòíûåìíîæåñòâà Γ è îïóñêàÿ ôèãóðíûå ñêîáêè, ïèñàòü A ` B .Çíàê ` ÿâëÿåòñÿ ñèìâîëîì îòíîøåíèÿ ïðåäïîðÿäêà íàìíîæåñòâå A.64 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÌîäåëè ÊðèïêåÏðîáëåìà âûâîäèìîñòè îäíà èç âàæíåéøèõ ïðîáëåì ëþáîãî ëîãè÷åñêîãîèñ÷èñëåíèÿ L: ¾âûâîäèìà ëè â L äàííàÿ ôîðìóëà?¿.` A ìîæíî ëèáî ïðåäúÿâèòü ñîîòâåòñòâóþùèé âûâîä, ëèáîäîêàçàòü åãî ñóùåñòâîâàíèå;6` A âîçìîæíî ëèøü äàòü äîêàçàòåëüñòâî íåñóùåñòâîâàíèÿâûâîäà A.Ìåòàòåîðèÿ òåîðèÿ, èçó÷àþùàÿ ÿçûê, ñòðóêòóðó è ñâîéñòâàíåêîòîðîé äðóãîé (ïðåäìåòíîé, èëè îáúåêòíîé) òåîðèè:êîððåêòíîñòü,íåïðîòèâîðå÷èâîñòü,ðàçëè÷íûå âèäû ïîëíîòû,ïðîáëåìà ðàçðåøèìîñòè,íåçàâèñèìîñòü ñèñòåì àêñèîì è ïðàâèë âûâîäà...65 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
