Лекции по упорядоченным множествам и универсальной алгебре: Учебно-методическое пособие
В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам pi решёткам. Изучаются свойства модулярных, дистрибутивных решёток и решёток с дополнениями. Указанным разделам посвящены первые главы. В последней главе рассматриваются универсальные алгебры. Вводится понятие алгебраической системы, рассматриваются различные типы таких систем и доказываются основные теоремы об их изоморфизме и гомоморфизме. Вводимые понятия и доказанные утверждения иллюстрируются большим количеством примеров. Пособие предназначено для студентов, изучающих соответствующие разделы алгебры и может быть использовано при самообразовании. Электронная версия пособия размещена на сайте факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова <a href="http://www.cs.msu.su" target="_blank">(www.cs.msu.su)</a>.
Ìîñêîâñêèé Ãîñóäàðñòâåííûé óíèâåðñèòåò
èì. Ì.Â. Ëîìîíîñîâà
Ôàêóëüòåò Âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè
Ñ.È. Ãóðîâ
ËÅÊÖÈÈ ÏÎ ÓÏÎÐßÄÎ×ÅÍÍÛÌ
ÌÍÎÆÅÑÒÂÀÌ È ÓÍÈÂÅÐÑÀËÜÍÎÉ
ÀËÃÅÁÐÅ
Ìîñêâà
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.
