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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
            Ìîñêîâñêèé Ãîñóäàðñòâåííûé óíèâåðñèòåò
                 èì. Ì.Â. Ëîìîíîñîâà
Ôàêóëüòåò Âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè


                    Ñ.È. Ãóðîâ
   ËÅÊÖÈÈ ÏÎ ÓÏÎÐßÄÎ×ÅÍÍÛÌ
  ÌÍÎÆÅÑÒÂÀÌ È ÓÍÈÂÅÐÑÀËÜÍÎÉ
           ÀËÃÅÁÐÅ




                        Ìîñêâà
                         2008


ÓÄÊ 512 (075.8)
ÁÁÊ 22.144
à 95

      Ïå÷àòàåòñÿ ïî ðåøåíèþ ðåäàêöèîííî-èçäàòåëüñêîãî ñîâåòà ôàêóëüòåòà
                 âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè
                          ÌÃÓ èì. Ì.Â. Ëîìîíîñîâà


                                   Ðåöåíçåíòû:
                       ä.ô.-ì.í, ïðîôåññîð Â.Ê. Ëåîíòüåâ
                       ä.ô.-ì.í, ïðîôåññîð Ñ.Ñ. Ìàð÷åíêîâ

Ãóðîâ Ñ.È.
Ëåêöèè ïî óïîðÿäî÷åííûì ìíîæåñòâàì è óíèâåðñàëüíîé àëãåáðå: Ó÷åáíî-
ìåòîäè÷åñêîå ïîñîáèå  Ì.: Èçäàòåëüñêèé îòäåë ôàêóëüòåòà ÂÌèÊ èì. Ì.Â. Ëîìîíîñîâà
(ëèöåíçèÿ ÈÄ  05899 îò 24.09.2001 ã.); ÌÀÊÑ Ïðåññ, 2009.  192 ñ.

   Â ïîñîáèè ðàññìîòðåíû îñíîâíûå ïîíÿòèÿ è òåîðåìû áóëåâîé àëãåáðû, îòíîøåíèé
ìíîæåñòâ, ïðè÷åì îñîáîå âíèìàíèå óäåëåíî ÷àñòè÷íî óïîðÿäî÷åííûì ìíîæåñòâàì è ðå-
ø¼òêàì. Èçó÷àþòñÿ ñâîéñòâà ìîäóëÿðíûõ, äèñòðèáóòèâíûõ ðåø¼òîê è ðåø¼òîê ñ äîïîë-
íåíèÿìè. Óêàçàííûì ðàçäåëàì ïîñâÿùåíû ïåðâûå ãëàâû. Â ïîñëåäíåé ãëàâå ðàññìàòðè-
âàþòñÿ óíèâåðñàëüíûå àëãåáðû. Ââîäèòñÿ ïîíÿòèå àëãåáðàè÷åñêîé ñèñòåìû, ðàññìàòðè-
âàþòñÿ ðàçëè÷íûå òèïû òàêèõ ñèñòåì è äîêàçûâàþòñÿ îñíîâíûå òåîðåìû îá èõ èçîìîð-
ôèçìå è ãîìîìîðôèçìå. Ââîäèìûå ïîíÿòèÿ è äîêàçàííûå óòâåðæäåíèÿ èëëþñòðèðóþòñÿ
áîëüøèì êîëè÷åñòâîì ïðèìåðîâ.
   Ïîñîáèå ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ, èçó÷àþùèõ ñîîòâåòñòâóþùèå ðàçäåëû àëãåáðû
è ìîæåò áûòü èñïîëüçîâàíî ïðè ñàìîîáðàçîâàíèè.



© Ôàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè
è êèáåðíåòèêè èì. Ì.Â. Ëîìîíîñîâà, 2009.
© Ñ.È. Ãóðîâ, 2009.


Ïðåäèñëîâèå                                                                            3


    Ïðåäèñëîâèå
               Ìû, êîíå÷íî, íå ïðåäïîëàãàåì áåñïîëåçíî ìó÷èòü ëþäåé, íî, âìåñòå ñ
               òåì, ìû íå ìîæåì ñòðåìèòüñÿ ê òîìó, ÷òîáû óáðàòü âñå òåðíèè ñ ïóòè,
               âåäóùåãî ê íàóêå, äîáðîäåòåëè è ñëàâå; ýòî íàì íå óäàñòñÿ íè ïðè êàêèõ
               óñëîâèÿõ.

                                            Äåíè Äèäðî. Ïëàí óíèâåðñèòåòà èëè øêîëû
                                                  ïóáëè÷íîãî ïðåïîäàâàíèÿ âñåõ íàóê.

   Äàííîå ó÷åáíî-ìåòîäè÷åñêîå ïîñîáèå ïîäãîòîâëåíî íà îñíîâå êîíñïåêòîâ ëåêöèé îä-
íîñåìåñòðîâîé ÷àñòè êóðñà Ïðèêëàäíîé àëãåáðû, êîòîðûé ÷èòàåòñÿ íà ô-òå ÂÌèÊ ÌÃÓ
äëÿ ñòóäåíòîâ, îáó÷àþùèõñÿ íà êàôåäðå ¾Ìàòåìàòè÷åñêèå ìåòîäû ïðîãíîçèðîâàíèÿ¿.
    ïîñîáèè íå èçëàãàåòñÿ ñêîëüêî-íèáóäü ãëóáîêèõ òåîðåì ò.ê. îíî ïðåäíàçíà÷åíî äëÿ
ïåðâîíà÷àëüíîãî çíàêîìñòâà ñ ïðåäìåòîì. Ïîýòîìó æå ââîäèìûå ïîíÿòèÿ è óòâåðæäå-
íèÿ, êàê äîêàçûâàåìûå, òàê è íå äîêàçûâàåìûå, èëëþñòðèðóþòñÿ áîëüøèì êîëè÷åñòâîì
ïðèìåðîâ. Êàê ïðàâèëî, îòñóòñòâèå äîêàçàòåëüñòâ íåêîòîðûõ ôàêòîâ ñâÿçàíî ñ íåæåëà-
íèåì ÷ðåçìåðíî óâåëè÷èâàòü îáú¼ì ïîñîáèÿ èëè óâîäèòü ÷èòàòåëÿ â ñòîðîíó îò îñíîâíûõ
èäåé (âñïîìíèì âûñêàçûâàíèå Ë.Ä. Ëàíäàó î òîì, ÷òî ó÷åáíèê äîëæåí áûòü òîíêèì, à
ñïðàâî÷íèê  òîëñòûì). Âïðî÷åì, çíà÷èòåëüíàÿ ÷àñòü òàêèõ äîêàçàòåëüñòâ ïðåäëàãàþò-
ñÿ êàê ñàìîñòîÿòåëüíûå çàäà÷è íà ïðàêòè÷åñêèõ çàíÿòèÿõ, ïîääåðæèâàþùèõ óêàçàííûé
âûøå êóðñ.
   Àâòîð ïûòàëñÿ ïîäãîòîâèòü äàííóþ êíèæêó òàê, ÷òîáû îíà ìîãëà áûòü èñïîëüçîâàíà
è ïðè ñàìîîáðàçîâàíèè. Æåëàòåëüíî ëèøü çíàêîìñòâî ÷èòàòåëÿ ñ îñíîâíûìè ïîíÿòèÿ-
ìè àëãåáðû è äèñêðåòíîé ìàòåìàòèêè â îáú¼ìå ìëàäøèõ êóðñîâ óíèâåðñèòåòîâ.  Ïðè-
ëîæåíèè äëÿ ñïðàâêè ôîðìàëüíî îïèñàíû êëàññè÷åñêèå óíèâåðñàëüíûå àëãåáðàè÷åñêèå
ñèñòåìû.
    ó÷åáíîì ïîñîáèè íåîáõîäèìî ïîëüçîâàòüñÿ îáùåïðèíÿòûìè îáîçíà÷åíèÿìè. Âî èç-
áåæàíèè íåäîðàçóìåíèé âñ¼-òàêè ïðèâåä¼ì îñíîâíûå èç íèõ. Ñèìâîëû N, Z, Q, R îáî-
çíà÷àþò ìíîæåñòâà íàòóðàëüíûõ, öåëûõ, ðàöèîíàëüíûõ è äåéñòâèòåëüíûõ ÷èñåë ñîîòâåò-
ñòâåííî; N0 = N∪{0}  ïîïîëíåííûé íàòóðàëüíûé ðÿä. ÍÎÊ è ÍÎÄ  ýòî íàèìåíüøåå
îáåå êðàòíîå è íàèáîëüøèé îáùèé äåëèòåëü ñîîòâåòñòâåííî. Ìíîæåñòâî öåëûõ, êðàòíûõ
n îáîçíà÷àåòñÿ nZ. Êàê îáû÷íî, Zn îáîçíà÷àåò öèêëè÷åñêóþ n-ýëåìåíòíóþ ãðóïïó (ïî
ñëîæåíèþ).
   Áóëåâû êîíñòàíòû (èñòèííîñòíûå çíà÷åíèÿ) ¾èñòèíà¿ è ¾ëîæü¿ îáîçíà÷àþòñÿ ñîîò-
âåòñòâåííî 1 è 0, à n-ìåðíûé åäèíè÷íûé êóá  2n . Ñèìâîë              îçíà÷àåò ¾ðàâíî ïî
îïðåäåëåíèþ¿, ¡       èìïëèêàöèþ, ≡  ¾ðàâíî ïî mod n¿. Ñèìâîë → îáîçíà÷àåò ïîä-
                                       n
ñòàíîâêó ýëåìåíòîâ, à ñèìâîë ↔  èõ ïåðåñòàíîâêó, à ←  îïåðàòîð ïðèñâàèâàíèÿ.
   Ñòðåëêè ⇒ è ⇔ ñëóæàò ñîêðàùåíèÿìè äëÿ âûðàæåíèé ðóññêîãî ÿçûêà ¾âëå÷¼ò¿,
¾åñëè ..., òî ...¿ è ¾ýêâèâàëåíòíî¿, ¾... åñëè è òîëüêî åñëè ...¿ ñîîòâåòñòâåííî. Êâàíòî-
ðû ñóùåñòâîâàíèÿ è âñåîáùíîñòè ïåðåìåííîé x ïî ìíîæåñòâó X îáîçíà÷àþòñÿ ∃ x è
                                                                                   X
∀ x ñîîòâåòñòâåííî; âïðî÷åì, óêàçàíèå íà X îïóñêàåòñÿ, êîãäà ýòî íå âåä¼ò ê äâóñìûñ-
X
ëåííîñòè. Ñîâìåñòíîå âûïîëíåíèå óñëîâèé îáîçíà÷àåòñÿ, êàê îáû÷íî, ëåâîé ôèãóðíîé, à
âûïîëíåíèå õîòÿ áû îäíîãî óñëîâèÿ  ëåâîé êâàäðàòíîé ñêîáêàìè.
    ó÷åáíûõ ïîñîáèÿõ íå ïðèíÿòî óêàçûâàòü àâòîðîâ òåõ èëè èíûõ ðåçóëüòàòîâ. Èç ìå-
òîäè÷åñêèõ ñîîáðàæåíèé ÿ ïîçâîëèë ñåáå â îòñòóïèòü îò äàííîãî ïðàâèëà, ïî âîçìîæíî-
ñòè ïðèâîäÿ ôàìèëèþ(è) àâòîðîâ òåîðåì, íå èìåþùèõ ñïåöèàëüíûõ íàçâàíèé.
   Âûðàæàþ èñêðåííþþ áëàãîäàðíîñòü ðåöåíçåíòàì äàííîãî òðóäà ïðîôåññîðàì
Â.Ê. Ëåîíòüåâó è Ñ.Ñ. Ìàð÷åíêîâó, âíèìàòåëüíî ïðî÷èòàâøèì ðóêîïèñü, óêàçàâøèì íà


4                                                                     Ïðåäèñëîâèå


ðÿä íåòî÷íîñòåé è ñäåëàâøèì ìíîãî öåííûõ çàìå÷àíèé. Î.Ì. Âàñèëüåâ è Í.Î. Ïòàø-
êî òùàòåëüíî ïðîðàáîòàëè òåêñò è âûÿâèëè çíà÷èòåëüíîå êîëè÷åñòâî ïðîïóùåííûõ ïðè
ïðåäûäóùèõ ÷òåíèÿõ îïèñîê è íåñîîòâåòñòâèé, çà ÷òî ÿ èì ãëóáîêî áëàãîäàðåí. Îòâåò-
ñòâåííîñòü çà âîçìîæíûå îñòàâøèåñÿ ïîãðåøíîñòè íåñ¼ò, áåçóñëîâíî, àâòîð.
   Õî÷ó âûðàçèòü îñîáóþ ïðèçíàòåëüíîñòü àêàäåìèêó ÐÀÍ Þ.È. Æóðàâë¼âó, â ñâîå âðå-
ìÿ ïðåäëîæèâøåìó ìíå ïðî÷åñòü çàêëþ÷èòåëüíóþ ÷àñòü óïîìÿíóòîãî ó÷åáíîãî êóðñà è
îïðåäåëèâøåìó åãî ñîäåðæàíèå. Îòäàë¼ííûì (íî äàëåêî íå åäèíñòâåííûì) ïîñëåäñòâèåì
ýòîãî ïðåäëîæåíèÿ ÿâèëîñü ïîÿâëåíèå äàííîãî ïîñîáèÿ.
   ¾Ïèñàíèå ìàòåìàòè÷åñêèõ òåêñòîâ  ñëîæíîå èñêóññòâî, è äàæå ëó÷øèå èç ìàòåìà-
òèêîâ íå âñåãäà îêàçûâàþòñÿ íà âûñîòå, à óæ áîëüøèíñòâî ìàòåìàòè÷åñêèõ ïóáëèêàöèé
(áóäü òî íàó÷íûå ñòàòüè, èëè ó÷åáíèêè, äàæå äëÿ ñðåäíåé èëè íà÷àëüíîé øêîëû) âîîáùå
íå âûäåðæèâàþò íèêàêîé êðèòèêè¿ [ Â.È. Àðíîëüä. ¾×òî òàêîå ìàòåìàòèêà?¿ ]. Íàñêîëü-
êî äàííîå ïîñîáèå îêàçàëîñü óäà÷íûì  ñóäèòü ÷èòàòåëþ.

                                                                          Ñ. Ãóðîâ


Îãëàâëåíèå                                                                                                                      5


  Îãëàâëåíèå
Ïðåäèñëîâèå                                                                                                                     3
1 Áóëåâû àëãåáðû                                                                                                                6
  1.1   Îïðåäåëåíèå áóëåâîé àëãåáðû.     Àëãåáðàè÷åñêèå ñèñòåìû                   .   .   .   .   .   .   .   .   .   .   .     6
  1.2   Àëãåáðû ìíîæåñòâ . . . . . . .   . . . . . . . . . . . . . . .            .   .   .   .   .   .   .   .   .   .   .     9
  1.3   Èçîìîðôèçìû áóëåâûõ àëãåáð       . . . . . . . . . . . . . . .            .   .   .   .   .   .   .   .   .   .   .    12
  1.4   Òåîðåìà Ñòîóíà . . . . . . . .   . . . . . . . . . . . . . . .            .   .   .   .   .   .   .   .   .   .   .    15

2 Îòíîøåíèÿ è ñîîòâåòñòâèÿ                                                                                                     18
  2.1   Äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ è îòíîøåíèÿ           .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    18
  2.2   Îäíîðîäíûå îòíîøåíèÿ . . . . . . . . . . . . . .      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    21
  2.3   Îòíîøåíèå ýêâèâàëåíòíîñòè . . . . . . . . . . .       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    25
  2.4   Ïðîñòðàíñòâà òîëåðàíòíîñòè . . . . . . . . . . .      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    31
  2.5   Îñíîâíûå ñâîéñòâà è òèïû ñîîòâåòñòâèé . . . .         .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    38
  2.6   Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà . . . . . .        .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .    39

3 ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà                                                                                             46
  3.1   Ïðåäïîðÿäêè è ïîðÿäêè . . . . . . . . . . . . . . . . . .             .   .   .   .   .   .   .   .   .   .   .   .    46
  3.2   Èçîòîííûå îòîáðàæåíèÿ è ïîðÿäêîâûå èäåàëû . . . .                     .   .   .   .   .   .   .   .   .   .   .   .    54
  3.3   Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè. Ðàçìåðíîñòü . . . . .                  .   .   .   .   .   .   .   .   .   .   .   .    57
  3.4   Âïîëíå óïîðÿäî÷åííûå ìíîæåñòâà è ñìåæíûå âîïðîñû                      .   .   .   .   .   .   .   .   .   .   .   .    66

4 Àëãåáðàè÷åñêèå ðåø¼òêè                                                                                                       73
  4.1   Ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà è ðåø¼òêè . . . . . . . . . . . . . . .                                              73
  4.2   Îñíîâíûå ñâîéñòâà ðåø¼òîê. Ðåø¼òî÷íûå ãîìîìîðôèçìû, èäåàëû è ôèëüòðû                                                   78
  4.3   Ìîäóëÿðíûå ðåø¼òêè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                       85
  4.4   Äèñòðèáóòèâíûå ðåø¼òêè . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                       87
  4.5   Ôàêòîððåø¼òêè. Ðåø¼òêè ñ äîïîëíåíèÿìè . . . . . . . . . . . . . . . . . . .                                            95

5 Áóëåâû àëãåáðû (ïðîäîëæåíèå)                                                                                                100
  5.1   Áóëåâû àëãåáðû êàê ðåø¼òêè. Áóëåâû ãîìîìîðôèçìû è ïîäàëãåáðû                                          .   .   .   .   100
  5.2   Áóëåâû êîëüöà è ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . .                               .   .   .   .   101
  5.3   Èäåàëû è ôèëüòðû â áóëåâîé àëãåáðå . . . . . . . . . . . . . . . . . .                                .   .   .   .   104
  5.4   Áóëåâû ìíîãî÷ëåíû . . . . . . . . . . . . . . . . . . . . . . . . . . . .                             .   .   .   .   110
  5.5   Óðàâíåíèÿ â áóëåâûõ àëãåáðàõ . . . . . . . . . . . . . . . . . . . . . .                              .   .   .   .   114

6 Àëãåáðàè÷åñêèå ñèñòåìû                                                                                                      117
  6.1   Îñíîâíûå îïðåäåëåíèÿ. Ìîäåëè è àëãåáðû .        . .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   117
  6.2   Ïîäñèñòåìû. Ïðÿìîå ïðîèçâåäåíèå ÀÑ . . .        . .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   120
  6.3   Ãîìîìîðôèçìû ÀÑ . . . . . . . . . . . . . .     . .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   122
  6.4   Êîíãðóýíöèè è ôàêòîðñèñòåìû . . . . . . .       . .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   125
  6.5   Òåîðåìû î ãîìîìîðôèçìàõ è èçîìîðôèçìàõ          ÀÑ    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   128
  6.6   Ìíîãîîñíîâíûå ñèñòåìû . . . . . . . . . . .     . .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   131

Ïðèëîæåíèå                                                                                                                    134
Ñïèñîê ëèòåðàòóðû                                                                                                             136


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


Ãëàâà 1
Áóëåâû àëãåáðû
    ¾Áóëåâû àëãåáðû ïðåäñòàâëÿþò ñîáîé óäîáíóþ ôîðìàëèçàöèþ ôðàãìåíòà òåî-
ðèè ìíîæåñòâ, ñëóæàùåé îñíîâîé áîëüøèíñòâà ñîâðåìåííûõ ðàçäåëîâ ìàòåìàòèêè,
÷òî è îïðåäåëÿåò øèðîêîå èõ ïðèìåíåíèå âî ìíîãèõ ìàòåìàòè÷åñêèõ êîíñòðóêöèÿõ.¿
[ Ñ.Ñ. Ãîí÷àðîâ. ¾Ñ÷¼òíûå áóëåâû àëãåáðû¿ ].


1.1 Îïðåäåëåíèå áóëåâîé àëãåáðû. Àëãåáðàè÷åñêèå ñèñòåìû
Îïðåäåëåíèå 1.1. Áóëåâîé àëãåáðîé B íàçûâàåòñÿ ñîäåðæàùåå ïî êðàéíåé ìåðå äâà
ýëåìåíòà  o (íóëü ) è ι (åäèíèöà )  ìíîæåñòâî B ñ çàäàííûìè íà í¼ì áèíàðíûìè
îïåðàöèÿìè      (îáúåäèíåíèÿ ), (ïåðåñå÷åíèÿ ) è óíàðíîé îïåðàöèåé (äîïîëíåíèÿ ).
Ïðè ýòîì äëÿ ëþáûõ x, y è z èç B âûïîëíÿþòñÿ ñëåäóþùèå çàêîíû (àêñèîìû ) áóëå-
âîé àëãåáðû :
 Com : x y = y x ;
 Com : x y = y x ;
   Dtr1 : (x y) z = (x z) (y z) ;
   Dtr2 : (x y) z = (x z) (y z) ;
       o : x o = x;
        ι : x ι = x;
  Cmp : x x = ι ;
    Isl : x x = o ;
   Inv : (x ) = x ;
       ι : ι = o;
      o : o = ι;
 DeM 1 : (x y) = x        y ;
 DeM 2 : (x y) = x        y ;
        ι : x ι = ι;
       o : x o = o;
  Ass : x (y z) = (x y) z ;
  Ass : x (y z) = (x y) z ;
   Id : x x = x ;
   Id : x x = x ;
   Abs1 : x (x y) = x ;
   Abs2 : x (x y) = x .
Ìíîæåñòâî B íàçûâàåòñÿ íîñèòåëåì áóëåâîé àëãåáðû B, à o è ι  âûäåëåííûìè ýëå-
ìåíòàìè èëè óíèâåðñàëüíûìè ãðàíÿìè.
   Òàêèì îáðàçîì, â áóëåâîé àëãåáðå äëÿ îáúåäèíåíèÿ è ïåðåñå÷åíèÿ âûïîëíÿþòñÿ ïàðû
çàêîíîâ êîììóòàòèâíîñòè ( Com ), ïåðâûé è âòîðîé äèñòðèáóòèâíûå çàêîíû ( Dtr1, 2 ),
çàêîíû àññîöèàòèâíîñòè ( Ass ), èäåìïîòåíòíîñòè ( Id )1 è ïîãëîùåíèÿ ( Abs). Îòìåòèì,
÷òî çàêîíû àññîöèàòèâíîñòè îáåñïå÷èâàþò ýêâèâàëåíòíîñòü ïðîèçâîëüíûõ ñêîáî÷íûõ
ñòðóêòóð êîíå÷íûõ îáúåäèíåíèé è ïåðåñå÷åíèé. Ïîíÿòíî, ÷òî â áóëåâîé àëãåáðå îïðå-
äåëåíû îáúåäèíåíèÿ è ïåðåñå÷åíèÿ ëþáîé êîíå÷íîé ñîâîêóïíîñòè ýëåìåíòîâ. Äàëåå ïðè
âûâîäå ñîîòíîøåíèé ìû, êàê ïðàâèëî, íå áóäåì ñïåöèàëüíî îòìå÷àòü ïðèìåíåíèå çàêîíîâ
àññîöèàòèâíîñòè è êîììóòàòèâíîñòè.
   Çàêîíû o, ι, ι è o îïèñûâàþò íåéòðàëüíûå è ïîãëîùàþùèå ñâîéñòâà îñî-
áûõ ýëåìåíòîâ áóëåâîé àëãåáðû ïî îòíîøåíèþ ê îáúåäèíåíèþ è ïåðåñå÷åíèþ. Ñâîéñòâà
    1 Îò   ëàò. idem  òî æå, potentia  ñèëà.


1.1. Îïðåäåëåíèå áóëåâîé àëãåáðû. Àëãåáðàè÷åñêèå ñèñòåìû                                                      7


ι , o óêàçûâàþò íà âçàèìíóþ äîïîëíèòåëüíîñòü ýòèõ ýëåìåíòîâ. Çàêîíû Cmp è Isl
ÿâëÿþòñÿ îñíîâíûìè çàêîíàìè, îïèñûâàþùèå ñâîéñòâà äîïîëíåíèÿ; îíè ïîñòóëèðóþò, ñî-
îòâåòñòâåííî, åãî ïîëíîòó è îáîñîáëåííîñòü. Çàêîí Inv óêàçûâàåò íà èíâîëþòèâíîñòü
äîïîëíåíèÿ. Âçàèìíûå ñâîéñòâà áèíàðíûõ îïåðàöèé è äîïîëíåíèÿ îïèñûâàþòñÿ çàêîíà-
ìè Äå Ìîðãàíà (DeM 1, 2).
    Ââåä¼ííûå îïåðàöèè íàçûâàþò àáñòðàêòíûìè, ïîñêîëüêó íè îíè ñàìè, íè íîñèòåëü,
íà êîòîðîì îíè îïðåäåëåíû íèêàê íå êîíêðåòèçèðóþòñÿ è íèêàêèõ èíûõ òðåáîâàíèé, êðî-
ìå óäîâëåòâîðåíèÿ âûøåïðèâåä¼ííûì çàêîíàì, ê íèì íå ïðåäúÿâëÿåòñÿ.  ïðèëîæåíèÿõ
ýëåìåíòû áóëåâîé àëãåáðû èíòåðïðåòèðóþòñÿ êàê ïîäìíîæåñòâà íåêîòîðûõ ìíîæåñòâ,
êàê ñîáûòèÿ, âûñêàçûâàíèÿ, ñèãíàëû è äð.
Ëåììà 1.1 (Î åäèíñòâåííîñòè äîïîëíåíèÿ).                       2
                                                                    Â áóëåâîé àëãåáðå
                                         x     y = o
                                                         ⇔ y = x .
                                         x     y = ι
Äîêàçàòåëüñòâî. (⇒, äîñòàòî÷íîñòü)
       ι       Cmp                   Com , Dtr1
  y = y    ι    =    y   (x    x )       =         (y   x)    (y    x ) =
                                             Isl                            Dtr, Abs, Com
                         = o    (y     x ) = (x         x )    (y     x )          =
                                                                                                       ι
                                                                            = (x       y)   x = ι   x = x .
   (⇐, íåîáõîäèìîñòü) î÷åâèäíà  çàêîíû Cmp è Isl .
    Îòäåëüíûé ýëåìåíò áóëåâîé àëãåáðû, à òàêæå ôîðìóëà, îïèñûâàþùàÿ ïðèìåíåíèå
êîíå÷íîãî ÷èñëà óêàçàííûõ îïåðàöèé ê ýëåìåíòàì íîñèòåëÿ, çàïèñàííîå â âèäå ñîîòâåò-
ñòâóþùåé ôîðìóëû, áóäåì íàçûâàòü áóëåâûì âûðàæåíèåì. ßñíî, ÷òî áóëåâî âûðàæåíèå
îïðåäåëÿåò íåêîòîðûé ýëåìåíò áóëåâîé àëãåáðû êàê çíà÷åíèå ôóíêöèè îò àðãóìåíòîâ 
ýëåìåíòîâ, âõîäÿùèõ â äàííîå âûðàæåíèå. Äâà âûðàæåíèÿ, ñâÿçàííûå çíàêîì = ïðåä-
ñòàâëÿþò ñîáîé áóëåâî ðàâåíñòâî. Òî÷íîå îïðåäåëåíèå äàííûõ ïîíÿòèé áóäåò äàíî â
ï. 5.4. Áóëåâî ðàâåíñòâî ìîæåò áûòü êàê èñòèííûì, òàê è ëîæíûì â çàâèñèìîñòè îò òî-
ãî, îïðåäåëÿþò ëè ëåâàÿ è ïðàâàÿ åãî ÷àñòè îäèí è òîò æå ýëåìåíò íîñèòåëÿ. Ïðèâåä¼ííûå
âûøå çàêîíû áóëåâîé àëãåáðû èñòèííû èìåííî â ýòîì ñìûñëå.
    Ïóñòü V  âûðàæåíèå èëè ðàâåíñòâî áóëåâîé àëãåáðû. Ðåçóëüòàòû îäíîâðåìåííîé
çàìåíû âñåõ ñèìâîëîâ      ↔ è ι ↔ o â V áóäåì îáîçíà÷àòü V , à x ↔ x , ãäå x 
íåêîòîðûé ýëåìåíò íîñèòåëÿ, íå ÿâëÿþùèéñÿ óíèâåðñàëüíîé ãðàíüþ  V . Åñëè æå â V
ïðîèçâîäÿòñÿ îáå óêàçàííûå çàìåíû, òî èõ ðåçóëüòàò îáîçíà÷èì V ∗ .  áóëåâîé àëãåáðå
ñïðàâåäëèâ ñëåäóþùèé
Ïðèíöèï äâîéñòâåííîñòè (äëÿ áóëåâîé àëãåáðû).      1. Åñëè V  èñòèííîå áóëåâî
     ðàâåíñòâî, òî ðàâåíñòâà V , V è V ∗ òàêæå èñòèííû.
  2. Åñëè V  âûðàæåíèå áóëåâîé àëãåáðû, òî V ∗ = V .
   Äåéñòâèòåëüíî, ïðèâåä¼ííûå âûøå çàêîíû, êðîìå Inv , ðàçáèâàþòñÿ íà ïàðû ïîñëå-
äîâàòåëüíî çàïèñàííûõ âçàèìîäâîéñòâåííûõ, ïðåõîäÿùèõ äðóã â äðóãà ïðè çàìåíå ; ïðè
ýòîì Inv ïåðåõîäèò ñàì â ñåáÿ. Ïðåîáðàçîâàíèå ïåðåâîäèò âñå çàêîíû, êðîìå Inv , èëè
ñ òî÷íîñòüþ äî îáîçíà÷åíèé â ñåáÿ, èëè â äâîéñòâåííûå, à Inv ïåðåõîäèò â òîæäåñòâî
x = x . Ïîýòîìó è ïðè çàìåíå ∗ èñòèííîñòü áóëåâà ðàâåíñòâà ñîõðàíèòñÿ. Â ðåçóëüòàòå
óòâåðæäåíèå (1) äîêàçàíî. Ñïðàâåäëèâîñòü óòâåðæäåíèÿ (2) ñëåäóåò èç ðàâåíñòâà V = z ,
ãäå z  ñîîòâåòñòâóþùèé ýëåìåíò áóëåâîé àëãåáðû: V = z ⇒ V ∗ = z ⇒ V ∗ = V .
  2Â  íåêîòîðûõ àêñèîìàòèçàöèÿõ äîïîëíåíèå ââîäèòñÿ êàê ýëåìåíò, óäîâëåòâîðÿþùèé óñëîâèÿì êîì-
ïëèìåíòàðíîñòè è èçîëèðîâàííîñòè. Íî òîãäà íåîáõîäèìî äîêàçûâàòü åãî åäèíñòâåííîñòü, ÷åì è îáúÿñ-
íÿåòñÿ íàçâàíèå ëåììû.


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


Çàìå÷àíèÿ.   1.  (1) ïðåäïîëàãàåòñÿ, ÷òî ðàññìàòðèâàåìîå ðàâåíñòâî èñòèííî äëÿ ëþ-
     áûõ ýëåìåíòîâ áóëåâîé àëãåáðû. Íàïðèìåð, ñïðàâåäëèâîñòü x y = o äëÿ íåêîòîðûõ
     x è y íå îçíà÷àåò, ÷òî x y = ι (ïðåîáðàçîâàíèå ).
       Ýòî çàìå÷àíèå áóäåò îòíîñèòñÿ è ê ðàññìàòðèâàåìûì äàëåå ïðèíöèïàì äâîéñòâåí-
       íîñòè äëÿ äðóãèõ ñòðóêòóð3 .
    2. Åñëè ïðè çàìåíå    ïðåíåáðå÷ü óêàçàíèåì ¾ x íå åñòü óíèâåðñàëüíàÿ ãðàíü¿, òî,
       íàïðèìåð, ïðèìåíÿÿ ê çàêîíó o, ïîëó÷èì íåâåðíîå ðàâåíñòâî x ι = x âìåñòî
       âåðíîãî x o = x , à ïðèìåíÿÿ ∗ ê DeM 1  íåâåðíîå ðàâåíñòâî x     y = x y
       âìåñòî âåðíîãî (x    y ) = x y.

    Íåòðóäíî îáíàðóæèòü, ÷òî ïðèâåä¼ííàÿ ñèñòåìà èç 21-îé àêñèîìû èçáûòî÷íà.

    ˆ Çàêîíû èäåìïîòåíòíîñòè âûòåêàþò èç çàêîíîâ ïîãëîùåíèÿ. Äåéñòâèòåëüíî, äëÿ
      ëþáîãî x ∈ B èìååò ìåñòî
                                                Abs1                      Abs2
                                      x    x = x        (x    (x    x)) = x.

       Èäåìïîòåíòíîñòü ïåðåñå÷åíèÿ ñëåäóåò èç òîëüêî ÷òî äîêàçàííîãî ïî ïðèíöèïó äâîé-
       ñòâåííîñòè4 .
    ˆ Çàêîíû ïîãëîùåíèÿ âëåêóò ýêâèâàëåíòíîñòü äèñòðèáóòèâíûõ çàêîíîâ. Äåéñòâè-
      òåëüíî, äëÿ ëþáûõ ýëåìåíòîâ x, y, z áóëåâîé àëãåáðû èìååì

                               Dtr1                                       Abs1, Dtr1
         (x     z)   (y   z) = (x          (y     z))   (z    (y    z))      =
                                                                                         Abs2
                                                             = (x   y)      (x    z)   z = (x      y)    z.

       ò.å. Dtr1 ⇒ Dtr2. Äâîéñòâåííî ïîêàçûâàåòñÿ, ÷òî Dtr2 ⇒ Dtr1.
    ˆ Èñïîëüçóÿ çàêîíû äèñòðèáóòèâíîñòè, àññîöèàòèâíîñòè, ñâîéñòâà äîïîëíåíèÿ è åäè-
      íèöû ïîêàçûâàåòñÿ, ÷òî äëÿ ëþáûõ x, y ∈ B ñïðàâåäëèâî

                          (x    y)    (x    y ) = ι      è     (x   y)     (x      y ) = o.

        ñîîòâåòñòâèè ñ ëåììîé 1.1 î åäèíñòâåííîñòè äîïîëíåíèÿ ýòî îçíà÷àåò, ÷òî
       x   y  äîïîëíåíèå ê x y , ò.å. èç óêàçàííûõ çàêîíîâ âûâåäåí çàêîí DeM 1.
       Àíàëîãè÷íàÿ âûâîäèìîñòü DeM 2 ñëåäóåò èç ïðèíöèïà äâîéñòâåííîñòè.

   Èçáûòî÷íîñòü ñèñòåìû àêñèîì îáû÷íî íå ÿâëÿåòñÿ ïîìåõîé â ïðàêòè÷åñêîé ðàáîòå,
è ïðè îïðåäåëåíèè áóëåâîé àëãåáðû óäîáíî çàäàâàòü èìåííî ïðèâåä¼ííûé íàáîð àêñèîì,
ñîäåðæàùèé âñå îñíîâíûå õàðàêòåðíûå äëÿ íå¼ ñîîòíîøåíèÿ. Âîïðîñ î íåèçáûòî÷íîé ñè-
ñòåìå àêñèîì äëÿ áóëåâîé àëãåáðû îêàçàëñÿ íå òàêèì ïðîñòûì, êàê ìîãëî áû ïîêàçàòüñÿ
íà ïåðâûé âçãëÿä. Â õîäå åãî èññëåäîâàíèÿ áûë îáíàðóæåí ðÿä èíòåðåñíûõ ôàêòîâ, ñ
íåêîòîðûìè èç êîòîðûõ ìû âñòðåòèìñÿ â äàëüíåéøåì. Çäåñü æå îòìåòèì âîñõîäÿùóþ
ê ðàáîòå Ý. Õàíòèíãòîíà5 ÷àñòî èñïîëüçóåìóþ ñèñòåìó, ñîäåðæàùóþ òîëüêî ïåðâûå âî-
ñåìü èç ïðèâåäåííûõ âûøå àêñèîì. Îäíàêî è óêàçàííàÿ ñîâîêóïíîñòü íå ÿâëÿåòñÿ íåçà-
âèñèìîé: ìîæíî ïîêàçàòü, ÷òî êàæäûé èç çàêîíîâ o, ι âûâîäèì èç îñòàëüíûõ ñåìè
àíàëîãè÷íî ïîêàçàííîìó âûøå äëÿ çàêîíîâ äèñòðèáóòèâíîñòè. Åäèíñòâåííàÿ èçâåñòíàÿ
    3 Îòìåòèì çäåñü, ÷òî âïåðâûå ïðèíöèï äâîéñòâåííîñòè áûë ñôîðìóëèðîâàí Ý. Øð¼äåðîì â 1877 ã.;
èì æå óêàçàíû íåêîòîðûå äðóãèå çàêîíû áóëåâîé àëãåáðû.
   4 Äëÿ íàñ óêàçàííûå ñëåäîâàíèÿ ïî÷òè î÷åâèäíû, îäíàêî îíè áûëè óñòàíîâëåíû âûäàþùèìñÿ íåìåö-
êèì ìàòåìàòèêîì Ð. Äåäåêèíäîì.
   5 Huntington E.V. Sets of independent postulates for algebra of logic.  Amer. Math. Soc., 1904, 5, p. 288-
309. Ïîäðîáíîñòè ñì. â [12].


1.2. Àëãåáðû ìíîæåñòâ                                                                    9


íà ñåãîäíÿøíèé äåíü (2008 ã.) áåçûçáûòî÷íàÿ ñàìîäâîéñòâåííàÿ ñèñòåìà àêñèîì áóëåâîé
àëãåáðû ñîäåðæèò ïî ïàðå çàêîíîâ Dtr, Abs, à òàêæå Cmp è Isl .
    Áóëåâà àëãåáðà ÿâëÿåòñÿ ïðèìåðîì àëãåáðàè÷åñêîé ñèñòåìû (ÀÑ), òî÷íåå, ÷àñòíî-
ãî ñëó÷àÿ ÀÑ  àëãåáðû . Ïðîèçâîëüíàÿ ÀÑ A çàäàåòñÿ ïàðîé ìíîæåñòâ A è σA , ò.å.
A = A, σA . Çäåñü A  íîñèòåëü, à σA  ñèãíàòóðà ÀÑ ñ íîñèòåëåì A. Íîñèòåëü ÀÑ
åñòü íåêîòîðîå íåïóñòîå ìíîæåñòâî. Ñèãíàòóðà σA àëãåáðû ñ íîñèòåëåì A åñòü óïîðÿ-
äî÷åííàÿ ñîâîêóïíîñòü ñèìâîëîâ îïåðàöèé, îòíîøåíèé è îñîáûõ ýëåìåíòîâ èç A. Åñëè
íóæíî ÿâíî óêàçàòü ìåñòíîñòü èëè àðíîñòü îïåðàöèé è îòíîøåíèé, èõ çàïèñûâàþò êàê
âåðõíèå èíäåêñû ó ñîîòâåòñòâóþùèõ ñèìâîëîâ (ñèìâîëû îñîáûõ ýëåìåíòîâ èìåþò íóëå-
âóþ ìåñòíîñòü). Åñëè ðåçóëüòàò íåêîòîðîé îïåðàöèè íàä ýëåìåíòàìè ìíîæåñòâà âñåãäà
ëåæèò â ýòîì ìíîæåñòâå, òî ãîâîðÿò, ÷òî ìíîæåñòâî óñòîé÷èâî îòíîñèòåëüíî äàííîé
îïåðàöèè, à îïåðàöèÿ óñòîé÷èâà íà äàííîì ìíîæåñòâå.  îïðåäåëåíèè àëãåáðû òðåáóåò-
ñÿ, ÷òîáû âñå îïåðàöèè áûëè óñòîé÷èâû íà å¼ íîñèòåëå. Çäåñü ïðèâåäåíî íåôîðìàëüíîå
ïîÿñíåíèå ïîíÿòèÿ ÀÑ, òî÷íûå îïðåäåëåíèÿ áóäóò äàíû â ï. 6.1.  ïðèëîæåíèè äëÿ
ïðèâåäåíû ôîðìàëüíûå îïèñàíèÿ êëàññè÷åñêèõ óíèâåðñàëüíûõ àëãåáðàè÷åñêèõ ñèñòåì.
Êàê ñèíîíèìîì ïîíÿòèÿ ÀÑ ìû áóäåì ïîëüçîâàòüñÿ òåðìèíîì ¾ñòðóêòóðà¿.
    Äëÿ ñëó÷àÿ áóëåâîé àëãåáðû ñ íîñèòåëåì B èìååì σB =         2
                                                                  , 2 , 1 , o0 , ι0 (ñèãíà-
òóðà íå ñîäåðæèò ñèìâîëîâ îòíîøåíèé), è ñâîéñòâà óêàçàííûõ îïåðàöèé è âûäåëåííûõ
ýëåìåíòîâ íîñèòåëÿ îïèñûâàþòñÿ óêàçàííûìè âûøå çàêîíàìè. Åñëè ðàññìàòðèâàåòñÿ ÀÑ
çàäàííîé ñèãíàòóðû, òî, ñòðåìÿñü ê êðàòêîñòè, äëÿ å¼ îáîçíà÷åíèÿ ÷àñòî èñïîëüçóþò ïðî-
ñòî ñèìâîë íîñèòåëÿ. Ìû áóäåì òàê ïîñòóïàòü, êîãäà ýòî íå ïðèâîäèò ê íåäîðàçóìåíèÿì.


1.2 Àëãåáðû ìíîæåñòâ
   Ðàññìîòðèì íåïóñòîå ìíîæåñòâî A è íåêîòîðóþ ñîâîêóïíîñòü S(A) åãî ïîäìíîæåñòâ,
óñòîé÷èâóþ îòíîñèòåëüíî îïåðàöèé îáúåäèíåíèÿ (∪), ïåðåñå÷åíèÿ (∩) è äîïîëíåíèÿ (− )
äî A. Ìíîæåñòâî âñåõ ïîäìíîæåñòâ (áóëåàí ) A áóäåì îáîçíà÷àòü P(A). Ïîíÿòíî, ÷òî
{ ∅, A } ⊆ S(A) ⊆ P(A).
   Àëãåáðàè÷åñêàÿ ñèñòåìà S(A), ∪, ∩, − , ∅, A íàçûâàåòñÿ àëãåáðîé ìíîæåñòâ (äðó-
ãèå íàçâàíèÿ  ïîëå ìíîæåñòâ, àëãåáðà Êàíòîðà, àëãåáðà êëàññîâ ). Àëãåáðó ìíîæåñòâ
ñ íîñèòåëåì P(A) áóäåì íàçûâàòü òîòàëüíîé (íàä A), à ñ äâóõýëåìåíòíûì íîñèòåëåì
{∅, A}  òðèâèàëüíîé àëãåáðàìè ìíîæåñòâ.
   Íåòðóäíî ïîêàçàòü, ÷òî èìååò ìåñòî
Óòâåðæäåíèå 1.1. Âñÿêàÿ àëãåáðà ìíîæåñòâ S(A) åñòü áóëåâà àëãåáðà ñ íóë¼ì ∅ è
åäèíèöåé A .

Äîêàçàòåëüñòâî. Äîñòàòî÷íî óáåäèòüñÿ, ÷òî â ëþáîé àëãåáðå S(A) ìíîæåñòâ âûïîëíÿþò-
ñÿ ïåðâûå âîñåìü çàêîíîâ áóëåâîé àëãåáðû â ôîðìóëèðîâêå êîòîðûõ ïðîèçâåäåíû ïîä-
ñòàíîâêè → ∩, → ∩, → − , ι → A, o → ∅.
   Çàêîíû êîììóòàòèâíîñòè, o, ι è Cmp , Isl îïèñûâàþò ýëåìåíòàðíûå ñâîéñòâà
òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé.
    ñèëó ïðèíöèïà äâîéñòâåííîñòè äîñòàòî÷íî äîêàçàòü ñïðàâåäëèâîñòü äëÿ àëãåáðû
ìíîæåñòâ ïåðâîãî çàêîíà äèñòðèáóòèâíîñòè: (X ∪ Y ) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z)
äëÿ ëþáûõ ïîäìíîæåñòâ X, Y, Z ∈ S(A). Äëÿ ýòîãî ðàññìîòðèì ïðîèçâîëüíûé ýëåìåíò
w ∈ (X ∪ Y ) ∩ Z . Îí ïðèíàäëåæèò Z , à òàêæå ëèáî X , ëèáî Y .  ïåðâîì ñëó÷àå
w ∈ X ∩ Z , à âî âòîðîì  w ∈ Y ∩ Z . Ñëåäîâàòåëüíî, w ∈ (X ∩ Z) ∪ (Y ∩ Z). Ïóñòü
òåïåðü w ∈ (X ∩ Z) ∪ (Y ∩ Z). Òîãäà w ∈ X ∩ Z èëè w ∈ Y ∩ Z , îòêóäà w ∈ Z è ëèáî
w ∈ X , ëèáî w ∈ Y , ò.å. w ∈ (X ∪ Y ) ∩ Z .


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


Ïðèìåð 1.1. σ -àëãåáðà ïîäìíîæåñòâ ïðîñòðàíñòâà ýëåìåíòàðíûõ ñîáûòèé, èñïîëüçóåìàÿ
â àêñèîìàòèêå òåîðèè âåðîÿòíîñòåé, åñòü àëãåáðà ìíîæåñòâ è, ñëåäîâàòåëüíî, áóëåâà àë-
ãåáðà.
   Çàìåòèì, ÷òî ñèñòåìà ïîäìíîæåñòâ íåêîòîðîãî ìíîæåñòâà ìîæåò îêàçàòüñÿ áóëåâîé
àëãåáðîé, íå ÿâëÿÿñü ïðè ýòîì àëãåáðîé ìíîæåñòâ. Ýòî áóäåò, êîãäà õîòÿ áû îäíà èç
îïåðàöèé íà äàííîé ñèñòåìå íå ñîâïàäàåò ñ ñîîòâåòñòâóþùåé òåîðåòèêî-ìíîæåñòâåííîé.
Íèæå òàêèå ñèñòåìû âñòðåòÿòñÿ.
   Ïðîâåðêó ðàâåíñòâ áóëåâîé àëãåáðû ëåã÷å âñåãî ïðîâîäèòü, èñïîëüçóÿ èçâåñòíûå ÷è-
òàòåëþ äèàãðàììû Ýéëåðà-Âåííà6 , â êîòîðûõ ìíîæåñòâî A èçîáðàæàåòñÿ ïðÿìîóãîëü-
íèêîì, à åãî ïîäìíîæåñòâà  ðàçëè÷íûìè êðóãàìè èëè îâàëàìè îáùåãî ïîëîæåíèÿ â
ýòîì ïðÿìîóãîëüíèêå. Ïðè ýòîì îáúåäèíåíèþ ýëåìåíòîâ ñîîòâåòñòâóåò îáúåäèíåíèå, à
ïåðåñå÷åíèþ  îáùàÿ ÷àñòü ôèãóð, ñâÿçàííûõ ñ äàííûìè ýëåìåíòàìè. Òàêèå äèàãðàììû
ñòðîÿò îòäåëüíî äëÿ ëåâûõ è ïðàâûõ ÷àñòåé ïðîâåðÿåìîãî ðàâåíñòâà, à èíòåðåñóþùóþ
ïðè äàííîé ïðîâåðêå îáëàñòü çàøòðèõîâûâàþò. Åñëè íà ñîîòâåòñòâóþùåé ïàðå äèàãðàìì
çàøòðèõîâàííûìè îêàçàëèñü îäèíàêîâûå îáëàñòè, òî, ðàññìàòðèâàÿ ðàçëè÷íûå ïîäîá-
ëàñòè A ïîëó÷àþùèåñÿ â ðåçóëüòàòå ïåðåñå÷åíèÿ ôèãóð, ìîæíî ïðîâåñòè ôîðìàëüíîå
äîêàçàòåëüñòâî, ïîäîáíîå ïðèâåä¼ííîìó âûøå.
   Âïðî÷åì, íà ïðàêòèêå ìîæíî ïðîñòî îãðàíè÷èòüñÿ óêàçàííîé êîíñòàòàöèåé, åñëè ñî-
îòâåòñòâóþùèå ïîñòðîåíèÿ ïðîâîäèòü äëÿ ïðàâèëüíî ïîñòðîåííûõ äèàãðàìì Ýéëåðà-
Âåííà. Íèæå äàííîå ïîíÿòèå ôîðìàëèçóåòñÿ.
Îïðåäåëåíèå 1.2. Ïóñòü äàíî íåïóñòîå ìíîæåñòâî U è ñèñòåìà åãî ïîäìíîæåñòâ
{X1 , . . . , Xn }. Ñîñòàâëÿþùèå s1 , . . . , sk äàííîé ñèñòåìû ìíîæåñòâ çàäàþòñÿ ñëåäóþ-
ùèì èíäóêòèâíûì îïðåäåëåíèåì:
     1) ñîñòàâëÿþùèå ñèñòåìû {X1 } ñóòü X1 è X 1 ;
     2) åñëè s  ñîñòàâëÿþùàÿ ñèñòåìû {X1 , . . . , Xn−1 }, òî s ∩ Xn è s ∩ X n  ñîñòàâëÿ-
        þùèå ñèñòåìû {X1 , . . . , Xn−1 , Xn }.
Ñèñòåìà ìíîæåñòâ X íàçûâàåòñÿ íåçàâèñèìîé, åñëè âñå å¼ ñîñòàâëÿþùèå íåïóñòû.
Ïðèìåð 1.2. Ðàññìîòðèì ìíîæåñòâî U = {a, b, c, d}.
     1. Ñîñòàâëÿþùèå ñèñòåìû X1 = {a, b}, X2 = {b} ñóòü {b}, ∅, {a}, {c, d}, è, ñëåäî-
        âàòåëüíî, äàííàÿ ñèñòåìà ìíîæåñòâ íå ÿâëÿåòñÿ íåçàâèñèìîé.
     2. Ñîñòàâëÿþùèå ñèñòåìû X1 = {a, b}, X2 = {b, c} ñóòü {b}, {c}, {a}, {d}, è, ñëå-
        äîâàòåëüíî, äàííàÿ ñèñòåìà ìíîæåñòâ íåçàâèñèìà.

     Äëÿ σ ∈ { 0, 1 } è ìíîæåñòâà X ââåä¼ì îáîçíà÷åíèå X σ : X σ åñòü X , åñëè σ = 1 è
                                               m
                                                      σ
X , åñëè σ = 0. Áóëåâî âûðàæåíèå âèäà               Xj j , ãäå X1 , . . . , Xm ñóòü ïîïàðíî ðàçëè÷-
                                              j=1
íûå ïîäìíîæåñòâà íåêîòîðîãî ìíîæåñòâà, à σj ∈ { 0, 1 }, íàçûâàåòñÿ èõ ýëåìåíòàðíûì
ïåðåñå÷åíèåì èëè êîíñòèòóåíòîé. Ïîíÿòíî, ÷òî êîíñòèòóåíòû ëèáî ñîâïàäàþò, ëèáî íå
ïåðåñåêàþòñÿ.
Ëåììà 1.2 (Ñâîéñòâà ñîñòàâëÿþùèõ ñèñòåìû ìíîæåñòâ).                1. Ïðîèçâîëüíàÿ ñî-
        ñòàâëÿþùàÿ ñèñòåìû ìíîæåñòâ {X1 , . . . , Xn }, Xi ∈ U , i = 1, n, ïðåäñòàâèìà
        â âèäå ýëåìåíòàðíîãî ïåðåñå÷åíèÿ è, ñëåäîâàòåëüíî, íåðàâíûå ñîñòàâëÿþùèå íå
        ïåðåñåêàþòñÿ.
     2. Íåçàâèñèìàÿ ñèñòåìà èç n ìíîæåñòâ èìååò 2n ðàçëè÷íûõ ñîñòàâëÿþùèõ.
     3. Îáúåäèíåíèå âñåõ ñîñòàâëÿþùèõ ñîâïàäàåò ñ óíèâåðñàëüíûì ìíîæåñòâîì U .
  6 Ñì., íàïðèìåð, À.Ñ. Êóçè÷åâ. Äèàãðàììû Âåííà  Ì.: Íàóêà, 1968 èëè Ð. Ôîð, À. Êîôìàí, Ì. Äåíè-
Ïàïåí. Ñîâðåìåííàÿ ìàòåìàòèêà  Ì.: Ìèð, 1966.



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