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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

t
(bp
B
t bq
B
)(a) = bp
B
(a) t bq
B
(a)
(5.2)
=
\
(p t q)
B
(a) ∈ P
n
B
a ∈ B
n
u
0
f
0
= 0 f
1
= 1 B
P
n
B
¤
2
p, q ∈ P
n
p ∼ q B
bp
B
= bq
B
P
n
N ⊆ P
n
P
n
N
N
x
σ
σ ∈ {0, 1} x ∈ { x
1
, . . . , x
n
, o, ι}
x
1
i
= x
i
, x
0
i
= x
i
0
, o
1
= 0, o
0
= 1, ι
1
= 1, ι
0
= 0.
x
i
x
i
0
B p P
n
bp
B
(b
1
, . . . , b
n
) : 2
n
→ 2 p B f
p
2
n
eα,
e
β, . . . eα = (α
1
, . . . , α
n
) α
i
∈ {0, 1} i = 1, n
f
p
N
1
f
p
N
0
f
p
p
d
(f
p
) =
F
eα=(α
1
, ..., α
n
)∈N
1
f
p
¡
x
α
1
1
u . . . u x
α
n
n
¢
p
c
(f
p
) =
d
eα=(α
1
, ..., α
n
)∈N
0
f
p
¡
x
α
1
1
t . . . t x
α
n
n
¢
N
1
f
p
6= ∅ N
0
f
p
6= ∅
p N
1
f
p
= ∅
p
d
(f
p
) = 0 N
0
f
p
= ∅ p
c
(f
p
) = 1
112                                                                 Ãëàâà 5. Áóëåâû àëãåáðû (ïðîäîëæåíèå)


      Äëÿ t èìååì
                                                              (5.2)
                           (b
                            pB t qbB )(a) = pbB (a) t qbB (a) = (p  \
                                                                    t q)B (a) ∈ PBn

äëÿ ïðîèçâîëüíîãî a ∈ B n . Äëÿ u è 0 äîêàçàòåëüñòâî àíàëîãè÷íî.
   Êðîìå òîãî, f0 = 0 è f1 = 1 äëÿ ëþáîé áóëåâîé àëãåáðû B è ïî (5.2) ýòè ôóíêöèè
ñîäåðæàòñÿ â PBn .                                                              ¤

   Ñ ïîìîùüþ òåîðåìû Ñòîóíà ïîêàçûâàåòñÿ, ÷òî ïîëèíîìèàëüíûå ôóíêöèè, ñîîòâåò-
ñòâóþùèå ýêâèâàëåíòíûì ìíîãî÷ëåíàì, ñîâïàäàþò íà ëþáîé áóëåâîé àëãåáðå, à íå òîëüêî
íà 2, ò.å. ñïðàâåäëèâà

Òåîðåìà 5.12. Ïóñòü p, q ∈ Pn è p ∼ q . Òîãäà äëÿ ïðîèçâîëüíîé áóëåâîé àëãåáðû B
ñïðàâåäëèâî pbB = qbB .

   Äîêàçàòåëüñòâî ìîæíî íàéòè â [8].
   ×àñòî âîçíèêàåò ïîòðåáíîñòü çàìåíèòü äàííûé ìíîãî÷ëåí ýêâèâàëåíòíûì åìó áîëåå
ïðîñòûì ìíîãî÷ëåíîì. Äàííóþ ïðîáëåìó ðåøàþò â äâà ýòàïà. Ñíà÷àëà ââîäÿò ò.í. íîð-
ìàëüíûå ôîðìû ìíîãî÷ëåíîâ. Ñîâîêóïíîñòü íîðìàëüíûõ ôîðì îáåñïå÷èâàåò íàëè÷èå ñè-
ñòåìû ïðåäñòàâèòåëåé äëÿ êàæäîãî êëàññà ýêâèâàëåíòíîñòè ìíîæåñòâà Pn . Äàëåå çàäà÷à
ñâîäèòñÿ ê íàõîæäåíèþ êðàò÷àéøåãî â òîì èëè èíîì ñìûñëå ìíîãî÷ëåíà, ýêâèâàëåíòíîãî
äàííîé íîðìàëüíîé ôîðìå.

Îïðåäåëåíèå 5.8. Ìíîæåñòâî N ⊆ Pn íàçûâàåòñÿ ñèñòåìîé ñîâåðøåííûõ íîðìàëüíûõ
ôîðì, åñëè
      ˆ äëÿ ëþáîãî ýëåìåíòà Pn íàéä¼òñÿ ýêâèâàëåíòíûé åìó ýëåìåíò N ;
      ˆ äâà ðàçíûõ ýëåìåíòà N íåýêâèâàëåíòíû.

   Áóäåì äàëåå ïîëüçîâàòüñÿ îáîçíà÷åíèåì xσ , àíàëîãè÷íûì ââåä¼ííîìó â ï. 1.2 äëÿ
ìíîæåñòâ, à èìåííî, äëÿ σ ∈ {0, 1} è x ∈ { x1 , . . . , xn , o, ι} ïîëîæèì

                    x1i = xi ,       x0i = xi 0 ,       o1 = 0,     o0 = 1,   ι1 = 1,   ι0 = 0.

Ïîñëåäíèå ðàâåíñòâà ãîâîðÿò î òîì, ÷òî ìû áóäåì äàëåå â ðàìêàõ äàííîãî ðàçäåëà äëÿ
ïðîñòîòû ïîëüçîâàòüñÿ ñèìâîëàìè 0 è 1 äëÿ îáîçíà÷åíèÿ íóëÿ è åäèíèöû áóëåâîé àëãåáðû
ñîîòâåòñòâåííî. Âûðàæåíèÿ âèäà xi , xi 0 , à òàêæå 0 è 1 áóäåì íàçûâàòü ëèòåðàëàìè.
     Ïóñòü B  áóëåâà àëãåáðà, p  áóëåâ ìíîãî÷ëåí èç Pn . Ïîëèíîìèàëüíóþ ôóíêöèþ
pbB (b1 , . . . , bn ) : 2n → 2, èíäóöèðîâàííóþ p íà B , îáîçíà÷èì fp . Ýëåìåíòû 2n áóäåì
îáîçíà÷àòü α            e . . .. Òàêèì îáðàçîì, íàïðèìåð, α
                    e, β,                                   e = (α1 , . . . , αn ), αi ∈ {0, 1}, i = 1, n.
Ôóíêöèè fp ñîïîñòàâëåíû äâà ìíîæåñòâà Nf1p è Nf0p å¼ åäèíè÷íûõ è íóëåâûõ íàáîðîâ.
Ñëåäóþùèå äâà áóëåâûõ ìíîãî÷ëåíà
                                F      ¡ α1               ¢
         pd (fp ) =                     x1 u . . . u xαnn   è
                    e=(α1 , ..., αn )∈Nf1p
                    α

                             d               ¡ α1               ¢
       pc (fp ) =                             x1 t . . . t xαnn
                    e=(α1 , ..., αn )∈Nf0p
                    α


ïðè Nf1p 6= ∅ è Nf0p 6= ∅ íàçûâàþòñÿ ñîîòâåòñòâåííî ñîâåðøåííûìè äèçúþíêòèâíîé è
êîíúþíêòèâíîé íîðìàëüíûìè ôîðìàìè (ÑÄÍÔ è ÑÊÍÔ) ìíîãî÷ëåíà p. Ïðè Nf1p = ∅
ïîëàãàþò pd (fp ) = 0, à ïðè Nf0p = ∅  pc (fp ) = 1. ßñíî, ÷òî äàííûå ôîðìû îïðåäåëåíû
îäíîçíà÷íî ñ òî÷íîñòüþ äî ïîðÿäêà ñîîòâåòñòâóþùèõ ÷ëåíîâ. Çàìåòèì, ÷òî ÑÄÍÔ äëÿ

Страницы