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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

X
n
P
n
p = q p q
(x
i
)
0
(0)
0
(1)
0
x
i
0
0
0
1
0
p = q
n
n + 1
P
1
⊂ P
2
⊂ . . . ⊂ P
n
⊂ P
n+1
⊂ . . . .
P
n
x
1
t x
2
6= x
2
t x
1
x
1
u x
2
6= x
2
u x
1
B
B = 2 = {0, 1}
B p P
n
bp
B
(b
1
, . . . , b
n
) B p x
i
b
i
∈ B, i = 1, . . . , n
bp
B
: B
n
→ B, (b
1
, . . . , b
n
) 7→ bp
B
(b
1
, . . . , b
n
)
p B
B = 2 n = 2 p = x
1
tx
2
q = x
2
tx
1
p 6= q bp
B
= a∨b
bq
B
= b ∨ a a, b ∈ {0, 1} bp
B
= bq
B
B = P(A) n = 2 p = (x
1
t x
2
)
0
q = x
1
0
u x
2
0
p 6= q
bp
B
= X ∪ Y bq
B
= X ∩ Y X, Y ⊆ A bp
B
= bq
B
p, q ∈ P
n
p ∼ q 2
p ∼ q ⇔ bp
2
= bq
2
.
∼ P
n
P
n
B
= {bp
B
| p ∈ P
n
}
P
n
B
P
n
/∼ P
n
/∼
∼
=
b
P
n
2
ϕ : P
n
2
→ P
n
/ ∼
P
n
2
p 2
[p]
∼
bp
2
= bq
2
⇒ p ∼ q ⇒ [p]
∼
= [q]
∼
ϕ ¤
B P
n
B
P
n
B
6 B
B
n
P
n
B
P
n
B
f
0
f
1
5.4. Áóëåâû ìíîãî÷ëåíû                                                                       111


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

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

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

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

                        pbB : B n → B,     (b1 , . . . , bn ) 7→ pbB (b1 , . . . , bn )     (5.2)

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

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

                                         p ∼ q ⇔ pb2 = qb2 .

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

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

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


Òåîðåìà 5.11. Åñëè B  áóëåâà àëãåáðà, òî è PBn  áóëåâà àëãåáðà, ïðè÷¼ì PBn 6 B B .
                                                                                               n




Äîêàçàòåëüñòâî. Íåîáõîäèìî óáåäèòüñÿ â óñòîé÷èâîñòè PBn îòíîñèòåëüíî îïåðàöèé îáú-
åäèíåíèÿ, ïåðåñå÷åíèÿ è äîïîëíåíèÿ, à òàêæå, ÷òî PBn ñîäåðæèò óêàçàííûå â òåîðåìå 5.2
ïîñòîÿííûå ôóíêöèè f0 è f1 .

Страницы