Единое окно доступа к образовательным ресурсам

Лекции по упорядоченным множествам и универсальной алгебре: Учебно-методическое пособие

Голосов: 0

В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам pi решёткам. Изучаются свойства модулярных, дистрибутивных решёток и решёток с дополнениями. Указанным разделам посвящены первые главы. В последней главе рассматриваются универсальные алгебры. Вводится понятие алгебраической системы, рассматриваются различные типы таких систем и доказываются основные теоремы об их изоморфизме и гомоморфизме. Вводимые понятия и доказанные утверждения иллюстрируются большим количеством примеров. Пособие предназначено для студентов, изучающих соответствующие разделы алгебры и может быть использовано при самообразовании. Электронная версия пособия размещена на сайте факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова <a href="http://www.cs.msu.su" target="_blank">(www.cs.msu.su)</a>.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    5.2. Áóëåâû êîëüöà è ñòðóêòóðû                                                     101


àëãåáðó. Åäèíèöåé â íåé áóäåò âåñü èíòåðâàë (0, 1], à íóë¼ì  ïóñòîå ìíîæåñòâî, ïðåä-
ñòàâëÿåìîå â âèäå (x, x]. Ëåãêî âèäåòü, ÷òî ýòà àëãåáðà íå èìååò àòîìîâ: ëþáîé èíòåðâàë
(x, y] ðàññìàòðèâàåìîãî âèäà ñîäåðæèò â ñåáå íåíóëåâîé ïîäûíòåðâàë òàêîãî æå âèäà.
    Ïðèâåä¼ì áåç äîêàçàòåëüñòâà ñëåäóþùåå óòâåðæäåíèå: âñÿêàÿ ïîëíàÿ íåàòîìíàÿ áó-
ëåâà àëãåáðà áóäåò ïðåäñòàâèìà â âèäå ïðÿìîãî ïðîèçâåäåíèÿ ïîëíûõ àòîìíîé è áåç-
àòîìíîé áóëåâûõ àëãåáð, êîòîðûå íàçûâàþò äèñêðåòíîé è íåïðåðûâíîé êîìïîíåíòàìè
ñîîòâåòñòâåííî.
    Â ï. 1.3 áûëî ââåäåíî ïîíÿòèå èçîìîðôèçìà áóëåâûõ àëãåáð. Äàäèì òåïåðü îïðåäåëå-
íèå áóëåâà ãîìîìîðôèçìà.
Îïðåäåëåíèå 5.2. Áóëåâ ãîìîìîðôèçì  ýòî îòîáðàæåíèå îäíîé áóëåâîé àëãåáðû â
äðóãóþ, ñîãëàñîâàííîå ñî âñåìè ïÿòüþ áóëåâûìè îïåðàöèÿìè. Èíúåêòèâíûå áóëåâû ãî-
ìîìîðôèçìû íàçûâàþò áóëåâûìè ìîíîìîðôèçìàìè.

   Èç îïðåäåëåíèÿ âèäíî, ÷òî áóëåâ ãîìîìîðôèçì áóäåò áóëåâûì èçîìîðôèçìîì ïðè áè-
åêòèâíîñòè ñîîòâåòñòâóþùåãî îòîáðàæåíèÿ. ßñíî, ÷òî, â ÷àñòíîñòè, ïðè ëþáîì áóëåâîì
ãîìîìîðôèçìå ϕ îáÿçàòåëüíî èìååò ìåñòî ϕ(o) = o, ϕ(ι) = ι.
Ïðèìåð 5.1.  1. Ïóñòü B  àòîìíàÿ áóëåâà àëãåáðà è a  å¼ àòîì. Òîãäà îòîáðàæåíèå
    ja : B → 2 òàêîå, ÷òî
                                      1, x ñîäåðæèò a,
                            ja (x) =
                                      0, èíà÷å,
     åñòü ãîìîìîðôèçì.
  2. Èç òåîðåìû 1.4 (Ñòîóíà äëÿ êîíå÷íûõ áóëåâûõ àëãåáð) ñëåäóåò, ÷òî äëÿ ïðîèçâîëü-
     íîé êîíå÷íîé áóëåâîé àëãåáðû B , ñîäåðæàùåé n àòîìîâ ñïðàâåäëèâî B ∼ 2n .
                                                                           =
   Ïîíÿòíî, ÷òî ïðîèçâîëüíûé ðåø¼òî÷íûé ãîìîìîðôèçì îäíîé áóëåâîé àëãåáðû â äðó-
ãóþ ìîæåò íå áûòü áóëåâûì ãîìîìîðôèçìîì. Íàïðèìåð, åñëè A ⊂ B , òî åñòåñòâåííîå
âëîæåíèå P(A) â P(B) ÿâëÿåòñÿ ðåø¼òî÷íûì ìîíîìîðôèçìîì, íî íå áóëåâûì ãîìîìîð-
ôèçìîì, ò.ê. äëÿ ïðîèçâîëüíîãî ïîäìíîæåñòâà A åãî äîïîëíåíèÿ â A è B ðàçëè÷íû.
   Ïðîîáðàç íóëÿ ϕ (0) áóëåâà ãîìîìîðôèçìà ϕ íàçûâàþò åãî ÿäðîì (ÿñíî, ÷òî
ϕ (0) = Core(x) äëÿ x òàêîãî, ÷òî ϕ(x) = 0 ).
Îïðåäåëåíèå 5.3. Áóëåâà àëãåáðà B íàçûâàåòñÿ ïîäàëãåáðîé áóëåâîé àëãåáðû B (ñèì-
âîëè÷åñêè B     B ), åñëè B ⊆ B è íà B óñòîé÷èâû ñóæåíèÿ âñåõ îïåðàöèé B .

   Ïîíÿòíî, ÷òî áóëåâà àëãåáðà è å¼ ïîäàëãåáðà èìåþò îáùèå íóëè è åäèíèöû.
Ïðèìåð 5.2.   1. Áóëåâà àëãåáðà P2n ëîãè÷åñêèõ ôóíêöèé îò n ïåðåìåííûõ ÿâëÿåòñÿ
     ïîäàëãåáðîé àëãåáðû P2 âñåõ ëîãè÷åñêèõ ôóíêöèé (ñì. ïðèìåð 3).
  2. Ïóñòü A ⊂ B . Òîãäà P(A)    P(B), ïîñêîëüêó ýòè áóëåâû àëãåáðû èìåþò, íàïðè-
     ìåð, ðàçíûå åäèíè÷íûå ýëåìåíòû (÷òî âëå÷¼ò è íåñîâïàäåíèå äîïîëíåíèé äàííîãî
     ïîäìíîæåñòâà A â P(A) è â P(B) ).
    Íåïîñðåäñòâåííî èç îïðåäåëåíèé è ðàíåå äîêàçàííûõ ôàêòîâ ñëåäóåò, ÷òî åñëè
ϕ : B1 → B2  áóëåâ ãîìîìîðôèçì, òî ϕ(B1 )  B2 .


5.2 Áóëåâû êîëüöà è ñòðóêòóðû
Îïðåäåëåíèå 5.4. Àññîöèàòèâíîå êîëüöî R, îáëàäàþùèå ñâîéñòâîì x2 = x äëÿ ëþáîãî
ñâîåãî ýëåìåíòà x ∈ R íàçûâàåòñÿ áóëåâûì êîëüöîì.
Òåîðåìà 5.3. Áóëåâî êîëüöî R, +, ·, −, 0 , ãäå −  óíàðíàÿ îïåðàöèÿ âçÿòèÿ ïðîòè-
âîïîëîæíîãî ýëåìåíòà, êîììóòàòèâíî è x + x = 0 äëÿ âñåõ x ∈ R.


102                                                   Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


Äîêàçàòåëüñòâî. Äîêàæåì ñíà÷àëà âòîðîå óòâåðæäåíèå:

          x + x = (x + x)2 = x2 + x2 + x2 + x2 = x + x + x + x ⇒ x + x = 0
(ò.å. x = −x). Îòñþäà

       x + y = (x + y)2 = x2 + xy + yx + y 2 = x + xy + yx + y ⇒ xy + yx = 0
è äàëåå ïîëó÷àåì

                xy = xy + (yx + yx) = (xy + yx) + yx = 0 + yx = yx .



Òåîðåìà 5.4. Ïóñòü B =             B,   , , , o, ι     áóëåâà àëãåáðà. Äëÿ ëþáûõ x, y ∈ B
ïîëîæèì
                        x + y = (x       y )   (x    y) ,   x·y = x   y.
Òîãäà ÀÑ B∗ =      B, +, ·, o, ι   åñòü áóëåâî êîëüöî ñ åäèíèöåé.
Äîêàçàòåëüñòâî. Ñèìâîë · óìíîæåíèÿ áóäåì, êàê îáû÷íî, îïóñêàòü è ñ÷èòàòü åãî ïðèî-
ðèòåò âûøå ïðèîðèòåòà ñëîæåíèÿ +. Òîãäà x + y = xy     x y.
   Ðàâåíñòâî x2 = x, àññîöèàòèâíîñòü óìíîæåíèÿ, íàëè÷èå åäèíèöû è êîììóòàòèâíîñòü
îáåèõ îïåðàöèé î÷åâèäíû. Äàëåå, ïðèíèìàÿ âî âíèìàíèå çàêîíû áóëåâîé àëãåáðû, ïîëó-
÷èì

                    (x + y) + z = (xy    x y)z   (xy     x y) z =
                                = xy z    x yz    [(xy ) (x y) ]z =
                                = xy z    x yz    (x    y)(x y )z+ =
                                = xy z    x yz    x y z xyz ,
                    x + (y + z) = x(yz    y z)   x (y z yz ) =
                                = x(y z )(y z) x y z x yz =
                                = x(yz y z ) x y z x yz =
                                = xyz xy z      x y z x yz =
                                = (x + y) + z ,
                          x + o = xo    x o = xι = x ,
                          x + x = xx    x x = o,
ò.å. B îêàçûâàåòñÿ àáåëåâîé ãðóïïîé ïî ñëîæåíèþ +. Íàêîíåö,

                    (x + y)z = (xy    x y)z = xy z x yz .
                     xz + yz = xz(yz)    (xz) (yz) =
                             = xz(y    z ) (x     z )yz = xy z + x yz
è äèñòðèáóòèâíûé çàêîí · îòíîñèòåëüíî + äîêàçàí.
   Îñíîâíûì ïðèìåðîì áóëåâà êîëüöà è ÿâëÿåòñÿ êàê ðàç êîëüöî               P(A), ⊕, ∩, ∅, A ,
ïîëó÷àåìîå óêàçàííûì ñïîñîáîì èç òîòàëüíîé àëãåáðû ìíîæåñòâ.
Òåîðåìà 5.5. Ïóñòü R =             R, +, ·, 0, 1      áóëåâî êîëüöî ñ åäèíèöåé. Äëÿ ëþáûõ
x, y ∈ R ïîëîæèì
                   x    y = x + y + x · y,     x     y = x·y,   x = x + 1.
Òîãäà ÀÑ R∗ =      R,   , , , 0, 1       áóëåâà àëãåáðà.


5.2. Áóëåâû êîëüöà è ñòðóêòóðû                                                                        103


Äîêàçàòåëüñòâî. Àññîöèàòèâíîñòü îïåðàöèé     è , à òàêæå ðàâåíñòâî x x = x
ïðîâåðÿþòñÿ íåïîñðåäñòâåííî. Êîììóòàòèâíîñòü áóëåâà êîëüöà, óñòàíîâëåííàÿ òåîðå-
ìîé 5.4, îáåñïå÷èâàåò êîììóòàòèâíîñòü ýòèõ îïåðàöèé. Êðîìå òîãî, x + x = 0 ïî
òåîðåìå 5.3. Îïóñêàÿ ñèìâîë · è ñ÷èòàÿ åãî ïðèîðèòåò âûøå ïðèîðèòåòà +, ïîëó÷èì
x x = x + x + xx = x.
   Óñòàíîâèì ñïðàâåäëèâîñòü çàêîíîâ ïîãëîùåíèÿ:

                    (x   y)    x = (x + y + xy)x = xx + xy + xyx =
                                 = xx + xy + xy = x .
                    x    (x   y) = x + x · y + x · (x · y) = x + x · y + x · y = x .

Òàêèì îáðàçîì, R  ðåø¼òêà. ßñíî, ÷òî x · 1 = x è x · 0 = 0 äëÿ âñåõ x ∈ R, ò.å.
ðåø¼òêà R îáëàäàåò óíèâåðñàëüíûìè ãðàíÿìè. Èç ðàâåíñòâ

                xx = x(1 + x) = x · 1 + xx = x + x = 0 è
               x x = x (1 + x) = x + 1 + x + x(1 + x) = x + 1 + x + x + x = 1

âûòåêàåò, ÷òî R  ðåø¼òêà ñ äîïîëíåíèÿìè. Óäîñòîâåðèìñÿ â å¼ äèñòðèáóòèâíîñòè. Äåé-
ñòâèòåëüíî ðàâåíñòâà

   (x     y)    y = (x + y + x     y) · z = x · z + y · z + (x   z) · (y   z) = (x     z)   (x   z)

äîêàçûâàþò ïåðâûé äèñòðèáóòèâíûé çàêîí, à âòîðîé äîêàçûâàåòñÿ äâîéñòâåííî.
   Òàêèì îáðàçîì, ëþáîå áóëåâî êîëüöî ñ åäèíèöåé ìîæåò áûòü çàäàíî ñ ïîìîùüþ áó-
ëåâîé àëãåáðû è íàîáîðîò. Ëåãêî ïðîâåðÿåòñÿ, ÷òî ñïðàâåäëèâî
Ñëåäñòâèå. B∗∗ = B è R∗∗ = R.
   Òåì ñàìûì óñòàíàâëèâàåòñÿ ò.í. ñòîóíîâñêàÿ äâîéñòâåííîñòü ìåæäó áóëåâûìè àë-
ãåáðàìè è áóëåâûìè êîëüöàìè.
   Ââîäÿ îòíîøåíèå     ñî ñâîéñòâàìè (4.1) â ñèãíàòóðó ÀÑ êàê îñíîâíîå, îïðåäåëÿþò
áóëåâó ñòðóêòóðó B, , , , , o, ι , ãäå å¼ ðåäóêò B, , , , o, ι  áóëåâà àëãåá-
ðà. Äëÿ ìíîãèõ ïðèëîæåíèé óäîáíåå ðàññìàòðèâàòü íå áóëåâû àëãåáðû, à ñðàçó áóëåâû
ñòðóêòóðû1 .
   Ïîêàæåì òåïåðü, ÷òî ñïðàâåäëèâà ñëåäóþùàÿ
Òåîðåìà 5.6. Ýëåìåíò áóëåâîé àëãåáðû ÿâëÿåòñÿ àòîìîì, åñëè è òîëüêî åñëè îí íåïî-
ñðåäñòâåííî ñëåäóåò çà íóë¼ì.

Äîêàçàòåëüñòâî. Ñ îäíîé ñòîðîíû, åñëè ýëåìåíò a íåïîñðåäñòâåííî ñëåäóåò çà íóë¼ì áó-
ëåâîé àëãåáðû, òî ëþáîé å¼ äðóãîé ýëåìåíò x ëèáî ñîäåðæèò ýëåìåíò a, ëèáî íåñðàâíèì
ñ íèì.  ïåðâîì ñëó÷àå a x = a, à âî âòîðîì  a x = o, ò.å. a óäîâëåòâîðÿåò
îïðåäåëåíèþ àòîìà áóëåâîé àëãåáðû B .
   Ñ äðóãîé ñòîðîíû, åñëè b  ýëåìåíò B , ñòðîãî ñîäåðæàùèé íåíóëåâîé ýëåìåíò a, òî
a b = a = b è b íå ÿâëÿåòñÿ àòîìîì.
   Â áóëåâîé ñòðóêòóðå ëåãêî äîêàçûâàþòñÿ ëåììà 1.4 èç ï. 1.4.
   Ëåììà 1.4 óòâåðæäàåò, ÷òî âñÿêèé íåíóëåâîé ýëåìåíò êîíå÷íîé áóëåâîé àëãåáðû ìî-
æåò áûòü ïðåäñòàâëåí â âèäå îáúåäèíåíèÿ ñîäåðæàùèõñÿ â í¼ì àòîìîâ. Äåéñòâèòåëüíî,
äëÿ êîíå÷íîé áóëåâîé àëãåáðû êàê äèñòðèáóòèâíîé ðåø¼òêè ñïðàâåäëèâî óòâåðæäåíèå
  1   [18] äëÿ áóëåâîé ñòðóêòóðû ïðèâåäåíà (èçáûòî÷íàÿ) ñèñòåìà èç 37 àêñèîì.


104                                                 Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


ëåììû 4.2 î ïðåäñòàâëåíèè êàæäîãî íåíóëåâîãî ýëåìåíòà â âèäå îáúåäèíåíèÿ íåðàçëî-
æèìûõ ýëåìåíòîâ, à òàêîâûìè â áóëåâîé àëãåáðå ÿâëÿþòñÿ èñêëþ÷èòåëüíî àòîìû.
   Ïîñêîëüêó áóëåâà àëãåáðà ÿâëÿåòñÿ ìîäóëÿðíîé ðåø¼òêîé ñ äîïîëíåíèÿìè, òî äëÿ íå¼
ñïðàâåäëèâà òåîðåìà 4.23, ò.å. áóëåâà ñòðóêòóðà åñòü ðåø¼òêà ñ îòíîñèòåëüíûìè äîïîëíå-
íèÿìè, è â íåé åäèíñòâåííîå äîïîëíåíèå y ýëåìåíòà x ∈ [ a, b ] îòíîñèòåëüíî íåïóñòîãî
èíòåðâàëà [ a, b ] îïðåäåëÿþòñÿ ïî ôîðìóëå

                            y = a        (b   x ) = b        (a     x ).

Åñëè íà èíòåðâàëå [ a, b ], a  b ïî äàííîé ôîðìóëå îïðåäåëèòü îïåðàöèþ âçÿòèÿ äî-
ïîëíåíèÿ ˘, òî ÀÑ [ a, b ], , ,˘, a, b îêàçûâàåòñÿ áóëåâîé àëãåáðîé. Îòìåòèì, ÷òî ïî-
ëó÷åííàÿ áóëåâà àëãåáðà íå áóäåò (çà èñêëþ÷åíèåì ñîáñòâåííîãî ñëó÷àÿ a = o, b = ι )
ÿâëÿòüñÿ ïîäàëãåáðîé èñõîäíîé àëãåáðû ò.ê. ýòè àëãåáðû èìåþò, íàïðèìåð, ðàçëè÷íûå
óíèâåðñàëüíûå ãðàíè.
   Òàêæå ÷àñòî ðàññìàòðèâàþò áóëåâó ñòðóêòóðó ìíîæåñòâ P(A), ∪, ∩, − , ⊆, ∅, A
äîïîëíÿÿ òîòàëüíóþ àëãåáðó ìíîæåñòâ îòíîøåíèåì âêëþ÷åíèÿ ⊆.


5.3 Èäåàëû è ôèëüòðû â áóëåâîé àëãåáðå
    Èäåàëîì I áóëåâîé àëãåáðû B íàçûâàåòñÿ íåïóñòîå å¼ ïîäìíîæåñòâî, êîòîðîå óñòîé-
÷èâî îòíîñèòåëüíî îáúåäèíåíèÿ è âìåñòå ñ êàæäûì ñâîèì ýëåìåíòîì a ñîäåðæèò âñå
ýëåìåíòû B , ñîäåðæàùèåñÿ â a. ×àñòî ïîñëåäíåå óñëîâèå çàìåíÿþò ðàâíîñèëüíûì: åñëè
x ∈ I è b ∈ B , òî x b ∈ I . Åñëè I  èäåàë áóëåâîé àëãåáðû B , òî ïèøóò I B .
    Äâîéñòâåííî, ôèëüòðîì F áóëåâîé àëãåáðû B íàçûâàåòñÿ íåïóñòîå å¼ ïîäìíîæå-
ñòâî, êîòîðîå óñòîé÷èâî îòíîñèòåëüíî ïåðåñå÷åíèÿ è âìåñòå ñ êàæäûì ñâîèì ýëåìåíòîì
a ñîäåðæèò âñå ýëåìåíòû B , ñîäåðæàùèå a. Äâîéñòâåííî èäåàëàì, ÷àñòî ïîñëåäíåå óñëî-
âèå çàìåíÿþò ðàâíîñèëüíûì: åñëè x ∈ F è b ∈ B , òî x b ∈ F .
    Òàêèì îáðàçîì, èäåàëû I [ ôèëüòðû F ] áóëåâîé àëãåáðû  ýòî å¼ ðåø¼òî÷íûå èäåàëû
[ ôèëüòðû ]. Ïîýòîìó ýòîãî ñïðàâåäëèâî ñëåäóþùåå

Óòâåðæäåíèå 5.1 (Ñâîéñòâà áóëåâûõ èäåàëîâ è ôèëüòðîâ). Äëÿ ïðîèçâîëüíûõ
èäåàëà I è ôèëüòðà F áóëåâîé àëãåáðû B ñïðàâåäëèâû ñëåäóþùèå ñîîòíîøåíèÿ.
      1)   x ∈ I ⇔ x ⊆ I,                     x ∈ F ⇔ x ⊆ F;
              x∈I                                x∈F
      2)             ⇒ I = B,                            ⇒ F = B;
              x ∈I                               x ∈F
                           x∈I                                x∈F
      3)   x y∈I ⇒                ,           x y∈F ⇒                ;
                           y∈I                                y∈F
      4)   { x y | x ∈ I, y ∈ I }   B,        { x y | x ∈ F, y ∈ F } 
                                                      ôèëüòð B .

Äîêàçàòåëüñòâî.  ñèëó äâîéñòâåííîñòè äîñòàòî÷íî ïîêàçàòü ñïðàâåäëèâîñòü óòâåðæäå-
íèé îòíîñèòåëüíî èäåàëîâ. Äàëåå I è I1  ïðîèçâîëüíûå èäåàëû áóëåâîé àëãåáðû B .

 1) Åñëè x ∈ I è z ∈ x , òîãäà z              x    è ïî îïðåäåëåíèþ èäåàëà z = x   z ∈ I.
    Îáðàòíîå óòâåðæäåíèå î÷åâèäíî.
 2) Ïî îïðåäåëåíèþ èäåàëà ι = x                x   ∈ I , ïîýòîìó ïî ïðåäûäóùåìó ñâîéñòâó
    B = ι ⊂ I , ò.å. I = B .
 3)    x = x   (x   y) ∈ I è, àíàëîãè÷íî, y = y         (x        y) ∈ I .


5.3. Èäåàëû è ôèëüòðû â áóëåâîé àëãåáðå                                                          105


 4) Ïóñòü J = { x y | x ∈ I, y ∈ I1 }. Åñëè x1 y1 ∈ J è x2                 y2 ∈ J , ãäå x1 , x2 ∈ I è
    y1 , y2 ∈ I1 , òî x1 x2 ∈ I è y1 y2 ∈ I1 . Ñëåäîâàòåëüíî,

                      (x1   y1 )   (x2   y2 ) = (x1     x2 )    (y1   y2 ) ∈ J .

     Äàëåå, ïóñòü x   y ∈ J è z ∈ B , ãäå x ∈ I è y ∈ I1 . Òîãäà x             z∈I è y       z ∈ I1 .
     Ñëåäîâàòåëüíî,
                             (x    y)    z = (x    z)    (y     z) ∈ J .
   Íà èäåàëû è ôèëüòðû áóëåâîé àëãåáðû ïåðåíîñÿòñÿ ïîíÿòèÿ êîíå÷íîïîðîæä¼ííûõ,
ñîáñòâåííûõ, íåñîáñòâåííûõ è ãëàâíûõ èäåàëîâ è ôèëüòðîâ (ñì. ï. 4.2). Òàê, èäåàëû è
ôèëüòðû, îïèñàííûå â ïðåäûäóùåì ïðèìåðå â ï. 1  ãëàâíûå, à â ï. 2  íå ãëàâíûå è
äàæå íå êîíå÷íîïîðîæä¼ííûå. Ïîñêîëüêó áóëåâà àëãåáðà åñòü ðåø¼òêà, òî â êîíå÷íîé
áóëåâîé àëãåáðå âñå èäåàëû è ôèëüòðû  ãëàâíûå.
Ïðèìåð 5.3. Ðàññìîòðèì òîòàëüíóþ àëãåáðó ìíîæåñòâ P(A) íàä ìíîæåñòâîì A.

  1. Ïóñòü B ⊆ A. Òîãäà ñîâîêóïíîñòü âñåõ ïîäìíîæåñòâ ìíîæåñòâà A, ñîäåðæàùèõñÿ
     â B åñòü èäåàë áóëåâîé àëãåáðû P(A), à ñîäåðæàùèõ B åñòü ôèëüòð P(A). Ýòî 
     ãëàâíûå èäåàëû è ôèëüòðû â áåñêîíå÷íîé áóëåâîé àëãåáðå.
  2. Ïðèâåä¼ì ïðèìåð íåãëàâíûõ èäåàëîâ è ôèëüòðîâ. Ïóñòü A  áåñêîíå÷íîå ìíî-
     æåñòâî. Ñîâîêóïíîñòü P0 (A) âñåõ êîíå÷íûõ ïîäìíîæåñòâ A åñòü èäåàë áóëåâîé
     àëãåáðû P(A), à ñîâîêóïíîñòü ïîäìíîæåñòâ, èìåþùèõ êîíå÷íîå äîïîëíåíèå äî A
     åñòü ôèëüòð P(A). Ôèëüòð óêàçàííîãî âèäà íàçûâàþò ôèëüòðîì Ôðåøå.

   Ñïðàâåäëèâà ñëåäóþùàÿ ïðîñòàÿ

Òåîðåìà 5.7. Ïóñòü B  áóëåâà àëãåáðà è X        ⊆ B . Òîãäà ìíîæåñòâî
X = { x | x ∈ X } áóäåò èäåàëîì B , åñëè X  ôèëüòð B è ôèëüòðîì B , åñëè
X  èäåàë B .

  Èäåàëû [ ôèëüòðû ] óêàçàííîãî âèäà íàçûâàþòñÿ ïðèñîåäèí¼ííûìè ê ñîîòâåòñòâóþ-
ùèì ôèëüòðàì [ èäåàëàì ].
  Ïóñòü ∼  êîíãðóýíöèÿ íà áóëåâîé àëãåáðå B êàê íà ðåø¼òêå. Åñëè ïðè ýòîì åù¼ è

                                   x∼y ⇒ x ∼y ,

òî ∼  êîíãðóýíöèÿ íà äàííîé áóëåâîé àëãåáðå. Êîíãðóýíöèè áóëåâîé àëãåáðû B îá-
ðàçóþò ïîëíóþ äèñòðèáóòèâíóþ ðåø¼òêó Con B . ż íàèìåíüøèì ýëåìåíòîì ÿâëÿåòñÿ
òîæäåñòâåííàÿ êîíãðóýíöèÿ B , à íàèáîëüøèì  àìîðôíàÿ êîíãðóýíöèÿ B .
   Âàæíûì îòëè÷àåì èäåàëîâ áóëåâîé àëãåáðû îò ðåø¼òî÷íûõ ÿâëÿåòñÿ òî, ÷òî îíè íàõî-
äÿòñÿ âî âçàèìíî îäíîçíà÷íîì ñîîòâåòñòâèè ñ êîíãðóýíöèÿìè áóëåâîé àëãåáðû. Èìåííî,
åñëè ∼ = ∼I  êîíãðóýíöèÿ íà áóëåâîé àëãåáðå B è I = [ o ]  êëàññ ýêâèâàëåíòíîñòè,
ñîäåðæàùèé ýëåìåíò o, òî I  èäåàë B , ïðè÷¼ì âûïîëíÿåòñÿ ñîîòíîøåíèå

                            a ∼I b ⇔ ∃ x (a        x = b       x) .                            (5.1)
                                         I

È îáðàòíî, åñëè I     B , òî îòíîøåíèå ∼I íà B , îïðåäåë¼ííîå óñëîâèåì (5.1), áóäåò
êîíãðóýíöèåé íà B , ïðè÷¼ì [ o ] = I .

Óòâåðæäåíèå 5.2. Ïóñòü a è b  ýëåìåíòû áóëåâîé àëãåáðû B è I                        B.

                            a ∼I b ⇔ (a      b )   (a     b) ∈ I .


106                                                  Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


Äîêàçàòåëüñòâî. (⇒) Ïóñòü ñóùåñòâóåò x ∈ I òàêîé, ÷òî a x = b x. Òîãäà, áåðÿ
ïåðåñå÷åíèÿ ñ b îáåèõ ÷àñòåé ðàâåíñòâà, ïîëó÷èì (a x) b = (a b ) (x b ) = x b ,
ò.å. a b      x b ∈ I è a b ∈ I . Àíàëîãè÷íî a        b ∈ I è, ïî ñâîéñòâó èäåàëà,
(a b ) (a     b) ∈ I .
    (⇐) Ïóñòü (a b ) (a b) = z ∈ I . Òîãäà a b     z è a b    z , ò.å. a b = x ∈ I
è a b = y ∈ I . Îòêóäà, áåðÿ îáúåäèíåíèÿ ñ b îáåèõ ÷àñòåé ïåðâîãî ðàâåíñòâà è ñ
a  âòîðîãî ðàâåíñòâà, ïîëó÷àåì a b = x b è a b = y b ñîîòâåòñòâåííî. Îòñþäà
x b = y a.
   Åñëè ∼  êîíãðóýíöèÿ íà áóëåâîé àëãåáðå B , à I  èäåàë, ñîîòâåòñòâóþùèé äàí-
íîé êîíãðóýíöèè â óêàçàííîì âûøå ñìûñëå, òî ôàêòîðàëãåáðó B/ ∼ îáîçíà÷àþò B/I .
Ê ïðèìåðó, B/a ∼b [ o, a ].
                 =
   Èäåàëû è ôèëüòðû áóëåâîé àëãåáðû ñâÿçàíû ñ áóëåâûìè ãîìîìîðôèçìàìè.

Óòâåðæäåíèå 5.3. ßäðî áóëåâà ãîìîìîðôèçìà åñòü èäåàë. Ïðîîáðàç åäèíèöû áóëåâà
ãîìîìîðôèçìà åñòü ôèëüòð.

Äîêàçàòåëüñòâî.  ñèëó ïðèíöèïà äâîéñòâåííîñòè äëÿ áóëåâûõ àëãåáð äîñòàòî÷íî äîêà-
çàòü òîëüêî óòâåðæäåíèå îòíîñèòåëüíî èäåàëîâ.
   Ïóñòü ϕ  ãîìîìîðôèçì èç áóëåâîé àëãåáðû B â áóëåâó àëãåáðó B , x, y ∈ ϕ (0).
Ïðåæäå âñåãî, ïî ñäåëàííîìó ïðåäïîëîæåíèþ, ÿäðî ϕ (0) íåïóñòî. Êðîìå òîãî,
ϕ(x y) = ϕ(x)       ϕ(y) = o o = o. Äàëåå, åñëè b      x, òî ϕ(b)   ϕ(x). Ïîýòîìó
x y ∈ ϕ (0) è b ∈ ϕ (0). Òàêèì îáðàçîì, ϕ (0) B .
   Ìàêñèìàëüíûå ôèëüòðû áóëåâûõ àëãåáð íàçûâàþò óëüòðàôèëüòðàìè 2 .
   Ïîíÿòíî, ÷òî åñëè x  àòîì [ êîàòîì ] êîíå÷íîé áóëåâîé àëãåáðû, òî x [ x ]  å¼ ìàê-
ñèìàëüíûé ôèëüòð [ èäåàë ].  êîíå÷íûõ áóëåâûõ àëãåáðàõ óëüòðàôèëüòðû äðóãèõ âèäîâ,
î÷åâèäíî, îòñóòñòâóþò. Ñóùåñòâîâàíèå ìàêñèìàëüíûõ èäåàëîâ è ôèëüòðîâ â áåñêîíå÷íîé
áóëåâîé àëãåáðå ñëåäóåò èç òåîðåìû 4.7 î ñîáñòâåííûõ èäåàëàõ ðåø¼òêè ñ åäèíèöåé.

Òåîðåìà 5.8 (Òàðñêèé). Èäåàë I áóëåâîé àëãåáðû B ìàêñèìàëåí, åñëè è òîëüêî åñëè
B/I ∼b 2.
    =

Äîêàçàòåëüñòâî. Ïóñòü B  áóëåâà àëãåáðà, à I è J  äâà å¼ èäåàëà, ïðè÷¼ì I ⊆ J .
Ðàññìîòðèì { [j]I | j ∈ J }  ìíîæåñòâî ñìåæíûõ êëàññîâ [j]I ýëåìåíòîâ èç J ïî
èäåàëó I . Ýòî  èäåàë B/I è îí áóäåò íóëåâûì òîëüêî ïðè I = J . Ñëåäîâàòåëüíî,
óñëîâèå B/I ∼b 2 ýêâèâàëåíòíî ìàêñèìàëüíîñòè èäåàëà I .
             =

Òåîðåìà 5.9 (Ñâîéñòâà ìàêñèìàëüíûõ áóëåâûõ èäåàëîâ è ôèëüòðîâ).
  1. Êàæäûé ñîáñòâåííûé èäåàë [ ôèëüòð ] áóëåâîé àëãåáðû ñîäåðæèòñÿ â íåêîòîðîì
     ìàêñèìàëüíîì èäåàëå [ óëüòðàôèëüòðå ] 3 .
  2. Èäåàë [ ôèëüòð ] áóëåâîé àëãåáðû B ÿâëÿåòñÿ ìàêñèìàëüíûì, åñëè è òîëüêî åñëè
     äëÿ ëþáîãî x ∈ B â í¼ì ñîäåðæèòñÿ â òî÷íîñòè îäèí èç ýëåìåíòîâ x è x .
  2 Òî÷íåå,   óëüòðàôèëüòð áóëåâîé àëãåáðû B  ýòî å¼ ñîáñòâåííûé ôèëüòð F , óäîâëåòâîðÿþùèé óñëî-
âèþ
                                        ∀x (x ∈ F ∨ x ∈ F ) .
Îäíàêî, ïîíÿòèÿ ¾óëüòðàôèëüòð¿ è ¾ìàêñèìàëüíûé ôèëüòð¿ (êàê ñîáñòâåííûé ôèëüòð, íå ëåæàùèé íè
â êàêîì äðóãîì ñîáñòâåííîì ôèëüòðå) îêàçûâàþòñÿ ýêâèâàëåíòíûìè (ñì. íèæå). Ýòî ïîçâîëÿåò ìàêñè-
ìàëüíûå ôèëüòðû áóëåâûõ àëãåáð íàçûâàòü óëüòðàôèëüòðàìè, ÷òî òðàäèöèîííî è äåëàåòñÿ.
   3 Äàííîå óòâåðæäåíèå äëÿ ôèëüòðîâ ÷àñòî íàçûâàþò òåîðåìîé îá óëüòðàôèëüòðàõ áóëåâîé àëãåáðû.


5.3. Èäåàëû è ôèëüòðû â áóëåâîé àëãåáðå                                                  107


  3. Ñîáñòâåííûé èäåàë I [ ôèëüòð F ] áóëåâîé àëãåáðû B áóäåò ìàêñèìàëüíûì, åñëè
     è òîëüêî åñëè äëÿ ëþáûõ x, y ∈ B èç óñëîâèÿ (x y) ∈ I [ (x y) ∈ F ] ñëåäóåò,
     ÷òî ëèáî x, ëèáî y ïðèíàäëåæèò I [ F ] 4 .
  4. Ñîáñòâåííûé èäåàë [ ôèëüòð ] áóëåâîé àëãåáðû ñîâïàäàåò ñ ïåðåñå÷åíèåì âñåõ ìàê-
     ñèìàëüíûõ èäåàëîâ [ óëüòðàôèëüòðîâ ], â êîòîðûõ îí ñîäåðæèòñÿ.
  5. Ìàêñèìàëüíûé èäåàë [ ôèëüòð ] áóëåâîé àëãåáðû ñîäåðæèò âñå àòîìû [ êîàòîìû ]
     áóëåâîé àëãåáðû, êðîìå, áûòü ìîæåò, îäíîãî.

Äîêàçàòåëüñòâî.  ñèëó äâîéñòâåííîñòè äîñòàòî÷íî ïîêàçàòü ñïðàâåäëèâîñòü óòâåðæäå-
íèé îòíîñèòåëüíî èäåàëîâ.

  1. Äîêàçàòåëüñòâî äëÿ èäåàëîâ ñîâïàäàåò ñ ïðèâåä¼ííûì äëÿ òåîðåìû 4.7 î ñîáñòâåí-
     íûõ èäåàëàõ ðåø¼òêè ñ åäèíèöåé.
  2. Äîêàæåì äàííîå óòâåðæäåíèå äëÿ èäåàëîâ. Ïóñòü I  ìàêñèìàëüíûé èäåàë áóëå-
     âîé àëãåáðû B, , , , o, ι . Îí íå ìîæåò ñîäåðæàòü íè îäíîé ïàðû ýëåìåíòîâ x
     è x , ò.ê. èíà÷å x x = ι ∈ I ⇒ I = B , ò.å. I  íåñîáñòâåííûé èäåàë. Ïðîòèâî-
     ðå÷èå.
     Ïóñòü òåïåðü èäåàë I áóëåâîé àëãåáðû B , x ∈ B è I íå ñîäåðæèò íè x, íè x .
     Ðàññìîòðèì ìíîæåñòâî I1 = { x i | i ∈ I }. Ëåãêî âèäåòü, ÷òî I1  èäåàë è I ⊆ I1 ,
     ò.å. I íå ìàêñèìàëåí.
  3. (⇒) Ïóñòü èäåàë I áóëåâîé àëãåáðû B ìàêñèìàëåí, ò.å. B/I ∼b 2 = { o, ι }. Òîãäà
                                                                 =
     äëÿ ëþáîãî x ∈ B åãî ñìåæíûé êëàññ [x]I åñòü ëèáî o, ëèáî ι.  ïåðâîì ñëó÷àå
     x ∈ I , âî âòîðîì  x ∈ I .
     (⇐) Ïóñòü äëÿ ëþáîãî ýëåìåíòà áóëåâîé àëãåáðû B ëèáî îí, ëèáî åãî äîïîëíåíèå
     ñîäåðæèòñÿ â èäåàëå I B . Ïóñòü I ⊂ I1 B . Òîãäà äëÿ x ∈ I1 I èìååì x ∈ I1 ,
     îòêóäà x x = ι ∈ I1 , ò.å. I1 = B è èäåàë I  ìàêñèìàëüíûé.

   Äîêàçàòåëüñòâî îñòàëüíûõ óòâåðæäåíèé ìîæíî íàéòè, íàïðèìåð, â [8], [11], [13].
    Ñ ïîìîùüþ ôàêòîðèçàöèè ìîãóò áûòü ïîñòðîåíû áåçàòîìíûå áóëåâû àëãåáðû. Ðàñ-
ñìîòðèì P(Z), ∪, ∩, − , ∅, Z  òîòàëüíóþ àëãåáðó íàä ìíîæåñòâîì öåëûõ ÷èñåë Z.
Îïðåäåëèì îòíîøåíèå        íàä ýëåìåíòàìè P(Z): áóäåì ñ÷èòàòü, ÷òî A B , åñëè ñèììåò-
ðè÷åñêàÿ ðàçíîñòü ìíîæåñòâ A è B êîíå÷íà. ßñíî, ÷òî         åñòü îòíîøåíèå ýêâèâàëåíò-
íîñòè. Ïîýòîìó ìîæíî îáðàçîâàòü ôàêòîðìíîæåñòâî P(Z)/ . Âñå êîíå÷íûå (âêëþ÷àÿ
ïóñòîå) ïîäìíîæåñòâà P(Z) áóäóò, î÷åâèäíî, ýêâèâàëåíòíûìè. Îáîçíà÷èì ýòîò êëàññ ýê-
âèâàëåíòíîñòè [∅]. Òàêæå áóäóò ýêâèâàëåíòíûìè âñå ïîäìíîæåñòâà öåëûõ ÷èñåë, èìåþ-
ùèõ êîíå÷íûå äîïîëíåíèÿ äî Z, âêëþ÷àÿ ñàìî Z; ýòîò êëàññ ýêâèâàëåíòíîñòè îáîçíà÷èì
[Z]. Äàëåå, ëåãêî ïðîâåðèòü, ÷òî ââåäåííîå îòíîøåíèå ÿâëÿåòñÿ òàêæå è ñòàáèëüíûì îò-
íîñèòåëüíî òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé, ò.å. äëÿ ëþáûõ A, B ∈ P(Z) èç A         A
è B B ñëåäóåò A ∪ B          A ∪B , A∩B         A ∩B è A       A . Ýòî îçíà÷àåò, ÷òî ÀÑ
 P(Z)/ , ∪, ∩, − , [∅], [Z] áóäåò ÿâëÿòüñÿ áóëåâîé àëãåáðîé.
    Ëåãêî óáåäèòüñÿ, ÷òî äàííàÿ áóëåâà àëãåáðà íå èìååò àòîìîâ. Äåéñòâèòåëüíî, ëþáîé
îòëè÷íûé îò [∅] ýëåìåíò P(Z)/        åñòü êëàññ áåñêîíå÷íûõ ìíîæåñòâ. Àòîì  ýëåìåíò,
íåïîñðåäñòâåííî ñëåäóþùèé çà [∅], à òàêîâûå îòñóòñòâóþò â P(Z)/ : äåéñòâèòåëüíî, â
  4 Ñîáñòâåííûé   ôèëüòð F áóëåâîé àëãåáðû B , óäîâëåòâîðÿþùèé óñëîâèþ

                                                     x∈F
                                     (x   y) ∈ F ⇒
                                                     y∈F

íàçûâàåòñÿ ïðîñòûì. Òàêèì îáðàçîì äàííîå óòâåðæäåíèå äîêàçûâàåò ýêâèâàëåíòíîñòü ïîíÿòèé ¾óëü-
òðàôèëüòð¿ è ¾ïðîñòîé ôèëüòð¿ áóëåâîé àëãåáðû.


108                                                 Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


ëþáîì áåñêîíå÷íîì ìíîæåñòâå X ìîæíî (ñ ïîìîùüþ àêñèîìû âûáîðà!) óêàçàòü ïîäìíî-
æåñòâî Y òàêîå, ÷òî è îíî, åãî äîïîëíåíèå áåñêîíå÷íû, è ïîýòîìó [Y ] ñòðîãî ñîäåðæèòñÿ
â [X]. Ïîíÿòíî, ÷òî ïîäîáíàÿ ïðîöåäóðà ìîæåò áûòü ïðîâåäåíà äëÿ ëþáîé áåñêîíå÷íîé
àëãåáðû ìíîæåñòâ: åñëè M  áåñêîíå÷íîå ìíîæåñòâî, òî P(M )/P0 (M )  áåçàòîìíàÿ
áóëåâà àëãåáðà.
   Ãîâîðÿò, ÷òî ãëàâíûå óëüòðàôèëüòðû àëãåáðû ìíîæåñòâ, ïîñêîëüêó âñå îíè èìåþò âèä
a , ôèêñèðîâàíû â òî÷êå a ìíîæåñòâà. Èõ íàçûâàþò òðèâèàëüíûìè óëüòðàôèëüòðàìè.
Ñîâìåñòíî ñ ôèëüòðàìè Ôðåøå îíè èãðàþò âàæíóþ ðîëü ïðè èññëåäîâàíèè ñõîäèìîñòè â
àíàëèçå (òîïîëîãè÷åñêàÿ ñèñòåìà îêðåñòíîñòåé äàííîé òî÷êè ÿâëÿåòñÿ ôèêñèðîâàííûì â
íåé òðèâèàëüíûì óëüòðàôèëüòðîì). Ãëàâíûå óëüòðàôèëüòðû òàêæå èñïîëüçóþò, íàïðè-
ìåð, ïðè èññëåäîâàíèÿõ ïîëíîòû ëîãè÷åñêèõ ñèñòåì â àëãåáðàõ ËèíäåíáàóìàÒàðñêîãî,
ïîðîæä¼ííûõ ñîîòâåòñòâóþùåé ëîãè÷åñêîé òåîðèåé5 .
Ïðèìåð 5.4. Ðàññìîòðèì ìíîæåñòâî A = {A, B, . . .} ôîðìóë àëãåáðû ëîãèêè (ôîðìóë
íàä âûñêàçûâàíèÿìè). Åñëè A ≡ B åñòü òîæäåñòâåííî èñòèííàÿ ôîðìóëà, òî ãîâîðÿò,
÷òî ôîðìóëû A è B ëîãè÷åñêè ýêâèâàëåíòíû èëè ðàâíîñèëüíû, ÷òî çàïèñûâàþò êàê
A ∼ B . ßñíî, ÷òî ∼ åñòü îòíîøåíèå ýêâèâàëåíòíîñòè íà A. Êëàññ ýêâèâàëåíòíîñòè,
ïîðîæäàåìûé ôîðìóëîé A áóäåì îáîçíà÷àòü [A], êëàññû òîæäåñòâåííî èñòèííûõ ôîð-
ìóë  T, à òîæäåñòâåííî ëîæíûõ ôîðìóë  F.
   Íà ôàêòîðìíîæåñòâå A/ ∼ êëàññîâ ýêâèâàëåíòíîñòè ôîðìóë àëãåáðû ëîãèêè ìîæíî
çàäàòü òåîðåòèêî ìíîæåñòâåííûå îïåðàöèè äîïîëíåíèÿ (− ), îáúåäèíåíèÿ (∪) è ïåðåñå-
÷åíèÿ (∩), ïðè÷¼ì

                  [A] = [¬A],     [A] ∪ [B] = [A ∨ B],     [A] ∩ [B] = [A B].

   Ëåãêî óñòàíîâèòü, ÷òî ââåä¼ííûå îïåðàöèè íàä êëàññàìè ýêâèâàëåíòíîñòåé èìåþò
ñëåäóþùèå ñâîéñòâà:

      ˆ îïåðàöèè ∪ è ∩ êîììóòàòèâíû è âçàèìíî äèñòðèáóòèâíû;
      ˆ âûïîëíÿþòñÿ ñîîòíîøåíèÿ [A] ∪ F = [A] è [A] ∩ T = [A];
      ˆ ñïðàâåäëèâû çàêîíû [A] ∪ [A] = T è [A] ∩ [A] = F.

Óêàçàííîå îçíà÷àåò, ÷òî ÀÑ A/∼, ∪, ∩, − , T, F ÿâëÿåòñÿ áóëåâîé àëãåáðîé. ż íàçû-
âàþò ôàêòîðàëãåáðîé ëîãè÷åñêèõ ôîðìóë. Äëÿ êëàññè÷åñêîé àëãåáðû âûñêàçûâàíèé îíà
ñîâïàäàåò ñ ñîîòâåòñòâóþùåé àëãåáðîé ËèíäåíáàóìàÒàðñêîãî (â ïîñëåäíåé ôàêòîðèçà-
öèÿ ïðîâîäèòñÿ ïî îòíîøåíèþ      òàêîìó, ÷òî A     B åñëè è òîëüêî åñëè èç ôîðìóëû
A âûâîäèòñÿ ôîðìóëà B è íàîáîðîò). Ñ êàæäûì ýëåìåíòîì A/ ∼ ñâÿçàíà ñîîòâåòñòâó-
þùàÿ ôóíêöèÿ àëãåáðû ëîãèêè.
   Îáîçíà÷èì ÷åðåç An ìíîæåñòâî ôîðìóë àëãåáðû ëîãèêè íàä n ýëåìåíòàðíûìè âû-
ñêàçûâàíèÿìè. Î÷åâèäíî, An áåñêîíå÷íî, à ôàêòîðìíîæåñòâî An / ∼  êîíå÷íî (è ñî-
          n
äåðæèò 22 ýëåìåíòîâ).
   Ðàññìîòðèì óðàâíåíèå
                                  a(˜) · X(˜) = F,
                                    x      x
ãäå a(˜) è X(˜)  ôîðìóëû, ðåàëèçóþùèå ñîîòâåòñòâåííî èçâåñòíóþ è èñêîìóþ áóëåâû
      x      x
ôóíêöèè (äëÿ ïðîñòîòû óêàçûâàþò èìåííî ôîðìóëû, à íå ïîðîæä¼ííûå èìè êëàññû). Òî-
ãäà ðåøåíèåì äàííîãî óðàâíåíèÿ áóäåò ëþáàÿ ôóíêöèÿ, ðåàëèçóåìàÿ ôîðìóëàìè èç ãëàâ-
íîãî èäåàëà, ïîðîæä¼ííîãî ôîðìóëîé a(˜) â ñîîòâåòñòâóþùåé àëãåáðå Ëèíäåíáàóìà
                                          x
Òàðñêîãî.
   Íàïðèìåð, ïóñòü a(˜) = x1 x2 , ò.å. äàíî óðàâíåíèå
                      x

                                      x1 x2 X(x1 , x2 ) = F.                                   (∗)
   5 Ñì., íàïðèìåð, [11] èëè Ñ.È. Ãóðîâ. Èñ÷èñëåíèÿ âûñêàçûâàíèé êëàññè÷åñêîé ëîãèêè. Ó÷åáíîå ïîñî-
áèå  Ì.: Èçäàòåëüñêèé îòäåë ôàêóëüòåòà ÂÌèÊ èì. Ì.Â.Ëîìîíîñîâà; ÌÀÊÑ Ïðåññ, 2007.


5.3. Èäåàëû è ôèëüòðû â áóëåâîé àëãåáðå                                                             109


Èìååì x1 x2 = x1 ∨ x2 , è ãëàâíûé èäåàë àëãåáðû ËèíäåíáàóìàÒàðñêîãî, ïîðîæä¼ííûé
êëàññîì ôîðìóë [ x1 ∨ x2 ], ñîñòàâëÿþò êëàññû [ x1 ∨ x2 ], [ x1 ], [ x2 ], [ x1 x2 ∨ x1 x2 ], [ x1 x2 ],
[ x1 x2 ], [ x1 x2 ] è F. Íà ðèñ. 5.1 ïîêàçàí äàííûé èäåàë. Äëÿ êàæäîãî êëàññà óêàçàí âåêòîð
çíà÷åíèé ñîîòâåòñòâóþùåé ôóíêöèè (ïîäðàçóìåâàåòñÿ óïîðÿäî÷åíèå íàáîðîâ çíà÷åíèé
ïåðåìåííûõ ñíà÷àëà ïî x, çàòåì ïî y ).


                                              [ x1 ∨ x2 ]
                                                (0111)

                                  AA AAA
                   [ x1 ]
                              A A
                              AA            [ x1 x2 ∨ x1 x2 ]                  [ x2 ]

                                                                    AAA
                  (0011)                         (0110)                       (0101)
                                      AAA                          A
                              A A
                              AA
                                    A
                                                            AA AAA
                  [ x1 x2 ]                     [ x1 x2 ]                    [ x1 x2 ]

                                                                     AAA
                  (0010)                        (0001)                       (0100)

                                                                  AA
                                                            AA  AA
                                                   F
                                                (0000)


              Ðèñ. 5.1: Ãëàâíûé èäåàë L∗ , ïîðîæäåííûé êëàññîì êîíúþíêöèè
                                       2


   Ðåøåíèåì óðàâíåíèÿ (∗) áóäåò ëþáàÿ áóëåâà ôóíêöèÿ, ðåàëèçóþùàÿñÿ ôîðìóëàìè
èç ïðèâåä¼ííûõ êëàññîâ.
   áåñêîíå÷íûõ áóëåâûõ àëãåáðàõ, Èõ òàêæå íàçûâàþò ñâîáîäíûìè, ïîñêîëüêó îíè íå
ôèêñèðîâàíû íè â êàêîé òî÷êå èñõîäíîãî ìíîæåñòâà. Ïåðåñå÷åíèå âñåõ ýëåìåíòîâ òàêîãî
ôèëüòðà åñòü íóëåâîé ýëåìåíò.
Ïðèìåð 5.5. Îïèøåì â ñàìîì îáùåì âèäå, êàê ìîæåò áûòü ïîñòðîåí íåãëàâíûé óëüòðà-
ôèëüòð F áóëåàíà P(N) . Íà ïåðâîì øàãå ðàññìîòðèì ôèëüòð Ôðåøå, êîòîðûé îáî-
çíà÷èì F0 . Îí íå ÿâëÿåòñÿ ìàêñèìàëüíûì, ïîñêîëüêó, íàïðèìåð, íè ìíîæåñòâî ÷¼òíûõ
÷èñåë 2N, íè åãî äîïîëíåíèå (ìíîæåñòâî íå÷¼òíûõ ÷èñåë) íå ïðèíàäëåæàò F0 . Ïîýòî-
ìó íàäî ïðèíÿòü ðåøåíèå, îòíåñòè 2N ê êîíñòðóèðóåìîìó óëüòðàôèëüòðó F èëè íåò.
Ïóñòü ïðèíÿòî ðåøåíèå î òîì, ÷òî 2N ∈ F . Ýòî áóäåò îçíà÷àòü, ÷òî íåêîòîðûå äðóãèå
ìíîæåñòâà (âñå ìíîæåñòâà, ñîäåðæàùèå 2N ) òàêæå áóäóò ïðèíàäëåæàòü F . Ïîëó÷åííûé
ôèëüòð îáîçíà÷èì F1 . Ïîíÿòíî, ÷òî îí òàêæå íå áóäåò ÿâëÿòüñÿ èñêîìûì óëüòðàôèëü-
òðîì, ïîñêîëüêó îòíîñèòåëüíî ðÿäà ìíîæåñòâ íåîïðåäåë¼ííîñòü îñòàíåòñÿ: íàïðèìåð, íè
ìíîæåñòâî 3N, íè åãî äîïîëíåíèå íå ïðèíàäëåæàò F1 . Çäåñü ñíîâà íóæíî ïðèíÿòü ðå-
øåíèå î âõîæäåíèè îäíîãî èç óêàçàííûõ ìíîæåñòâ â F1 , ïîñòðîèòü F2 è ò.ä. Ïîêàçàíî,
÷òî â ðåçóëüòàòå âûïîëíåíèÿ òðàíñôèíèòíîãî ÷èñëà øàãîâ áóäåò ïîñòðîåí èñêîìûé
óëüòðàôèëüòð F .
   Õîòÿ ìû ïðèâåëè ÷ðåçâû÷àéíî ãðóáûé íàáðîñîê ñïîñîáà ïîñòðîåíèÿ ôèëüòðà F , íà-
äååìñÿ, ÷òî ÷èòàòåëþ âèäíà ðîëü àêñèîìû âûáîðà â äàííûõ ðàññóæäåíèÿõ: íèêàêîãî
ñïîñîáà óêàçàòü, êàêîå ìíîæåñòâî íóæíî ðàññìàòðèâàòü íà êàæäîì øàãå äëÿ âêëþ÷åíèÿ
åãî èëè åãî äîïîëíåíèÿ â F , íåò. Êðîìå òîãî, íà êàæäîì øàãå ìîæíî ïðèíÿòü ëþáóþ
èç óêàçàííûõ àëüòåðíàòèâ. Ìû âèäèì, ÷òî ïðîöåññ ïîñòðîåíèÿ F ñóùåñòâåííî íåîäíî-


110                                              Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


çíà÷åí, è, íà ñàìîì äåëå, äî ñèõ ïîð íå óêàçàíî íè îäíîãî íåãëàâíîãî óëüòðàôèëüòðà â
ÿâíîì âèäå, áåç ïðèìåíåíèÿ àêñèîìû âûáîðà.
   Íåãëàâíûå óëüòðàôèëüòðû íàä P(N) ìîãóò áûòü èñïîëüçîâàíû, íàïðèìåð, ïðè ïî-
ñòðîåíèè ïîëÿ ãèïåðäåéñòâèòåëüíûõ ÷èñåë â íåñòàíäàðòíîì àíàëèçå.
Ïðèìåð 5.6. Ìíîæåñòâî ãèïåðäåéñòâèòåëüíûõ ÷èñåë ∗ R, èçó÷àåìûõ â íåñòàíäàðòíîì àíà-
ëèçå, ïðåäñòàâëÿåò ñîáîé íåàðõèìåäîâî óïîðÿäî÷åííîå ïîëå, ÿâëÿþùååñÿ ðàñøèðåíèåì
ïîëÿ R äåéñòâèòåëüíûõ ÷èñåë6 . Ýòî îçíà÷àåò, ÷òî ∗ R  öåïü, â êîòîðóþ âëîæåíî ìíî-
æåñòâî R (îáðàç R  ñòàíäàðòíûå ãèïåðäåéñòâèòåëüíûå ÷èñëà) è ñîäåðæàùåå, êðîìå
òîãî, ìíîæåñòâî ò.í. íåñòàíäàðòíûõ ãèïåðäåéñòâèòåëüíûõ ÷èñåë. Ïðè ýòîì â ∗ R âûïîë-
íÿþòñÿ âñå àêñèîìû ïîëÿ, îäíàêî íå âûïîëíÿåòñÿ ñïðàâåäëèâàÿ â R àêñèîìà Àðõèìåäà :
¾äëÿ ëþáûõ äâóõ ïîëîæèòåëüíûõ ÷èñåë A è B ñóùåñòâóåò íàòóðàëüíîå n òàêîå, ÷òî
nA > B ¿.
   Ñîãëàñíî ïðèíöèïó íàñëåäîâàíèÿ ñâîéñòâ ïðè ðàñøèðåíèè, àêñèîìà Àðõèìåäà ìîæåò
íàðóøàòüñÿ ëèøü êîãäà õîòÿ áû îäíî èç ÷èñåë A è B íåñòàíäàðòíîå. Ñðåäè íåñòàí-
äàðòíûõ ÷èñåë âûäåëÿþò áåñêîíå÷íî áîëüøèå è áåñêîíå÷íî ìàëûå. Òàê, åñëè ÷èñëà ε è
I ñóòü ïîëîæèòåëüíûå áåñêîíå÷íî ìàëîå è áåñêîíå÷íî áîëüøîå ãèïåðäåéñòâèòåëüíûå, à
x  ïîëîæèòåëüíîå äåéñòâèòåëüíîå, òî íåðàâåíñòâà

                        ε + ... + ε > x      è      x + ... + x > I
                           n ðàç                       n ðàç

íå áóäóò âûïîëíÿòüñÿ íè äëÿ êàêîãî íàòóðàëüíîãî n.
    Ïîëå ãèïåðäåéñòâèòåëüíûõ ÷èñåë ∗ R ìîæíî ïîñòðîèòü, èñïîëüçóÿ íåêîòîðûé íåãëàâ-
íûé óëüòðàôèëüòð F â P(N). Ðàññìîòðèì âñåâîçìîæíûå ïîñëåäîâàòåëüíîñòè îáû÷-
íûõ äåéñòâèòåëüíûõ ÷èñåë. Áóäåì ãîâîðèòü, ÷òî ïîñëåäîâàòåëüíîñòè a = a1 , a2 , . . . è
b = b1 , b2 , . . .. ýêâèâàëåíòíû, åñëè ðàâåíñòâî ai = bi íàðóøàåòñÿ íà ìíîæåñòâå, íå ïðè-
íàäëåæàùåì F .
    Ëåãêî ïðîâåðÿåòñÿ, ÷òî, â ñèëó ñâîéñòâ óëüòðàôèëüòðîâ ââåä¼ííîå îòíîøåíèÿ äåé-
ñòâèòåëüíî ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè è, íàïðèìåð, âñå ïîñëåäîâàòåëüíîñòè,
îòëè÷àþùèåñÿ â êîíå÷íîì ÷èñëå ÷ëåíîâ, ýêâèâàëåíòíû. Ïîëó÷àþùèåñÿ êëàññû ýêâèâà-
ëåíòíîñòè íàçîâ¼ì ãèïåðäåéñòâèòåëüíûìè ÷èñëàìè; îíè è áóäóò ÿâëÿòüñÿ ýëåìåíòàìè
∗
  R. Äåéñòâèòåëüíîìó ÷èñëó a ñîîòâåòñòâóåò êëàññ ýêâèâàëåíòíîñòè [ a, a, . . . ], ýòî 
ñòàíäàðòíîå ãèïåðäåéñòâèòåëüíîå ÷èñëî.
    Àðèôìåòè÷åñêèå äåéñòâèÿ +, −, Ч è ч ïðîèçâîäÿòñÿ íàä ïîñëåäîâàòåëüíîñòÿìè
ïî÷ëåííî. Áóäåì ñ÷èòàòü, ÷òî a < b , åñëè íåðàâåíñòâî ai           bi âûïîëíÿåòñÿ íà êàêîì-
ëèáî ìíîæåñòâå, íå âõîäÿùåì â F .
    Íåòðóäíî ïðîâåðèòü, ÷òî, ïîñêîëüêó F  óëüòðàôèëüòð, ïîëó÷åíî óïîðÿäî÷åííîå
ïîëå. Â ýòîì ïîëå, îäíàêî, àêñèîìà Àðõèìåäà íå âûïîëíÿåòñÿ: íàïðèìåð, [ 1, 1 , 1 , . . . ]
                                                                                   2 3
åñòü áåñêîíå÷íî ìàëîå, à [ 1, 2, 3, . . . ]  áåñêîíå÷íî áîëüøîå ãèïåðäåéñòâèòåëüíûå ÷èñëà.
Ïðè ïðîâåðêå ýòèõ ñâîéñòâ è òðåáóåòñÿ, ÷òîáû F áûë íåãëàâíûì óëüòðàôèëüòðîì.


5.4 Áóëåâû ìíîãî÷ëåíû
Îïðåäåëåíèå 5.5. Ïóñòü Xn = { x1 , . . . , xn }  n -ýëåìåíòíîå ìíîæåñòâî íåèçâåñòíûõ
èëè ïåðåìåííûõ, íå ñîäåðæàùåå ñèìâîëîâ o è ι. Òîãäà áóëåâû ìíîãî÷ëåíû íàä Xn ñóòü
îáúåêòû, óäîâëåòâîðÿþùèå ñëåäóþùèì óñëîâèÿì:

 1) x1 , . . . , xn , 0, 1  áóëåâû ìíîãî÷ëåíû;
 2) åñëè p è q  áóëåâû ìíîãî÷ëåíû, òî òàêîâûìè ÿâëÿþòñÿ è (p) (q), (p) (q), (p) .
   6 Ýëåìåíòàðíîìó ââåäåíèþ â íåñòàíäàðòíûé àíàëèç ïîñâÿùåíà áðîøþðà Â.À. Óñïåíñêèé. ¾Íåñòàí-
äàðòíûé, èëè íåàðõèìåäîâ, àíàëèç¿.  Ì.: Çíàíèå, 1983, îòêóäà âçÿòû ýòîò è ïðåäûäóùèé ïðèìåðû.



    
Яндекс цитирования Яндекс.Метрика