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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

a
x a u x = o a u x = a
x a
n
B = { b
1
, b
2
, . . . , b
m
} x
m = 2
n
n x
a ←[ x k ←[ 1
b = a u b
k
b = o b = a
k = n k ←[ k + 1
a ←[ b k = n k ←[ k + 1
a x
a < n
x, x u b
i
1
, x u b
i
1
u b
i
2
, . . .
y = x u b
i
1
u b
i
2
. . . u b
i
n
y u z = o y u z = y z ∈ B
y u x = x u y = x u (x u b
i
1
u b
i
2
. . . u b
i
n
) = x u b
i
1
u b
i
2
. . . u b
i
n
= y .
y x y ¤
a
1
a
2
a
1
u a
2
= o.
1.4. Òåîðåìà Ñòîóíà                                                                             15


1.4 Òåîðåìà Ñòîóíà
   Ñïðàâåäëèâà ñëåäóþùàÿ ôóíäàìåíòàëüíàÿ òåîðåìà î ïðåäñòàâëåíèè ïðîèçâîëüíûõ
áóëåâûõ àëãåáð àëãåáðàìè ìíîæåñòâ. Îíà ïîêàçûâàåò, ÷òî ýëåìåíòû ëþáîé áóëåâîé àë-
ãåáðû ìîæíî ñ÷èòàòü ïîäìíîæåñòâàìè íåêîòîðîãî ìíîæåñòâà, à áóëåâû îïåðàöèè îòîæ-
äåñòâëÿòü ñ îäíîèì¼ííûìè òåîðåòèêî-ìíîæåñòâåííûìè.

Òåîðåìà 1.3 (Ñòîóí). Âñÿêàÿ áóëåâà àëãåáðà èçîìîðôíà ïîäõîäÿùåé àëãåáðå ìíî-
æåñòâ.

   Èíûìè ñëîâàìè, òåîðåìà Ñòîóíà óòâåðæäàåò ñóùåñòâîâàíèå âëîæåíèÿ ëþáîé áóëå-
âîé àëãåáðû â íåêîòîðóþ òîòàëüíóþ àëãåáðó ìíîæåñòâ. Ìû äîêàæåì ýòó òåîðåìó äëÿ
êîíå÷íîãî ñëó÷àÿ. Äëÿ ýòîãî íàì ïîòðåáóþòñÿ ââåñòè íîâîå ïîíÿòèå.

Îïðåäåëåíèå 1.4. Íåíóëåâîé ýëåìåíò a áóëåâîé àëãåáðû íàçûâàåòñÿ àòîìîì, åñëè äëÿ
ëþáîãî å¼ ýëåìåíòà x ñïðàâåäëèâî ëèáî a u x = o, ëèáî a u x = a.  ïîñëåäíåì ñëó÷àå
ãîâîðÿò, ÷òî ýëåìåíò x ñîäåðæèò àòîì a.

   Íàïðèìåð, â áóëåâîé àëãåáðå âñåõ n-ìåðíûõ äâîè÷íûõ âåêòîðîâ àòîìû ñóòü äâîè÷íûå
íàáîðû åäèíè÷íîãî âåñà.  òîòàëüíîé àëãåáðå ìíîæåñòâ àòîìàìè áóäóò ÿâëÿòüñÿ âñå
îäíîýëåìåíòíûå ïîäìíîæåñòâà.

Ëåììà 1.3.  êîíå÷íîé áóëåâîé àëãåáðå êàæäûé íåíóëåâîé ýëåìåíò ñîäåðæèò õîòÿ
áû îäèí àòîì.

Äîêàçàòåëüñòâî. Ïóñòü B = { b1 , b2 , . . . , bm }  íîñèòåëü áóëåâîé àëãåáðû è x  åãî
íåíóëåâîé ýëåìåíò (â äàëüíåéøåì áóäåò óñòàíîâëåíî, ÷òî m = 2n äëÿ íåêîòîðîãî íàòó-
ðàëüíîãî n). Ïðèâåä¼ì àëãîðèòì, îáíàðóæèâàþùèé àòîì, ñîäåðæàùèéñÿ â x.

  Øàã 1. Ïîëîæèòü a ←[ x, k ←[ 1.
  Øàã 2. Âû÷èñëèòü b = a u bk . Åñëè b = o èëè b = a, òî ïåðåõîä ê øàãó 3, èíà÷å 
    ê øàãó 4.
  Øàã 3. Åñëè k = n, òî êîíåö. Èíà÷å k ←[ k + 1 è ïåðåõîä ê øàãó 2.
  Øàã 4. Ïîëîæèòü a ←[ b. Åñëè k = n, òî êîíåö, èíà÷å k ←[ k + 1 è ïåðåõîä ê øàãó
    2.

   Ïîñëå îêîí÷àíèÿ ðàáîòû àëãîðèòìà â a áóäåò çàïèñàí àòîì, ñîäåðæàùèéñÿ â x.  ñà-
ìîì äåëå, àëãîðèòì ïðîïóñêàåò ÷åðåç a êîíå÷íóþ (äëèíû < n ) ïîñëåäîâàòåëüíîñòü
íåíóëåâûõ ýëåìåíòîâ x, x u bi1 , x u bi1 u bi2 , . . ., ïîñëåäíèé èç êîòîðûõ

                                    y = x u bi1 u bi2 . . . u bin

îáëàäàåò òåì ñâîéñòâîì, ÷òî y u z = o èëè y u z = y äëÿ ëþáîãî z ∈ B . Êðîìå òîãî,

         y u x = x u y = x u (x u bi1 u bi2 . . . u bin ) = x u bi1 u bi2 . . . u bin = y .

Ýòî îçíà÷àåò, ÷òî y ñîäåðæèòñÿ â x è, òàêèì îáðàçîì, y  èñêîìûé àòîì.                           ¤



Óòâåðæäåíèå 1.2 (Îñíîâíîå ñâîéñòâî àòîìîâ). Åñëè a1 è a2  ðàçëè÷íûå àòîìû
áóëåâîé àëãåáðû, òî
                                           a1 u a2 = o.                                       (1.1)

Страницы