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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    1.2. Àëãåáðû ìíîæåñòâ                                                                              11


Äîêàçàòåëüñòâî ïï. 1 è 3) ëåãêî ïðîâîäÿòñÿ ïî èíäóêöèè, à 2) ñëåäóåò èç 1).
    Èç ëåììû ñëåäóåò, ÷òî ïîëó÷àåìàÿ â ñîîòâåòñòâèè ñ îïðåäåëåíèåì ñîâîêóïíîñòü ñî-
ñòàâëÿþùèõ íåêîòîðîé ñèñòåìû ìíîæåñòâ íå çàâèñèò îò ïîðÿäêà âûáîðà ýòèõ ìíîæåñòâ
è, òàêèì îáðàçîì, îïðåäåëåíèå íàáîðà ñîñòàâëÿþùèõ êîððåêòíî.
    Èòàê, âñå ñîñòàâëÿþùèå ñèñòåìû ìíîæåñòâ ñóòü êîíñòèòóåíòû. Âûðàæåíèå FM , çà-
äàþùåå íåêîòîðîå ïîäìíîæåñòâî M àëãåáðû ìíîæåñòâ âèäå îáúåäèíåíèÿ ðàçëè÷íûõ
ýëåìåíòàðíûõ ïåðåñå÷åíèé íàçûâàåòñÿ íîðìàëüíîé ôîðìîé Êàíòîðà äëÿ M íàä ñîîò-
âåòñòâóþùèìè ïîïàðíî ðàçëè÷íûìè ìíîæåñòâàìè. Äâå íîðìàëüíûå ôîðìû Êàíòîðà,
îòëè÷àþùèåñÿ ïîðÿäêîì îáúåäèíåíèÿ ýëåìåíòàðíûõ ïåðåñå÷åíèé, áóäåì ñ÷èòàòü ýêâèâà-
ëåíòíûìè, ïîñêîëüêó îíè, î÷åâèäíî, çàäàþò îäíî è òîæå ìíîæåñòâî.
Òåîðåìà 1.1 (Âåíí). Åñëè â àëãåáðå ìíîæåñòâ áóëåâî ðàâåíñòâî âûïîëíåíî äëÿ íåêî-
òîðîé íåçàâèñèìîé ñèñòåìû ïîäìíîæåñòâ, òî îíî ñïðàâåäëèâî äëÿ ëþáîé ñèñòåìû
ïîäìíîæåñòâ.
Äîêàçàòåëüñòâî. Ðàññìîòðèì íåïóñòîå ìíîæåñòâî M , ïðåäñòàâëåííîå íîðìàëüíîé ôîð-
ìîé Êàíòîðà FM íàä íåçàâèñèìîé ñèñòåìîé ìíîæåñòâ X = {X1 , . . . , Xn } ( Xi ∈ U ,
i = 1, n ):
                                                      n
                                                             σ
               M = FM =                                     Xj j =                          sk .   (∗)
                           σ=(σ1 , ..., σn ) ∈NM ⊆ 2n j=1            k ∈IM ⊆{1, ..., 2n }

(çäåñü NM è IM  ñîîòâåòñòâóþùèå ìíîæåñòâó M ñîâîêóïíîñòè âåðøèí n-ìåðíîãî
åäèíè÷íîãî êóáà 2n è ìíîæåñòâà {1, . . . , 2n } íîìåðîâ ñîñòàâëÿþùèõ ñèñòåìû X ). Çà-
ìåòèì, ÷òî äëÿ çàâèñèìîé ñèñòåìû X óêàçàííîå ïðåäñòàâëåíèå ìîæåò îòñóòñòâîâàòü.
Òàêîå ïðåäñòàâëåíèå åäèíñòâåííî ñ ó÷¼òîì ââåä¼ííîé âûøå ýêâèâàëåíòíîñòè.
   Çàìåòèì, ÷òî åñëè s = ∅  ñîñòàâëÿþùàÿ êàêîé-ëèáî íåçàâèñèìîé ñèñòåìû ìíî-
æåñòâ, òî ëèáî s ⊆ M , ëèáî s ∩ M = ∅. Äàëåå, ñïðàâåäëèâîñòü x ∈ s ïîëíîñòüþ
îïðåäåëÿåò èñòèííîñòü x ∈ Xi äëÿ âñåõ i = 1, . . . , n. Â ñèëó ýòîãî ïðåäñòàâëåíèå (∗)
îñòà¼òñÿ ñïðàâåäëèâûì è åäèíñòâåííûì äëÿ ëþáîé ïðîèçâîëüíîé íåçàâèñèìîé ñèñòåìû
ìíîæåñòâ (äëÿ çàâèñèìîé ñèñòåìû ìîãóò ïîÿâèòüñÿ è äðóãèå ïðåäñòàâëåíèÿ). Ïîýòîìó
åñëè â íåçàâèñèìîé ñèñòåìå äâà áóëåâûõ âûðàæåíèÿ F1 è F2 èìåþò îäíè è òå æå ñî-
ñòàâëÿþùèå, òî ñïðàâåäëèâîñòü èëè íåñïðàâåäëèâîñòü ðàâåíñòâà F1 = F2 ñîõðàíèòñÿ è
â ëþáîé äðóãîé íåçàâèñèìîé ñèñòåìå.
   Èç òåîðåìû ñëåäóåò, ÷òî ðàâåíñòâî â àëãåáðå ìíîæåñòâ äîñòàòî÷íî ïðîâåðèòü íà îäíîé
äèàãðàììå Ýéëåðà-Âåííà ñ íåçàâèñèìîé ñèñòåìîé ìíîæåñòâ. Èõ è íàçûâàþò ìíîæåñòâà-
ìè îáùåãî ïîëîæåíèÿ. Èíòåðïðåòàöèÿ æå âûðàæåíèé ëþáîé áóëåâîé àëãåáðû ñîîòíîøå-
íèÿìè ìíîæåñòâ îáîñíîâûâàåòñÿ ïðèâåä¼ííîé íèæå òåîðåìîé 1.3.
   Îáúåäèíåíèå, ïåðåñå÷åíèå è äîïîëíåíèå áóäåì ñ÷èòàòü îñíîâíûìè òåîðåòèêî-
ìíîæåñòâåííûìè îïåðàöèÿìè. Îáû÷íî ââîäÿò è ïðîèçâîäíûå îïåðàöèè íàä ìíî-
æåñòâàìè. Íàïðèìåð, îïåðàöèÿ           (ðàçíîñòè ) ìíîæåñòâ X è Y îïðåäåëÿåòñÿ
êàê X      Y    = X ∩ Y , à îïåðàöèÿ ⊕ (èõ ñèììåòðè÷åñêîé ðàçíîñòè ) êàê
X ⊕ Y = (X ∩ Y ) ∪ (X ∩ Y ). Ëåãêî ïîêàçûâàåòñÿ, ÷òî X ⊕ Y = (X ∪ Y ) (X ∩ Y ). Â àë-
ãåáðå ìíîæåñòâ îáû÷íî èñïîëüçóþòñÿ ñëåäóþùèå ëåãêî ïðîâåðÿåìûå ñâîéñòâà óêàçàííûõ
ïðîèçâîäíûõ îïåðàöèé:

     X (Y Z) = (X Y ) ∪ (X ∩ Z) ;
     X (Y ∩ Z) = (X Y ) ∪ (X Z) ;
     X (Y ∪ Z) = (X Y ) ∩ (X Z) ;
     X ⊕ (Y ⊕ Z) = (X ⊕ Y ) ⊕ Z ;
     X ⊕Y = Y ⊕X;


12                                                                 Ãëàâà 1. Áóëåâû àëãåáðû


          (X ⊕ Y ) ∩ Z = (X ∩ Y ) ⊕ (Y ∩ Z) .

     Òàêæå ÷àñòî èñïîëüçóþò îòíîøåíèå ⊆ âêëþ÷åíèÿ ìíîæåñòâ. Î÷åâèäíî

                            X ⊆ Y ⇔ X ∩ Y = X ⇔ X ∪ Y = Y.

Ïðè X ⊆ Y , íàïîìíèì, X íàçûâàþò ïîäìíîæåñòâîì Y , à Y  íàäìíîæåñòâîì X .
    äàëüíåéøåì ìû áóäåì èñïîëüçîâàòü îáîçíà÷åíèå P ∗ (A) äëÿ ñîâîêóïíîñòè âñåõ íåïó-
ñòûõ ïîäìíîæåñòâ (íåïóñòîãî) ìíîæåñòâà A .


1.3 Èçîìîðôèçìû áóëåâûõ àëãåáð
   Õîòÿ àëãåáðû ìíîæåñòâ ÿâëÿþòñÿ, êàê ìû óâèäèì, â íåêîòîðîì ñìûñëå, îñíîâíûìè
ïðèìåðàìè áóëåâûõ àëãåáð, ïîñëåäíèå èìè íå èñ÷åðïûâàþòñÿ.
Ïðèìåð 1.3.   1. Ðàññìîòðèì äâîè÷íîå ìíîæåñòâî èñòèííîñòíûõ çíà÷åíèé B = {1, 0}
    è ñèãíàòóðó σ = ∨, , ¬, 0, 1 , ñîñòîÿùóþ èç ëîãè÷åñêèõ îïåðàöèé äèçúþíêöèè,
    êîíúþíêöèè è îòðèöàíèÿ, à òàêæå ñèìâîëîâ ýëåìåíòîâ B  ëîãè÷åñêîãî íóëÿ 0
    (¾ëîæü¿) è ëîãè÷åñêîé åäèíèöû 1 (¾èñòèíà¿). Ïîëó÷åííàÿ ÀÑ B, σ ÿâëÿåò-
    ñÿ, êàê íåòðóäíî âèäåòü, áóëåâîé àëãåáðîé. Ýòà ïðîñòåéøàÿ áóëåâà àëãåáðà èãðàåò
    ôóíäàìåíòàëüíóþ ðîëü â ëîãèêå. Îíà íàçûâàåòñÿ àëãåáðîé âûñêàçûâàíèé ; áóäåì
    îáîçíà÷àòü å¼ 2. Çàìåòèì, ÷òî Cmp è Isl (îñíîâíûå çàêîíû, îïèñûâàþùèå ñâîé-
    ñòâà äîïîëíåíèÿ) â ëîãèêå íàçûâàþòñÿ ñîîòâåòñòâåííî çàêîíàìè ¾èñêëþ÷åííîãî
    òðåòüåãî¿ è ¾ïðîòèâîðå÷èÿ¿.
     2. ÀÑ 2n , ∨, , ¬, 0, 1 , ãäå 2n  n-ìåðíûé åäèíè÷íûé êóá, 0 = (0 . . . 0),
        1 = (1 . . . 1), à ñèãíàòóðíûå îïåðàöèè ïðèìåíÿþòñÿ ê áóëåâûì âåêòîðàì ïîêîì-
        ïîíåíòíî, íàçûâàþò áóëåâîé àëãåáðîé n-ìåðíûõ äâîè÷íûõ âåêòîðîâ.
     3. Îáîçíà÷èì ÷åðåç P2 ìíîæåñòâî âñåõ äâóçíà÷íûõ áóëåâûõ ôóíêöèé, à ÷åðåç 0 è
        1  ôóíêöèè ¾òîæäåñòâåííûé íóëü¿ è ¾òîæäåñòâåííàÿ åäèíèöà¿ ñîîòâåòñòâåííî.
        Òîãäà ÀÑ P2 , ∨, , ¬, 0, 1 åñòü áóëåâà àëãåáðà. ż íàçûâàþò áóëåâîé àëãåáðîé
        ëîãè÷åñêèõ ôóíêöèé.
     4. Ïóñòü N  ñâîáîäíîå îò êâàäðàòîâ íàòóðàëüíîå ÷èñëî. Ýòî îçíà÷àåò, ÷òî ñïðàâåä-
        ëèâî ïðåäñòàâëåíèå N = p1 · . . . · pk , ãäå p1 , . . . , pk  ðàçëè÷íûå ïðîñòûå ÷èñëà.
        Ñîâîêóïíîñòü âñåõ íàòóðàëüíûõ äåëèòåëåé N îáîçíà÷èì D(N ). Íàïðèìåð, äëÿ
        N = 30 = 2 · 3 · 5 èìååì D(30) = {1, 2, 3, 5, 6, 10, 15, 30}.
        Íàèìåíüøåå îáùåå êðàòíîå ÷èñåë m è n îáîçíà÷èì m ∨ n, à èõ íàèáîëüøèé îáùèé
        äåëèòåëü  m ∧ n. Ïîëîæèì m = N . Òîãäà ÀÑ D(N ), ∨, ∧, , 1, N , êàê íåòðóä-
                                           m
        íî ïðîâåðèòü, åñòü áóëåâà àëãåáðà. Äàííàÿ áóëåâà àëãåáðà øèðîêî èñïîëüçóåòñÿ â
        òåîðèè ÷èñåë7 .
     5. Ðàññìîòðèì ìíîæåñòâî ýëåêòðè÷åñêèõ âûêëþ÷àòåëåé, èëè êîíòàêòîâ, êîòîðûå ìî-
        ãóò íàõîäèòüñÿ â îäíîì èç äâóõ ñîñòîÿíèé  çàìêíóòîì (ïðîâîäÿùåì) èëè ðàçî-
        ìêíóòîì (íå ïðîâîäÿùåì). Ó òàêèõ êîíòàêòîâ ðàçëè÷àþò âõîäíîé è âûõîäíîé ïîëþ-
        ñû, êîòîðûå ìîæíî ñîåäèíÿòü ñ ïîëþñàìè äðóãèõ êîíòàêòîâ, ñòðîÿ ýëåêòðè÷åñêèå
        äâóõïîëþñíûå (îäèí âõîä è îäèí âûõîä) öåïè.
          Åñëè ñîåäèíÿòü äðóã ñ äðóãîì òîëüêî âõîäíûå è âûõîäíûå ïîëþñû, òî èìååòñÿ
          òîëüêî äâà ñïîñîáà îáúåäèíåíèÿ òàêèõ öåïåé: ïîñëåäîâàòåëüíîå è ïàðàëëåëüíîå.
          Ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèåì öåïåé A è B âûõîäíîé ïîëþñ öåïè A ïðèñî-
          åäèíÿåòñÿ ê âõîäíîìó ïîëþñó öåïè B , ïðè ïàðàëëåëüíîì  ïîïàðíî îáúåäèíÿþòñÿ
          âõîäíûå è âûõîäíûå öåïè A è B (â îáîèõ ñëó÷àÿõ âõîäíîé è âûõîäíîé ïîëþñû
     7Â
      ÷àñòíîñòè, îòñþäà ñëåäóåò, ÷òî ìàêñèìàëüíîå ÷èñëî âçàèìíî ïðîñòûõ äåëèòåëåé ñâîáîäíîãî îò
                          N
êâàäðàòîâ ÷èñëà N åñòü [N/2]


1.3. Èçîìîðôèçìû áóëåâûõ àëãåáð                                                               13


     ïîëó÷åííîé öåïè îïðåäåëÿþòñÿ âõîäíûì ïîëþñîì A è âûõîäíûì ïîëþñîì B ñî-
     îòâåòñòâåííî). Òàêèì îáðàçîì, ïîëó÷àþò êëàññ ò.í. ïàðàëëåëüíî-ïîñëåäîâàòåëüíûõ
     êîíòàêòíûõ ñõåì. Èõ åù¼ íàçûâàþò π -ñõåìàìè.
     Ïîä ïðîèçâåäåíèåì A · B áóäåì ïîíèìàòü öåïü, îáðàçîâàííóþ ïîñëåäîâàòåëüíûì,
     à ïîä ñóììîé A + B  ïàðàëëåëüíûì ñîåäèíåíèåì öåïåé A è B . Ïîä öåïüþ A
     áóäåì ïîíèìàòü öåïü, ïîëó÷åííóþ ðàçìûêàíèåì âñåõ çàìêíóòûõ êîíòàêòîâ A è
     çàìûêàíèåì âñåõ å¼ ðàçîìêíóòûõ êîíòàêòîâ.
     Ïðîâîäèìîñòü äâóõïîëþñíîé öåïè ìîæåò áûòü îïèñàíà íåêîòîðîé áóëåâîé ôóíêöè-
     åé, òî÷íåå  ôóíêöèåé, ïðåäñòàâèìîé ò.í. áåñïîâòîðíîé ôîðìóëîé íàä ìíîæåñòâîì
     ëîãè÷åñêèõ ñâÿçîê {∨, , ¬}, ñîîòâåòñòâóþùèõ îïåðàöèÿì {+, ·, − , }, â êîòîðîé
     êàæäîìó êîíòàêòó öåïè ñîîòâåòñòâóåò âûðàæàþùàÿ åãî ïðîâîäèìîñòü ïðîïîçèöè-
     îíàëüíàÿ ïåðåìåííàÿ, âñòðå÷àþùàÿñÿ â ôîðìóëå ðîâíî îäèí ðàç.
     Äâå öåïè áóäåì ñ÷èòàòü îäèíàêîâûìè, åñëè ìîæíî òàê ñîïîñòàâèòü êîíòàêòàì ïå-
     ðåìåííûå, ÷òî ïðè îäíîì è òîì æå ñîñòîÿíèè êîíòàêòîâ, ñîîòâåòñòâóþùèì îäíîé
     ïåðåìåííîé è âñåõ ïðîèçâîëüíûõ ñîñòîÿíèÿõ îñòàëüíûõ êîíòàêòîâ, îáå ðàññìàò-
     ðèâàåìûå öåïè ÿâëÿþòñÿ îäíîâðåìåííî ëèáî ïðîâîäÿùèìè, ëèáî íå ïðîâîäÿùèìè.
     Ââåäåííîå îòíîøåíèå, î÷åâèäíî, ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè íà ìíîæå-
     ñòâå öåïåé. Îáîçíà÷èì ÷åðåç I ïîñòîÿííî çàìêíóòûé, à ÷åðåç O  ïîñòîÿííî ðàçî-
     ìêíóòûé êîíòàêòû. Îáîçíà÷èì ÷åðåç C ìíîæåñòâî âñåõ ïîïàðíî íåýêâèâàëåíòíûõ
     π -ñõåì (äâóõïîëþñíûõ ýëåêòðè÷åñêèõ öåïåé). Òîãäà ÀÑ C, +, ·, − , O, I åñòü, êàê
     íåòðóäíî âèäåòü, áóëåâà àëãåáðà.
     Ïðèìåíåíèå ôîðìóëüíîãî àïïàðàòà áóëåâûõ àëãåáð äëÿ àíàëèçà è ñèíòåçà ýëåêòðè-
     ÷åñêèõ ñõåì èìååò îãðîìíîå ïðèêëàäíîå çíà÷åíèå.
   Ñèñòåìû äàííîãî ïðèìåðà ÿâëÿþòñÿ ïðåäñòàâëåíèÿìè èëè ðåàëèçàöèÿìè áóëåâîé
àëãåáðû.
Ïðèìåð 1.4.  1. Êðîìå ïàðàëëåëüíî-ïîñëåäîâàòåëüíûõ, ñóùåñòâóþò åù¼ ò.í. ìîñòèêî-
    âûå ñõåìû, êîãäà âõîäíûå èëè âûõîäíûå êîíòàêòû îäíîé öåïè ïðèñîåäèíÿåòñÿ ê
    âíóòðåííåìó ïîëþñó äðóãîé, îáðàçóÿ, òåì íå ìåíåå, äâóõïîëþñíóþ öåïü  ïðîñòåé-
    øàÿ ìîñòèêîâàÿ ñõåìà èçîáðàæåíà íà ðèñ. 1.1.



                                             [[
                                              ◦
                                          x1     x
                                           x
                                                       3


                                         • [       •
                                            [ 
                                               5


                                          x2    x     4
                                                   ◦


          Ðèñ. 1.1: Ìîñòèêîâàÿ ñõåìà (âõîäíîé è âûõîäíîé ïîëþñû âûäåëåíû)

     Ýòè ñõåìû íå ÿâëÿþòñÿ ïàðàëëåëüíî-ïîñëåäîâàòåëüíûìè è äëÿ èõ îïèñàíèÿ ÿçûê
     áóëåâîé àëãåáðû îêàçûâàåòñÿ íåäîñòàòî÷íûì: ¾íå óäà¼òñÿ òàê óñîâåðøåíñòâîâàòü
     îáû÷íûé áóëåâ àïïàðàò àëãåáðû ëîãèêè, äîáàâèâ ê íåìó åù¼ íåñêîëüêî (êîíå÷íîå
     ÷èñëî!) îïåðàöèé òàê, ÷òîáû îí ñòàë ñîäåðæàòü ñðåäñòâà äëÿ îïèñàíèÿ ñòðîåíèÿ
     íå òîëüêî ïàðàëëåëüíî-ïîñëåäîâàòåëüíûõ, íî è ìîñòèêîâûõ ñõåì, ïðèòîì îïèñà-
     íèÿ àäåêâàòíîãî, ò.å. òàêîãî, ïðè êîòîðîì êàæäîìó êîíòàêòó â ñõåìå ñîîòâåòñòâóåò
     ðîâíî îäíà áóêâà â ôîðìóëå, âûðàæàþùàÿ ïðîâîäèìîñòü äàííîé ñõåìû¿8 .
     Äåéñòâèòåëüíî, ïðîâîäèìîñòü ìîñòèêîâîé ñõåìû íà                       ðèñ. 1.1 îïèñû-
     âàåòñÿ  áóëåâîé  ôóíêöèåé,  êîòîðàÿ  ìîæåò  áûòü                      çàäàíà  ôîðìóëîé
   8 À.Â. Êóçíåöîâ. Î áåñïîâòîðíûõ êîíòàêòíûõ ñõåìàõ è áåñïîâòîðíûõ ñóïåðïîçèöèÿõ ôóíêöèé àëãåáðû
ëîãèêè // Òðóäû ìàòåì. èí-òà èì. Â.À. Ñòåêëîâà, ò. LI.  Ì.: 1958.


14                                                                 Ãëàâà 1. Áóëåâû àëãåáðû


       F = x1 (x3 ∨ (x4 x5 )) ∨ x2 (x4 ∨ (x3 x5 )), íå ÿâëÿþùåéñÿ áåñïîâòîðíîé, è
       íèêàêîå ýêâèâàëåíòíîå ïðåîáðàçîâàíèå F íå ïðèâåä¼ò, êàê ìîæíî ïîêàçàòü, ê
       áåñïîâòîðíîé ôîðìå íàä ìíîæåñòâîì ñâÿçîê {∨, , ¬}.
     2. Äëÿ äåéñòâèòåëüíûõ ÷èñåë a, b èç îòðåçêà [ 0, 1 ] ïîëîæèì
                    a ⊕ b = max {a, b},    a ⊗ b = min {a, b},     ⊕a = 1 − a.
       Ñèñòåìó [ 0, 1 ], ⊕, ⊗, ⊕, 0, 1 íàçûâàþò ìàêñèìèííîé àëãåáðîé. Îíà íå áóäåò ÿâ-
       ëÿòüñÿ áóëåâîé àëãåáðîé, ïîñêîëüêó â íåé íå âûïîëíÿþòñÿ çàêîíû Cmp è Isl .
       Îòìåòèì, ÷òî â ïðèâåä¼ííîé âûøå ñèñòåìå èç 21-îé àêñèîìû íå âûïîëíÿþòñÿ òîëüêî
       äàííûå çàêîíû. Ïîñëåäíåå äîêàçûâàåò èõ íåçàâèñèìîñòü îò îñòàëüíûõ è íåîáõîäè-
       ìîñòü èõ ïðèñóòñòâèÿ â ëþáîé ñèñòåìå àêñèîì äëÿ áóëåâîé àëãåáðû.
       Îòìåòèì, ÷òî äîïîëíåíèÿ â ìàêñèìèííîé àëãåáðå åäèíñòâåííû. Òàêèì îáðàçîì,
       óêàçàííàÿ ñòðóêòóðà ÷ðåçâû÷àéíî áëèçêà ê áóëåâîé àëãåáðå, íî åé âñ¼-òàêè íå ÿâ-
       ëÿåòñÿ.
Îïðåäåëåíèå 1.3. Ïóñòü äàíû äâå áóëåâû àëãåáðû B1 è B2 è âçàèìíîîäíîçíà÷íàÿ
ôóíêöèÿ ϕ : B1 → B2 òàêàÿ, ÷òî ðàâåíñòâà
        1) ϕ(x   y) = ϕ(x)   ϕ(y);   2) ϕ(x   y) = ϕ(x)    ϕ(y);     3) ϕ(x ) = ϕ(x)
ñïðàâåäëèâû äëÿ âñåõ x è y èç B1 . Òîãäà ãîâîðÿò, ÷òî ϕ  áóëåâ èçîìîðôèçì ìåæäó
B1 è B2 , äàííûå àëãåáðû áóëåâî èçîìîðôíû (ñèìâîëè÷åñêè B1 ∼b B2 ).
                                                            =
Çàìå÷àíèå. Ëåãêî ïîêàçàòü, ÷òî èç 1)  3) ñëåäóåò
                             4) ϕ(o) = o      è   5) ϕ(ι) = ι.
Äåéñòâèòåëüíî, èìååì ϕ(o) = ϕ(x x ) = ϕ(x) ϕ(x ) = ϕ(x) ϕ(x) = o è àíàëîãè÷íî
äëÿ ϕ(ι).
    Ìû âèäèì, ÷òî áóëåâ èçîìîðôèçì  ýòî âçàèìíîîäíîçíà÷íîå îòîáðàæåíèå íîñèòåëåé
áóëåâûõ àëãåáð, ñîõðàíÿþùåå îïåðàöèè è îñîáûå ýëåìåíòû o è ι.
     çàïèñè áóëåâûõ àëãåáð B1 è B2 ìû èñïîëüçîâàëè îäèíàêîâûå îáîçíà÷åíèÿ è äëÿ
ñîîòâåòñòâóþùèõ îïåðàöèé, è äëÿ âûäåëåííûõ ýëåìåíòîâ. Ñòðåìÿñü íå óñëîæíÿòü îáî-
çíà÷åíèÿ, òàê îáû÷íî è ïîñòóïàþò. Ïðè âíèìàòåëüíîì ÷òåíèè ïóòàíèöû îòíîñèòåëüíî
ïðèíàäëåæíîñòè îïåðàöèé è âûäåëåííûõ ýëåìåíòîâ ê îäíîé èëè äðóãîé àëãåáðå âîçíèê-
íóòü íå äîëæíî.
Ïðèìåð 1.5.          1. Àëãåáðà âûñêàçûâàíèé, î÷åâèäíî, èçîìîðôíà òðèâèàëüíîé àëãåáðå
      ìíîæåñòâ.
   2. Òîòàëüíàÿ àëãåáðà íàä n-ýëåìåíòíûì ìíîæåñòâîì A = {a1 , . . . , an } èçîìîðôíà
      áóëåâîé àëãåáðå n-ìåðíûõ äâîè÷íûõ âåêòîðîâ 2n . Áóëåâûì èçîìîðôèçìîì çäåñü
      áóäåò ÿâëÿåòñÿ îòîáðàæåíèå ϕ : 2n → P(A), ñòàâÿùåå â ñîîòâåòñòâèå áóëåâó âåêòîðó
      (α1 , . . . , αn ) ïîäìíîæåñòâî { aik | αik = 1, k = 1, n } ìíîæåñòâà A.
    Ñóùåñòâóåò ïðîñòîé êðèòåðèé èçîìîðôíîñòè òîòàëüíûõ àëãåáð ìíîæåñòâ.
Òåîðåìà 1.2. Äëÿ òîãî ÷òîáû òîòàëüíûå àëãåáðû ìíîæåñòâ P(A) è P(B) áûëè
èçîìîðôíû, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû A è B èìåëè îäèíàêîâóþ ìîùíîñòü.
Äîêàçàòåëüñòâî. (⇐) Ïóñòü ñóùåñòâóåò èçîìîðôèçì ϕ ìåæäó àëãåáðàìè P(A) è P(B).
Òîãäà ϕ  âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ìíîæåñòâàìè A è B , îòêóäà ñëåäóåò
èõ ðàâíîìîùíîñòü.
   (⇒) Ïóñòü ìíîæåñòâà A è B ðàâíîìîùíû. Òîãäà ìåæäó èõ ýëåìåíòàìè ìîæíî óñòà-
íîâèòü âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå f . Îäíàêî, ýëåìåíòàìè P(A) è P(B) ñëóæàò
ïîäìíîæåñòâà A è B ñîîòâåòñòâåííî è f íå ÿâëÿåòñÿ èñêîìûì èçîìîðôèçìîì. Ïîýòîìó
ðàñïðîñòðàíèì îòîáðàæåíèå f íà ïîäìíîæåñòâà äàííûõ ìíîæåñòâ, ïîñòàâèâ â ñîîòâåò-
ñòâèå ïðîèçâîëüíîìó ïîäìíîæåñòâó X ìíîæåñòâà A åãî îáðàç ϕ(X) = a∈X f (a) ⊆ B .
Ïðîñòàÿ ïðîâåðêà ïîêàçûâàåò, ÷òî ϕ ÿâëÿåòñÿ áóëåâûì èçîìîðôèçìîì ìåæäó P(A) è
P(B).


1.4. Òåîðåìà Ñòîóíà                                                                                       15


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

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

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

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

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

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

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

  Øàã 1. Ïîëîæèòü a ← x, k ← 1.
  Øàã 2. Âû÷èñëèòü b = a 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 bi1 , x bi1 bi2 , . . ., ïîñëåäíèé èç êîòîðûõ

                                   y = x       bi1     bi2 . . .   bin

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

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

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

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


16                                                                              Ãëàâà 1. Áóëåâû àëãåáðû


Äîêàçàòåëüñòâî. Åñëè a1     a2 = b = o, òî ñîãëàñíî îïðåäåëåíèþ, äîëæíî áûòü b = a1 è
b = a2 .
   Áóëåâà àëãåáðà, â êîòîðîé êàæäûé íåíóëåâîé ýëåìåíò ñîäåðæèò àòîì, íàçûâàåòñÿ
àòîìíîé. Âñå ðàññìîòðåííûå âûøå àëãåáðû àòîìíûå. Èç ëåììû 1.3 ñëåäóåò, ÷òî êîíå÷-
íàÿ áóëåâà àëãåáðà ÿâëÿåòñÿ àòîìíîé. Áóëåâó àëãåáðó, íå ñîäåðæàùóþ íè îäíîãî àòîìà
íàçûâàþò áåçàòîìíîé èëè íåïðåðûâíîé. Ïðèìåð áåçàòîìíîé áóëåâîé àëãåáðû áóäåò ïðè-
âåä¼í â ï. 5.1.
   Ìíîæåñòâî âñåõ àòîìîâ, ñîäåðæàùèõñÿ â ýëåìåíòå x îáîçíà÷èì At(x) è ôîðìàëüíî
ñ÷èòàòü, ÷òî At(o) = ∅. Ñîâîêóïíîñòü âñåõ àòîìîâ áóëåâîé àëãåáðû B áóäåì îáîçíà÷àòü
At(B).
Ëåììà 1.4. Âñÿêèé íåíóëåâîé ýëåìåíò êîíå÷íîé áóëåâîé àëãåáðû ìîæåò áûòü ïðåä-
ñòàâëåí â âèäå îáúåäèíåíèÿ ñîäåðæàùèõñÿ â í¼ì àòîìîâ:

                                              x =               a.                                 (1.2)
                                                     a∈At(x)


   Íàïðèìåð, â òîòàëüíîé àëãåáðå íàä ìíîæåñòâîì {1, 2, 3, 4} ýëåìåíò x = {1, 2, 3}
ñîäåðæèò àòîìû {1}, {2}, {3} è ðàâåí èõ îáúåäèíåíèþ: x = {1} ∪ {2} ∪ {3}. Ïðè
At(x) = {a} ôîðìàëüíî ïîëàãàþò x = a, à ïðè At(x) = ∅  x = o. Ïîíÿòíî, ÷òî
åäèíèöà ι åñòü îáúåäèíåíèå âñåõ àòîìîâ áóëåâîé àëãåáðû.Äîêàçàòåëüñòâî ýòîé ïðîñòîé
ëåììû îòëîæèì äî ï. 5.2.
     Äëÿ êîíå÷íîãî ñëó÷àÿ òåîðåìà Ñòîóíà äîïóñêàåò ñëåäóþùåå óñèëåíèå.
Òåîðåìà 1.4. Âñÿêàÿ êîíå÷íàÿ áóëåâà àëãåáðà èçîìîðôíà ïîäõîäÿùåé òîòàëüíîé àëãåá-
ðå ìíîæåñòâ.
Äîêàçàòåëüñòâî. Ïóñòü B  êîíå÷íàÿ áóëåâà àëãåáðà. Ïîñòðîèì òîòàëüíóþ àëãåáðó ìíî-
æåñòâ íàä At(B) è ïîêàæåì, ÷òî îíà èçîìîðôíà B . Ïðè ýòîì áóäåì ïîñòîÿííî ïîëüçî-
âàòüñÿ óòâåðæäåíèåì ëåììû 1.4.
   Ðàññìîòðèì ôóíêöèþ ϕ, ñîïîñòàâëÿþùóþ êàæäîìó ýëåìåíòó x èç B ìíîæåñòâî
At(x) ñîäåðæàùèõñÿ â í¼ì àòîìîâ. Ïîêàæåì, ÷òî ϕ ÿâëÿåòñÿ èñêîìûì èçîìîðôèçìîì
ìåæäó B è P(At(B)).
   Óáåäèìñÿ ñíà÷àëà, ÷òî ϕ(x) = At(x)  áèåêöèÿ9 ìåæäó B è P(At(B)). Èç ðàçëîæå-
íèÿ 1.2 ñëåäóåò, ÷òî

 1) ýëåìåíò x îäíîçíà÷íî îïðåäåëÿåòñÿ ìíîæåñòâîì At(x) ñâîèõ àòîìîâ è íàîáîðîò,
    ò.å. îòîáðàæåíèå ϕ(x) èíúåêòèâíî;
 2) äëÿ ïðîèçâîëüíîãî ïîäìíîæåñòâà A àòîìîâ áóëåâîé àëãåáðû ìîæíî îïðåäåëèòü
    ýëåìåíò x ïî ñîîòíîøåíèåì x = a∈A a, òîãäà ϕ(x) = A è ϕ  ñþðúåêòèâíî.

Òàêèì îáðàçîì, áèåêòèâíîñòü îòîáðàæåíèÿ ϕ ïîêàçàíà.
   Òåïåðü óäîñòîâåðèìñÿ, ÷òî äëÿ ϕ âûïîëíåíû ñâîéñòâà (1)(3) îïðåäåëåíèÿ 1.3 (íè-
æåïðèâåä¼ííûå âûêëàäêè ïðîâåäåíû äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ x, y èç B ).
   Âî-ïåðâûõ, î÷åâèäíî, ÷òî

                      x    y =               a1                 a2 =                   a,
                                 a1 ∈At(x)          a2 ∈At(y)          a∈At(x)∪At(y)


îòêóäà ϕ(x    y) = ϕ(x) ∪ ϕ(y).
   9 ×èòàòåëþ èçâåñòíû ñâîéñòâà èíúåêòèâíîñòè, ñþðúåêòèâíîñòè è áèåêòèâíîñòè îòîáðàæåíèé. Èõ àë-
ãåáðàè÷åñêèå îïðåäåëåíèÿ áóäóò äàíû â ï. 2.6.


1.4. Òåîðåìà Ñòîóíà                                                                                         17


   Âî-âòîðûõ,
                                                   Dtr1                        (1.1)
          x   y =               a1               a2 =                 (a1   a2 ) =                     a,
                    a1 ∈At(x)        a2 ∈At(y)            a1 ∈At(x)                    a∈At(x)∩At(y)
                                                          a2 ∈At(y)



ò.å. ϕ(x y) = ϕ(x) ∩ ϕ(y).
    Â-òðåòüèõ, ïîäñòàâëÿÿ â ïîëó÷åííûå âûøå ðàâåíñòâà y = x èìååì

                    At(x) ∪ At(x ) = At(B)                è    At(x) ∩ At(x ) = ∅,

îòêóäà ïî ëåììå 1.1 At(x ) = At(B)               At(x) è ϕ(x ) = ϕ(x).
   Äîêàçàííàÿ òåîðåìà èìååò ñëåäóþùèå ïðîñòûå
Ñëåäñòâèÿ.     1. Åñëè êîíå÷íàÿ áóëåâà àëãåáðà èìååò n àòîìîâ, òî îáùåå ÷èñëî å¼
     ýëåìåíòîâ ðàâíî 2n .
  2. Ëþáàÿ êîíå÷íàÿ áóëåâà àëãåáðà èçîìîðôíà ïîäõîäÿùåé àëãåáðå n-ìåðíûõ äâîè÷íûõ
     âåêòîðîâ.
   Ïåðâîå ñëåäóåò èç òîãî, ÷òî ìîùíîñòü ìíîæåñòâà âñåõ ïîäìíîæåñòâ ñîâîêóïíîñòè èç
àòîìîâ n åñòü 2n , à âòîðîå  èç ïðèìåðà 1.5.2.

   Òåîðåìà Ñòîóíà ïîêàçûâàåò, ÷òî ýëåìåíòû ëþáîé áóëåâîé àëãåáðû ìîæíî ñ÷èòàòü
ïîäìíîæåñòâàìè íåêîòîðîãî ìíîæåñòâà, à áóëåâû îïåðàöèè îòîæäåñòâëÿòü ñ îäíîèì¼í-
íûìè òåîðåòèêî-ìíîæåñòâåííûìè.
   Åñëè â áóëåâîé àëãåáðå îïðåäåëåíû îáúåäèíåíèå è ïåðåñå÷åíèå ïðîèçâîëüíîé ñîâî-
êóïíîñòè å¼ ýëåìåíòîâ, òî òàêàÿ áóëåâà àëãåáðà íàçûâàåòñÿ ïîëíîé. Ëåãêî ïîêàçûâàåòñÿ,
÷òî â ïîëíîé àòîìíîé áóëåâîé àëãåáðå At(B) = At(ι). ßñíî, ÷òî ïîëíîé áóëåâîé àëãåáðîé
ÿâëÿåòñÿ ëþáàÿ àëãåáðà ìíîæåñòâ, à σ -àëãåáðà, ãäå ýòè îïåðàöèè ìîãóò áûòü âçÿòû ëèøü
ïî ñ÷¼òíîé ñîâîêóïíîñòè ìíîæåñòâ, ÿâëÿåòñÿ ïðîìåæóòî÷íîé ìåæäó îáû÷íîé è ïîëíîé
áóëåâûìè àëãåáðàìè.
   Ïðèâåä¼ííîå äîêàçàòåëüñòâî îñòàíåòñÿ ñïðàâåäëèâûì äëÿ ïîëíûõ àòîìíûõ àëãåáð, è
ñïðàâåäëèâîé ÿâëÿåòñÿ ñëåäóþùàÿ
Òåîðåìà 1.5 (Î ïðåäñòàâëåíèè ïîëíûõ àòîìíûõ áóëåâûõ àëãåáð). Ïóñòü B 
ïîëíàÿ àòîìíàÿ áóëåâà àëãåáðà. Òîãäà

                                           B ∼b P(At(B)).
                                             =

   Òàêèì îáðàçîì, ñ òî÷íîñòüþ äî èçîìîðôèçìà ïîëíûå àòîìíûå áóëåâû àëãåáðû èñ÷åð-
ïûâàþòñÿ òîòàëüíûìè àëãåáðàìè ïîäõîäÿùèõ ìíîæåñòâ.
   Çàìåòèì, ÷òî äëÿ äîêàçàòåëüñòâà òåîðåìû Ñòîóíà â ñëó÷àå áåñêîíå÷íûõ áóëåâûõ àë-
ãåáð èñïîëüçóåòñÿ ïîíÿòèå óëüòðàôèëüòðà (ñì. ï. 4.2).


18                                                      Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Ãëàâà 2
Îòíîøåíèÿ è ñîîòâåòñòâèÿ
   ¾Ïîíÿòèå îòîáðàæåíèè ÿâëÿåòñÿ íàñòîëüêî îáùèì, ÷òî, âîîáùå ãîâîðÿ, ëþáîå àëãåá-
ðàè÷åñêîå ïîñòðîåíèå â ÿâíîé èëè íåÿâíîé ôîðìå îñíîâûâàåòñÿ íà ïîíÿòèè îòîáðàæåíèÿ.
Ïîýòîìó ëþáàÿ ðàáîòà ïî àëãåáðå â òîé èëè èíîé ñòåïåíè ïîñâÿùåíà èçó÷åíèþ îòîáðà-
æåíèé ìíîæåñòâ.¿ [ È.È. Âàëóöå. ¾Îòîáðàæåíèÿ. Àëãåáðàè÷åñêèå àñïåêòû òåîðèè¿ ].


2.1 Äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ è îòíîøåíèÿ
   Ïóñòü I = {1, . . . , n}  ìíîæåñòâî èíäåêñîâ è êàæäîìó i ∈ I ñîïîñòàâëåíî íåïóñòîå
ìíîæåñòâî Ai . Äåêàðòîâûì (èëè ïðÿìûì ) ïðîèçâåäåíèåì ìíîæåñòâ {Ai }i∈I íàçûâàþò
ìíîæåñòâî êîíå÷íûõ ïîñëåäîâàòåëüíîñòåé ( a1 , a2 , . . . , an ), ãäå ai ∈ Ai , i ∈ I . Äåêàðòîâî
ïðîèçâåäåíèå îáû÷íî îïðåäåëÿþò äëÿ ïðîèçâîëüíîé, à íå òîëüêî êîíå÷íîé, ñîâîêóïíîñòè
èíäåêñîâ. Íàì, îäíàêî, áóäåò äîñòàòî÷íî äàííîãî îïðåäåëåíèÿ è â äàëüíåéøåì ìû áóäåì
îáîçíà÷àòü äåêàðòîâî ïðîèçâåäåíèå
                                                              n
                              A1 Ч A2 Ч . . . Ч An   èëè            Ai .
                                                             i =1


   Çàìåòèì, ÷òî A Ч B = B Ч A; òàêæå A Ч B Ч C , (A Ч B) Ч C è A Ч (B Ч C) ñóòü
ðàçíûå ìíîæåñòâà.
   Äåêàðòîâî ïðîèçâåäåíèå n ýêçåìïëÿðîâ ìíîæåñòâà A îáîçíà÷àþò An è íàçûâàþò
n-îé äåêàðòîâîé ñòåïåíüþ ìíîæåñòâà A. Åñòåñòâåííî ïîëàãàþò A1 = A, à ïîä A0
ïîíèìàþò íåêîòîðîå îäíîýëåìåíòíîå ïîäìíîæåñòâî A. ßñíî, ÷òî Am Ч An = Am+n .

Îïðåäåëåíèå 2.1. Îòíîøåíèÿ ñóòü ïîäìíîæåñòâà äåêàðòîâûõ ïðîèçâåäåíèé ìíîæåñòâ.
   ×èñëî ìíîæåñòâ â ñîîòâåòñòâóþùåì äåêàðòîâîì ïðîèçâåäåíèè îïðåäåëÿåò ìåñòíîñòü
èëè àðíîñòü îòíîøåíèÿ. Ãîâîðÿò îá óíàðíûõ (îäíîìåñòíûõ), áèíàðíûõ (äâóõìåñòíûõ),
òåðíàðíûõ (òð¼õìåñòíûõ) è ò.ä. îòíîøåíèÿõ. Ïîíÿòíî, ÷òî îòíîøåíèå ρ ⊆ A1 Ч . . . Ч An
îïðåäåëÿåò ñîâîêóïíîñòü n-îê (a1 , . . . , an ) ∈ ρ, ai ∈ Ai , i = 1, . . . , n.

Îïðåäåëåíèå 2.2. Åñëè ρ  îòíîøåíèå íà A1 Ч. . .ЧAn , òî ñîâîêóïíîñòü âñåõ ýëåìåíòîâ
a1 ∈ A1 äëÿ êîòîðûõ íàéäóòñÿ òàêèå a2 ∈ A2 , . . . , an ∈ An , ÷òî (a1 , a2 , . . . , an ) ∈ ρ, íà-
çûâàþò ïðîåêöèåé îòíîøåíèÿ ρ íà ìíîæåñòâî A1 èëè ïåðâîé ïðîåêöèåé. Àíàëîãè÷íî
îïðåäåëÿþòñÿ âòîðûå, òðåòüè è ò.ä. ïðîåêöèè. Ñèìâîëè÷åñêè i-ÿ ïðîåêöèÿ ρ îáîçíà÷à-
åòñÿ P ri ρ.

     Òàêèì îáðàçîì, i-ÿ ïðîåêöèÿ îòíîøåíèÿ ñîñòîèò èç âñåõ ýëåìåíòîâ, ñòîÿùèõ íà i-ì
ìåñòå â n-êàõ èç äàííîãî îòíîøåíèÿ.
     Îòíîøåíèÿ ìîæíî ðàññìàòðèâàòü êàê ïðåäèêàòû, ò.å. ôóíêöèè, ïðèíèìàþùèå äâà
çíà÷åíèÿ  ¾èñòèíà¿ ( 1 ) è ¾ëîæü¿ ( 0 ), à èìåííî, ρ (a1 , . . . , an ) èñòèííî, åñëè
(a1 , . . . , an ) ∈ ρ è ëîæíî â ïðîòèâíîì ñëó÷àå. Ïîýòîìó ê îòíîøåíèÿì ìîæíî ïðèìåíÿòü
îïåðàöèè àëãåáðû ëîãèêè: äèçúþíêöèè (∨), êîíúþíêöèè ( ), îòðèöàíèÿ (¬), òîæäåñòâà
(≡), èìïëèêàöèè (  ) è äð. Ïðè ÷òåíèè ñîîòâåòñòâóþùèõ ôîðìóë ñëåäóåò èìåòü â âèäó,
                          ¡
÷òî, ïîñêîëüêó ïðèîðèòåò îòíîøåíèé âûøå ïðèîðèòåòà îïåðàöèé àëãåáðû ëîãèêè, ñêîáêè
âîêðóã îòíîøåíèé, êàê ïðàâèëî, îïóñêàþò.


2.1. Äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ è îòíîøåíèÿ                                 19


   Óíàðíûå îòíîøåíèÿ íà íåêîòîðîì ìíîæåñòâå îïðåäåëÿþò òå èëè èíûå ñâîéñòâà
åãî ýëåìåíòîâ.
   Áèíàðíûå îòíîøåíèÿ íà äåêàðòîâîì ïðîèçâåäåíèè ìíîæåñòâ A è B íàçûâàþò
îòíîøåíèÿìè ìåæäó A è B èëè ñîîòâåòñòâèÿìè ìåæäó äàííûìè ìíîæåñòâàìè.
   Äëÿ ñîîòâåòñòâèÿ ρ ⊆ A Ч B óäîáíî ïîëüçîâàòüñÿ îáîçíà÷åíèåì aρb, åñëè (a, b) ∈ ρ.
Ïðè ýòîì ïåðâàÿ ïðîåêöèÿ ñîîòâåòñòâèÿ íàçûâàåòñÿ îáëàñòüþ îïðåäåëåíèÿ, à âòîðàÿ 
îáëàñòüþ çíà÷åíèé ρ, êîòîðûå îáîçíà÷àþòñÿ Dom ρ è Im ρ ñîîòâåòñòâåííî. Äëÿ a ∈ A
ìíîæåñòâî ρ(a) = { b ∈ B | aρb } íàçûâàåòñÿ îáðàçîì ýëåìåíòà a ïðè ñîîòâåòñòâèè ρ.
Åñëè ∅ = X ⊆ A, òî ìíîæåñòâî ρ(X) =         ρ (x) íàçûâàåòñÿ îáðàçîì ìíîæåñòâà X
                                          x∈X
ïðè ñîîòâåòñòâèè ρ ïðè ñîîòâåòñòâèè ρ.
   Ïîñêîëüêó îòíîøåíèÿ ñóòü ïîäìíîæåñòâà, òî äëÿ áèíàðíûõ îòíîøåíèé îïðåäåëåíà
òîòàëüíàÿ àëãåáðà P(A Ч B) . ßñíî, ÷òî òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè, ïðèìåí¼í-
íûå ê ñîîòâåòñòâèÿì α, β ⊆ A Ч B , äëÿ a ∈ A, b ∈ B èìåþò ñëåäóþùèå ñâîéñòâà:
 1)   a(α ∪ β)b ⇔ aαb ∨ aβb ⇔ (a, b) ∈ α èëè (a, b) ∈ β ;
 2)   a(α ∩ β)b ⇔ aαb aβb ⇔ (a, b) ∈ α è (a, b) ∈ β ;
 3)   aαb ⇔ ¬(aαb) ⇔ (a, b) ∈ α.
                            /
   Ëåãêî ïîêàçûâàåòñÿ, ÷òî
                             α⊆β           α∪γ ⊆ β ∪δ,
                                      ⇒
                             γ⊆δ           α∩γ ⊆ β∩δ
( α, β, γ è δ ñóòü ñîîòâåòñòâèÿ îäíîé è òîé æå ïàðû ìíîæåñòâ).
    Îòíîøåíèå ρ íàçûâàþò äîïîëíèòåëüíûì ê ρ.
   Òåïåðü ìû ââåä¼ì äâå íîâûå îïåðàöèè äëÿ áèíàðíûõ îòíîøåíèé (ñîîòâåòñòâèé): óíàð-
íóþ ïñåâäîîáðàùåíèÿ è áèíàðíóþ ïðîèçâåäåíèÿ.
Îïðåäåëåíèå 2.3. Ïóñòü ρ ⊆ A Ч B . Îïåðàöèÿ      (ïñåâäîîáðàùåíèÿ ) ñîîòâåòñòâèÿ ρ
çàäà¼ò ïñåâäîîáðàòíîå ê íåìó ñîîòâåòñòâèå ρ ⊆ B Ч A, îïðåäåëÿåìîå êàê bρ a ⇔ aρb
äëÿ ëþáûõ a ∈ A, b ∈ B .
   ßñíî, ÷òî ïñåâäîîáðàòíîå ê äàííîìó îòíîøåíèþ ñóùåñòâóåò âñåãäà. Äëÿ ïñåâäî-
îáðàùåíèÿ ÷àñòî óïîòðåáëÿþò òàêæå òåðìèíû îáðàòíîå, òðàíñïîíèðîâàííîå, èíâåðñ-
íîå, ñèììåòðè÷íîå èëè äóàëüíîå îòíîøåíèå è ïîëüçóþòñÿ îáîçíà÷åíèÿìè ρ−1 , ρ , ρd
è äð. Ëåãêî óñòàíîâèòü ñëåäóþùèå ñâîéñòâà ïñåâäîîáðàùåíèÿ îòíîñèòåëüíî òåîðåòèêî-
ìíîæåñòâåííûõ îïåðàöèé è îòíîøåíèÿ âêëþ÷åíèÿ:
                    (ρ ) = ρ (èíâîëþòèâíîñòü ïñåâäîîáðàùåíèÿ) ,
                      ρ = (ρ) ,
                   α ⊆ β ⇒α ⊆ β      (ìîíîòîííîñòü ïñåâäîîáðàùåíèÿ) ,
                 (α ∪ β) = α ∪ β ,
                 (α ∩ β) = α ∩ β .
   Ïîêàæåì, íàïðèìåð, ñïðàâåäëèâîñòü ïîñëåäíåãî ðàâåíñòâà (a è b  ïðîèçâîëüíûå
ýëåìåíòû ñîîòâåòñòâóþùèõ ìíîæåñòâ):
           b(α ∩ β) a = a(α ∩ β)b = aαb    aβb = bα a   bβ a = b(α ∩ β )a .
   Äëÿ ρ ⊆ A Ч B è b ∈ B ìíîæåñòâî ρ (b) = {a ∈ A | aρb} íàçûâàåòñÿ ïðîîáðàçîì ýëå-
ìåíòà b ïðè ñîîòâåòñòâèè ρ. Åñëè Y ⊆ B , òî ìíîæåñòâî ρ (Y ) =    ρ (y) íàçûâàåòñÿ
                                                                 y∈Y
ïðîîáðàçîì ìíîæåñòâà Y .


20                                                  Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Îïðåäåëåíèå 2.4. Ïóñòü A , B è C  íåïóñòûå ìíîæåñòâà, α ⊆ A Ч B è β ⊆ B Ч C .
Òîãäà ïðîèçâåäåíèå èëè óìíîæåíèå α β ñîîòâåòñòâèé α è β îïðåäåëÿåòñÿ äëÿ ïðîèç-
âîëüíûõ a ∈ A, c ∈ C êàê

                              a(α β)c ⇔ ∃ b (aαb       bβc).
                                            B

×àñòî çíàê     îïóñêàþò è âìåñòî α β ïèøóò αβ .

   Ïîíÿòíî, ÷òî â îáùåì ñëó÷àå ïðîèçâåäåíèå ñîîòâåòñòâèé ìîæåò è íå ñóùåñòâîâàòü.
B ñëó÷àå æå ñóùåñòâîâàíèÿ îíî îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:


              α(βγ) = (αβ)γ   (àññîöèàòèâíîñòü ïðîèçâåäåíèÿ ñîîòâåòñòâèé ),
              (αβ) = β α ,
             α⊆β
                   ⇒ αγ ⊆ βδ     (ìîíîòîííîñòü óìíîæåíèÿ ñîîòâåòñòâèé ),
             γ⊆δ
          α(β ∪ γ) = αβ ∪ αγ      è (α ∪ β)γ = αγ ∪ βγ ,        îòêóäà
                     (α ∪ β)(γ ∪ δ) = αγ ∪ αδ ∪ βγ ∪ βδ ,
          α(β ∩ γ) ⊆ αβ ∩ αγ      è (α ∩ β)γ ⊆ αγ ∩ βγ .

   Àññîöèàòèâíîñòü ïðîèçâåäåíèÿ ñîîòâåòñòâèé ñëåäóåò èç àññîöèàòèâíîñòè ëîãè÷åñêîé
îïåðàöèè    è ïðàâèë å¼ âçàèìîäåéñòâèÿ ñ êâàíòîðîì ñóùåñòâîâàíèÿ. Äîêàæåì ñïðàâåä-
ëèâîñòü ïðàâèëà (αβ) = β α : äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ a è c ñîîòâåòñòâóþùèõ
ìíîæåñòâ èìååì

          c(αβ) a = a(αβ)c = ∃b (aαb      bβc ) = ∃b cβ b      bα a   = c(β α )a.

   Ïîêàæåì ñïðàâåäëèâîñòü ñâîéñòâà ìîíîòîííîñòè óìíîæåíèÿ ñîîòâåòñòâèé. Äåéñòâè-
òåëüíî, äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ a è c ñîîòâåòñòâóþùèõ ìíîæåñòâ èìååì

                 a(αγ)c = ∃ b ( aαb   bγc ) ⇒ ∃b ( aβb    bδc ) = a(βδ)c .

   Äîêàæåì òåïåðü, ÷òî (α∩β)γ ⊆ αγ ∩βγ . Äåéñòâèòåëüíî, äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ
a è c ñîîòâåòñòâóþùèõ ìíîæåñòâ áóäåì èìåòü

 a[(α ∩ β)γ]c = ∃ b ( a(α ∩ β)b bγc ) = ∃ b ( aαb aβb bγc ) =
       = ∃ b ( (aαb bγc) (aβb bγc) ) ⇒ ∃ b ( aαb bγc ) ∃ b ( aβb bγc ) =
                                                  = a(αγ)c a(βγ)c = a(αγ ∩ βγ)c .

 ïðèâåä¼ííîì âûâîäå çàìåíèòü ( ⇒ ) íà ( ⇔ ) íåëüçÿ, ïîñêîëüêó ýëåìåíòû b, îáåñïå÷è-
âàþùèå ñïðàâåäëèâîñòü aαb bγc è aβb bγc ìîãóò áûòü ðàçëè÷íûìè. Ñîîòíîøåíèå
α(β ∩ γ) ⊆ αβ ∩ αγ äîêàçûâàåòñÿ àíàëîãè÷íî.
    Ñóùåñòâóåò óäîáíûé ñïîñîá ïðåäñòàâëåíèÿ ñîîòâåòñòâèé êîíå÷íûõ ìíîæåñòâ â âèäå
(0,1)-ìàòðèö. Ïóñòü ρ  ñîîòâåòñòâèå ìåæäó A = {a1 , . . . , am } è B = {b1 , . . . , bn }.
Çàôèêñèðóåì óêàçàííûé ïîðÿäîê ñëåäîâàíèÿ ýëåìåíòîâ â ìíîæåñòâàõ A è B . Òîãäà
ìàòðèöà M (ρ) îòíîøåíèÿ ρ èìååò ðàçìåðû m Ч n è å¼ ýëåìåíò rij ðàâåí 1, åñëè ai ρbj
è 0 èíà÷å.
    Ìíîæåñòâî âñåõ (0,1)-ìàòðèö ðàçìåðà mЧn áóäåì îáîçíà÷àòü MmЧn , îïóñêàÿ èíäåêñ,
êîãäà ñîîòâåòñòâóþùèé ðàçìåð ïîäðàçóìåâàåòñÿ. Âî ââåä¼ííîì ìíîæåñòâå âûäåëÿþòñÿ
ìàòðèöà, ó êîòîðîé âñ¼ ýëåìåíòû ðàâíû 1 è ìàòðèöà, ó êîòîðîé âñ¼ ýëåìåíòû ðàâíû



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