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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

D = C
1
∨ . . . ∨ C
l
C
i
i = 1, l
p D
C = D
1
N. . . ND
m
D
i
i = 1, m
p p = 0
D
i
= 0, i = 1, m D
i
=
F
j∈I
i
x
σ
j
j
, I
i
⊆ {1, . . . , n}
β = (β
1
, . . . , β
n
) β
k
= σ
j
, j ∈ I
i
β
k
∈ {1, 0} j 6∈ I
i
p = 0
p = q R = 0
p = q pq
0
∨ p
0
q = 0
B (b
1
, . . . , b
n
) ∈ B
n
x = bp
B
(b
1
, . . . , b
n
)
y = bq
B
(b
1
, . . . , b
n
) (x ∨ y)(x
0
∨ y
0
) = xy
0
∨ x
0
y
x = y ⇒ xy
0
∨ x
0
y = 0.
xy
0
∨ x
0
y = 0
x ∨ y v (x
0
∨ y
0
)
0
= xy,
x = y ¤
{(p
i
, q
i
) | i = 1, . . . , m }
p
1
q
1
∨ p
1
0
q
1
∨ p
2
q
2
0
∨ p
2
0
q
2
∨ . . . ∨ p
m
q
m
0
∨ p
m
0
q
m
= 0.
{(x
1
x
2
, x
1
x
3
∨ x
2
), (x
1
∨ x
2
0
, x
3
)}
x
1
x
2
= x
1
x
3
∨ x
2
,
x
1
∨ x
2
0
= x
3
.
(x
1
x
2
)(x
1
x
3
∨ x
2
)
0
∨ (x
1
x
2
)
0
(x
1
x
3
∨ x
2
) ∨ (x
1
∨ x
2
0
)x
3
0
∨ (x
1
∨ x
2
0
)
0
x
3
= 0.
(x
1
∨ x
2
∨ x
3
0
)(x
1
0
∨ x
2
0
∨ x
3
0
) = 0,
2
(001) (111)
x h B, t, u,
0
, o, ι i
o
5.5. Óðàâíåíèÿ â áóëåâûõ àëãåáðàõ                                                                      115


   Ïóñòü D = C1 ∨ . . . ∨ Cl , ãäå Ci  ýëåìåíòàðíûå êîíúþíêöèè, i = 1, l, åñòü
ÑÄÍÔ ìíîãî÷ëåíà p. Ñ ïîìîùüþ çàêîíîâ áóëåâîé àëãåáðû ïðåîáðàçóåì D â ÊÍÔ
C = D1 N. . . NDm , ãäå Di  äèçúþíêòû, i = 1, m (èëè ñðàçó òåì èëè èíûì ïóò¼ì
ïîëó÷èì ÊÍÔ, ýêâèâàëåíòíóþ p). Òîãäà ðàâåíñòâî p = 0 áóäåò
                                                        F σâûïîëíÿòüñÿ         ïðè âû-
ïîëíåíèè ëþáîãî èç ðàâåíñòâ Di = 0, i = 1, m. Åñëè Di =   xj j , Ii ⊆ {1, . . . , n}, òî
                                                                          j∈Ii
ëþáîé íàáîð β = (β1 , . . . , βn ), ãäå βk = σj , j ∈ Ii è βk ∈ {1, 0} j 6∈ Ii áóäåò ðåøåíèåì
óðàâíåíèÿ p = 0.
   Èç ýòîãî ÿñíî, ÷òî äëÿ äàëüíåéøåãî óäîáíî ïðåîáðàçîâàòü p = q ê âèäó R = 0.
Òåîðåìà 5.13. Óðàâíåíèÿ p = q è pq 0 ∨ p 0 q = 0 èìåþò îäíè è òå æå ðåøåíèÿ.
Äîêàçàòåëüñòâî. Ïóñòü B  áóëåâà àëãåáðà è (b1 , . . . , bn ) ∈ B n . Äëÿ x = pbB (b1 , . . . , bn ),
y = qbB (b1 , . . . , bn ) èìååì (x ∨ y)(x 0 ∨ y 0 ) = xy 0 ∨ x 0 y . C îäíîé ñòîðîíû,

                                     x = y ⇒ xy 0 ∨ x 0 y = 0.

C äðóãîé, åñëè xy 0 ∨ x0 y = 0, òî ïî òåîðåìå 5.1

                                      x ∨ y v (x 0 ∨ y 0 ) 0 = xy,

îòêóäà x = y .                                                                                          ¤

   Ïî äàííîé òåîðåìå ñèñòåìà óðàâíåíèé {(pi , qi ) | i = 1, . . . , m} ýêâèâàëåíòíà åäèí-
ñòâåííîìó óðàâíåíèþ

                  p1 q1 ∨ p1 0 q1 ∨ p2 q2 0 ∨ p2 0 q2 ∨ . . . ∨ pm qm 0 ∨ pm 0 qm = 0.

Âûðàçèâ ëåâóþ ÷àñòü â êîíúþíêòèâíîé ôîðìå, ïîëó÷èì, ÷òî ïðèâåä¼ííîå âûøå óðàâíå-
íèå èìååò ðåøåíèå, êîãäà õîòÿ áû îäèí èç ñîìíîæèòåëåé ïðèíèìàåò çíà÷åíèå 0. Òàêèì
îáðàçîì, ïîëó÷àþò âñå ðåøåíèÿ ñèñòåìû.
Ïðèìåð 5.10. Ðàññìîòðèì ñèñòåìó {(x1 x2 , x1 x3 ∨ x2 ), (x1 ∨ x2 0 , x3 )}. Ïåðåïèøåì å¼ â
îáû÷íîì âèäå
                                            x1 x 2 = x1 x3 ∨ x2 ,
                                        x1 ∨ x2 0 = x3 .
Ïî òåîðåìå 5.13 äàííàÿ ñèñòåìà ýêâèâàëåíòíà åäèíñòâåííîìó óðàâíåíèþ
      (x1 x2 )(x1 x3 ∨ x2 ) 0 ∨ (x1 x2 ) 0 (x1 x3 ∨ x2 ) ∨ (x1 ∨ x2 0 )x3 0 ∨ (x1 ∨ x2 0 ) 0 x3 = 0.
Ïðåîáðàçóÿ ëåâóþ ÷àñòü â ÑÊÍÔ, ïîëó÷èì óðàâíåíèå
                             (x1 ∨ x2 ∨ x3 0 )(x1 0 ∨ x2 0 ∨ x3 0 ) = 0,
êîòîðîå èìååò òî æå ìíîæåñòâî ðåøåíèé, ÷òî è èñõîäíàÿ ñèñòåìà. Ýòè ðåøåíèÿ ÿâëÿþòñÿ
íóëÿìè ïåðâîãî è âòîðîãî ñîìíîæèòåëåé. Íàïðèìåð, â 2 äàííàÿ ñèñòåìà èìååò ðîâíî äâà
ðåøåíèÿ: (001) è (111) .
   B ïðîèçâîëüíîé áóëåâîé àëãåáðå ðåøåíèÿ çàïèñûâàþòñÿ áîëåå ñëîæíî, íî òàêæå äî-
ñòàâëÿþò 0 îáîèì ñîìíîæèòåëÿì ïîñëåäíåãî óðàâíåíèÿ.
   Îäèí èç ìåòîäîâ ðåøåíèÿ áóëåâûõ óðàâíåíèé îòíîñèòåëüíî îäíîãî íåèçâåñòíîãî ýëå-
ìåíòà x áóëåâîé àëãåáðû h B, t, u, 0 , o, ι i ñîñòîèò â ïîñëåäîâàòåëüíîì âûïîëíåíèè ñëå-
äóþùèõ øàãîâ.
Øàã 1. Ïðèâîäèì äàííîå óðàâíåíèå ê ðàâíîñèëüíîìó óðàâíåíèþ ñ o â ïðàâîé ÷àñòè (÷òî
    îáåñïå÷èâàåòñÿ òåîðåìîé 5.13).

Страницы