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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

0 I O
M ¬
∨ N
2 1 = 1 0 = 0 h M
m×n
, ∨, N, ¬, O, I i
h P(A × B), ∪, ∩,
−
, ∅, A × B i
M(α ∪ β) = M(α) ∨ M(β); M(α ∩ β) = M(α)NM(β); M(α) = ¬ M(α).
M(α
]
) ∈ M
n×m
M(α) ∈ M
m×n
M
1
∈ M
m×n
, M
2
∈ M
n×k
M
1
· M
2
∈ M
m×k
∨
N M
n
M n ∈ N
α ⊆ A × B β ⊆ B × C A, B, C
M(α ¦ β) = M(α) · M(β)
M(α
2
) = M
2
(α)
ρ ⊆ A
2
A
A R(A)
A
ρ ∈ R(A)
A x y xρy
α = { (a, c), (a, d) }
β = α ∪ { (d, b) } { a, b, c, d } xρx
a
b
a
b
c
d
c
d
x
R(A)
h R(A), ¦ i ρ ∈ R(A) ∅ 6= B ⊆ A
ρ ∩ B
2
ρ
B ρ |
B
k α
k
= α¦. . .¦α k α
1
= α
α ⊆ β ⇒ α
k
⊆ β
k
, k = 1, 2, . . . .
(α ∩ β)
2
⊆ α
2
∩ β
2
.
2.2. Îäíîðîäíûå îòíîøåíèÿ                                                           21


0. Èõ íàçûâàþò óíèâåðñàëüíîé è íóëü-ìàòðèöåé è îáîçíà÷àþò I è O ñîîòâåòñòâåííî.
Ê ëþáîé ìàòðèöå èç M ìîæíî ïîýëåìåíòíî ïðèìåíèòü ëîãè÷åñêóþ îïåðàöèþ ¬ , à ê
ìàòðèöàì îäèíàêîâîãî ðàçìåðà  ëîãè÷åñêèå îïåðàöèè ∨ è N ïî ïðàâèëàì àëãåáðû
2 (ïîëàãàÿ 1 = 1 è 0 = 0). Ëåãêî âèäåòü, ÷òî ÀÑ h Mm×n , ∨, N, ¬, O, I i ÿâëÿåòñÿ
áóëåâîé àëãåáðîé, èçîìîðôíîé òîòàëüíîé àëãåáðå h P(A × B), ∪, ∩, − , ∅, A × B i. Èçî-
ìîðôèçì ñëåäóåò èç ñëåäóþùèõ ðàâåíñòâ:

        M (α ∪ β) = M (α) ∨ M (β); M (α ∩ β) = M (α)NM (β); M (α) = ¬ M (α).

   Ïîíÿòíî, ÷òî ìàòðèöà M (α] ) ∈ Mn×m ïîëó÷àåòñÿ èç ìàòðèöû M (α) ∈ Mm×n òðàíñ-
ïîíèðîâàíèåì.
   Ïóñòü M1 ∈ Mm×n , M2 ∈ Mn×k . Îïðåäåëèì ïðîèçâåäåíèå M1 · M2 ∈ Mm×k äàííûõ
ìàòðèö êàê îáû÷íîå ìàòðè÷íîå ïðîèçâåäåíèå ñ çàìåíîé îïåðàöèè ñóììèðîâàíèÿ íà ∨,
à îïåðàöèè óìíîæåíèÿ  íà N. Îáû÷íûì îáðàçîì ââîäèòüñÿ íàòóðàëüíàÿ ñòåïåíü M n
ìàòðèöû M êàê ðåçóëüòàò ïåðåìíîæåíèÿ n ∈ N ýêçåìïëÿðîâ äàííîé ìàòðèöû. Ëåãêî
ïîêàçûâàåòñÿ, ÷òî åñëè α ⊆ A × B è β ⊆ B × C , ãäå A, B, C  êîíå÷íûå ìíîæåñòâà,
òî ñïðàâåäëèâî ðàâåíñòâî
                              M (α ¦ β) = M (α) · M (β)
è ïîýòîìó, â ÷àñòíîñòè, M (α2 ) = M 2 (α).


2.2 Îäíîðîäíûå îòíîøåíèÿ
   Îòíîøåíèå ρ ⊆ A2 íàçûâàåòñÿ áèíàðíûì íà A èëè îäíîðîäíûì. Ìíîæåñòâî âñåõ
áèíàðíûõ íà A îòíîøåíèé îáîçíà÷èì R(A).
    ñëó÷àå, êîãäà A  êîíå÷íîå ìíîæåñòâî íåáîëüøîé ìîùíîñòè, îäíîðîäíûå îòíî-
øåíèÿ ρ ∈ R(A) óäîáíî èçîáðàæàòü â âèäå îðèåíòèðîâàííîãî ãðàôà. Âåðøèíàì ýòîãî
ãðàôà ñîîòâåòñòâóþò ýëåìåíòû A, à äóãà âåä¼ò èç x â y , åñëè xρy . Íà ðèñ. 2.1 ïî-
êàçàíû ïðèìåðû òàêèõ ãðàôîâ ñîîòâåòñòâåííî äëÿ îòíîøåíèé α = { (a, c), (a, d) } è
β = α ∪ { (d, b) } íà ÷åòûð¼õýëåìåíòíîì ìíîæåñòâå { a, b, c, d }. Åñëè xρx, òî ó âåðøè-


                          a   [[     b                  a    [[      bu
                                []                              []
                          u                             u
                          c          d                  c            d


                         Ðèñ. 2.1: Ãðàôû áèíàðíûõ îòíîøåíèé

íû x ðèñóþò ïåòëþ.
   Ïîñêîëüêó â R(A) ïðîèçâåäåíèå âñåãäà îïðåäåëåíî, òî â ñèëó àññîöèàòèâíîñòè ïðîèç-
âåäåíèÿ ñîîòâåòñòâèé àëãåáðà h R(A), ¦ i åñòü ïîëóãðóïïà. Åñëè ρ ∈ R(A) è ∅ 6= B ⊆ A,
òî îòíîøåíèå ρ ∩ B 2 íàçûâàþò ñóæåíèåì èëè îãðàíè÷åíèåì îòíîøåíèÿ ρ íà ïîäìíî-
æåñòâî B è îáîçíà÷àþò ρ |B .
   Äëÿ íàòóðàëüíîãî k ââîäÿò åñòåñòâåííîå îáîçíà÷åíèå αk = α¦. . .¦α ( k ðàç, α1 = α ).
Ðàçóìååòñÿ,
                          α ⊆ β ⇒ αk ⊆ β k , k = 1, 2, . . . .
   Ïîêàæåì, ÷òî
                                     (α ∩ β)2 ⊆ α2 ∩ β 2 .                        (2.1)

Страницы