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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

X
Y [Y ]
[X]
M P(M)/P
0
(M)
a
M
a
A = {A, B, . . .}
A ≡ B
A B
A ∼ B ∼ A
A [A]
A/∼
(
−
) (∪)
(∩)
[A] = [¬A], [A] ∪ [B] = [A ∨ B], [A] ∩ [B] = [ANB].
∪ ∩
[A] ∪ = [A] [A] ∩ = [A]
[A] ∪ [A] = [A] ∩ [A] =
h A/∼, ∪, ∩,
−
, , i
' A ' B
A B A/∼
A
n
n
A
n
A
n
/ ∼
2
2
n
a(˜x) · X(˜x) = ,
a(˜x) X(˜x)
a(˜x)
a(˜x) = x
1
x
2
x
1
x
2
X(x
1
, x
2
) = . (∗)
108                                                 Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


ëþáîì áåñêîíå÷íîì ìíîæåñòâå X ìîæíî (ñ ïîìîùüþ àêñèîìû âûáîðà!) óêàçàòü ïîäìíî-
æåñòâî Y òàêîå, ÷òî è îíî, åãî äîïîëíåíèå áåñêîíå÷íû, è ïîýòîìó [Y ] ñòðîãî ñîäåðæèòñÿ
â [X]. Ïîíÿòíî, ÷òî ïîäîáíàÿ ïðîöåäóðà ìîæåò áûòü ïðîâåäåíà äëÿ ëþáîé áåñêîíå÷íîé
àëãåáðû ìíîæåñòâ: åñëè M  áåñêîíå÷íîå ìíîæåñòâî, òî P(M )/P0 (M )  áåçàòîìíàÿ
áóëåâà àëãåáðà.
   Ãîâîðÿò, ÷òî ãëàâíûå óëüòðàôèëüòðû àëãåáðû ìíîæåñòâ, ïîñêîëüêó âñå îíè èìåþò âèä
a , ôèêñèðîâàíû â òî÷êå a ìíîæåñòâà. Èõ íàçûâàþò òðèâèàëüíûìè óëüòðàôèëüòðàìè.
 M

Ñîâìåñòíî ñ ôèëüòðàìè Ôðåøå îíè èãðàþò âàæíóþ ðîëü ïðè èññëåäîâàíèè ñõîäèìîñòè â
àíàëèçå (òîïîëîãè÷åñêàÿ ñèñòåìà îêðåñòíîñòåé äàííîé òî÷êè ÿâëÿåòñÿ ôèêñèðîâàííûì â
íåé òðèâèàëüíûì óëüòðàôèëüòðîì). Ãëàâíûå óëüòðàôèëüòðû òàêæå èñïîëüçóþò, íàïðè-
ìåð, ïðè èññëåäîâàíèÿõ ïîëíîòû ëîãè÷åñêèõ ñèñòåì â àëãåáðàõ ËèíäåíáàóìàÒàðñêîãî,
ïîðîæä¼ííûõ ñîîòâåòñòâóþùåé ëîãè÷åñêîé òåîðèåé5 .
Ïðèìåð 5.4. Ðàññìîòðèì ìíîæåñòâî A = {A, B, . . .} ôîðìóë àëãåáðû ëîãèêè (ôîðìóë
íàä âûñêàçûâàíèÿìè). Åñëè A ≡ B åñòü òîæäåñòâåííî èñòèííàÿ ôîðìóëà, òî ãîâîðÿò,
÷òî ôîðìóëû A è B ëîãè÷åñêè ýêâèâàëåíòíû èëè ðàâíîñèëüíû, ÷òî çàïèñûâàþò êàê
A ∼ B . ßñíî, ÷òî ∼ åñòü îòíîøåíèå ýêâèâàëåíòíîñòè íà A. Êëàññ ýêâèâàëåíòíîñòè,
ïîðîæäàåìûé ôîðìóëîé A áóäåì îáîçíà÷àòü [A], êëàññû òîæäåñòâåííî èñòèííûõ ôîð-
ìóë  T, à òîæäåñòâåííî ëîæíûõ ôîðìóë  F.
   Íà ôàêòîðìíîæåñòâå A/ ∼ êëàññîâ ýêâèâàëåíòíîñòè ôîðìóë àëãåáðû ëîãèêè ìîæíî
çàäàòü òåîðåòèêî ìíîæåñòâåííûå îïåðàöèè äîïîëíåíèÿ (− ), îáúåäèíåíèÿ (∪) è ïåðåñå-
÷åíèÿ (∩), ïðè÷¼ì

                  [A] = [¬A],     [A] ∪ [B] = [A ∨ B],     [A] ∩ [B] = [ANB].

   Ëåãêî óñòàíîâèòü, ÷òî ââåä¼ííûå îïåðàöèè íàä êëàññàìè ýêâèâàëåíòíîñòåé èìåþò
ñëåäóþùèå ñâîéñòâà:

      ˆ îïåðàöèè ∪ è ∩ êîììóòàòèâíû è âçàèìíî äèñòðèáóòèâíû;
      ˆ âûïîëíÿþòñÿ ñîîòíîøåíèÿ [A] ∪ F = [A] è [A] ∩ T = [A];
      ˆ ñïðàâåäëèâû çàêîíû [A] ∪ [A] = T è [A] ∩ [A] = F.

Óêàçàííîå îçíà÷àåò, ÷òî ÀÑ h A/∼, ∪, ∩, − , T, F i ÿâëÿåòñÿ áóëåâîé àëãåáðîé. ż íàçû-
âàþò ôàêòîðàëãåáðîé ëîãè÷åñêèõ ôîðìóë. Äëÿ êëàññè÷åñêîé àëãåáðû âûñêàçûâàíèé îíà
ñîâïàäàåò ñ ñîîòâåòñòâóþùåé àëãåáðîé ËèíäåíáàóìàÒàðñêîãî (â ïîñëåäíåé ôàêòîðèçà-
öèÿ ïðîâîäèòñÿ ïî îòíîøåíèþ ' òàêîìó, ÷òî A ' B åñëè è òîëüêî åñëè èç ôîðìóëû
A âûâîäèòñÿ ôîðìóëà B è íàîáîðîò). Ñ êàæäûì ýëåìåíòîì A/ ∼ ñâÿçàíà ñîîòâåòñòâó-
þùàÿ ôóíêöèÿ àëãåáðû ëîãèêè.
   Îáîçíà÷èì ÷åðåç An ìíîæåñòâî ôîðìóë àëãåáðû ëîãèêè íàä n ýëåìåíòàðíûìè âû-
ñêàçûâàíèÿìè. Î÷åâèäíî, An áåñêîíå÷íî, à ôàêòîðìíîæåñòâî An / ∼  êîíå÷íî (è ñî-
          n
äåðæèò 22 ýëåìåíòîâ).
   Ðàññìîòðèì óðàâíåíèå
                                  a(x̃) · X(x̃) = F,
ãäå a(x̃) è X(x̃)  ôîðìóëû, ðåàëèçóþùèå ñîîòâåòñòâåííî èçâåñòíóþ è èñêîìóþ áóëåâû
ôóíêöèè (äëÿ ïðîñòîòû óêàçûâàþò èìåííî ôîðìóëû, à íå ïîðîæä¼ííûå èìè êëàññû). Òî-
ãäà ðåøåíèåì äàííîãî óðàâíåíèÿ áóäåò ëþáàÿ ôóíêöèÿ, ðåàëèçóåìàÿ ôîðìóëàìè èç ãëàâ-
íîãî èäåàëà, ïîðîæä¼ííîãî ôîðìóëîé a(x̃) â ñîîòâåòñòâóþùåé àëãåáðå Ëèíäåíáàóìà
Òàðñêîãî.
   Íàïðèìåð, ïóñòü a(x̃) = x1 x2 , ò.å. äàíî óðàâíåíèå

                                      x1 x2 X(x1 , x2 ) = F.                                   (∗)
   5 Ñì., íàïðèìåð, [11] èëè Ñ.È. Ãóðîâ. Èñ÷èñëåíèÿ âûñêàçûâàíèé êëàññè÷åñêîé ëîãèêè. Ó÷åáíîå ïîñî-
áèå  Ì.: Èçäàòåëüñêèé îòäåë ôàêóëüòåòà ÂÌèÊ èì. Ì.Â.Ëîìîíîñîâà; ÌÀÊÑ Ïðåññ, 2007.

Страницы