Лекции по упорядоченным множествам и универсальной алгебре. Гуров С.И. - 52 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

h N, | i
h 2
n
, 4 i
P n w(P ) = n P
n
P n
n
ρ : P → { 0, 1, . . . , n } ρ(x) = 0
x P ρ(y) = ρ(x) + 1 y
x
3 ρ(x) = k x
k
k P W
k
(P )
•
• • ◦
◦ • •
◦
P
max
k
W
k
(P ) = w(P ) .
max
k
W
k
(P ) = 3 w(P ) = 4 max
k
W
k
(P ) 6 w(P )
x h P, v i x
x
1
∈ P x v x
1
x v x
1
v . . .
P x
n
P x v x
n
¤
h N
1
f
, 4 i N
1
f
f(x
1
, x
2
, x
3
, x
4
, x
5
) = x
1
∨ x
2
x
3
∨ x
3
x
4
x
5
52                                           Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


h N, | i àíòèöåïüþ ÿâëÿåòñÿ ïðîèçâîëüíîå ïîäìíîæåñòâî ïîïàðíî íåêðàòíûõ ÷èñåë, à â
ìíîæåñòâå h 2n , 4 i  ñîâîêóïíîñòè âåðõíèõ íóëåé ëèáî íèæíèõ åäèíèö íåêîòîðîé (íå
òîæäåñòâåííîé êîíñòàíòàì) ìîíîòîííîé áóëåâîé ôóíêöèè. Îäíîýëåìåíòíîå ïîäìíîæå-
ñòâî ÷.ó. ìíîæåñòâà íàçûâàþò òðèâèàëüíîé àíòèöåïüþ.
    Ãîâîðÿò, ÷òî øèðèíà ÷.ó. ìíîæåñòâà P ðàâíà n (ñèìâîëè÷åñêè w(P ) = n ) åñëè â P
ñóùåñòâóåò àíòèöåïü, ñîäåðæàùàÿ n ýëåìåíòîâ, è íåò àíòèöåïåé, ñîäåðæàùèõ áîëüøåå
÷èñëî ýëåìåíòîâ.
    Åñëè êàæäàÿ ìàêñèìàëüíàÿ öåïü â P èìååò îäíó è òó æå äëèíó n, òî ãîâîðÿò, ÷òî
äàííîå ÷.ó. ìíîæåñòâî  ãðàäóèðîâàííîå (ðàíæèðîâàííîå) ðàíãà n.  ýòîì ñëó÷àå ñóùå-
ñòâóåò åäèíñòâåííàÿ ðàíãîâàÿ ôóíêöèÿ ρ : P → { 0, 1, . . . , n } òàêàÿ, ÷òî ρ(x) = 0, åñëè
x  ìèíèìàëüíûé ýëåìåíò P è ρ(y) = ρ(x) + 1, åñëè y íåïîñðåäñòâåííî ñëåäóåò çà
x. Íàïðèìåð, öåïü è áóëåàí, èçîáðàæ¼ííûå íà ðèñ. 3.1, ñóòü ãðàäóèðîâàííûå ìíîæåñòâà
ðàíãà 3, âåñ ïåðâîãî åñòü 1, à âòîðîãî  3. Åñëè ρ(x) = k , òî ãîâîðÿò, ÷òî ýëåìåíò x
èìååò ðàíã k . Ýëåìåíòû îäíîãî ðàíãà îáðàçóþò ñëîé ñîîòâåòñòâóþùåãî ãðàäóèðîâàííîãî
÷.ó. ìíîæåñòâà; ÷èñëî ýëåìåíòîâ â k -ì ñëîå ÷.ó. ìíîæåñòâà P îáîçíà÷èì Wk (P ).
    ßñíî, ÷òî ñëîé ÷.ó. ìíîæåñòâà åñòü àíòèöåïü. Îäíàêî íå âñÿêàÿ àíòèöåïü åñòü ñëîé:
íà ðèñ. 3.4 ïðåäñòàâëåíî ãðàäóèðîâàííîå ÷.ó. ìíîæåñòâî, ó êîòîðîãî ýëåìåíòû ìàêñè-
ìàëüíîé àíòèöåïè, îáîçíà÷åííûå •, íå ïðèíàäëåæàò êàêîìó-òî îäíîìó ñëîþ.


                                •   [[ •          ◦   [[
                                      [                 [
                                         ◦   [[ •    •

                                               [ 
                                                  ◦


             Ðèñ. 3.4: ×.ó. ìíîæåñòâî, íå îáëàäàþùåå ñâîéñòâîì Øïåðíåðà

   Ãîâîðÿò, ÷òî êîíå÷íîå ãðàäóèðîâàííîå ÷.ó. ìíîæåñòâî P îáëàäàåò ñâîéñòâîì Øïåð-
íåðà, åñëè
                                max Wk (P ) = w(P ) .
                                     k

×.ó. ìíîæåñòâî, èçîáðàæ¼ííîå íà ðèñ. 3.4 íå îáëàäàåò ñâîéñòâîì Øïåðíåðà, ò.ê. ó íåãî
max Wk (P ) = 3, à w(P ) = 4. Ïðè ýòîì ÿñíî, ÷òî âñåãäà max Wk (P ) 6 w(P ).
 k                                                           k

Òåîðåìà 3.3.  êîíå÷íîì ÷.ó. ìíîæåñòâå êàæäûé ýëåìåíò ñîäåðæèòñÿ â íåêîòîðîì
ìàêñèìàëüíîì ýëåìåíòå è ñîäåðæèò íåêîòîðûé ìèíèìàëüíûé ýëåìåíò.

Äîêàçàòåëüñòâî. Ïóñòü x  ïðîèçâîëüíûé ýëåìåíò ÷.ó. ìíîæåñòâà h P, v i. Åñëè x íå
ìàêñèìàëåí, òî íàéä¼òñÿ òàêîé ýëåìåíò x1 ∈ P , ÷òî x v x1 . Ïîâòîðÿÿ ðàññóæäåíèÿ
äëÿ íîâûõ ýëåìåíòîâ, ïîëó÷àåì âîçðàñòàþùóþ öåïü x v x1 v . . .. Ïîñêîëüêó ìíîæåñòâî
P êîíå÷íî, òî è äàííàÿ öåïü êîíå÷íà. ż ïîñëåäíèé ýëåìåíò xn , ïî îïðåäåëåíèþ áóäåò
ìàêñèìàëüíûì ýëåìåíòîì P è x v xn .
   Äëÿ íàõîæäåíèÿ ìèíèìàëüíîãî ýëåìåíòà ðàññóæäåíèÿ àíàëîãè÷íû, ïðè ýòîì ñòðîèò-
ñÿ óáûâàþùàÿ öåïü.                                                                ¤


Ïðèìåð 3.5.  1. Ðàññìîòðèì ÷.ó. ìíîæåñòâî h Nf1 , 4 i, ãäå Nf1  ìíîæåñòâî åäèíè÷íûõ
    íàáîðîâ ìîíîòîííîé áóëåâîé ôóíêöèè f (x1 , x2 , x3 , x4 , x5 ) = x1 ∨ x2 x3 ∨ x3 x4 x5 .

Страницы