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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

{x
1
} x = x
1
(a u x) t (b u x
0
)
a b B
p ∈ P
n
P
n
2
= 2
2
n
|P
n
/∼ | = 2
2
n
2
n
2
2
n
|B| = m > 2 |P
n
B
| = |P
n
/ ∼ | = 2
2
n
< m
m
n
= |B
B
n
| 2
n
p = (( x
1
t x
2
) u x
1
0
) t ((x
2
0
)
0
u (x
1
t x
2
0
)) ∈ P
2
.
bp
B
(0, 0) = bp
B
(1, 0) = 0 bp
B
(0, 1) = bp
B
(1, 1) = 1
p ∼ (x
1
0
u x
2
) t (x
1
u x
2
0
) = p
d
(f
p
).
p
d
(f
p
) ∼ (x
1
0
t x
1
) u x
2
∼ 1 u x
2
∼ x
2
.
p
DeM1, 2
Dtr1, 2 p
x
i
x
i
0
p x
i
t x
i
0
DeM1
Id u p
a, b ∈ 2
p = (( a u x
1
) t (b u x
2
)
0
)
0
t (x
1
t b)
0
.
p ∼ ((a u x
1
)
0
u (b u x
2
)
00
) t (x
1
0
u b
0
) ∼ ((a
0
t x
1
0
) u (b u x
2
)) t (x
1
0
u b
0
)
((a
0
t x
1
0
) u (b u x
2
)) t (x
1
0
u b
0
) ∼
∼ (( a
0
u b u x
2
) t (x
1
0
u b u x
2
)) t (x
1
0
t b
0
) ∼
∼ (a
0
u b u x
2
) t (x
1
0
u b u x
2
) t (x
1
0
t b
0
).
(a
0
u b u x
2
)
| {z }
1
t (x
1
0
u b u x
2
)
| {z }
2
t (x
1
0
u b
0
)
| {z }
3
= y
x
1
x
1
t x
1
0
x
1
x
2
x
2
x
2
t x
2
0
y ∼ (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
)).
5.4. Áóëåâû ìíîãî÷ëåíû                                                                                   113


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

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

                        p = ((x1 t x2 ) u x1 0 ) t ((x2 0 ) 0 u (x1 t x2 0 )) ∈ P2 .

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

                                p ∼ (x1 0 u x2 ) t (x1 u x2 0 ) = pd (fp ).

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

                              pd (fp ) ∼ (x1 0 t x1 ) u x2 ∼ 1 u x2 ∼ x2 .

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

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

                                p = ((a u x1 ) t (b u x2 )0 )0 t (x1 t b)0 .

Øàã 1. p ∼ ((a u x1 )0 u (b u x2 )00 ) t (x1 0 u b 0 ) ∼ ((a 0 t x1 0 ) u (b u x2 )) t (x1 0 u b 0 ).
Øàã 2.

        ((a 0 t x1 0 ) u (b u x2 )) t (x1 0 u b 0 ) ∼
                              ∼ ((a 0 u b u x2 ) t (x1 0 u b u x2 )) t (x1 0 t b 0 ) ∼
                                                      ∼ (a 0 u b u x2 ) t (x1 0 u b u x2 ) t (x1 0 t b 0 ).

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

               y ∼ (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 )).

Страницы