Лекции по упорядоченным множествам и универсальной алгебре: Учебно-методическое пособие
В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам 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.