Лекции по упорядоченным множествам и универсальной алгебре. Гуров С.И. - 7 стр.

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


ι0 , o 0 óêàçûâàþò íà âçàèìíóþ äîïîëíèòåëüíîñòü ýòèõ ýëåìåíòîâ. Çàêîíû Cmp 0 è Isl 0
ÿâëÿþòñÿ îñíîâíûìè çàêîíàìè, îïèñûâàþùèå ñâîéñòâà äîïîëíåíèÿ; îíè ïîñòóëèðóþò, ñî-
îòâåòñòâåííî, åãî ïîëíîòó è îáîñîáëåííîñòü. Çàêîí Inv 0 óêàçûâàåò íà èíâîëþòèâíîñòü
äîïîëíåíèÿ. Âçàèìíûå ñâîéñòâà áèíàðíûõ îïåðàöèé è äîïîëíåíèÿ îïèñûâàþòñÿ çàêîíà-
ìè Äå Ìîðãàíà (DeM 1, 2).
     Ââåä¼ííûå îïåðàöèè íàçûâàþò àáñòðàêòíûìè, ïîñêîëüêó íè îíè ñàìè, íè íîñèòåëü,
íà êîòîðîì îíè îïðåäåëåíû íèêàê íå êîíêðåòèçèðóþòñÿ è íèêàêèõ èíûõ òðåáîâàíèé, êðî-
ìå óäîâëåòâîðåíèÿ âûøåïðèâåä¼ííûì çàêîíàì, ê íèì íå ïðåäúÿâëÿåòñÿ.  ïðèëîæåíèÿõ
ýëåìåíòû áóëåâîé àëãåáðû èíòåðïðåòèðóþòñÿ êàê ïîäìíîæåñòâà íåêîòîðûõ ìíîæåñòâ,
êàê ñîáûòèÿ, âûñêàçûâàíèÿ, ñèãíàëû è äð.
Ëåììà 1.1 (Î åäèíñòâåííîñòè äîïîëíåíèÿ).                            2
                                                                        Â áóëåâîé àëãåáðå
                                        ½
                                            xuy = o
                                                               ⇔ y = x 0.
                                            xty = ι
Äîêàçàòåëüñòâî. (⇒, äîñòàòî÷íîñòü)
    uι       Cmp 0                    Com u, Dtr1
  y = yuι     =      y u (x t x 0 )         =           (y u x) t (y u x 0 ) =
                                                Isl 0                        Dtr, Abs, Com
                         = o t (y u x 0 ) = (x u x 0 ) t (y u x 0 )               =
                                                                                                       uι
                                                                             = (x t y) u x 0 = ι u x 0 = x 0 .
   (⇐, íåîáõîäèìîñòü) î÷åâèäíà  çàêîíû Cmp 0 è Isl 0 .                                                          ¤

    Îòäåëüíûé ýëåìåíò áóëåâîé àëãåáðû, à òàêæå ôîðìóëà, îïèñûâàþùàÿ ïðèìåíåíèå
êîíå÷íîãî ÷èñëà óêàçàííûõ îïåðàöèé ê ýëåìåíòàì íîñèòåëÿ, çàïèñàííîå â âèäå ñîîòâåò-
ñòâóþùåé ôîðìóëû, áóäåì íàçûâàòü áóëåâûì âûðàæåíèåì. ßñíî, ÷òî áóëåâî âûðàæåíèå
îïðåäåëÿåò íåêîòîðûé ýëåìåíò áóëåâîé àëãåáðû êàê çíà÷åíèå ôóíêöèè îò àðãóìåíòîâ 
ýëåìåíòîâ, âõîäÿùèõ â äàííîå âûðàæåíèå. Äâà âûðàæåíèÿ, ñâÿçàííûå çíàêîì = ïðåä-
ñòàâëÿþò ñîáîé áóëåâî ðàâåíñòâî. Òî÷íîå îïðåäåëåíèå äàííûõ ïîíÿòèé áóäåò äàíî â
ï. 5.4. Áóëåâî ðàâåíñòâî ìîæåò áûòü êàê èñòèííûì, òàê è ëîæíûì â çàâèñèìîñòè îò òî-
ãî, îïðåäåëÿþò ëè ëåâàÿ è ïðàâàÿ åãî ÷àñòè îäèí è òîò æå ýëåìåíò íîñèòåëÿ. Ïðèâåä¼ííûå
âûøå çàêîíû áóëåâîé àëãåáðû èñòèííû èìåííî â ýòîì ñìûñëå.
    Ïóñòü V  âûðàæåíèå èëè ðàâåíñòâî áóëåâîé àëãåáðû. Ðåçóëüòàòû îäíîâðåìåííîé
çàìåíû âñåõ ñèìâîëîâ u ↔ t è ι ↔ o â V áóäåì îáîçíà÷àòü V \ , à x ↔ x 0 , ãäå x 
íåêîòîðûé ýëåìåíò íîñèòåëÿ, íå ÿâëÿþùèéñÿ óíèâåðñàëüíîé ãðàíüþ  V [ . Åñëè æå â V
ïðîèçâîäÿòñÿ îáå óêàçàííûå çàìåíû, òî èõ ðåçóëüòàò îáîçíà÷èì V ∗ .  áóëåâîé àëãåáðå
ñïðàâåäëèâ ñëåäóþùèé
Ïðèíöèï äâîéñòâåííîñòè (äëÿ áóëåâîé àëãåáðû).          1. Åñëè V  èñòèííîå áóëåâî
     ðàâåíñòâî, òî ðàâåíñòâà V \ , V [ è V ∗ òàêæå èñòèííû.
  2. Åñëè V  âûðàæåíèå áóëåâîé àëãåáðû, òî V ∗ = V 0 .
   Äåéñòâèòåëüíî, ïðèâåä¼ííûå âûøå çàêîíû, êðîìå Inv 0 , ðàçáèâàþòñÿ íà ïàðû ïîñëå-
äîâàòåëüíî çàïèñàííûõ âçàèìîäâîéñòâåííûõ, ïðåõîäÿùèõ äðóã â äðóãà ïðè çàìåíå \ ; ïðè
ýòîì Inv 0 ïåðåõîäèò ñàì â ñåáÿ. Ïðåîáðàçîâàíèå [ ïåðåâîäèò âñå çàêîíû, êðîìå Inv 0 , èëè
ñ òî÷íîñòüþ äî îáîçíà÷åíèé â ñåáÿ, èëè â äâîéñòâåííûå, à Inv 0 ïåðåõîäèò â òîæäåñòâî
x0 = x0 . Ïîýòîìó è ïðè çàìåíå ∗ èñòèííîñòü áóëåâà ðàâåíñòâà ñîõðàíèòñÿ. Â ðåçóëüòàòå
óòâåðæäåíèå (1) äîêàçàíî. Ñïðàâåäëèâîñòü óòâåðæäåíèÿ (2) ñëåäóåò èç ðàâåíñòâà V = z ,
ãäå z  ñîîòâåòñòâóþùèé ýëåìåíò áóëåâîé àëãåáðû: V = z ⇒ V ∗ = z 0 ⇒ V ∗ = V 0 .
  2Â  íåêîòîðûõ àêñèîìàòèçàöèÿõ äîïîëíåíèå ââîäèòñÿ êàê ýëåìåíò, óäîâëåòâîðÿþùèé óñëîâèÿì êîì-
ïëèìåíòàðíîñòè è èçîëèðîâàííîñòè. Íî òîãäà íåîáõîäèìî äîêàçûâàòü åãî åäèíñòâåííîñòü, ÷åì è îáúÿñ-
íÿåòñÿ íàçâàíèå ëåììû.