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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

z
z = x t y z = x z = y
h N, | i
J(P ) P
M P
m
J(M)
x P r M
J(M)
J(x) r {x}
J(x) r {x}
J(x) r {x}
J(M ∪ {x})
y {P rM}r{x}
J(M ∪ {x})
J(x) r {y}
J(M ∪ {x, y})
J(P )
Z
5
d
e
a
b
c
Z
5
n F
n+2
(n + 2)
|J(Z
5
)| = F
7
= 13
4.4. Äèñòðèáóòèâíûå ðåø¼òêè                                                       91


Îïðåäåëåíèå 4.8. Íåíóëåâîé ýëåìåíò z ðåø¼òêè íàçîâ¼ì íåðàçëîæèìûì (â îáúåäèíå-
íèå), åñëè èç z = x t y ñëåäóåò z = x èëè z = y .

  Î÷åâèäíî, íåðàçëîæèìûé ýëåìåíò íåëüçÿ çàïèñàòü â âèäå îáúåäèíåíèÿ ñòðîãî ñîäåð-
æàùèõñÿ â í¼ì ýëåìåíòîâ.
Ïðèìåð 4.8.   1. Àòîìû ëþáîé ðåø¼òêè íåðàçëîæèìû, è â àòîìíîé áóëåâîé àëãåáðå íåò
     äðóãèõ íåðàçëîæèìûõ ýëåìåíòîâ.  ðåø¼òêå h N, | i íåðàçëîæèìû â òî÷íîñòè ñòå-
     ïåíè ïðîñòûõ ÷èñåë.
  2. Â öåïè íè îäèí ýëåìåíò íå ÿâëÿåòñÿ ðàçëîæèìûì.
   Ðàíåå ìû ñòðîèëè ÷.ó. ìíîæåñòâî J(P ) äëÿ íåêîòîðîãî ÷.ó. ìíîæåñòâà P , ðàññìàòðè-
âàÿ âñå ïîðÿäêîâûå èäåàëû ïîñëåäíåãî è èõ âçàèìíûå âêëþ÷åíèÿ. Òåïåðü ìîæíî óêàçàòü
áîëåå ýôôåêòèâíûé àëãîðèòì ïîñòðîåíèÿ äèàãðàììû Õàññå äëÿ ðåø¼òêè ïîðÿäêîâûõ
èäåàëîâ êîíå÷íîãî ÷.ó. ìíîæåñòâà ïî äàííîé åãî äèàãðàììå Õàññå2 .
   Ïóñòü ìíîæåñòâî M ìèíèìàëüíûõ ýëåìåíòîâ êîíå÷íîãî ÷.ó. ìíîæåñòâà P èìååò
ìîùíîñòü m.

  1. Ïîñòðîèì äèàãðàììó êîíå÷íîé áóëåâîé àëãåáðû, èçîìîðôíîé J(M ).
  2. Âûáåðåì íåêîòîðûé ìèíèìàëüíûé ýëåìåíò x ìíîæåñòâà P r M è ïðèñîåäèíèì
     ê J(M ) íåðàçëîæèìûé â îáúåäèíåíèå ýëåìåíò, ñîäåðæàùèé ïîðÿäêîâûé èäåàë
     J(x) r {x}.
  3. Äîáàâèì âñå íåîáõîäèìûå îáúåäèíåíèÿ ýëåìåíòîâ, ñîäåðæàùèõ èäåàë J(x) r {x},
     ÷òîáû îíè îáðàçîâûâàëè áóëåâó àëãåáðó.
  4. Åñëè ñóùåñòâóþò ýëåìåíòû, ñîäåðæàùèå ìíîæåñòâî J(x) r {x} è ïîêðûâàþùèå
     ýëåìåíòû êîòîðûõ íå èìåþò îáúåäèíåíèé, òî èçîáðàçèì ïîñëåäíèå òàê, ÷òîáû îá-
     ðàçîâàëàñü áóëåâà àëãåáðà.
     Ïðîäîëæàÿ òàêèì îáðàçîì äî òåõ ïîð, ïîêà êàæäîå ìíîæåñòâî ýëåìåíòîâ, ñîäåð-
     æàùåå äàííûé ýëåìåíò íå áóäåò èìåòü îáúåäèíåíèÿ, ïîëó÷èì äèàãðàììó äèñòðè-
     áóòèâíîé ðåø¼òêè J(M ∪ {x}).
  5. Âûáåðåì íåêîòîðûé ìèíèìàëüíûé ýëåìåíò y ìíîæåñòâà {P rM }r{x} è ïðèñîåäè-
     íèì ê J(M ∪ {x}) íåðàçëîæèìûé â îáúåäèíåíèå ýëåìåíò, ñîäåðæàùèé ïîðÿäêîâûé
     èäåàë J(x) r {y}.
  6. Ïîâòîðÿÿ øàãè 3 è 4, ïîëó÷èì äèàãðàììó äèñòðèáóòèâíîé ðåø¼òêè J(M ∪ {x, y}).
  7. Ïðîäîëæàåì àíàëîãè÷íî, ïîêà íå ïîëó÷èì äèàãðàììó ðåø¼òêè J(P ).
Ïðèìåð 4.9. Ïîñòðîèì ïî ïðèâåä¼ííîìó àëãîðèòìó ðåø¼òêó ïîðÿäêîâûõ èäåàëîâ ÷.ó. ìíî-
æåñòâà Z5 çèãçàã, èçîáðàæ¼ííîãî íà ðèñ. 4.11. Ïîëó÷åííàÿ ðåø¼òêà èçîáðàæåíà


                                                  e [
                                            [
                                            d
                                             [      [
                                             
                                     a             b            c


                                   Ðèñ. 4.11: ×.ó. ìíîæåñòâî Z5

íà ðèñ. 4.12.
   Èçâåñòíî, ÷òî n-ýëåìåíòíûé çèãçàã èìååò Fn+2 ïîðÿäêîâûõ èäåàëîâ ( (n + 2)-å ÷èñëî
Ôèáîíà÷÷è). Íàïðèìåð, â íàøåì ñëó÷àå |J(Z5 )| = F7 = 13.
  2 Ïîäðîáíî   àëãîðèòì îïèñàí â ìîíîãðàôèè [15], ñ. 164-166.

Страницы