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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

(X ⊕ Y ) ∩ Z = (X ∩ Y ) ⊕ (Y ∩ Z) .
⊆
X ⊆ Y ⇔ X ∩ Y = X ⇔ X ∪ Y = Y.
X ⊆ Y X Y Y X
P
∗
(A)
A
B = {1, 0}
σ = h ∨, N, ¬, 0, 1 i
B 0
1 h B, σ i
2 Cmp
0
Isl
0
h 2
n
, ∨, N, ¬,
e
0,
e
1 i 2
n
n
e
0 = (0 . . . 0)
e
1 = (1 . . . 1)
n
P
2
0
1
h P
2
, ∨, N, ¬, 0, 1 i
N
N = p
1
· . . . · p
k
p
1
, . . . , p
k
N D(N)
N = 30 = 2 · 3 · 5 D(30) = {1, 2, 3, 5, 6, 10, 15, 30 }
m n m∨n
m ∧ n m
0
=
N
m
h D(N), ∨, ∧,
0
, 1, N i
A B A
B
A B
N
¡
N
[N/2]
¢
12                                                                 Ãëàâà 1. Áóëåâû àëãåáðû


          (X ⊕ Y ) ∩ Z = (X ∩ Y ) ⊕ (Y ∩ Z) .

     Òàêæå ÷àñòî èñïîëüçóþò îòíîøåíèå ⊆ âêëþ÷åíèÿ ìíîæåñòâ. Î÷åâèäíî

                            X ⊆ Y ⇔ X ∩ Y = X ⇔ X ∪ Y = Y.

Ïðè X ⊆ Y , íàïîìíèì, X íàçûâàþò ïîäìíîæåñòâîì Y , à Y  íàäìíîæåñòâîì X .
    äàëüíåéøåì ìû áóäåì èñïîëüçîâàòü îáîçíà÷åíèå P ∗ (A) äëÿ ñîâîêóïíîñòè âñåõ íåïó-
ñòûõ ïîäìíîæåñòâ (íåïóñòîãî) ìíîæåñòâà A .


1.3 Èçîìîðôèçìû áóëåâûõ àëãåáð
   Õîòÿ àëãåáðû ìíîæåñòâ ÿâëÿþòñÿ, êàê ìû óâèäèì, â íåêîòîðîì ñìûñëå, îñíîâíûìè
ïðèìåðàìè áóëåâûõ àëãåáð, ïîñëåäíèå èìè íå èñ÷åðïûâàþòñÿ.
Ïðèìåð 1.3.    1. Ðàññìîòðèì äâîè÷íîå ìíîæåñòâî èñòèííîñòíûõ çíà÷åíèé B = {1, 0}
     è ñèãíàòóðó σ = h ∨, N, ¬, 0, 1 i, ñîñòîÿùóþ èç ëîãè÷åñêèõ îïåðàöèé äèçúþíêöèè,
     êîíúþíêöèè è îòðèöàíèÿ, à òàêæå ñèìâîëîâ ýëåìåíòîâ B  ëîãè÷åñêîãî íóëÿ 0
     (¾ëîæü¿) è ëîãè÷åñêîé åäèíèöû 1 (¾èñòèíà¿). Ïîëó÷åííàÿ ÀÑ h B, σ i ÿâëÿåò-
     ñÿ, êàê íåòðóäíî âèäåòü, áóëåâîé àëãåáðîé. Ýòà ïðîñòåéøàÿ áóëåâà àëãåáðà èãðàåò
     ôóíäàìåíòàëüíóþ ðîëü â ëîãèêå. Îíà íàçûâàåòñÿ àëãåáðîé âûñêàçûâàíèé ; áóäåì
     îáîçíà÷àòü å¼ 2. Çàìåòèì, ÷òî Cmp 0 è Isl 0 (îñíîâíûå çàêîíû, îïèñûâàþùèå ñâîé-
     ñòâà äîïîëíåíèÿ) â ëîãèêå íàçûâàþòñÿ ñîîòâåòñòâåííî çàêîíàìè ¾èñêëþ÷åííîãî
     òðåòüåãî¿ è ¾ïðîòèâîðå÷èÿ¿.
  2. ÀÑ h 2n , ∨, N, ¬, e 0, e
                             1 i, ãäå 2n  n-ìåðíûé åäèíè÷íûé êóá, e          0 = (0 . . . 0),
     e
     1 = (1 . . . 1), à ñèãíàòóðíûå îïåðàöèè ïðèìåíÿþòñÿ ê áóëåâûì âåêòîðàì ïîêîì-
     ïîíåíòíî, íàçûâàþò áóëåâîé àëãåáðîé n-ìåðíûõ äâîè÷íûõ âåêòîðîâ.
  3. Îáîçíà÷èì ÷åðåç P2 ìíîæåñòâî âñåõ äâóçíà÷íûõ áóëåâûõ ôóíêöèé, à ÷åðåç 0 è
     1  ôóíêöèè ¾òîæäåñòâåííûé íóëü¿ è ¾òîæäåñòâåííàÿ åäèíèöà¿ ñîîòâåòñòâåííî.
     Òîãäà ÀÑ h P2 , ∨, N, ¬, 0, 1 i åñòü áóëåâà àëãåáðà. ż íàçûâàþò áóëåâîé àëãåáðîé
     ëîãè÷åñêèõ ôóíêöèé.
  4. Ïóñòü N  ñâîáîäíîå îò êâàäðàòîâ íàòóðàëüíîå ÷èñëî. Ýòî îçíà÷àåò, ÷òî ñïðàâåä-
     ëèâî ïðåäñòàâëåíèå N = p1 · . . . · pk , ãäå p1 , . . . , pk  ðàçëè÷íûå ïðîñòûå ÷èñëà.
     Ñîâîêóïíîñòü âñåõ íàòóðàëüíûõ äåëèòåëåé N îáîçíà÷èì D(N ). Íàïðèìåð, äëÿ
     N = 30 = 2 · 3 · 5 èìååì D(30) = {1, 2, 3, 5, 6, 10, 15, 30}.
        Íàèìåíüøåå îáùåå êðàòíîå ÷èñåë m è n îáîçíà÷èì m ∨ n, à èõ íàèáîëüøèé îáùèé
        äåëèòåëü  m ∧ n. Ïîëîæèì m0 = N   m
                                             . Òîãäà ÀÑ h D(N ), ∨, ∧, 0 , 1, N i, êàê íåòðóä-
        íî ïðîâåðèòü, åñòü áóëåâà àëãåáðà. Äàííàÿ áóëåâà àëãåáðà øèðîêî èñïîëüçóåòñÿ â
        òåîðèè ÷èñåë7 .
     5. Ðàññìîòðèì ìíîæåñòâî ýëåêòðè÷åñêèõ âûêëþ÷àòåëåé, èëè êîíòàêòîâ, êîòîðûå ìî-
        ãóò íàõîäèòüñÿ â îäíîì èç äâóõ ñîñòîÿíèé  çàìêíóòîì (ïðîâîäÿùåì) èëè ðàçî-
        ìêíóòîì (íå ïðîâîäÿùåì). Ó òàêèõ êîíòàêòîâ ðàçëè÷àþò âõîäíîé è âûõîäíîé ïîëþ-
        ñû, êîòîðûå ìîæíî ñîåäèíÿòü ñ ïîëþñàìè äðóãèõ êîíòàêòîâ, ñòðîÿ ýëåêòðè÷åñêèå
        äâóõïîëþñíûå (îäèí âõîä è îäèí âûõîä) öåïè.
          Åñëè ñîåäèíÿòü äðóã ñ äðóãîì òîëüêî âõîäíûå è âûõîäíûå ïîëþñû, òî èìååòñÿ
          òîëüêî äâà ñïîñîáà îáúåäèíåíèÿ òàêèõ öåïåé: ïîñëåäîâàòåëüíîå è ïàðàëëåëüíîå.
          Ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèåì öåïåé A è B âûõîäíîé ïîëþñ öåïè A ïðèñî-
          åäèíÿåòñÿ ê âõîäíîìó ïîëþñó öåïè B , ïðè ïàðàëëåëüíîì  ïîïàðíî îáúåäèíÿþòñÿ
          âõîäíûå è âûõîäíûå öåïè A è B (â îáîèõ ñëó÷àÿõ âõîäíîé è âûõîäíîé ïîëþñû
     7Â
      ÷àñòíîñòè, îòñþäà ñëåäóåò,
                        ¡ N ¢ ÷òî ìàêñèìàëüíîå ÷èñëî âçàèìíî ïðîñòûõ äåëèòåëåé ñâîáîäíîãî îò
êâàäðàòîâ ÷èñëà N åñòü [N/2]

Страницы