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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    5.4. Áóëåâû ìíîãî÷ëåíû                                                                111


     Ìíîæåñòâî âñåõ áóëåâûõ ìíîãî÷ëåíîâ íàä Xn îáîçíà÷èì ÷åðåç Pn .
     Ïîíÿòíî, ÷òî áóëåâû ìíîãî÷ëåíû  ôîðìàëüíûå ñòðîêè ñèìâîëîâ (ñëîâà). Ïîä çàïè-
ñüþ p = q ìû áóäåì ïîíèìàòü, ÷òî ìíîãî÷ëåíû p è q ñîâïàäàþò êàê ñòðîêè ñèìâîëîâ,
ò.å. èõ ñèíòàêñè÷åñêîå òîæäåñòâî, ãîâîðÿ ïðè ýòîì, ÷òî äàííûå ìíîãî÷ëåíû ðàâíû. Äà-
ëåå ìû áóäåì ïîëüçîâàòüñÿ èçâåñòíûìè ÷èòàòåëþ ïðàâèëàìè ýêîíîìèè ñêîáîê  âìåñòî
(xi ) , (0) è (1) ïèñàòü xi , 0 è 1 ñîîòâåòñòâåííî  è ñ÷èòàòü, ÷òî p = q , åñëè äàí-
íûå ìíîãî÷ëåíû ñîâïàäàþò ïðè âîññòàíîâëåíèè âñåõ ñêîáîê ñîãëàñíî îïðåäåëåíèþ 5.5.
Ëþáîé áóëåâ ìíîãî÷ëåí íàä n ïåðåìåííûìè ìîæíî ðàññìàòðèâàòü êàê ìíîãî÷ëåí íàä
n + 1 ïåðåìåííîé, ïîýòîìó

                           P1 ⊂ P2 ⊂ . . . ⊂ Pn ⊂ Pn+1 ⊂ . . . .

   Çàìåòèì, ÷òî Pn íå ÿâëÿåòñÿ áóëåâîé àëãåáðîé, ïîñêîëüêó x1 x2 = x2 x1 è
x1 x2 = x2 x1 . Äëÿ îòîæäåñòâëåíèÿ ïîäîáíûõ âûðàæåíèé ââåä¼ì ïîíÿòèå ïîëè-
íîìèàëüíîé ôóíêöèè, èíäóöèðîâàííîé ìíîãî÷ëåíîì íà áóëåâîé àëãåáðå B , îáîáùàþùåå
èçâåñòíîå ÷èòàòåëþ ïîíÿòèå áóëåâîé ôóíêöèè [17] (ñëó÷àé B = 2 = {0, 1}).

Îïðåäåëåíèå 5.6. Ïóñòü B  áóëåâà àëãåáðà è p  áóëåâ ìíîãî÷ëåí èç Pn . Îáîçíà÷èì
÷åðåç pB (b1 , . . . , bn ) ýëåìåíò èç B , êîòîðûé ïîëó÷àåòñÿ èç p çàìåíîé êàæäîãî xi íà
bi ∈ B, i = 1, . . . , n. Òîãäà îòîáðàæåíèå

                      pB : B n → B,     (b1 , . . . , bn ) → pB (b1 , . . . , bn )   (5.2)

íàçûâàåòñÿ ïîëèíîìèàëüíîé ôóíêöèåé, èíäóöèðîâàííîé áóëåâûì ìíîãî÷ëåíîì p íà B .

Ïðèìåð 5.7.   1. Ïóñòü B = 2, n = 2, p = x1 x2 è q = x2 x1 . Òîãäà p = q , pB = a∨b,
     qB = b ∨ a, ãäå a, b ∈ {0, 1} è pB = qB .
  2. Ïóñòü B = P(A), n = 2, p = (x1 x2 ) è q = x1         x2 . Òîãäà îïÿòü p = q , à
     pB = X ∪ Y , qB = X ∩ Y , ãäå X, Y ⊆ A è ñíîâà pB = qB .
Îïðåäåëåíèå 5.7. Äâà áóëåâûõ ìíîãî÷ëåíà p, q ∈ Pn íàçûâàþòñÿ ýêâèâàëåíòíûìè
(ñèìâîëè÷åñêè p ∼ q ), åñëè ðàâíû èõ ïîëèíîìèàëüíûå ôóíêöèè íà 2, ò.å.

                                      p ∼ q ⇔ p2 = q2 .

   Ëåãêî âèäåòü, ÷òî ∼ äåéñòâèòåëüíî åñòü îòíîøåíèå ýêâèâàëåíòíîñòè íà Pn , ïîñêîëü-
êó åãî ñâîéñòâà ðåôëåêñèâíîñòè, ñèììåòðè÷íîñòè è òðàíçèòèâíîñòè íàñëåäóþòñÿ èç îò-
íîøåíèÿ ðàâåíñòâà ôóíêöèé.
                 n
   Îáîçíà÷èì PB = {pB | p ∈ Pn }  ìíîæåñòâî âñåõ ïîëèíîìèàëüíûõ ôóíêöèé, èíäó-
öèðîâàííûõ ìíîãî÷ëåíàìè èç Pn íà B .

Òåîðåìà 5.10. Pn / ∼ åñòü áóëåâà àëãåáðà, è Pn / ∼ ∼b P2 .
                                                   =   n


                                             n
Äîêàçàòåëüñòâî. Îïðåäåëèì îòîáðàæåíèå ϕ : P2 → Pn / ∼, êîòîðîå ïåðåâîäèò ïîëèíîìè-
                    n
àëüíóþ ôóíêöèþ P2 , èíäóöèðîâàííóþ ìíîãî÷ëåíîì p íà 2 â êëàññ ýêâèâàëåíòíîñòè
[p]∼ . Äàííîå îïðåäåëåíèå êîððåêòíî, ò.ê. p2 = q2 ⇒ p ∼ q ⇒ [p]∼ = [q]∼ . Ëåãêî
ïðîâåðèòü, ÷òî ϕ è åñòü èñêîìûé áóëåâ èçîìîðôèçì.

Òåîðåìà 5.11. Åñëè B  áóëåâà àëãåáðà, òî è PB  áóëåâà àëãåáðà, ïðè÷¼ì PB
                                                                                        n
                                             n                           n
                                                                                     BB .
                                                       n
Äîêàçàòåëüñòâî. Íåîáõîäèìî óáåäèòüñÿ â óñòîé÷èâîñòè PB îòíîñèòåëüíî îïåðàöèé îáú-
åäèíåíèÿ, ïåðåñå÷åíèÿ è äîïîëíåíèÿ, à òàêæå, ÷òî PB ñîäåðæèò óêàçàííûå â òåîðåìå 5.2
                                                  n

ïîñòîÿííûå ôóíêöèè f0 è f1 .


112                                                           Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


      Äëÿ    èìååì
                                                               (5.2)               n
                           (pB      qB )(a) = pB (a)      qB (a) = (p   q)B (a) ∈ PB

äëÿ ïðîèçâîëüíîãî a ∈ B n . Äëÿ  è äîêàçàòåëüñòâî àíàëîãè÷íî.
   Êðîìå òîãî, f0 = 0 è f1 = 1 äëÿ ëþáîé áóëåâîé àëãåáðû B è ïî (5.2) ýòè ôóíêöèè
               n
ñîäåðæàòñÿ â PB .
   Ñ ïîìîùüþ òåîðåìû Ñòîóíà ïîêàçûâàåòñÿ, ÷òî ïîëèíîìèàëüíûå ôóíêöèè, ñîîòâåò-
ñòâóþùèå ýêâèâàëåíòíûì ìíîãî÷ëåíàì, ñîâïàäàþò íà ëþáîé áóëåâîé àëãåáðå, à íå òîëüêî
íà 2, ò.å. ñïðàâåäëèâà

Òåîðåìà 5.12. Ïóñòü p, q ∈ Pn è p ∼ q . Òîãäà äëÿ ïðîèçâîëüíîé áóëåâîé àëãåáðû B
ñïðàâåäëèâî pB = qB .

   Äîêàçàòåëüñòâî ìîæíî íàéòè â [8].
   ×àñòî âîçíèêàåò ïîòðåáíîñòü çàìåíèòü äàííûé ìíîãî÷ëåí ýêâèâàëåíòíûì åìó áîëåå
ïðîñòûì ìíîãî÷ëåíîì. Äàííóþ ïðîáëåìó ðåøàþò â äâà ýòàïà. Ñíà÷àëà ââîäÿò ò.í. íîð-
ìàëüíûå ôîðìû ìíîãî÷ëåíîâ. Ñîâîêóïíîñòü íîðìàëüíûõ ôîðì îáåñïå÷èâàåò íàëè÷èå ñè-
ñòåìû ïðåäñòàâèòåëåé äëÿ êàæäîãî êëàññà ýêâèâàëåíòíîñòè ìíîæåñòâà Pn . Äàëåå çàäà÷à
ñâîäèòñÿ ê íàõîæäåíèþ êðàò÷àéøåãî â òîì èëè èíîì ñìûñëå ìíîãî÷ëåíà, ýêâèâàëåíòíîãî
äàííîé íîðìàëüíîé ôîðìå.

Îïðåäåëåíèå 5.8. Ìíîæåñòâî N ⊆ Pn íàçûâàåòñÿ ñèñòåìîé ñîâåðøåííûõ íîðìàëüíûõ
ôîðì, åñëè
      ˆ äëÿ ëþáîãî ýëåìåíòà Pn íàéä¼òñÿ ýêâèâàëåíòíûé åìó ýëåìåíò N ;
      ˆ äâà ðàçíûõ ýëåìåíòà N íåýêâèâàëåíòíû.

   Áóäåì äàëåå ïîëüçîâàòüñÿ îáîçíà÷åíèåì xσ , àíàëîãè÷íûì ââåä¼ííîìó â ï. 1.2 äëÿ
ìíîæåñòâ, à èìåííî, äëÿ σ ∈ {0, 1} è x ∈ { x1 , . . . , xn , o, ι} ïîëîæèì

                    x1 = xi ,
                     i               x 0 = xi ,
                                       i            o1 = 0,   o0 = 1,   ι1 = 1,   ι0 = 0.

Ïîñëåäíèå ðàâåíñòâà ãîâîðÿò î òîì, ÷òî ìû áóäåì äàëåå â ðàìêàõ äàííîãî ðàçäåëà äëÿ
ïðîñòîòû ïîëüçîâàòüñÿ ñèìâîëàìè 0 è 1 äëÿ îáîçíà÷åíèÿ íóëÿ è åäèíèöû áóëåâîé àëãåáðû
ñîîòâåòñòâåííî. Âûðàæåíèÿ âèäà xi , xi , à òàêæå 0 è 1 áóäåì íàçûâàòü ëèòåðàëàìè.
    Ïóñòü B  áóëåâà àëãåáðà, p  áóëåâ ìíîãî÷ëåí èç Pn . Ïîëèíîìèàëüíóþ ôóíêöèþ
pB (b1 , . . . , bn ) : 2n → 2, èíäóöèðîâàííóþ p íà B , îáîçíà÷èì fp . Ýëåìåíòû 2n áóäåì
îáîçíà÷àòü α, β, . . .. Òàêèì îáðàçîì, íàïðèìåð, α = (α1 , . . . , αn ), αi ∈ {0, 1}, i = 1, n.
Ôóíêöèè fp ñîïîñòàâëåíû äâà ìíîæåñòâà Nfp è Nfp å¼ åäèíè÷íûõ è íóëåâûõ íàáîðîâ.
                                                 1     0

Ñëåäóþùèå äâà áóëåâûõ ìíîãî÷ëåíà

       pd (fp ) =                           xα1
                                             1    ...   xαn
                                                         n      è
                                       1
                    α=(α1 , ..., αn )∈Nfp


       pc (fp ) =                           xα1
                                             1    ...   xαn
                                                         n
                                       0
                    α=(α1 , ..., αn )∈Nfp


ïðè Nfp = ∅ è Nfp = ∅ íàçûâàþòñÿ ñîîòâåòñòâåííî ñîâåðøåííûìè äèçúþíêòèâíîé è
      1             0

êîíúþíêòèâíîé íîðìàëüíûìè ôîðìàìè (ÑÄÍÔ è ÑÊÍÔ) ìíîãî÷ëåíà p. Ïðè Nfp = ∅        1

ïîëàãàþò pd (fp ) = 0, à ïðè Nfp = ∅  pc (fp ) = 1. ßñíî, ÷òî äàííûå ôîðìû îïðåäåëåíû
                              0

îäíîçíà÷íî ñ òî÷íîñòüþ äî ïîðÿäêà ñîîòâåòñòâóþùèõ ÷ëåíîâ. Çàìåòèì, ÷òî ÑÄÍÔ äëÿ


5.4. Áóëåâû ìíîãî÷ëåíû                                                                                                                     113


ìíîãî÷ëåíà íàä {x1 } íàçûâàåòñÿ ðàçëîæåíèåì Øåííîíà ïî x = x1 : (a x)        (b x ),
ãäå a è b  èçâåñòíûå ýëåìåíòû áóëåâîé àëãåáðû B .
    ìíîãî÷èñëåííûõ ïîñîáèÿõ (ñì., íàïðèìåð, [8] èëè [17]) ïîêàçûâàåòñÿ ÷òî ñîâîêóï-
íîñòè ÑÄÍÔ è ÑÊÍÔ âñåõ p ∈ Pn åñòü ñèñòåìû ñîâåðøåííûõ íîðìàëüíûõ ôîðì. Êàê
ñëåäñòâèå, èìååì
               n                            n
  1. P2 = 22 è |Pn / ∼ | = 22 , ò.å. ëþáàÿ ôóíêöèÿ èç 2n â 2 ÿâëÿåòñÿ ïîëèíîìèàëüíîé
       n

     áóëåâîé ôóíêöèåé. Ïîýòîìó ãîâîðÿò, ÷òî àëãåáðà 2n ïîëèíîìèàëüíî ïîëíà.
                                                                                            n               n              n
  2. Åñëè |B| = m > 2, òî |PB | = |Pn / ∼ | = 22 < mm
                               n
                                                                                                                 = |B B |, ò.å. 2n 
     åäèíñòâåííî ïîëèíîìèàëüíî ïîëíàÿ áóëåâà àëãåáðà.

Ïîëèíîìèàëüíàÿ ïîëíîòà îçíà÷àåò, ÷òî êàæäóþ ôóíêöèþ ìîæíî ïðåäñòàâèòü ïîëèíî-
ìîì.
Ïðèìåð 5.8. Ïóñòü

                        p = ((x1            x2 )        x1 )      ((x2 )             (x1        x2 )) ∈ P2 .

Ïîñêîëüêó pB (0, 0) = pB (1, 0) = 0 è pB (0, 1) = pB (1, 1) = 1, èìååì

                                   p ∼ (x1               x2 )     (x1       x2 ) = pd (fp ).

Çàìåòèì, ÷òî ïðèìåíÿÿ çàêîíû áóëåâîé àëãåáðû, ìîæíî ïîëó÷èòü

                                 pd (fp ) ∼ (x1                x1 )     x2 ∼ 1             x2 ∼ x2 .

   ÑÄÍÔ áóëåâà ìíîãî÷ëåíà p ìîæíî ïîëó÷èòü ïî ñëåäóþùåìó àëãîðèòìó.

Øàã 1. Ïðèìåíÿÿ çàêîíû DeM 1, 2 äîáèâàåìñÿ, ÷òîáû çíàêè äîïîëíåíèÿ îòíîñèëèñü
    òîëüêî ê ëèòåðàëàì è êîíñòàíòàì.
Øàã 2. Ïðèìåíÿÿ çàêîíû Dtr1, 2 âûðàæàåì p â âèäå îáúåäèíåíèÿ ïåðåñå÷åíèé.
Øàã 3. Åñëè â íåêîòîðîì ïåðåñå÷åíèè îòñóòñòâóþò êàê xi , òàê è xi , â êà÷åñòâå ìíîæè-
    òåëÿ ê p äîáàâëÿåì xi xi .
Øàã 4. Ïðèìåíÿÿ (âîçìîæíî íåîäíîêðàòíî) DeM 1, ïîêà íå áóäåò ïîëó÷åíî îáúåäèíåíèå
    ïåðåñå÷åíèé. Ïðèìåíÿÿ çàêîí Id , ïîëó÷àåì ÑÄÍÔ p.
Ïðèìåð 5.9. Ïóñòü a, b ∈ 2 è

                                  p = ((a               x1 )     (b     x2 ) )         (x1        b) .

Øàã 1. p ∼ ((a        x1 )       (b   x2 ) )            (x1       b ) ∼ ((a                x1 )        (b    x2 ))     (x1        b ).
Øàã 2.

       ((a    x1 )      (b       x2 )) (x1               b ) ∼
                                 ∼ ((a   b              x2 ) (x1   b                 x2 )) (x1  b ) ∼
                                                               ∼ (a                  b x2 ) (x1    b x2 )                       (x1      b ).

Øàã 3. (a     b      x2 )    (x1        b        x2 )      (x1         b ) = y.
              1                         2                         3
     B ïåðåñå÷åíèè 1 îòñóòñòâóåò x1 , ïîýòîìó â 1 äîáàâëÿåì x1 x1 ; â ïåðåñå÷åíèè 2
     âñòðå÷àþòñÿ êàê x1 , òàê è x2 , ïîýòîìó â 2 íå äîáàâëÿåì íè÷åãî; â ïåðåñå÷åíèè 3
     îòñóòñòâóåò x2  äîáàâëÿåì x2 x2 . Èìååì

             y ∼ (a          b    (x1           x1 )      x2 )        (x1        b    x2 )        (b        x1       (x2       x2 )).


114                                                       Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


Øàã 4.

         (a    b    (x1 x1 ) x2 ) (x1    b x2 ) (b   x1     (x2                  x2 )) ∼
                      ∼ ((a   b x1 x2 ) (a    b x1    x2 ) (b                   x1    x2 )
                                 ((b  x1  x2 ) (b  x1     x2 ))                ∼
                       ∼ (a  b x1 x2 ) (a     b x1   x2 ) (b                    x1    x2 )
                                                     (b    x1                   x2 ) (b         x1    x2 ).
      Ðàññìîòðèì îòäåëüíî òðè ñðåäíèõ ïåðåñå÷åíèÿ, ñîäåðæàùèå x1                         x2 :

         ((a   b)    (x1   x2 ))     (b ( x1   x2 )) (b   (x1     x2 )) ∼
                                    ∼ ((a  b) b b ) (x1       x2 ) ∼
                                             ∼ ((a   b) 1) (x1        x2 ) ∼             1      (x1   x2 ).
      Èòàê, îêîí÷àòåëüíî ïîëó÷àåì èñêîìóþ ÑÄÍÔ
                      p ∼ (a       b     x1   x2 )   (1   x1   x2 )   (b       x1    x2 ).

   Ìåòîäû ìèíèìèçàöèè áóëåâûõ ìíîãî÷ëåíîâ èçâåñòíû ÷èòàòåëþ è ìû íå áóäåì èõ
çäåñü ðàññìàòðèâàòü (ñì., íàïðèìåð, [17]).


5.5 Óðàâíåíèÿ â áóëåâûõ àëãåáðàõ
   Â áóëåâûõ àëãåáðàõ ìîæíî ðåøàòü óðàâíåíèÿ. Óäîáíåå âñåãî ðàññìàòðèâàòü óðàâíå-
íèÿ íàä áóëåâûìè ìíîãî÷ëåíàìè.
   Òåïåðü ìîæíî ïåðåéòè ê áóëåâûì óðàâíåíèÿì è ìåòîäàì èõ ðåøåíèÿ. Ïðåæäå âñåãî,
íóæíî îïðåäåëèòü ñàì òåðìèí ¾áóëåâî óðàâíåíèå¿, ïîñêîëüêó ðàâåíñòâî p = q ãîâîðèò
ïðîñòî, ÷òî ìíîãî÷ëåíû p è q èäåíòè÷íû.
Îïðåäåëåíèå 5.9. Ïóñòü p è q  áóëåâû ìíîãî÷ëåíû èç Pn . Ïàðó (p, q) íàçîâ¼ì (áó-
ëåâûì) óðàâíåíèåì.
   Ïóñòü B  ïðîèçâîëüíàÿ áóëåâà àëãåáðà. Ýëåìåíò (b1 , . . . , bn ) ∈ B n íàçûâàåòñÿ
ðåøåíèåì óðàâíåíèÿ (p, q) â áóëåâîé àëãåáðå B , åñëè pB (b1 , . . . , bn ) = qB (b1 , . . . , bn ).
   Ìíîæåñòâî óðàâíåíèé {(pi , qi ) | i ∈ I ⊆ N} îáðàçóåò ñèñòåìó óðàâíåíèé. Ðåøåíèåì
ñèñòåìû íàçûâàåòñÿ îáùåå ðåøåíèå âñåõ óðàâíåíèé ñèñòåìû.
    Åñëè íå âîçíèêàåò ïóòàíèöû, óðàâíåíèå (p, q) äîïóñòèìî çàïèñûâàòü â âèäå p = q .
Íàïðèìåð, x1 x2 ∨x3 = x1 (x2 ∨x3 )  áóëåâî óðàâíåíèå, à (101)  åãî ðåøåíèå, ïîñêîëüêó
â (1 0) ∨ 1 = 1 (0 ∨ 1) = 1.
    Äàëåå â ðàìêàõ äàííîãî ðàçäåëà áóäåì, ñëåäóÿ òðàäèöèè, âìåñòî x y è x y ïèñàòü
x ∨ y è xy ( x y ) è íàçûâàòü äàííûå âûðàæåíèÿ ñóììîé è ïðîèçâåäåíèåì ñîîòâåòñòâåí-
íî. Äèçúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÄÍÔ) íàçîâ¼ì áóëåâ ìíîãî÷ëåí, ÿâëÿþùèéñÿ
ñóììîé êîíå÷íîãî ÷èñëà ïðîèçâåäåíèé, êîòîðûå â äàííîì ñëó÷àå áóäåì íàçûâàòü ýëå-
ìåíòàðíûìè êîíúþíêöèÿìè èëè êîíúþíêòàìè. Êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé
(ÊÍÔ) íàçîâ¼ì ïðîèçâåäåíèå êîíå÷íîãî ÷èñëà ñóìì, êîòîðûå â äàííîì ñëó÷àå áóäåì
íàçûâàòü ýëåìåíòàðíûìè äèçúþíêöèÿìè èëè äèçúþíêòàìè.
    Îòìåòèì èçâåñòíîå ñâîéñòâî íîðìàëüíûõ ôîðì. Åñëè D = C1 ∨ . . . ∨ Cl  ÄÍÔ íàä
{x1 , . . . , xn } è Ci  ýëåìåíòàðíûå êîíúþíêöèè, i = 1, l, à C = D1 ∨ . . . ∨ Dm  ÊÍÔ
íàä {x1 , . . . , xn } è Di  ýëåìåíòàðíûå äèçúþíêöèè, i = 1, m, òî
                                    l                                      l
                     D = 0 ⇔       & Ci = 0          è      C = 0 ⇔            Di = 0.                  (5.3)
                                   i=1                                 i=m


5.5. Óðàâíåíèÿ â áóëåâûõ àëãåáðàõ                                                               115


   Ïóñòü D = C1 ∨ . . . ∨ Cl , ãäå Ci  ýëåìåíòàðíûå êîíúþíêöèè, i = 1, l, åñòü
ÑÄÍÔ ìíîãî÷ëåíà p. Ñ ïîìîùüþ çàêîíîâ áóëåâîé àëãåáðû ïðåîáðàçóåì D â ÊÍÔ
C = D1 . . . Dm , ãäå Di  äèçúþíêòû, i = 1, m (èëè ñðàçó òåì èëè èíûì ïóò¼ì
ïîëó÷èì ÊÍÔ, ýêâèâàëåíòíóþ p). Òîãäà ðàâåíñòâî p = 0 áóäåò âûïîëíÿòüñÿ ïðè âû-
                                                           σ
ïîëíåíèè ëþáîãî èç ðàâåíñòâ Di = 0, i = 1, m. Åñëè Di =  xj j , Ii ⊆ {1, . . . , n}, òî
                                                                     j∈Ii
ëþáîé íàáîð β = (β1 , . . . , βn ), ãäå βk = σj , j ∈ Ii è βk ∈ {1, 0} j ∈ Ii áóäåò ðåøåíèåì
óðàâíåíèÿ p = 0.
   Èç ýòîãî ÿñíî, ÷òî äëÿ äàëüíåéøåãî óäîáíî ïðåîáðàçîâàòü p = q ê âèäó R = 0.
Òåîðåìà 5.13. Óðàâíåíèÿ p = q è pq ∨ p q = 0 èìåþò îäíè è òå æå ðåøåíèÿ.
Äîêàçàòåëüñòâî. Ïóñòü B  áóëåâà àëãåáðà è (b1 , . . . , bn ) ∈ B n . Äëÿ x = pB (b1 , . . . , bn ),
y = qB (b1 , . . . , bn ) èìååì (x ∨ y)(x ∨ y ) = xy ∨ x y . C îäíîé ñòîðîíû,

                                   x = y ⇒ xy ∨ x y = 0.

C äðóãîé, åñëè xy ∨ x y = 0, òî ïî òåîðåìå 5.1

                                    x∨y       (x ∨ y ) = xy,

îòêóäà x = y .
   Ïî äàííîé òåîðåìå ñèñòåìà óðàâíåíèé {(pi , qi ) | i = 1, . . . , m} ýêâèâàëåíòíà åäèí-
ñòâåííîìó óðàâíåíèþ

                 p1 q1 ∨ p1 q1 ∨ p2 q2 ∨ p2 q2 ∨ . . . ∨ pm qm ∨ pm qm = 0.

Âûðàçèâ ëåâóþ ÷àñòü â êîíúþíêòèâíîé ôîðìå, ïîëó÷èì, ÷òî ïðèâåä¼ííîå âûøå óðàâíå-
íèå èìååò ðåøåíèå, êîãäà õîòÿ áû îäèí èç ñîìíîæèòåëåé ïðèíèìàåò çíà÷åíèå 0. Òàêèì
îáðàçîì, ïîëó÷àþò âñå ðåøåíèÿ ñèñòåìû.
Ïðèìåð 5.10. Ðàññìîòðèì ñèñòåìó {(x1 x2 , x1 x3 ∨ x2 ), (x1 ∨ x2 , x3 )}. Ïåðåïèøåì å¼ â
îáû÷íîì âèäå
                                         x1 x 2 = x1 x3 ∨ x2 ,
                                     x1 ∨ x2 = x3 .
Ïî òåîðåìå 5.13 äàííàÿ ñèñòåìà ýêâèâàëåíòíà åäèíñòâåííîìó óðàâíåíèþ
     (x1 x2 )(x1 x3 ∨ x2 ) ∨ (x1 x2 ) (x1 x3 ∨ x2 ) ∨ (x1 ∨ x2 )x3 ∨ (x1 ∨ x2 ) x3 = 0.
Ïðåîáðàçóÿ ëåâóþ ÷àñòü â ÑÊÍÔ, ïîëó÷èì óðàâíåíèå
                            (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 ) = 0,
êîòîðîå èìååò òî æå ìíîæåñòâî ðåøåíèé, ÷òî è èñõîäíàÿ ñèñòåìà. Ýòè ðåøåíèÿ ÿâëÿþòñÿ
íóëÿìè ïåðâîãî è âòîðîãî ñîìíîæèòåëåé. Íàïðèìåð, â 2 äàííàÿ ñèñòåìà èìååò ðîâíî äâà
ðåøåíèÿ: (001) è (111) .
   B ïðîèçâîëüíîé áóëåâîé àëãåáðå ðåøåíèÿ çàïèñûâàþòñÿ áîëåå ñëîæíî, íî òàêæå äî-
ñòàâëÿþò 0 îáîèì ñîìíîæèòåëÿì ïîñëåäíåãî óðàâíåíèÿ.
   Îäèí èç ìåòîäîâ ðåøåíèÿ áóëåâûõ óðàâíåíèé îòíîñèòåëüíî îäíîãî íåèçâåñòíîãî ýëå-
ìåíòà x áóëåâîé àëãåáðû B, , , , o, ι ñîñòîèò â ïîñëåäîâàòåëüíîì âûïîëíåíèè ñëå-
äóþùèõ øàãîâ.
Øàã 1. Ïðèâîäèì äàííîå óðàâíåíèå ê ðàâíîñèëüíîìó óðàâíåíèþ ñ o â ïðàâîé ÷àñòè (÷òî
    îáåñïå÷èâàåòñÿ òåîðåìîé 5.13).


116                                                 Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


Øàã 2. Ïðèâîäèì ïîëó÷åííîå óðàâíåíèå ê ðàâíîñèëüíîìó óðàâíåíèþ âèäà

                                     (a     x)     (b        x ) = o,

    ãäå a è b  èçâåñòíûå ýëåìåíòû B . Ïîíÿòíî, ÷òî íà äàííîì øàãå íàõîäèòñÿ ðàç-
    ëîæåíèå Øåííîíà (ñì. 5.4) ïî ïåðåìåííîé x.
Øàã 3. Çàìåíÿåì ïîëó÷åííîå óðàâíåíèå íà ýêâèâàëåíòíóþ ñèñòåìó

                                 a        x = o,             b   x = o

    (èñïîëüçóåòñÿ ñâîéñòâî (5.3) ÑÄÍÔ).
Øàã 4. Åñëè b    a , òî èñõîäíîå óðàâíåíèå ðåøåíèÿ íå èìååò. Èíà÷å, ëþáîé x òàêîé,
    ÷òî
                  b x a          èëè     x = (b u) a = (a     u) b ,
       ãäå u  ïðîèçâîëüíûé ýëåìåíò B , åñòü èñêîìîå ðåøåíèå.

      Ïîñëåäíèé øàã îáîñíîâûâàþò ñëåäóþùèå âûêëàäêè. Èìååì

 a     x = 0 ⇔ (a    x)   a = a ⇔ (a         a)         (x       a ) = a ⇔
                                                                         ⇔x   a = a ⇔ x        a .

Àíàëîãè÷íî b x = 0 ⇔ b        x. Ñïðàâåäëèâîñòü ôîðìóëû äëÿ x ñ èñïîëüçîâàíèåì
ïðîèçâîëüíîãî ýëåìåíòà B ñëåäóåò èç

            b   x         x = b u äëÿ íåêîòîðîãî u ∈ B
                    ⇔                                                    ⇔ x = (b   u)   a .
            x   a         x a = x

Âòîðàÿ ôîðìà ïðåäñòàâëåíèÿ x ñëåäóåò èç ïåðâîé ïî ìîäóëÿðíîñòè.


6.1. Îñíîâíûå îïðåäåëåíèÿ. Ìîäåëè è àëãåáðû                                             117


Ãëàâà 6
Àëãåáðàè÷åñêèå ñèñòåìû
    ¾Òåîðèÿ óíèâåðñàëüíûõ àëãåáð óæå îêàçûâàåò è, íóæíî îæèäàòü, áëèæàéøåå äåñÿ-
òèëåòèÿ áóäåò îêàçûâàòü âñ¼ âîçðàñòàþùåå âëèÿíèå íà ðàçâèòèå âñåé îáùåé àëãåáðû.¿
[ À.Ã. Êóðîø. ¾Êóðñ îáùåé àëãåáðû¿ ].


6.1 Îñíîâíûå îïðåäåëåíèÿ. Ìîäåëè è àëãåáðû
   Ìû óæå ïîëüçîâàëèñü îäíèì èç îñíîâíûõ ïîíÿòèé ñîâðåìåííîé ìàòåìàòèêè  ïî-
íÿòèåì àëãåáðàè÷åñêîé ñèñòåìû (ÀÑ). Íåôîðìàëüíî, ÀÑ  ýòî íåêîòîðîå ìíîæåñòâî ñ
îïðåäåë¼ííûìè íà í¼ì îïåðàöèÿìè è îòíîøåíèÿìè. Äëÿ ôîðìàëüíîãî çàäàíèÿ ÀÑ A
îïðåäåëèì ñîñòàâëÿþùèå å¼ ýëåìåíòû.
   Ïóñòü Op è Rel  íåêîòîðûå íåïóñòûå îäíîâðåìåííî è íå èìåþùèå îáùèõ ýëåìåí-
òîâ ñîâîêóïíîñòè ñèìâîëîâ ïðîèçâîëüíûõ îïåðàöèé è îòíîøåíèé ñîîòâåòñòâåííî. Åñëè
îáà óêàçàííûå ìíîæåñòâà êîíå÷íû, òî ñîîòâåòñòâóþùàÿ àëãåáðàè÷åñêàÿ ñèñòåìà íàçû-
âàåòñÿ ÀÑ êîíå÷íîãî òèïà. Ìû áóäåì ðàññìàòðèâàòü òîëüêî òàêèå ñèñòåìû. Ìîùíîñòè
ìíîæåñòâ Op è Rel îáîçíà÷èì N è M ñîîòâåòñòâåííî.
   Ñèãíàòóðà σ åñòü óïîðÿäî÷åííàÿ ïàðà Op, Rel , ñèìâîëè÷åñêè σ = sgnt A. Åñëè
Rel = ∅, òî ÀÑ íàçûâàþò (óíèâåðñàëüíîé) àëãåáðîé, à åñëè Op = ∅  òî ðåëÿöèîííîé
ñèñòåìîé èëè ìîäåëüþ.
   Êàæäîìó ýëåìåíòó fi ∈ Op ñîïîñòàâëåíî íàòóðàëüíîå ÷èñëî ni                0, i = 1, N , à
ýëåìåíòó rj ∈ Rel  öåëîå ÷èñëî mj > 0, j = 1, M , âûðàæàþùåå ¾ìåñòíîñòü¿ èëè
¾àðíîñòü¿ ñîîòâåòñòâóþùåãî ôóíêöèîíàëüíîãî èëè ïðåäèêàòíîãî ñèìâîëà. Íóëüàðíûå
îòíîøåíèÿ íå âêëþ÷àþò â ñèãíàòóðó (òàêîâûõ òîëüêî äâà: ýòî ëîãè÷åñêèå êîíñòàíòû
¾èñòèíà¿ (0) è ¾ëîæü¿ (1), è îíè íåÿâíî ïðèñóòñòâóþò â êàæäîé ÀÑ ñ íåïóñòûì ìíîæå-
ñòâîì Rel).
   Ñèãíàòóðíûì îïåðàöèÿì ñ íóëåâûìè àðíîñòÿìè ñîîòâåòñòâóþò ôèêñèðîâàííûå ýëå-
ìåíòû îáëàñòè çíà÷åíèé ôóíêöèé. Áóäåì ñ÷èòàòü, ÷òî îïåðàöèè ñ íåíóëåâûìè àðíîñòÿìè
èìåþò íîìåðà ñ 1 ïî N    N . Ìåñòíîñòè ñèãíàòóðíûõ îïåðàöèé è îòíîøåíèé çàïèñûâàþò
â âèäå êîðòåæà
                      τ = n1 , . . . , nN , m1 , . . . , mM , 0, . . . , 0 ,
êîòîðûé íàçûâàþò òèïîì ÀÑ (ïðè N = N çàêëþ÷èòåëüíûå íóëè îòñóòñòâóþò). Åñ-
ëè îãîâàðèâàþò, ÷òî çàäàåòñÿ àëãåáðà èëè ìîäåëü, òî èõ òèïû çàïèñûâàþò, ïåðå÷èñëÿÿ
àðíîñòè ëèøü ýëåìåíòîâ èç Op èëè, ñîîòâåòñòâåííî, èç Rel.
      Ïðè çàäàíèè òèïà, ïîñëåäîâàòåëüíîñòè àðíîñòåé n1 , . . . , nN è m1 , . . . , mM ïðèíÿ-
òî óïîðÿäî÷èâàòü òàê, ÷òîáû îíè îêàçàëèñü íåâîçðàñòàþùèìè. Çàäàâàÿ ñèãíàòóðó, å¼
ýëåìåíòû ïåðå÷èñëÿþò â ñîîòâåòñòâèè ñ âûáðàííîé óïîðÿäî÷åííîñòüþ. Åñëè íåîáõî-
äèìî ÿâíî óêàçûâàòü àðíîñòè ýëåìåíòîâ, èõ çàïèñûâàþò â êà÷åñòâå âåðõíèõ èíäåêñîâ:
                   m
fini , i = 1, N , rj j , j = 1, M .
      Ðàññìîòðèì òåïåðü íå èìåþùåå îáùèõ ýëåìåíòîâ ñ Op è Rel íåïóñòîå ìíîæåñòâî
A. Îíî áóäåò íàçûâàòüñÿ íîñèòåëåì èëè îñíîâíûì ìíîæåñòâîì ÀÑ A, ñèìâîëè÷åñêè
A = Supp A. Åñëè A  êîíå÷íî, òî ñîîòâåòñòâóþùàÿ àëãåáðàè÷åñêàÿ ñèñòåìà íàçûâàåòñÿ
êîíå÷íîé.
      Ñîâîêóïíîñòè âñåõ îïåðàöèé è îòíîøåíèé, êîòîðûå ìîæíî îïðåäåëèòü íà A áóäåì
îáîçíà÷àòü Op A è Rel A ñîîòâåòñòâåííî. Ïîíÿòíî, ÷òî ýòî  î÷åíü ìîùíûå ìíîæåñòâà,


118                                                                  Ãëàâà 6. Àëãåáðàè÷åñêèå ñèñòåìû


ñîñòîÿùèå èç áîëüøîãî ÷èñëà ýëåìåíòîâ, äàæå åñëè A  êîíå÷íîå ìíîæåñòâî íåáîëüøîé
ìîùíîñòè.
   Îïðåäåëèì äàëåå ïîíÿòèå èíòåðïðåòàöèè äàííîé àáñòðàêòíîé ñèãíàòóðû. Èíòåðïðå-
òàöèÿ ω åñòü ïàðà ôóíêöèé ω1 , ω2 ,

                          ω1 : Op → Op A           è           ω2 : Rel → Rel A,

ñîïîñòàâëÿþùèõ êàæäîìó ñèìâîëó èç Op è Rel ñîîòâåòñòâåííî êîíêðåòíûå îïåðàöèè
èëè îòíîøåíèÿ íà A òîé æå àðíîñòè.
   Îêîí÷àòåëüíî, àëãåáðàè÷åñêàÿ ñèñòåìà A åñòü ïÿò¼ðêà

                                        A, Op, Rel, ω1 , ω2 .

   Îáðàçàìè èíòåðïðåòàöèè ÿâëÿþòñÿ ñîâîêóïíîñòè ôóíêöèé Op A ⊆ Op A è ïðåäèêà-
òîâ Rel A ⊆ Rel A íà ìíîæåñòâå A. Àëãåáðàè÷åñêèå ñèñòåìû ñ îäèíàêîâûìè àáñòðàêò-
íûìè ñèãíàòóðàìè íàçûâàþò îäíîòèïíûìè. Îäíîòèïíûå ÀÑ ðàçëè÷àþòñÿ íîñèòåëÿìè è
èíòåðïðåòàöèÿìè. Îïåðàöèè è îòíîøåíèÿ îäíîòèïíûõ ÀÑ, ÿâëÿþùèåñÿ îáðàçàìè ðàçíûõ
èíòåðïðåòàöèé ñîîòâåòñòâóþùèõ ñèìâîëîâ ñèãíàòóðû íàçûâàþò îäíîèì¼ííûìè.
   Ïðè ðàáîòå ñ êîíêðåòíûìè ÀÑ èõ çàïèñûâàþò êîðî÷å, ëèáî â îáùåì âèäå êàê

                                     A =      A, Op A, Rel A ,

ëèáî ïåðå÷èñëåíèåì êîíêðåòíûõ îïåðàöèé è îòíîøåíèé
                                 n             n      m              m
                     A =     A, f1 1 , . . . , fNN , r1 1 , . . . , rMM , 0, . . . , 0 .

Ýëåìåíòû Op A íåíóëåâîé àðíîñòè íàçûâàþò ãëàâíûìè îïåðàöèÿìè, ýëåìåíòû Rel A 
ãëàâíûìè îòíîøåíèÿìè, à ýëåìåíòû Op A íóëåâîé àðíîñòè  ãëàâíûìè ýëåìåíòàìè
ÀÑ. Ýëåìåíò íîñèòåëÿ A, îòìå÷àåìûé íóëüàðíîé îïåðàöèåé fi0 áóäåì îáîçíà÷àòü fi0 (A0 ),
îïóñêàÿ, âîçìîæíî âåðõíèé è íèæíèé èíäåêñû ó ñèìâîëà ôóíêöèè.
Ïðèìåð 6.1. 1 Äëÿ ñèãíàòóðû σ = f1 , f2 , f3 , r1 , c1 , c2 òèïà 2, 2, 1, 2, 0, 0 ïîñòðîèì
ðàçëè÷íûå îäíîòèïíûå ÀÑ, âûáèðàÿ ðàçëè÷íûå íîñèòåëè è ïî-ðàçíîìó çàäàâàÿ èíòåð-
ïðåòàöèþ ñèìâîëîâ ñèãíàòóðû σ .
A1 : supp A1 = N0 , à ýëåìåíòû ñèãíàòóðû èíòåðïðåòèðóþòñÿ (ñ ïåðåõîäîì ê èíôåêñíîé
     çàïèñè) ñëåäóþùèì îáðàçîì:

              f1 → +,      f2 → ·,      f3 (n) = n + 1,            r →    ,   c1 → 0,       c2 → 1.

      ßñíî, ÷òî òàêàÿ ÀÑ îïèñûâàåò àðèôìåòèêó íåîòðèöàòåëüíûõ öåëûõ ÷èñåë.
A2 : supp A2 = supp A1 , íî ñèãíàòóðíûå ñèìâîëû èíòåðïðåòèðóþòñÿ ïî-äðóãîìó:

                          f1 → 0, f2 (m, n) = mn , f3 (n) = 2n,
                    r(m, n) → m è n âçàèìíî ïðîñòû, c1 → 1, c2 → 1.

      Ýòà ýêçîòè÷íàÿ ÀÑ íå èìååò ñïåöèàëüíîãî íàçâàíèÿ.
A3 : supp A3 = P(A). Ñèãíàòóðíûå ñèìâîëû áóäåì òðàêòîâàòü ñëåäóþùèì îáðàçîì:
                                                       −
               f1 → ∪ ,     f2 → ∩ ,        f3 →           ,    r → ⊆,    c1 → ∅ ,         c2 → A.

      ßñíî, ÷òî ìû ïîëó÷èëè òîòàëüíóþ áóëåâó ñòðóêòóðó ìíîæåñòâ.
   1 Ñì. Ïèíóñ À.Ã. Îñíîâû óíèâåðñàëüíîé àëãåáðû: Ó÷åáíîå ïîñîáèå.  Íîâîñèáèðñê: Èçä-âî ÍÃÒÓ,
1998.


6.2. Ïîäñèñòåìû. Ïðÿìîå ïðîèçâåäåíèå ÀÑ                                                       119


A4 : Íîñèòåëü ÀÑ A4 åñòü ìíîæåñòâî V âñåõ âåêòîðîâ x òð¼õìåðíîãî ïðîñòðàíñòâà, à
     ñèãíàòóðíûå ñèìâîëû èíòåðïðåòèðóþòñÿ òàê:
                            f1 (a, b) = a + b ,   f2 (a, b) = a Ч b ,   f3 (a) = −a
                        r(a, b) → ¾âåêòîð a êîëëèíåàðåí âåêòîðó b¿ ,         c1 , c2 → 0.

    Îïåðàöèè è îòíîøåíèÿ âî âñåõ ïðèâåä¼ííûõ ïðèìåðàõ, ñîîòâåòñòâóþùèå ñèãíàòóð-
íûì ñèìâîëàì f1 , f2 , f3 è r1 áóäóò îäíîèì¼ííûìè. Âåçäå ìû ïðåäïîëàãàëè, ÷òî ââåäåí-
íûå îïåðàöèè è îòíîøåíèÿ èìåþò îáû÷íûé ìàòåìàòè÷åñêèé ñìûñë.
    Ïðèâåä¼ì ïðèìåðû êîíêðåòíûõ àëãåáðàè÷åñêèõ ñèñòåì ðàçëè÷íîé ñèãíàòóðû.
Ïðèìåð 6.2.       1. AC A, f , ãäå f  îäíîìåñòíàÿ îïåðàöèÿ íà ìíîæåñòâå A íàçûâà-
      åòñÿ óíàðîì.
   2. Ïîëå äåéñòâèòåëüíûõ ÷èñåë R, +, ·, −, 0, 1 åñòü àëãåáðà òèïà 2, 2, 1, 0, 0 . Çà-
      ìåòèì, ÷òî êîðòåæ +, ·, −, −1 , 0, 1 íåëüçÿ ðàññìàòðèâàòü êàê ñèãíàòóðó ïîëÿ,
      ò.ê. îïåðàöèÿ −1 íå îïðåäåëåíà äëÿ íóëÿ.
      Êîëüöî K ñ åäèíèöåé åñòü àëãåáðà ñèãíàòóðû σ =                  ·, +, −, 0, 1 òèïà
        2, 2, 1, 0, 0 .
      Ãðóïïà åñòü àëãåáðà òèïà 2, 1, 0 ñèãíàòóðû σ = ◦, −1 , e .
   3. ×àñòè÷íî ïðåäóïîðÿäî÷åííîå ìíîæåñòâî P, ≤ , ãäå ≤  ñèìâîë ïðåäïîðÿäêà
      åñòü ìîäåëü òèïà 2 .
   4. Åñëè îäíà ÀÑ ìîæåò áûòü ïîëó÷åíà èç äðóãîé óäàëåíèåì íåêîòîðûõ îïåðàöèé,
      îòíîøåíèé èëè êîíñòàíò, òî ïåðâàÿ ÀÑ íàçûâàåòñÿ ðåäóêòîì âòîðîé.
    Âî âñåõ ïðèâåä¼ííûõ âûøå ïðèìåðàõ ñ÷èòàëîñü, ÷òî ïðèâåä¼ííûå îïåðàöèè è îò-
íîøåíèÿ îáëàäàþò èçâåñòíûìè ñâîéñòâàìè.  îáùåì ñëó÷àå ýòè ñâîéñòâà íåîáõîäèìî
çàäàâàòü.
    Ñîâîêóïíîñòü ÀÑ ôèêñèðîâàííîé ñèãíàòóðû íàçûâàåòñÿ êëàññîì àëãåáðàè÷åñêèõ ñè-
ñòåì. Êëàññ M ÀÑ ñèãíàòóðû σ íàçûâàåòñÿ ìíîãîîáðàçèåì, åñëè ñóùåñòâóåò ìíîæåñòâî
Σ òîæäåñòâ ñèãíàòóðû σ òàêîå, ÷òî ÀÑ ñèãíàòóðû σ ïðèíàäëåæèò êëàññó M åñëè è
òîëüêî åñëè â íåé âûïîëíÿþòñÿ âñå òîæäåñòâà Σ. Ñîâîêóïíîñòü òîæäåñòâ Σ íàçûâàþò
àêñèîìàòèêîé äàííîãî êëàññà.
Ïðèìåð 6.3.       1. Áóëåâà àëãåáðà  ìíîãîîáðàçèå ñèãíàòóðû             , , , o, ι òèïà
        2, 2, 1, 0, 0 , îïðåäåëÿåìîé ñèñòåìîé àêñèîì, ïðèâåä¼ííîé â îïðåäåëåíèè 1.1.
     2. Ïîëóãðóïïû  ýòî ìíîãîîáðàçèÿ ñèãíàòóðû, ñîñòîÿùåé èç åäèíñòâåííîé áèíàðíîé
        îïåðàöèè ◦, óäîâëåòâîðÿþùèå òîæäåñòâó (x ◦ y) ◦ z = x ◦ (y ◦ z).
     3. Àññîöèàòèâíî-êîììóòàòèâíûå êîëüöà ñ åäèíèöåé  ýòî ìíîãîîáðàçèÿ ñèãíàòóðû
         +, ·, −, 0, 1 òèïà 2, 2, 1, 0, 0 óäîâëåòâîðÿþùèå ñëåäóþùèì òîæäåñòâàì Σ :
                   (x + y) + z = x + (y + z); x + 0 = 0 + x = x;
                   x + (−x) = 0;              x + y = y + x;
                   (x + y)z = xz + yz ;       x(y + z) = xy + xz ;
                   (xy)z = x(yz);             x1 = 1x = x;
                   xy = yx.
   Îòìåòèì, ÷òî ïðîèçâîëüíîé àëãåáðå ìîæíî ñîïîñòàâèòü àäåêâàòíóþ åé ìîäåëü, åñ-
                                                                               n+1
ëè êàæäóþ îïåðàöèþ âèäà fin (x1 , . . . , xn ) çàìåíèòü íà îòíîøåíèå ri (x1 , . . . , xn , xn+1 )
            n+1
òàêîå, ÷òî ri (x1 , . . . , xn , y) ⇔ fin (x, . . . , xn ) = y . Òàêàÿ ìîäåëü íàçûâàåòñÿ ïðåäñòàâ-
ëÿþùåé.
Ïðèìåð 6.4. Ïóñòü çàäàíà ãðóïïà Z, +, −, 0 . Åñëè
              3                           2                     1
             r1 (m, n, k) ≡ (m + n = k), r2 (m, n) ≡ (m = −n), r3 (n) ≡ (n = 0),
òî        3    2    1
      Z, r1 , r2 , r3   áóäåò ïðåäñòàâëÿþùåé ìîäåëüþ äëÿ äàííîé ãðóïïû.


120                                                 Ãëàâà 6. Àëãåáðàè÷åñêèå ñèñòåìû


6.2 Ïîäñèñòåìû. Ïðÿìîå ïðîèçâåäåíèå ÀÑ
   Íàïîìíèì, ÷òî ìíîæåñòâî X íàçûâàåòñÿ óñòîé÷èâûì îòíîñèòåëüíî îòîáðàæåíèÿ
f : X n → X , åñëè f (x1 , . . . , xn ) ∈ X . Ïóñòü A = A, Op A, Rel A  àëãåáðàè÷åñêàÿ
ñèñòåìà è ∅ = B ⊆ A. Íàçîâ¼ì ìíîæåñòâî B óñòîé÷èâûì îòíîñèòåëüíî îïåðàöèé èç
Op A, åñëè îíî óñòîé÷èâî îòíîñèòåëüíî ñóæåíèé íà B êàæäîé îïåðàöèè èç Op A.
Îïðåäåëåíèå 6.1. Ïóñòü A = A, Op A, Rel A  ÀÑ, ∅ = B ⊆ A, à Op B è Rel B 
ñîâîêóïíîñòè ñóæåíèé íà B îïåðàöèé èç Op A è îòíîøåíèé èç Rel A ñîîòâåòñòâåííî. Åñ-
ëè ìíîæåñòâî B óñòîé÷èâî îòíîñèòåëüíî îïåðàöèé èç Op A, òî ÀÑ B = B, Op B, Rel B
íàçûâàåòñÿ ïîäñèñòåìîé A (ñèìâîëè÷åñêè B A ).
   Ïîäñèñòåìó àëãåáðû íàçûâàþò ïîäàëãåáðîé, à ïîäñèñòåìó ìîäåëè  ïîäìîäåëüþ. Åñëè
B ⊂ A, òî ñîîòâåòñòâóþùóþ ïîäñèñòåìó íàçûâàþò ñîáñòâåííîé (ñèìâîëè÷åñêè B < A ).
    ßñíî, ÷òî ëþáîå ïîäìíîæåñòâî íîñèòåëÿ îïðåäåëÿåò ïîäìîäåëü, íî íå ëþáîå  ïîäàë-
ãåáðó. Äëÿ ïîñëåäíåãî òðåáóåòñÿ óñòîé÷èâîñòü ïîäìíîæåñòâà îòíîñèòåëüíî âñåõ îïåðàöèé
ñèãíàòóðû, â òîì ÷èñëå è íóëüàðíûõ, ò.å. ïîäñèñòåìà äîëæíà ñîäåðæàòü âñå ãëàâíûå ýëå-
ìåíòû èñõîäíîé ñèñòåìû, åñëè òàêîâûå èìåþòñÿ.
Ïðèìåð 6.5.       1. Ïîëå ðàöèîíàëüíûõ ÷èñåë åñòü ïîäàëãåáðà ïîëÿ äåéñòâèòåëüíûõ ÷èñåë
      (ñì. ïðèìåð 6.2).
   2. Åñëè ìíîæåñòâî A  ñîáñòâåííîå ïîäìíîæåñòâî ìíîæåñòâà B , òî àëãåáðà ìíî-
      æåñòâ P(A) íå ÿâëÿåòñÿ ïîäàëãåáðîé P(B), ïîñêîëüêó òàêîå ñóæåíèå íå ñîõðàíÿåò
      åäèíèöó P(A).
   3. Ïóñòü F  ìíîæåñòâî äèôôåðåíöèðóåìûõ äåéñòâèòåëüíûõ ôóíêöèé. Òîãäà óíàð
            d          d
       F, dx , ãäå dx  îïåðàòîð äèôôåðåíöèðîâàíèÿ, åñòü àëãåáðà. Ìíîæåñòâî ïîëèíî-
      ìèàëüíûõ ôóíêöèé áóäåò å¼ ïîäàëãåáðîé.
      Çàìåòèì, ÷òî ÀÑ, íîñèòåëåì êîòîðîé ÿâëÿåòñÿ ìíîæåñòâî ôóíêöèé íàçûâàþò ôóíê-
      öèîíàëüíîé ñèñòåìîé.
   4. Ïðè ëþáîì íàòóðàëüíîì n óíàð Z, + ñîäåðæèò ïîäàëãåáðó nZ, + .
   5. Ïîäàëãåáðàìè öèêëè÷åñêîé ãðóïïû Z6 = { 0, 1, . . . , 5 }, +6 áóäóò ïîäãðóïïû
      { 0 }, { 0, 3 }, { 0, 2, 4 } è Z6 .
    Ñîâîêóïíîñòü âñåõ ïîäñèñòåì ÀÑ A áóäåì îáîçíà÷àòü Sub A. ßñíî, ÷òî ýòî ÷.ó. ìíî-
æåñòâî, óïîðÿäî÷åííîå ïî âêëþ÷åíèþ (íîñèòåëåé ïîäñèñòåì).
Òåîðåìà 6.1. Ïóñòü A  ÀÑ è {Ai }i∈I  íåêîòîðàÿ ñîâîêóïíîñòü å¼ ïîäñèñòåì. Òîãäà
 i∈I   Ai ëèáî ïóñòî, ëèáî ÿâëÿåòñÿ ïîäñèñòåìîé.
Äîêàçàòåëüñòâî. Äîñòàòî÷íî çàìåòèòü, ÷òî ïåðåñå÷åíèå íîñèòåëåé âñåõ ïîäñèñòåì, åñëè
îíî íå ïóñòî, óñòîé÷èâî îòíîñèòåëüíî âñåõ îïåðàöèé ëþáîé ïîäñèñòåìû.

Ñëåäñòâèå. Åñëè ÀÑ A èìååò ãëàâíûå ýëåìåíòû, òî ïåðåñå÷åíèå âñåõ å¼ ïîäñèñòåì
íåïóñòî.
   Ñïðàâåäëèâîñòü äàííîãî ñëåäñòâèÿ âûòåêàåò èç óñëîâèÿ ïðèíàäëåæíîñòè ãëàâíûõ
ýëåìåíòîâ ÀÑ A ëþáîé å¼ ïîäñèñòåìå.
   Íàèìåíüøóþ ïîäñèñòåìîé ÀÑ íàçûâàþò å¼ ãëàâíîé ïîäñèñòåìîé. Ãëàâíàÿ ïîäñè-
ñòåìà, îäíàêî, ñóùåñòâóåò íå äëÿ ëþáîé ÀÑ: íàïðèìåð, êîëüöî öåëûõ ÷èñåë (àëãåáðà)
 Z, +, ·, 0 èëè ÷.ó. ìíîæåñòâî Z,     (ìîäåëü) íàèìåíüøèõ ïîäñèñòåì, î÷åâèäíî, íå
èìåþò.
   Ïóñòü äàíà ÀÑ A = A, Op A, Rel A è B ⊆ A. Îáîçíà÷èì ÷åðåç B = [ B ] ïåðåñå÷å-
íèå âñåõ ïîäñèñòåì èç Sub A, ñîäåðæàùèõ B . B íàçûâàþò ïîäñèñòåìîé, ïîðîæä¼ííîé
ìíîæåñòâîì B , à ýëåìåíòû B  ïîðîæäàþùèìè ýëåìåíòàìè. Ïîýòîìó B ìû òàêæå
áóäåì çàïèñûâàòü B = [B], Op A, Rel A . Åñëè B  êîíå÷íîå ìíîæåñòâî, òî B åñòü
êîíå÷íîïîðîæä¼ííàÿ ñèñòåìà. Ïðè B = {b}, òî âìåñòî [ {b} ] ïèøóò [ b ].



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