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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

F = x
1
N(x
3
∨ (x
4
Nx
5
)) ∨ x
2
N(x
4
∨ (x
3
Nx
5
))
F
{∨, N, ¬}
a, b [ 0, 1 ]
a ⊕ b = max {a, b}, a ⊗ b = min {a, b}, ⊕a = 1 − a.
h [ 0, 1 ], ⊕, ⊗, ⊕, 0, 1 i
Cmp
0
Isl
0
B
1
B
2
ϕ : B
1
→ B
2
1) ϕ(x t y) = ϕ(x) t ϕ(y); 2) ϕ(x u y) = ϕ(x) u ϕ(y); 3) ϕ(x
0
) = ϕ(x)
0
x y B
1
ϕ
B
1
B
2
B
1
∼
=
b
B
2
4) ϕ(o) = o 5) ϕ(ι) = ι.
ϕ(o) = ϕ(xux
0
) = ϕ(x) u ϕ(x
0
) = ϕ(x) u ϕ(x)
0
= o
ϕ(ι)
o ι
B
1
B
2
n A = {a
1
, . . . , a
n
}
n 2
n
ϕ : 2
n
→ P(A)
(α
1
, . . . , α
n
) { a
i
k
| α
i
k
= 1, k = 1, n } A
P(A) P(B)
A B
(⇐) ϕ P(A) P(B)
ϕ A B
(⇒) A B
f P(A) P(B)
A B f
f
X A ϕ(X) =
S
a∈X
f(a) ⊆ B
ϕ P(A)
P(B) ¤
14                                                                Ãëàâà 1. Áóëåâû àëãåáðû


       F = x1 N(x3 ∨ (x4 Nx5 )) ∨ x2 N(x4 ∨ (x3 Nx5 )), íå ÿâëÿþùåéñÿ áåñïîâòîðíîé, è
       íèêàêîå ýêâèâàëåíòíîå ïðåîáðàçîâàíèå F íå ïðèâåä¼ò, êàê ìîæíî ïîêàçàòü, ê
       áåñïîâòîðíîé ôîðìå íàä ìíîæåñòâîì ñâÿçîê {∨, N, ¬}.
     2. Äëÿ äåéñòâèòåëüíûõ ÷èñåë a, b èç îòðåçêà [ 0, 1 ] ïîëîæèì
                    a ⊕ b = max {a, b},    a ⊗ b = min {a, b},    ⊕a = 1 − a.
       Ñèñòåìó h [ 0, 1 ], ⊕, ⊗, ⊕, 0, 1 i íàçûâàþò ìàêñèìèííîé àëãåáðîé. Îíà íå áóäåò ÿâ-
       ëÿòüñÿ áóëåâîé àëãåáðîé, ïîñêîëüêó â íåé íå âûïîëíÿþòñÿ çàêîíû Cmp 0 è Isl 0 .
       Îòìåòèì, ÷òî â ïðèâåä¼ííîé âûøå ñèñòåìå èç 21-îé àêñèîìû íå âûïîëíÿþòñÿ òîëüêî
       äàííûå çàêîíû. Ïîñëåäíåå äîêàçûâàåò èõ íåçàâèñèìîñòü îò îñòàëüíûõ è íåîáõîäè-
       ìîñòü èõ ïðèñóòñòâèÿ â ëþáîé ñèñòåìå àêñèîì äëÿ áóëåâîé àëãåáðû.
       Îòìåòèì, ÷òî äîïîëíåíèÿ â ìàêñèìèííîé àëãåáðå åäèíñòâåííû. Òàêèì îáðàçîì,
       óêàçàííàÿ ñòðóêòóðà ÷ðåçâû÷àéíî áëèçêà ê áóëåâîé àëãåáðå, íî åé âñ¼-òàêè íå ÿâ-
       ëÿåòñÿ.
Îïðåäåëåíèå 1.3. Ïóñòü äàíû äâå áóëåâû àëãåáðû B1 è B2 è âçàèìíîîäíîçíà÷íàÿ
ôóíêöèÿ ϕ : B1 → B2 òàêàÿ, ÷òî ðàâåíñòâà
        1) ϕ(x t y) = ϕ(x) t ϕ(y);   2) ϕ(x u y) = ϕ(x) u ϕ(y);     3) ϕ(x 0 ) = ϕ(x) 0
ñïðàâåäëèâû äëÿ âñåõ x è y èç B1 . Òîãäà ãîâîðÿò, ÷òî ϕ  áóëåâ èçîìîðôèçì ìåæäó
B1 è B2 , äàííûå àëãåáðû áóëåâî èçîìîðôíû (ñèìâîëè÷åñêè B1 ∼=b B2 ).
Çàìå÷àíèå. Ëåãêî ïîêàçàòü, ÷òî èç 1)  3) ñëåäóåò
                             4) ϕ(o) = o     è   5) ϕ(ι) = ι.
Äåéñòâèòåëüíî, èìååì ϕ(o) = ϕ(x u x 0 ) = ϕ(x) u ϕ(x 0 ) = ϕ(x) u ϕ(x)0 = o è àíàëîãè÷íî
äëÿ ϕ(ι).
    Ìû âèäèì, ÷òî áóëåâ èçîìîðôèçì  ýòî âçàèìíîîäíîçíà÷íîå îòîáðàæåíèå íîñèòåëåé
áóëåâûõ àëãåáð, ñîõðàíÿþùåå îïåðàöèè è îñîáûå ýëåìåíòû o è ι.
     çàïèñè áóëåâûõ àëãåáð B1 è B2 ìû èñïîëüçîâàëè îäèíàêîâûå îáîçíà÷åíèÿ è äëÿ
ñîîòâåòñòâóþùèõ îïåðàöèé, è äëÿ âûäåëåííûõ ýëåìåíòîâ. Ñòðåìÿñü íå óñëîæíÿòü îáî-
çíà÷åíèÿ, òàê îáû÷íî è ïîñòóïàþò. Ïðè âíèìàòåëüíîì ÷òåíèè ïóòàíèöû îòíîñèòåëüíî
ïðèíàäëåæíîñòè îïåðàöèé è âûäåëåííûõ ýëåìåíòîâ ê îäíîé èëè äðóãîé àëãåáðå âîçíèê-
íóòü íå äîëæíî.
Ïðèìåð 1.5.          1. Àëãåáðà âûñêàçûâàíèé, î÷åâèäíî, èçîìîðôíà òðèâèàëüíîé àëãåáðå
      ìíîæåñòâ.
   2. Òîòàëüíàÿ àëãåáðà íàä n-ýëåìåíòíûì ìíîæåñòâîì A = {a1 , . . . , an } èçîìîðôíà
      áóëåâîé àëãåáðå n-ìåðíûõ äâîè÷íûõ âåêòîðîâ 2n . Áóëåâûì èçîìîðôèçìîì çäåñü
      áóäåò ÿâëÿåòñÿ îòîáðàæåíèå ϕ : 2n → P(A), ñòàâÿùåå â ñîîòâåòñòâèå áóëåâó âåêòîðó
      (α1 , . . . , αn ) ïîäìíîæåñòâî { aik | αik = 1, k = 1, n } ìíîæåñòâà A.
    Ñóùåñòâóåò ïðîñòîé êðèòåðèé èçîìîðôíîñòè òîòàëüíûõ àëãåáð ìíîæåñòâ.
Òåîðåìà 1.2. Äëÿ òîãî ÷òîáû òîòàëüíûå àëãåáðû ìíîæåñòâ P(A) è P(B) áûëè
èçîìîðôíû, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû A è B èìåëè îäèíàêîâóþ ìîùíîñòü.
Äîêàçàòåëüñòâî. (⇐) Ïóñòü ñóùåñòâóåò èçîìîðôèçì ϕ ìåæäó àëãåáðàìè P(A) è P(B).
Òîãäà ϕ  âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ìíîæåñòâàìè A è B , îòêóäà ñëåäóåò
èõ ðàâíîìîùíîñòü.
   (⇒) Ïóñòü ìíîæåñòâà A è B ðàâíîìîùíû. Òîãäà ìåæäó èõ ýëåìåíòàìè ìîæíî óñòà-
íîâèòü âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå f . Îäíàêî, ýëåìåíòàìè P(A) è P(B) ñëóæàò
ïîäìíîæåñòâà A è B ñîîòâåòñòâåííî è f íå ÿâëÿåòñÿ èñêîìûì èçîìîðôèçìîì. Ïîýòîìó
ðàñïðîñòðàíèì îòîáðàæåíèå f íà ïîäìíîæåñòâà äàííûõ ìíîæåñòâ, ïîñòàâèâ
                                                                   S    â ñîîòâåò-
ñòâèå ïðîèçâîëüíîìó ïîäìíîæåñòâó X ìíîæåñòâà A åãî îáðàç ϕ(X) = a∈X f (a) ⊆ B .
Ïðîñòàÿ ïðîâåðêà ïîêàçûâàåò, ÷òî ϕ ÿâëÿåòñÿ áóëåâûì èçîìîðôèçìîì ìåæäó P(A) è
P(B).                                                                            ¤

Страницы