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

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

(a
0
u b u (x
1
t x
1
0
) u x
2
) t (x
1
0
u b u x
2
) t (b
0
u x
1
0
u (x
2
t x
2
0
)) ∼
∼ ((a
0
u b u x
1
t x
2
) t (a
0
u b u x
1
0
t x
2
) t (b u x
1
0
u x
2
) t
t ((b
0
u x
1
0
u x
2
) t (b
0
u x
1
0
u x
2
0
)) ∼
∼ (a
0
u b u x
1
t x
2
) t (a
0
u b u x
1
0
t x
2
) t (b u x
1
0
u x
2
) t
t (b
0
u x
1
0
u x
2
) t (b
0
u x
1
0
u x
2
0
).
x
1
0
t x
2
((a
0
u b) u (x
1
0
t x
2
)) t (b u (ux
1
0
u x
2
)) t (b
0
u (x
1
0
u x
2
)) ∼
∼ ((a
0
u b) t b t b
0
) u (x
1
0
u x
2
) ∼
∼ ((a
0
u b) t 1) u (x
1
0
u x
2
) ∼ u 1 u (x
1
0
u x
2
).
p ∼ (a
0
u b u x
1
u x
2
) t (1 u x
1
0
u x
2
) t (b
0
u x
1
0
u x
2
0
).
p = q
p q
p q P
n
(p, q)
B (b
1
, . . . , b
n
) ∈ B
n
(p, q) B bp
B
(b
1
, . . . , b
n
) = bq
B
(b
1
, . . . , b
n
)
{(p
i
, q
i
) | i ∈ I ⊆ N}
(p, q) p = q
x
0
1
x
2
∨x
3
= x
1
(x
2
∨x
3
) (101)
(1
0
N0) ∨ 1 = 1N(0 ∨ 1) = 1
x t y x u y
x ∨ y xy xNy
D = C
1
∨ . . . ∨ C
l
{x
1
, . . . , x
n
} C
i
i = 1, l C = D
1
∨ . . . ∨ D
m
{x
1
, . . . , x
n
} D
i
i = 1, m
D = 0 ⇔
l
i=1
C
i
= 0 C = 0 ⇔
l
_
i=m
D
i
= 0.
114                                                        Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


Øàã 4.

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

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

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


5.5 Óðàâíåíèÿ â áóëåâûõ àëãåáðàõ
   Â áóëåâûõ àëãåáðàõ ìîæíî ðåøàòü óðàâíåíèÿ. Óäîáíåå âñåãî ðàññìàòðèâàòü óðàâíå-
íèÿ íàä áóëåâûìè ìíîãî÷ëåíàìè.
   Òåïåðü ìîæíî ïåðåéòè ê áóëåâûì óðàâíåíèÿì è ìåòîäàì èõ ðåøåíèÿ. Ïðåæäå âñåãî,
íóæíî îïðåäåëèòü ñàì òåðìèí ¾áóëåâî óðàâíåíèå¿, ïîñêîëüêó ðàâåíñòâî p = q ãîâîðèò
ïðîñòî, ÷òî ìíîãî÷ëåíû p è q èäåíòè÷íû.
Îïðåäåëåíèå 5.9. Ïóñòü p è q  áóëåâû ìíîãî÷ëåíû èç Pn . Ïàðó (p, q) íàçîâ¼ì (áó-
ëåâûì) óðàâíåíèåì.
   Ïóñòü B  ïðîèçâîëüíàÿ áóëåâà àëãåáðà. Ýëåìåíò (b1 , . . . , bn ) ∈ B n íàçûâàåòñÿ
ðåøåíèåì óðàâíåíèÿ (p, q) â áóëåâîé àëãåáðå B , åñëè pbB (b1 , . . . , bn ) = qbB (b1 , . . . , bn ).
   Ìíîæåñòâî óðàâíåíèé {(pi , qi ) | i ∈ I ⊆ N} îáðàçóåò ñèñòåìó óðàâíåíèé. Ðåøåíèåì
ñèñòåìû íàçûâàåòñÿ îáùåå ðåøåíèå âñåõ óðàâíåíèé ñèñòåìû.
    Åñëè íå âîçíèêàåò ïóòàíèöû, óðàâíåíèå (p, q) äîïóñòèìî çàïèñûâàòü â âèäå p = q .
Íàïðèìåð, x01 x2 ∨x3 = x1 (x2 ∨x3 )  áóëåâî óðàâíåíèå, à (101)  åãî ðåøåíèå, ïîñêîëüêó
â (10 N0) ∨ 1 = 1N(0 ∨ 1) = 1.
    Äàëåå â ðàìêàõ äàííîãî ðàçäåëà áóäåì, ñëåäóÿ òðàäèöèè, âìåñòî x t y è x u y ïèñàòü
x ∨ y è xy ( xNy ) è íàçûâàòü äàííûå âûðàæåíèÿ ñóììîé è ïðîèçâåäåíèåì ñîîòâåòñòâåí-
íî. Äèçúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÄÍÔ) íàçîâ¼ì áóëåâ ìíîãî÷ëåí, ÿâëÿþùèéñÿ
ñóììîé êîíå÷íîãî ÷èñëà ïðîèçâåäåíèé, êîòîðûå â äàííîì ñëó÷àå áóäåì íàçûâàòü ýëå-
ìåíòàðíûìè êîíúþíêöèÿìè èëè êîíúþíêòàìè. Êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé
(ÊÍÔ) íàçîâ¼ì ïðîèçâåäåíèå êîíå÷íîãî ÷èñëà ñóìì, êîòîðûå â äàííîì ñëó÷àå áóäåì
íàçûâàòü ýëåìåíòàðíûìè äèçúþíêöèÿìè èëè äèçúþíêòàìè.
    Îòìåòèì èçâåñòíîå ñâîéñòâî íîðìàëüíûõ ôîðì. Åñëè 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

Страницы