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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

x
1
x
2
= x
1
∨ x
2
[ x
1
∨x
2
] [ x
1
∨x
2
] [ x
1
] [ x
2
] [ x
1
x
2
∨x
1
x
2
] [ x
1
x
2
]
[ x
1
x
2
] [ x
1
x
2
]
x y
[ x
1
∨ x
2
]
(0111)
[ x
1
]
(0011)
[ x
1
x
2
∨ x
1
x
2
]
(0110)
[ x
2
]
(0101)
[ x
1
x
2
]
(0010)
[ x
1
x
2
]
(0001)
[ x
1
x
2
]
(0100)
(0000)
L
∗
2
(∗)
F P(N)
F
0
2N F
0
2N F
2N ∈ F
2N F
F
1
3N F
1
F
1
F
2
F
F
F
F
5.3. Èäåàëû è ôèëüòðû â áóëåâîé àëãåáðå                                                             109


Èìååì x1 x2 = x1 ∨ x2 , è ãëàâíûé èäåàë àëãåáðû ËèíäåíáàóìàÒàðñêîãî, ïîðîæä¼ííûé
êëàññîì ôîðìóë [ x1 ∨ x2 ], ñîñòàâëÿþò êëàññû [ x1 ∨ x2 ], [ x1 ], [ x2 ], [ x1 x2 ∨ x1 x2 ], [ x1 x2 ],
[ x1 x2 ], [ x1 x2 ] è F. Íà ðèñ. 5.1 ïîêàçàí äàííûé èäåàë. Äëÿ êàæäîãî êëàññà óêàçàí âåêòîð
çíà÷åíèé ñîîòâåòñòâóþùåé ôóíêöèè (ïîäðàçóìåâàåòñÿ óïîðÿäî÷åíèå íàáîðîâ çíà÷åíèé
ïåðåìåííûõ ñíà÷àëà ïî x, çàòåì ïî y ).


                                                  [ x1 ∨ x2 ]
                                                    (0111)
                                      A A A
                                  AAA
                   [ x1 ]
                              AAA               [ x1 x2 ∨ x1 x2 ]                [ x2 ]
                  (0011)
                                            A
                                                     (0110)
                                                                        A A A   (0101)

                                      A A A                           AA
                                  A                                AA
                  [ x1 x2 ]
                              AAA                   [ x1 x2 ]
                                                                AA              [ x1 x2 ]
                  (0010)                            (0001)
                                                                         AA A   (0100)

                                                                      AA
                                                                AA  AA
                                                       F
                                                    (0000)


              Ðèñ. 5.1: Ãëàâíûé èäåàë L∗2 , ïîðîæäåííûé êëàññîì êîíúþíêöèè

   Ðåøåíèåì óðàâíåíèÿ (∗) áóäåò ëþáàÿ áóëåâà ôóíêöèÿ, ðåàëèçóþùàÿñÿ ôîðìóëàìè
èç ïðèâåä¼ííûõ êëàññîâ.
   áåñêîíå÷íûõ áóëåâûõ àëãåáðàõ, Èõ òàêæå íàçûâàþò ñâîáîäíûìè, ïîñêîëüêó îíè íå
ôèêñèðîâàíû íè â êàêîé òî÷êå èñõîäíîãî ìíîæåñòâà. Ïåðåñå÷åíèå âñåõ ýëåìåíòîâ òàêîãî
ôèëüòðà åñòü íóëåâîé ýëåìåíò.
Ïðèìåð 5.5. Îïèøåì â ñàìîì îáùåì âèäå, êàê ìîæåò áûòü ïîñòðîåí íåãëàâíûé óëüòðà-
ôèëüòð F áóëåàíà P(N) . Íà ïåðâîì øàãå ðàññìîòðèì ôèëüòð Ôðåøå, êîòîðûé îáî-
çíà÷èì F0 . Îí íå ÿâëÿåòñÿ ìàêñèìàëüíûì, ïîñêîëüêó, íàïðèìåð, íè ìíîæåñòâî ÷¼òíûõ
÷èñåë 2N, íè åãî äîïîëíåíèå (ìíîæåñòâî íå÷¼òíûõ ÷èñåë) íå ïðèíàäëåæàò F0 . Ïîýòî-
ìó íàäî ïðèíÿòü ðåøåíèå, îòíåñòè 2N ê êîíñòðóèðóåìîìó óëüòðàôèëüòðó F èëè íåò.
Ïóñòü ïðèíÿòî ðåøåíèå î òîì, ÷òî 2N ∈ F . Ýòî áóäåò îçíà÷àòü, ÷òî íåêîòîðûå äðóãèå
ìíîæåñòâà (âñå ìíîæåñòâà, ñîäåðæàùèå 2N ) òàêæå áóäóò ïðèíàäëåæàòü F . Ïîëó÷åííûé
ôèëüòð îáîçíà÷èì F1 . Ïîíÿòíî, ÷òî îí òàêæå íå áóäåò ÿâëÿòüñÿ èñêîìûì óëüòðàôèëü-
òðîì, ïîñêîëüêó îòíîñèòåëüíî ðÿäà ìíîæåñòâ íåîïðåäåë¼ííîñòü îñòàíåòñÿ: íàïðèìåð, íè
ìíîæåñòâî 3N, íè åãî äîïîëíåíèå íå ïðèíàäëåæàò F1 . Çäåñü ñíîâà íóæíî ïðèíÿòü ðå-
øåíèå î âõîæäåíèè îäíîãî èç óêàçàííûõ ìíîæåñòâ â F1 , ïîñòðîèòü F2 è ò.ä. Ïîêàçàíî,
÷òî â ðåçóëüòàòå âûïîëíåíèÿ òðàíñôèíèòíîãî ÷èñëà øàãîâ áóäåò ïîñòðîåí èñêîìûé
óëüòðàôèëüòð F .
   Õîòÿ ìû ïðèâåëè ÷ðåçâû÷àéíî ãðóáûé íàáðîñîê ñïîñîáà ïîñòðîåíèÿ ôèëüòðà F , íà-
äååìñÿ, ÷òî ÷èòàòåëþ âèäíà ðîëü àêñèîìû âûáîðà â äàííûõ ðàññóæäåíèÿõ: íèêàêîãî
ñïîñîáà óêàçàòü, êàêîå ìíîæåñòâî íóæíî ðàññìàòðèâàòü íà êàæäîì øàãå äëÿ âêëþ÷åíèÿ
åãî èëè åãî äîïîëíåíèÿ â F , íåò. Êðîìå òîãî, íà êàæäîì øàãå ìîæíî ïðèíÿòü ëþáóþ
èç óêàçàííûõ àëüòåðíàòèâ. Ìû âèäèì, ÷òî ïðîöåññ ïîñòðîåíèÿ F ñóùåñòâåííî íåîäíî-

Страницы