Дискретная математика

ДИСКРЕТНАЯ
МАТЕМАТИКА

С.А. Канцедал

Допущено Министерством образования и науки Российской Федерации

в качестве учебного пособия для студентов учреждений

среднего профессионального образования

УЧЕБНОЕ ПОСОБИЕ

Москва 

ИД «ФОРУМ» — ИНФРА-М

2019

УДК 51(075.32) 
ББК 22.176я723
 
К19

Канцедал С.А.

К19  
Дискретная математика : учеб. пособие / С.А. Канцедал. — М. : 

ИД «ФОРУМ» : ИНФРА-М, 2019. — 222 с. — (Среднее профессиональное образование).

ISBN 978-5-8199-0719-1 (ИД «ФОРУМ»)
ISBN 978-5-16-013446-8 (ИНФРА-М, print)
ISBN 978-5-16-104039-3 (ИНФРА-М, online)

В учебном пособии на элементарном уровне изложены традиционные 

разделы дискретной математики и содержится глава «Экстремальные задачи», где на примерах показано применение ее основ.

Предназначено для студентов средних специальных учебных заведе
ний, а также может быть рекомендовано студентам вузов.

УДК 51(075.32) 
ББК 22.176я723

Р е ц е н з е н т ы:

В.В. Сенатов — доктор физико-математических наук, профессор 

кафедры теории вероятности Московского государственного университета им. М.В. Ломоносова;

А.В. Панишев — доктор технических наук, профессор, заведующий 

кафедрой информатики и компьютерного моделирования Житомирского государственного технологического университета

ISBN 978-5-8199-0719-1 (ИД «ФОРУМ»)
ISBN 978-5-16-013446-8 (ИНФРА-М, print)
ISBN 978-5-16-104039-3 (ИНФРА-М, online)

© Канцедал С.А., 2016
© ИД «ФОРУМ», 2016

Ìàòåìàòèêà — ýòî íàóêà î êîëè÷åñòâåííûõ îòíîøåíèÿõ
è ïðîñòðàíñòâåííûõ ôîðìàõ äåéñòâèòåëüíîãî ìèðà. Íàóêà ýòà
äðåâíÿÿ, õîòÿ è íå òàê ñòàðà, êàê ñòàðî âñå ÷åëîâå÷åñòâî.
Êîãäà-òî î÷åíü äàâíî, êîãäà ëþäè ñòàëè íóæäàòüñÿ â ïîäñ÷åòå
êîëè÷åñòâ íåêîòîðûõ ïðåäìåòîâ, îíè ïðèäóìàëè ÷èñëà 1, 2, 3, ... .
Ïðè ïîìîùè ýòèõ ÷èñåë îíè è îòðàæàëè òî èëè èíîå êîëè÷åñòâî
ïðåäìåòîâ, íåïîñðåäñòâåííî àáñòðàãèðóÿñü îò ñàìèõ ïðåäìåòîâ.
Ïîçæå óêàçàííûå ÷èñëà áûëè íàçâàíû ÷èñëàìè íàòóðàëüíîãî ðÿäà.
Àðèôìåòè÷åñêèå îïåðàöèè íàä ÷èñëàìè íàòóðàëüíîãî ðÿäà,
è â ïåðâóþ î÷åðåäü âû÷èòàíèå, ïðèâåëè ê íåîáõîäèìîñòè ââåñòè
â îáèõîä ÷èñëà îòðèöàòåëüíûå 1, 2, 3, ... ,à òàêæå ÷èñëî íóëü,
îòîáðàæàþùåå îòñóòñòâèå êîëè÷åñòâà, ò.å., ïðîñòî ãîâîðÿ, îçíà÷àþùåå «íè÷åãî». Ïîëó÷åííàÿ ñîâîêóïíîñòü ÷èñåë íàòóðàëüíîãî
ðÿäà, íóëÿ è ÷èñåë îòðèöàòåëüíûõ áûëà íàçâàíà ìíîæåñòâîì öåëûõ ÷èñåë.
Ïðàêòè÷åñêàÿ íåîáõîäèìîñòü èçìåðÿòü âåëè÷èíû, íàïðèìåð,
äëèíû, âåñà, ïëîùàäè, îáúåìû è ò.ï. ïðèâåëà ê âûðàáîòêå ïîíÿòèÿ ìåðû è åäèíèöû èçìåðåíèÿ. Ïðè ïîìîùè åäèíèöû èçìåðåíèÿ òà èëè èíàÿ âåëè÷èíà óêàçûâàëàñü ÷èñëîì ñîîòâåòñòâóþùèõ
åäèíèö. Îäíàêî íà ïðàêòèêå ýòî ÷èñëî ÷àñòî îêàçûâàëîñü íå öåëûì. Òîãäà ðåøèëè ââåñòè ïîíÿòèå ïðàâèëüíîé äðîáè, êàê ÷àñòè
öåëîé åäèíèöû èçìåðåíèÿ. Â ðåçóëüòàòå îêàçàëîñü âîçìîæíûì
óêàçûâàòü èçìåðÿåìóþ âåëè÷èíó öåëûì êîëè÷åñòâîì åäèíèö èçìåðåíèÿ è êîëè÷åñòâîì ÷àñòåé ýòèõ åäèíèö. Ñîâîêóïíîñòü ïðàâèëüíûõ äðîáåé è öåëûõ ÷èñåë ïîëó÷èëà íàçâàíèå ìíîæåñòâà ðàöèîíàëüíûõ ÷èñåë.
Ââåäåííûé íàáîð ðàöèîíàëüíûõ ÷èñåë áûë âåñüìà øèðîê, îäíàêî ïðàêòè÷åñêè îêàçàëñÿ íåäîñòàòî÷íûì äëÿ âûðàæåíèÿ âñåõ
âåëè÷èí. Íàïðèìåð, íèêàêîå ðàöèîíàëüíîå ÷èñëî íå ïîäõîäèëî
äëÿ âûðàæåíèÿ äëèíû äèàãîíàëè êâàäðàòà ÷åðåç åãî åäèíè÷íóþ
ñòîðîíó. Òàêèì îáðàçîì, ïîíàäîáèëîñü ââåñòè ïîíÿòèå ìíîæåñòâà èððàöèîíàëüíûõ ÷èñåë, êàê ìíîæåñòâà ïðàâèëüíèõ è áåñêîíå÷íûõ äðîáåé.

Âñå âìåñòå ïåðå÷èñëåííûå êëàññû ïîëó÷èëè íàçâàíèå ìíîæåñòâà äåéñòâèòåëüíûõ ÷èñåë, êîòîðîå òåì íå ìåíåå íå ÿâëÿåòñÿ äîñòàòî÷íûì äëÿ îòîáðàæåíèÿ êîëè÷åñòâåííûõ ñâÿçåé ìåæäó âñåìè
îáúåêòàìè, êîòîðûìè îïåðèðóåò ìàòåìàòèêà. Åñòü åùå ÷èñëà
íåäåéñòâèòåëüíûå — êîìïëåêñíûå.
Áåãëûé âçãëÿä íà âîçíèêíîâåíèå ÷èñåë, èçëîæåííûé âûøå,
ñâèäåòåëüñòâóåò î òîì, ÷òî ìàòåìàòèêà íå ïðèíàäëåæèò ê åñòåñòâåííûì íàóêàì, òàêèì, íàïðèìåð, êàê ôèçèêà, áèîëîãèÿ, àñòðîíîìèÿ, ãåîëîãèÿ è äð. Ýòî íàóêà, îñíîâàííàÿ íà àáñòðàêöèè è âîîáðàæåíèè, è îíà, ââîäÿ â åñòåñòâåííûå íàóêè êîëè÷åñòâåííûå
ñâÿçè, îáñëóæèâàåò èõ. Òàêîâà ðîëü ìàòåìàòèêè è â ïðîñòðàíñòâåííûõ, ò.å. ãåîìåòðè÷åñêèõ, ôîðìàõ äåéñòâèòåëüíîãî ìèðà.
Ñîâðåìåííàÿ ìàòåìàòèêà îáúåäèíÿåò ìíîãî ðàçäåëîâ.  ñðåäíåé øêîëå èçó÷àþò àðèôìåòèêó, àëãåáðó, ãåîìåòðèþ è òðèãîíîìåòðèþ. Ïðîãðàììû âûñøèõ ó÷åáíûõ çàâåäåíèé â çàâèñèìîñòè îò
ñïåöèàëèçàöèè èõ âûïóñêíèêîâ ïðåäëàãàþò ðàçëè÷íóþ ãëóáèíó
èçó÷åíèÿ àíàëèòè÷åñêîé ãåîìåòðèè, âûñøåé àëãåáðû, äèôôåðåíöèàëüíîãî è èíòåãðàëüíîãî èñ÷èñëåíèÿ, òåîðèè ÷èñåë, ôóíêöèîíàëüíîãî àíàëèçà, ÷èñëåííûõ ìåòîäîâ àíàëèçà, òîïîëîãèè è äð.
Îäíàêî ïî ñîâðåìåííûì âîççðåíèÿì â îñíîâå âñåõ ìàòåìàòè÷åñêèõ äèñöèïëèí ëåæèò ïîíÿòèå ìíîæåñòâà è îñíîâíûå ïîëîæåíèÿ òåîðèè ìíîæåñòâ, âïåðâûå èçëîæåííûå íåìåöêèì ìàòåìàòèêîì Ã. Êàíòîðîì (1845—1918).
Äèñêðåòíàÿ ìàòåìàòèêà — ýòî ðàçäåë ìàòåìàòèêè, êîòîðûé
îïèðàåòñÿ íà ïîíÿòèå äèñêðåòíîãî ìíîæåñòâà. Ê ýòîìó ðàçäåëó ìû
îòíîñèì ýëåìåíòû òåîðèè êîíå÷íûõ ìíîæåñòâ êàê ôóíäàìåíòà
äèñêðåòíîé ìàòåìàòèêè, òåîðèþ ãðàôîâ êàê íàãëÿäíîå ïðåäñòàâëåíèå äèñêðåòíûõ ìíîæåñòâ, èìåþùóþ øèðîêîå ïðàêòè÷åñêîå
ïðèìåíåíèå êîìáèíàòîðèêó, ýëåìåíòû ìàòåìàòè÷åñêîé ëîãèêè,
âêëþ÷àþùèå áóëåâó àëãåáðó è àëãåáðó âûñêàçûâàíèé, òåîðèþ àëãîðèòìîâ è ýêñòðåìàëüíûå çàäà÷è äèñêðåòíîé ìàòåìàòèêè, ðåçóëüòàòû ðåøåíèÿ êîòîðûõ èìåþò âàæíûå ïðàêòè÷åñêèå ïðèëîæåíèÿ.
Ñ îïðåäåëåííîé ñòåïåíüþ ïîëíîòû óêàçàííûå ðàçäåëû äèñêðåòíîé ìàòåìàòèêè èçëîæåíû â äàííîì ó÷åáíîì ïîñîáèè. Îíî
ïðåäíàçíà÷åíî äëÿ ó÷àùèõñÿ ñðåäíèõ ñïåöèàëüíûõ çàâåäåíèé,
îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòÿì: 2202 — àâòîìàòèçèðîâàííûå
ñèñòåìû îáðàáîòêè èíôîðìàöèè è óïðàâëåíèÿ, 2203 — ïðîãðàììíîå îáåñïå÷åíèå âû÷èñëèòåëüíîé òåõíèêè è àâòîìàòèçèðîâàííûõ
ñèñòåì.

4
Ââåäåíèå

Ïîíÿòèå ìíîæåñòâà ÿâëÿåòñÿ áàçèñîì ñîâðåìåííîé ìàòåìàòèêè, òåîðèÿ ìíîæåñòâ — åå ôóíäàìåíò.
Îïðåäåëåíèå 1.1. Ìíîæåñòâî — ýòî ñîâîêóïíîñòü âïîëíå îïðåäåëå ííûõè ðàçëè÷èìûõ ìåæäó ñîáîé îáúåêòîâ ëþáîé ïðèðîäû,
ìûñëèìûõ êàê åäèíîå öåëîå.
Ãëàâíîå â ýòîì îïðåäåëåíèè òî, ÷òî íåêîòîðàÿ ñîâîêóïíîñòü
(ñîáðàíèå) îáúåêòîâ ðàññìàòðèâàåòñÿ êàê åäèíîå öåëîå. Â ýòó ñîâîêóïíîñòü ìîãóò âõîäèòü êàê ðåàëüíî ñóùåñòâóþùèå îáúåêòû,
òàê è âîîáðàæàåìûå. Íàïðèìåð, ìîæíî îïðåäåëèòü ìíîæåñòâî
ñòóäåíòîâ äàííîãî óíèâåðñèòåòà, ìíîæåñòâî åãî ïðåïîäàâàòåëåé,
ìíîæåñòâî àóäèòîðèé, ìíîæåñòâî ó÷åáíèêîâ, êîòîðûìè ïîëüçóþòñÿ ñòóäåíòû, ìíîæåñòâî àâòîìîáèëåé äàííîãî ãîðîäà, ìíîæåñòâî çâåçä Ñîëíå÷íîé ãàëàêòèêè, ìíîæåñòâî ïåñ÷èíîê íà áåðåãó
ìîðÿ è ò.ä.
Âñå ýòî — ðåàëüíî ñóùåñòâóþùèå ìíîæåñòâà. Âîîáðàæàåìûå
ìíîæåñòâà, ñ êîòîðûìè ìû áóäåì èìåòü äåëî, — ýòî îáúåêòû
ìàòåìàòèêè. Ìîæíî ïðèâåñòè òàêèå ïðèìåðû ýòèõ ìíîæåñòâ:
ìíîæåñòâà íàòóðàëüíûõ, öåëûõ, ðàöèîíàëüíûõ, äåéñòâèòåëüíûõ è êîìïëåêñíûõ ÷èñåë, ìíîæåñòâî òî÷åê ïëîñêîñòè ïëîùàäüþ 1 ñì 1 ñì, ìíîæåñòâî êðèâûõ, ïðîõîäÿùèõ ÷åðåç äàííóþ
òî÷êó ïðÿìîé, ìíîæåñòâî îêðóæíîñòåé äèàìåòðîì ìåíüøå 1 ìì
ñ öåíòðîì â îäíîé òî÷êå ïëîñêîñòè. È ýòîò ïåðå÷åíü ëåãêî ïðîäîëæèòü.
Ëþáîå ìíîæåñòâî ñîñòîèò èç åãî ýëåìåíòîâ. Îíî ñ÷èòàåòñÿ çàäàííûì, åñëè èçâåñòíû ýòè ýëåìåíòû. Ïîýòîìó òåðìèí «âïîëíå
îïðåäåëåííûõ è ðàçëè÷èìûõ ìåæäó ñîáîé», ôèãóðèðóþùèé â îïðåäåëåíèè ìíîæåñòâà, ñëåäóåò ïîíèìàòü êàê òî, ÷òî äëÿ ëþáûõ
äâóõ ýëåìåíòîâ ìíîæåñòâà ìîæíî ñêàçàòü, ðàçëè÷èìû îíè èëè
îäèíàêîâû è ÿâëÿåòñÿ ëè êîíêðåòíûé ïðåäìåò ýëåìåíòîì ìíîæåñòâà.

Ìíîæåñòâî ïðèíÿòî çàäàâàòü äâîÿêî: ëèáî ïåðå÷èñëåíèåì åãî
ýëåìåíòîâ, êîòîðûå çàïèñûâàþòñÿ â ôèãóðíûõ ñêîáêàõ, ëèáî ñïåöèàëüíûì ïðàâèëîì, ïî êîòîðîìó ìîæíî îòíåñòè ýëåìåíò ê ìíîæåñòâó. Ñàìî ìíîæåñòâî ïðè ýòîì îáîçíà÷àåòñÿ ïðîïèñíîé
(áîëüøîé) áóêâîé ðóññêîãî èëè ëàòèíñêîãî àëôàâèòà.
Âîò ïðèìåðû çàïèñè ìíîæåñòâ ïåðâûì ñïîñîáîì:
A = {à, á, â} — òðè íà÷àëüíûå áóêâû ðóññêîãî àëôàâèòà;
C = {0, 1, 2, 3, ... ,9} — öèôðû äåñÿòè÷íîé ñèñòåìû ñ÷èñëåíèÿ;
 = {0, 1} — öèôðû äâîè÷íîé ñèñòåìû ñ÷èñëåíèÿ;
D = {0, 1} — çíà÷åíèÿ êîðíåé óðàâíåíèÿ x
x
2
0
;
N = {1, 2, 3, ... } — íàòóðàëüíûå ÷èñëà;
M = {2, 4, 6, ... } — ÷åòíûå íàòóðàëüíûå ÷èñëà;
L = {0, 1, 1, 2, 2, ... } — öåëûå ÷èñëà;
K = {a, b, c, d, t, f, ... ,x, y, z} — áóêâû ëàòèíñêîãî àëôàâèòà.
Ïðè âòîðîì ñïîñîáå ìíîæåñòâî çàäàåòñÿ òàê: X
x P x
{
( )}. Ýòî
îçíà÷àåò, ÷òî Õ — ìíîæåñòâî âñåõ ýëåìåíòîâ õ òàêèõ, ÷òî âûñêàçûâàíèå Ð(õ) èñòèííî. Íàïðèìåð, Y
y
y
{
}
1
10 — ìíîæåñòâî
çíà÷åíèé ó èç èíòåðâàëà [1,10]; I
ii
{ }, i — öèôðà äåñÿòè÷íîé ñèñòåìû ñ÷èñëåíèÿ — ìíîæåñòâî äåñÿòè÷íûõ öèôð 0, 1, 2, ... , 9;
X
x x
{
}, õ — äåéñòâèòåëüíûé êîðåíü óðàâíåíèÿ x
x
2
2
0
—
ìíîæåñòâî äåéñòâèòåëüíûõ êîðíåé óêàçàííîãî óðàâíåíèÿ.
Çàïèñü ìíîæåñòâà ïåðå÷èñëåíèåì åãî ýëåìåíòîâ õàðàêòåðíà
äëÿ ìíîæåñòâ ñ íåáîëüøèì êîëè÷åñòâîì ýëåìåíòîâ. Âòîðîé ñïîñîá çàäàíèÿ áîëåå îáùèé è ìîæåò áûòü èñïîëüçîâàí âñåãäà.
Òîò ôàêò, ÷òî íåêîòîðûé ýëåìåíò õ ïðèíàäëåæèò ìíîæåñòâó
Õ, çàïèñûâàþò òàê: x
X
, ãäå — òàê íàçûâàåìûé êâàíòîð ïðèíàäëåæíîñòè, çàìåíÿþùèé ñëîâî «âõîäèòü». Åñëè æå ýëåìåíò õ íå
ïðèíàäëåæèò ìíîæåñòâó Õ, òî ïðèìåíÿåòñÿ çàïèñü x
X
.
Ïóñòü çàäàíî ÷èñëîâîå ìíîæåñòâî X
x x
x
{
}
1
2
è
. Ýòî
ìíîæåñòâî íå ñîäåðæèò íèêàêèõ ýëåìåíòîâ, òàê êàê íåò ÷èñåë,
êîòîðûå áû îäíîâðåìåííî áûëè áîëüøå 2 è ìåíüøå 1. Òàêîå ìíîæåñòâî íàçûâàåòñÿ ïóñòûì è îáîçíà÷àåòñÿ çíàêîì .
Òàêèì îáðàçîì, X
x x
x
{
}
1
2
è
, X
x x
x
x
{
}
. Îäíàêî ìíîæåñòâî X { }
0
, ïîñêîëüêó ýòî ìíîæåñòâî ñîäåðæèò
îäèí ýëåìåíò, à èìåííî ÷èñëî 0. Ïóñòîå ìíîæåñòâî { }
0, òàê
êàê — ìíîæåñòâî, à 0 ìíîæåñòâîì íå ÿâëÿåòñÿ ïî îáîçíà÷åíèþ.
Äàëåå { }
, ïîñêîëüêó ìíîæåñòâî { }
ñîäåðæèò îäèí ýëåìåíò,
à èìåííî ïóñòîå ìíîæåñòâî . Ïðè ýòîì ëþáîå ìíîæåñòâî À âñåãäà ñîäåðæèò ïóñòîå ìíîæåñòâî .

6
Ãëàâà 1. Ìíîæåñòâà, îòíîøåíèÿ, ôóíêöèè

Ýëåìåíòû ìíîæåñòâà ìîãóò áûòü çàïèñàíû â ëþáîì ïîðÿäêå.
Íàïðèìåð, {1, 2, 3} è {3, 2, 1} — îäíî è òîæå ìíîæåñòâî, ñîäåðæàùåå òðè ýëåìåíòà.
Îïðåäåëåíèå 2.1. Äâà ìíîæåñòâà ðàâíû, êîãäà îíè ñîñòîÿò èç
îäíèõ è òåõ æå ýëåìåíòîâ.
Ìíîæåñòâà A = {1, 2, 3}, B = {3, 1, 2}, C = {1, 2, 3, 3} — ðàâíû.
Ìíîæåñòâî Ñ åñòü, â ñóùíîñòè, ìíîæåñòâî À, òîëüêî â íåì ýëåìåíò 3 çàïèñàí äâàæäû, ò.å. äâå òðîéêè â íåì íåðàçëè÷èìû. Ìíîæåñòâà A = {1, 2}, B = {1, 2, 3} – íå ðàâíû.
Îïðåäåëåíèå 3.1. Ñåìåéñòâîì ìíîæåñòâ íàçûâàåòñÿ ìíîæåñòâî, ýëåìåíòû êîòîðîãî ñàìè ÿâëÿþòñÿ ìíîæåñòâàìè.
Íàïðèìåð, A = {{}, {1, 2}, {3, 4, 5}} — ñ ìåéñòâî,ñîñòîÿùåå èç
òðåõ ìíîæåñòâ. Î÷åâèäíî, ÷òî 2
1 2 3
X
{ , , } è â òî æå âðåìÿ
{ ,
}
{{ , , }, { , }, ,
}
1 2
1 2 3
1 3
1 2
X
, òàê êàê ñðåäè ýëåìåíòîâ ñåìåéñòâà Õ
íåò ìíîæåñòâà {1, 2}.
Îïðåäåëåíèå 4.1. Åñëè À è Â — ìíîæåñòâà, òî ãîâîðÿò, ÷òî
ìíîæåñòâî À ñîäåðæèòñÿ â  èëè âêëþ÷åíî â ìíîæåñòâî  è ïèøóò A
B
â òîì è òîëüêî â òîì ñëó÷àå, åñëè êàæäûé ýëåìåíò ìíîæåñòâà À ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Â.
Ìíîæåñòâî À â ýòîì ñëó÷àå íàçûâàåòñÿ ïîäìíîæåñòâîì Â. Êîãäà æå ìíîæåñòâî À ñîäåðæèò òîëüêî ÷àñòü ýëåìåíòîâ ìíîæåñòâà
Â, îíî íàçûâàåòñÿ ñîáñòâåííûì ïîäìíîæåñòâîì ìíîæåñòâà Â è çàïèñûâàåòñÿ òàê: A
B
.
Ïóñòü
çàäàíû
ìíîæåñòâà
A
a b c
{
}
, ,
,
B
a b c
{ , , },
C
a b c d e
{ , , ,
, }, òîãäà A
B
, A
C
, B
C
. Ïóñòü X
x
x
{
}
1
2 ,

Y
y
y
{
}
1
2 , Z
z
z
{
}
0
3 , òîãäà X
Y
, X
Z
,Y
Z
. È åñëè
N {{ ,
}}
1 2 , M {{ ,
}}
1 2 , P {{ ,
}, { , , }}
1 2
1 2 3 , òîãäà N
M
, N
P
,
M
P
.
Îñíîâíûå
ñâîéñòâà
âêëþ÷åíèÿ
ñëåäóþùèå:
X
X
;
åñëè
X
Y
, à Y
Z
, òî X
Z
; åñëè X
Y
è Y
X
, òî X
Y
.
Îïðåäåëåíèå 5.1. Êàæäîå íåïóñòîå ïîäìíîæåñòâî A èìååò
ïî êðàéíåé ìåðå äâà ðàçëè÷íûõ ïîäìíîæåñòâà: ñàìî ìíîæåñòâî À
è ïóñòîå ìíîæåñòâî . Êðîìå òîãî, êàæäûé ýëåìåíò ìíîæåñòâà À
îïðåäåëÿåò íåêîòîðîå åãî ïîäìíîæåñòâî. Íàïðèìåð, åñëè a
A
,
òî { }
a
A
.
Îïðåäåëåíèå 6.1. Ñåìåéñòâî âñåõ ïîäìíîæåñòâ äàííîãî À íàçûâàåòñÿ ìíîæåñòâîì-ñòåïåíüþ ìíîæåñòâà À è îáîçíà÷àåòñÿ Ð(À).
Íàïðèìåð, åñëè A {
}
1, 2, 3 , òî P(A) {A, , {1}, {2}, {3}, {1, 2},
{1, 3}, {2, 3}}.

1.1. Ìíîæåñòâà
7

Òî, ÷òî A äîêàçûâàåòñÿ ïðîñòî. Ïðåäïîëîæèì, ÷òî íå
âêëþ÷åíî â À, ò.å. A. Ýòî ìîæåò áûòü òîëüêî â òîì ñëó÷àå, êîãäà ñóùåñòâóåò íåêîòîðûé ýëåìåíò A , íå ÿâëÿþùèéñÿ ýëåìåíòîì ìíîæåñòâà À. Íî ýòî íåâîçìîæíî, òàê êàê ìíîæåñòâî íå
èìååò ýëåìåíòîâ, îíî ïóñòîå. Çíà÷èò A è, ñëåäîâàòåëüíî,
A ëîæíî. Òàêèì îáðàçîì, A.
Íà ïðàêòèêå âåñüìà ÷àñòî èñïîëüçóþòñÿ èíäåêñèðîâàííûå
ìíîæåñòâà. Íàïðèìåð, çàïèñü X
x i
n
i
{
, , ...,
}
1 2
îçíà÷àåò, ÷òî
Õ — ìíîæåñòâî, ñîñòîÿùåå èç ýëåìåíòîâ x1, x 2, ... ,xi ,..., x n . Ïðè
ýòîì I
ii
n
{
, , ...,
}
1 2
— èíäåêñíîå ìíîæåñòâî.
Ðàçëè÷àþò ìíîæåñòâà êîíå÷íûå è áåñêîíå÷íûå.
Îïðåäåëåíèå 7.1. Ìíîæåñòâî íàçûâàåòñÿ êîíå÷íûì, åñëè êîëè÷åñòâî åãî ýëåìåíòîâ ìîæåò áûòü âûðàæåíî íåêîòîðûì ïîëîæèòåëüíûì ÷èñëîì.
Ïðè ýòîì ñîâåðøåííî íåâàæíî, èçâåñòíî ýòî ÷èñëî èëè íåò.
Âàæåí ëèøü ôàêò ñóùåñòâîâàíèÿ òàêîãî ÷èñëà.  êà÷åñòâå ïðèìåðîâ êîíå÷íûõ ìíîæåñòâ ìîæíî ïðèâåñòè òàêèå: ìíîæåñòâî áóêâ
ðóññêîãî àëôàâèòà, ìíîæåñòâî ñòðàíèö äàííîé êíèãè, ìíîæåñòâî
äîìîâ íåêîòîðîãî ïîñåëêà, ìíîæåñòâî ï÷åë â äàííîì óëüå, ìíîæåñòâî ñòóäåíòîâ è ñòóëüåâ äàííîé àóäèòîðèè. Ýòîò ñïèñîê, áåçóñëîâíî, ìîæíî ïðîäîëæàòü. Äëÿ êîíå÷íîãî ìíîæåñòâà À, ñîäåðæàùåãî n ýëåìåíòîâ, åãî ìíîæåñòâî-ñòåïåíü P(A) ðàâíà 2 n .
Áåñêîíå÷íûå ìíîæåñòâà — ýòî òîæå îáúåêòû ìàòåìàòèêè.
Áåñêîíå÷íû ìíîæåñòâà íàòóðàëüíûõ, öåëûõ, ðàöèîíàëüíûõ, äåéñòâèòåëüíûõ è êîìïëåêñíûõ ÷èñåë. Áåñêîíå÷íî ìíîæåñòâî âñåõ
òî÷åê ïëîñêîñòè, ìíîæåñòâî âñåõ òî÷åê ïðÿìîé, äëèíîé, íàïðèìåð, 1 ìì, ìíîæåñòâî âñåõ íåïðåðûâíûõ ôóíêöèé, ìíîæåñòâî
ïðÿìûõ, ïåðåñåêàþùèõñÿ â îäíîé òî÷êå è ò.ä.
Äèñêðåòíàÿ èëè, êàê ÷àñòî ãîâîðÿò, êîíå÷íàÿ ìàòåìàòèêà îïåðèðóåò ñ êîíå÷íûìè ìíîæåñòâàìè, ò.å. ñ ìíîæåñòâàìè, ýëåìåíòû
êîòîðûõ ìîæíî ñîñ÷èòàòü.
Áåçóñëîâíî, äèñêðåòíîñòü (ïðåðûâíîñòü) áîëåå ñâîéñòâåííà
îêðóæàþùåìó íàñ ìèðó, à ïîíÿòèÿ áåñêîíå÷íîñòè, íåïðåðûâíîñòè, ïðåäåëà, êîòîðûìè îïåðèðóåò êîíòèíóàëüíàÿ ìàòåìàòèêà,
ââåäåíû ñïåöèàëüíî äëÿ óïðîùåíèÿ èçó÷åíèÿ ÿâëåíèé, êîòîðûå
ëèøü êàæóòñÿ íàì íåïðåðûâíûìè.
Ìíîæåñòâà íàòóðàëüíûõ, öåëûõ, ðàöèîíàëüíûõ è äåéñòâèòåëüíûõ ÷èñåë, à òàêæå ïðîèçâîäíûå îò íèõ óïîðÿäî÷åííûå íàáîðû ÷èñåë (ìíîæåñòâà âåêòîðîâ), êîòîðûå èñïîëüçóþòñÿ êàê â íåïðåðûâíîé, òàê è ÷àñòè÷íî â äèñêðåòíîé ìàòåìàòèêå, ïîëó÷èëè

8
Ãëàâà 1. Ìíîæåñòâà, îòíîøåíèÿ, ôóíêöèè

íàçâàíèå ÷èñëîâûõ (!) ìíîæåñòâ. Îíî ïðîèñõîäèò îò òîãî, ÷òî ëþáîå ÷èñëî èç íàçâàííûõ ìíîæåñòâ èëè óïîðÿäî÷åííûé èõ íàáîð
ìîæíî èçîáðàçèòü òî÷êîé íà ãåîìåòðè÷åñêîé îñè èëè â n-êîîðäèíàòíîì ïðîñòðàíñòâå.
Îäíàêî ñðåäè íàçâàííûõ ÷èñëîâûõ ìíîæåñòâ íåïðåðûâíîñòüþ îáëàäàåò ëèøü ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë èëè ñîîòâåòñòâóþùèé óïîðÿäî÷åííûé èõ íàáîð. Ýòî ïðîÿâëÿåòñÿ â òîì,
÷òî äëÿ ìíîæåñòâà äåéñòâèòåëüíûõ ÷èñåë ìåæäó òî÷êàìè íà ãåîìåòðè÷åñêîé ïðÿìîé, îòîáðàæàþùåé íåêîòîðûå ÷èñëà, íå ñóùåñòâóåò ïðîñâåòà. Ãîâîðÿ ñòðîãî, êàæäîìó ÷èñëó ñîîòâåòñòâóåò òî÷êà íà ãåîìåòðè÷åñêîé ïðÿìîé, è ëþáîé òî÷êå íà ïðÿìîé ñîîòâåòñòâóåò
ñâîå
äåéñòâèòåëüíîå
÷èñëî.
Âñå
îñòàëüíûå
÷èñëîâûå
ìíîæåñòâà ýòèì ñâîéñòâîì âçàèìíîé îäíîçíà÷íîñòè òî÷åê è ÷èñåë íå îáëàäàþò. Äàæå äëÿ âñþäó ïëîòíîãî ìíîæåñòâà ðàöèîíàëüíûõ ÷èñåë, ò.å. òàêîãî, ÷òî äëÿ äâóõ åãî ÷èñåë r
r
1
2
âñåãäà íàéäåò
ñÿ òðåòüå ÷èñëî r
r
1
2
2
, ñóùåñòâóåò òî÷êà — äëèíà äèàãîíàëè êâàä
ðàòà
ñ
åäèíè÷íûìè
ñòîðîíàìè,
êîòîðàÿ
íå
îòîáðàæàåòñÿ
â ðàöèîíàëüíîå ÷èñëî. Ïîýòîìó, îïðåäåëÿÿ äèñêðåòíîå ìíîæåñòâî, ÷àñòî ãîâîðÿò, ÷òî îíî ñîñòîèò èç ìíîæåñòâà èçîëèðîâàííûõ
òî÷åê, îòòàëêèâàÿñü ïðè ýòîì èìåííî îò ãåîìåòðè÷åñêîé èíòåðïðåòàöèè ýëåìåíòîâ ÷èñëîâûõ ìíîæåñòâ.
Ñóùåñòâóåò ðÿä òàê íàçûâàåìûõ òåîðåòèêî-ìíîæåñòâåííûõ
îïåðàöèé íàä ìíîæåñòâàìè.  ðåçóëüòàòå ýòèõ îïåðàöèé ïîëó÷àþòñÿ íîâûå ìíîæåñòâà èç óæå ñóùåñòâóþùèõ. Òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè â íåêîòîðîì îòíîøåíèè àíàëîãè÷íû îïåðàöèÿì ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ öåëûõ ÷èñåë.
Îïðåäåëåíèå 8.1. Îáúåäèíåíèåì (ñóììîé) ìíîæåñòâ À è Â
(îáîçíà÷àåòñÿ A
B
) íàçûâàåòñÿ ìíîæåñòâî òåõ ýëåìåíòîâ, êàæäûé èç êîòîðûõ ïðèíàäëåæèò õîòÿ áû îäíîìó èç ìíîæåñòâ À èëè
Â. Èíûìè ñëîâàìè, A
B
x x
A èëè x
B
{
}. Ïðè ýòîì ïîäðàçóìåâàåòñÿ íåèñêëþ÷àþùèé ñìûñë ñëîâà «èëè».
Ïðè âûïîëíåíèè îïåðàöèè îáúåäèíåíèÿ ìîãóò âñòðåòèòüñÿ
òðè ñëó÷àÿ: 1) A
B
è B
A
, ò.å. A
B
; 2) ìíîæåñòâà èìåþò îáùèå ýëåìåíòû; 3) ìíîæåñòâà íå èìåþò îáùèõ ýëåìåíòîâ.
 ïåðâîì ñëó÷àå îáúåäèíåíèå A
B
— ñóòü îäíè è òå æå ýëåìåíòû
À
è
Â.
Íàïðèìåð,
A {
}
1, 2, 3 ,
B {
}
1, 2, 3 .
Òîãäà
A
B
{
}
1, 2, 3 .

1.1. Ìíîæåñòâà
9

Âî âòîðîì ñëó÷àå òîëüêî ÷àñòü ýëåìåíòîâ îáùàÿ. Íàïðèìåð,
A {
}
1, 2, 3 , B {
}
2, 3, 4, 5, 6 . Òîãäà A
B
{
}
1, 2, 3, 4, 5, 6 . Ïðè
ýòîì îáùèé ýëåìåíò 2 âêëþ÷àåòñÿ â îáúåäèíåíèå A
B
îäèí ðàç.
Òðåòèé
ñëó÷àé
äåìîíñòðèðóåòñÿ
ñëåäóþùèì
ïðèìåðîì
A {
}
1, 2, 3 , B {
}
4, 6, 8 , A
B
{
}
1, 2, 3, 4, 6, 8 .
Ðàññìîòðåííûå
ñëó÷àè
íàãëÿäíî
ïðîèëëþñòðèðîâàíû
íà
ðèñ. 1.1 ïðè ïîìîùè äèàãðàìì Âåííà-Ýéëåðà.
Çàøòðèõîâàííûå îêðóæíîñòè ïðåäñòàâëÿþò ñîáîé îáúåäèíåíèÿ ìíîæåñòâ.

Îáúåäèíåíèåì (ñóììîé) ëþáîé ñîâîêóïíîñòè ìíîæåñòâ A1,
A2, ... ,Ai , ...,An íàçûâàåòñÿ ìíîæåñòâî À òàêèõ ýëåìåíòîâ, êàæäûé
èç êîòîðûõ ïðèíàäëåæèò õîòÿ áû îäíîìó èç ñëàãàåìûõ ìíîæåñòâ.
Îáúåäèíåíèå
ìíîãèõ
ìíîæåñòâ
çàïèñûâàåòñÿ
òàê: A
A
A
1
2
...
Ai
...A
A
n
i
n
i
1
.
Íàïðèìåð,
A
a b
1 { ,
},
A
b c d
2 { , ,
},
A
c d e f
3 { ,
, ,
}. Òîãäà A
A
A
A
a b c d e f
1
2
3
{ , , ,
, ,
}.
Íåòðóäíî âèäåòü, ÷òî A
A
A
. Ýòî îòëè÷àåò ñâîéñòâà òåîðåòèêî-ìíîæåñòâåííîãî ñëîæåíèÿ îò àëãåáðàè÷åñêîãî. Êðîìå òîãî,
A
A
.
Îïðåäåëåíèå 9.1. Ïåðåñå÷åíèåì (ïðîèçâåäåíèåì) ìíîæåñòâ À
è  (îáîçíà÷àåòñÿ A
B
) íàçûâàåòñÿ ìíîæåñòâî òåõ ýëåìåíòîâ, êîòîðûå îäíîâðåìåííî ïðèíàäëåæàò êàê ìíîæåñòâó À, òàê è ìíîæåñòâó Â. Èíûìè ñëîâàìè, A
B
x x
A
x
B
{
}
è
.
Ïðè âûïîëíåíèè îïåðàöèè ïåðåñå÷åíèÿ ìîãóò âñòðåòèòñÿ
òàêæå òðè ñëó÷àÿ: 1) A
B
è B
A
, ò.å. A
B
; 2) ìíîæåñòâà èìåþò
÷àñòü îáùèõ ýëåìåíòîâ; 3) ìíîæåñòâà íå èìåþò îáùèõ ýëåìåíòîâ.
 ïåðâîì ñëó÷àå ïåðåñå÷åíèå A
B
— ýòî ëèáî ýëåìåíòû À,
ëèáî ýëåìåíòû Â, êîòîðûå íåðàçëè÷èìû. Íàïðèìåð, A {
}
1, 2 ,
B {
}
1, 2 . Òîãäà A
B
{
}
1, 2 .
Âî âòîðîì ñëó÷àå ïåðåñå÷åíèåì ÿâëÿþòñÿ îáùèå ýëåìåíòû äëÿ
À è Â. Íàïðèìåð, A {
}
1, 2, 3 , B {
}
2, 3, 4, 5 . Òîãäà A
B
{
}
2, 3 .

10
Ãëàâà 1. Ìíîæåñòâà, îòíîøåíèÿ, ôóíêöèè

ñëó÷àé 1
ñëó÷àé 2
ñëó÷àé 3

À,Â
À
Â
Â
À

Ðèñ. 1.1. Ãðàôè÷åñêàÿ èëëþñòðàöèÿ îïåðàöèè îáúåäèíåíèÿ ìíîæåñòâ