Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 6 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

6
2. Ïóñòü A={a, b}, B={c, d}, òîãäà A∩B=∅.
Äîïîëíåíèå ìíîæåñòâ îïåðàöèÿ \ (âû÷èòàíèå).
Ìíîæåñòâî À\ âêëþ÷àåò âñå ýëåìåíòû ìíîæåñòâà À, íå ïðèíàäëå-
æàùèå Â, ò. å. èç À âû÷èòàþòñÿ ýëåìåíòû îáùèå ñ Â. Íàïðèìåð, ïóñòü
A={a, b}, B={b, c}, òîãäà A\Â={a}.
Òåîðåòèêî-ìíîæåñòâåííîå ïðîèçâåäåíèå îïåðàöèÿ ×.
Ïóñòü À è  äâà ìíîæåñòâà. ×åðåç À× îáîçíà÷èì ìíîæåñòâî,
ñîñòîÿùåå èç óïîðÿäî÷åííûõ ïàð (a,b), òàêèõ, ÷òî à∈À, b∈Â. Èíà÷å ãî-
âîðÿ, ñ∈À× òîãäà è òîëüêî òîãäà, êîãäà ñ åñòü ïàðà (a, b), ïðè÷åì à∈À,
b∈B.
Íàïðèìåð, ïóñòü A={a, b}, B={c, d}, òîãäà À×Â={(a, c), (a, d), (b, c),
(b, d)}.
Äëÿ îáëåã÷åíèÿ îáùåãî îïðåäåëåíèÿ ââåäåì ïîíÿòèå ïðîèçâåäåíèÿ
ìíîæåñòâà ñàìîãî íà ñåáÿ.
Óïîðÿäî÷åííûì, èëè äåêàðòîâûì (ïðÿìûì), ïðîèçâåäåíèåì ìíî-
æåñòâà V ñàìîãî íà ñåáÿ (êîòîðîå îáîçíà÷àåòñÿ V×V) íàçûâàåòñÿ
ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð (s, t), ãäå s∈V è t∈V. Çäåñü (s, t) è (t,
s) ðàññìàòðèâàþòñÿ êàê ðàçëè÷íûå ýëåìåíòû, èñêëþ÷àÿ ñëó÷àé s=t.
Åñëè ÷èñëî ýëåìåíòîâ |V|=n, òî V×V ñîñòîèò èç n
2
óïîðÿäî÷åííûõ
ïàð. Íàïðèìåð, ïóñòü V={v
1
, v
2
, v
3
}, òîãäà V×V={(v
1
, v
1
), (v
1
, v
2
), (v
1
,
v
3
), (v
2
, v
1
), (v
2
, v
2
), (v
2
, v
3
), (v
3
, v
1
), (v
3
, v
2
), (v
3
, v
3
)}.
Íåóïîðÿäî÷åííûì ïðîèçâåäåíèåì ìíîæåñòâà V ñàìîãî íà ñåáÿ
(îáîçíà÷èì êàê V&V) íàçûâàåòñÿ ìíîæåñòâî âñåõ ðàçëè÷íûõ íå-
óïîðÿäî÷åííûõ ïàð [s, t], ïðè ýòîì ïàðû [s, t] è [t, s] ýêâèâàëåíò-
íû è òàê æå, êàê ïðè äåêàðòîâîì ïðîèçâåäåíèè, äîïóñêàåòñÿ ñî-
âïàäåíèå ýëåìåíòîâ ïàðû, ò. å. s=t. Ïðè |V|=n ìíîæåñòâî V&V
ñîñòîèò èç n(n+1)/2 ðàçëè÷íûõ íåóïîðÿäî÷åííûõ ïàð. Íàïðèìåð,
ïóñòü V={v
1
, v
2
, v
3
}, òîãäà V&V={[v
1
, v
1
], [v
1
, v
2
], [v
1
, v
3
], [v
2
, v
2
],
[v
2
, v
3
], [v
3
, v
3
]}.
Ñïðàâåäëèâû îòíîøåíèÿ: A∩B⊆A, A∩B⊆B, A⊆A∪B, B⊆A∪B.
Íàïðèìåð, åñëè A⊆B, B⊆C, òî A⊆C, ïîýòîìó èç ïðèâåäåííûõ âûøå
ñîîòíîøåíèé ñëåäóåò, ÷òî A∩B⊆A∪B.
Ñïðàâåäëèâû òàêæå ôîðìóëû äèñòðèáóòèâíîñòè:
(A∪B)∩C=(A∩B)∪(B∩C), (A∩B)∪C=(A∪C)∩(B∪C).
Ðàâåíñòâî ìíîæåñòâ îïåðàöèÿ =.
A=B ñïðàâåäëèâî òîãäà è òîëüêî òîãäà, êîãäà A⊆B è A⊆B.

Страницы