fragment 22656-2

ÑÐÅÄÍÅÅ ÏÐÎÔÅÑÑÈÎÍÀËÜÍÎÅ ÎÁÐÀÇÎÂÀÍÈÅ
М. С. СПИРИНА, П. А. СПИРИН
ДИСКРЕТНАЯ
МАТЕМАТИКА
Учебник
Рекомендовано
Государственным образовательным учреждением
высшего профессионального образования
«Московский государственный технический университет
имени Н. Э. Баумана» в качестве учебника для студентов
образовательных учреждений среднего профессионального
образования, обучающихся по специальностям
«Автоматизированные системы обработки информации
и управления (по отраслям)» и «Программное обеспечение
вычислительной техники и автоматизированных систем»
9е издание, исправленное
ÓÄÊ 51(075.32)
ÁÁÊ 22.176ÿ723
Ñ722
Ð å ö å í ç å í ò û:
àêàäåìèê ÌÀÍ ÂØ, ä-ð òåõí. íàóê, ïðîô. Ï. À. Àðóòþíîâ;
ïðîô. êàôåäðû «Âûñøàÿ ìàòåìàòèêà» Ìîñêîâñêîãî ãîñóäàðñòâåííîãî
òåõíè÷åñêîãî óíèâåðñèòåòà èì. Í. Ý. Áàóìàíà À. Â. Ôèëèíîâñêèé;
ïðåïîäàâàòåëü Ìîñêîâñêîãî ýëåêòðîííî-òåõíîëîãè÷åñêîãî
êîëëåäæà Ò. Á. Àáàøåâà
Ñ722
Ñïèðèíà Ì. Ñ.
Äèñêðåòíàÿ ìàòåìàòèêà : ó÷åáíèê äëÿ ñòóä. ó÷ðåæäåíèé
ñðåä. ïðîô. îáðàçîâàíèÿ / Ì. Ñ. Ñïèðèíà, Ï. À. Ñïèðèí. —
9-å èçä., èñïð. — Ì. : Èçäàòåëüñêèé öåíòð «Àêàäåìèÿ»,
2013. — 368 ñ.
ISBN 978-5-7695-9907-1
Ó÷åáíèê ñîäåðæèò òåîðåòè÷åñêèé ìàòåðèàë ïî òðàäèöèîííûì òåìàì
äèñêðåòíîé ìàòåìàòèêè è íåêîòîðûå âîïðîñû êëàññè÷åñêîé ëîãèêè.  êàæäîé ãëàâå åñòü èñòîðè÷åñêèé ìàòåðèàë, ðàçîáðàííûå çàäà÷è ñ óêàçàíèåì
ìåòîäîâ èõ ðåøåíèé, ñèñòåìà óïðàæíåíèé äëÿ ñàìîñòîÿòåëüíîé ðàáîòû.
Äëÿ ñòóäåíòîâ ó÷ðåæäåíèé ñðåäíåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ,
îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòÿì «Àâòîìàòèçèðîâàííûå ñèñòåìû îáðàáîòêè èíôîðìàöèè è óïðàâëåíèÿ (ïî îòðàñëÿì)» è «Ïðîãðàììíîå îáåñïå÷åíèå âû÷èñëèòåëüíîé òåõíèêè è àâòîìàòèçèðîâàííûõ ñèñòåì».
ÓÄÊ 51(075.32)
ÁÁÊ 22.176ÿ723
Ó÷åáíîå èçäàíèå
Ñïèðèíà Ìàðèíà Ñàâåëüåâíà, Ñïèðèí Ïàâåë Àëåêñååâè÷
Äèñêðåòíàÿ ìàòåìàòèêà
Ó÷åáíèê
Ðåäàêòîð Â. À. Íîâèêîâ. Òåõíè÷åñêèé ðåäàêòîð Î. Ñ. Àëåêñàíäðîâà
Êîìïüþòåðíàÿ âåðñòêà: Ã. Þ. Íèêèòèíà
Êîððåêòîðû Ë. Ñ.Êèììåëü, Ñ. Þ. Ñâèðèäîâà
Èçä. ¹ 109105947. Ïîäïèñàíî â ïå÷àòü 05.03.2013. Ôîðìàò 60½90/16. Ãàðíèòóðà «Òàéìñ».
Ïå÷àòü îôñåòíàÿ. Áóìàãà îôñåòíàÿ ¹ 1. Óñë. ïå÷. ë. 23,0. Òèðàæ 1 500 ýêç. Çàêàç ¹
ÎÎÎ «Èçäàòåëüñêèé öåíòð «Àêàäåìèÿ». www.academia-moscow.ru
129085, Ìîñêâà, ïð-ò Ìèðà, 101Â, ñòð. 1. Òåë./ôàêñ: (495) 648-0507, 616-00-29.
Ñàíèòàðíî-ýïèäåìèîëîãè÷åñêîå çàêëþ÷åíèå ¹ ÐÎÑÑ RU. AE51. H 16067 îò 06.03.2012.
Îòïå÷àòàíî ñ ýëåêòðîííûõ íîñèòåëåé, ïðåäîñòàâëåííûõ èçäàòåëüñòâîì,
â ÎÀÎ «Ñàðàòîâñêèé ïîëèãðàôêîìáèíàò». www.sarpk.ru
410004, ã. Ñàðàòîâ, óë. ×åðíûøåâñêîãî, 59.
Îðèãèíàë-ìàêåò äàííîãî èçäàíèÿ ÿâëÿåòñÿ ñîáñòâåííîñòüþ
Èçäàòåëüñêîãî öåíòðà «Àêàäåìèÿ», è åãî âîñïðîèçâåäåíèå ëþáûì ñïîñîáîì
áåç ñîãëàñèÿ ïðàâîîáëàäàòåëÿ çàïðåùàåòñÿ
ISBN 978-5-7695-9907-1
© Ñïèðèíà Ì. Ñ., Ñïèðèí Ï. À., 2004
© Ñïèðèíà Ì. Ñ., Ñïèðèí Ï. À., 2013, ñ èñïðàâëåíèÿìè
© Îáðàçîâàòåëüíî-èçäàòåëüñêèé öåíòð «Àêàäåìèÿ», 2013
© Îôîðìëåíèå. Èçäàòåëüñêèé öåíòð «Àêàäåìèÿ», 2013
ÏÐÅÄÈÑËÎÂÈÅ
Ìàòåìàòèêà ñòàëà ÷àñòüþ íàøåé êóëüòóðû. ×åëîâåê íå ìîæåò
ñ÷èòàòü ñåáÿ øèðîêîîáðàçîâàííûì, íå èìåÿ ïðåäñòàâëåíèÿ î ñîâðåìåííîé ìàòåìàòèêå, åå ðîëè â ïîâñåäíåâíîé æèçíè, â íàóêå.
Äëÿ ïîíèìàíèÿ èçëàãàåìûõ âîïðîñîâ äîñòàòî÷íî çíàíèé â îáúåìå ïðîãðàììû ñðåäíåé øêîëû. Íåêîòîðûå çàòðóäíåíèÿ ìîæåò
âûçâàòü øèðîêîå èñïîëüçîâàíèå ÿçûêà òåîðèè ìíîæåñòâ. ×òîáû
ýòîãî íå ïðîèçîøëî, èçëîæåíèå êóðñà äèñêðåòíîé ìàòåìàòèêè íà÷èíàåòñÿ èìåííî ñ ýòîé òåìû. Áîëüøîå âíèìàíèå óäåëÿåòñÿ ïðèêëàäíîìó õàðàêòåðó ñîäåðæàíèÿ ýòîãî êóðñà.
Åãî îñíîâó ñîñòàâëÿþò òàêèå ðàçäåëû ìàòåìàòèêè, êàê êîìáèíàòîðíûé àíàëèç, òåîðèÿ ìíîæåñòâ, ýëåìåíòû ìàòåìàòè÷åñêîé è
êëàññè÷åñêîé ëîãèêè.
Äèñêðåòíàÿ ìàòåìàòèêà äëÿ ïðîãðàììèñòîâ îòíîñèòñÿ ê ÷èñëó
îáùåïðîôåññèîíàëüíûõ ïðåäìåòîâ, ôîðìèðóþùèõ áàçîâûé óðîâåíü çíàíèé, íåîáõîäèìûõ äëÿ èçó÷åíèÿ äðóãèõ äèñöèïëèí, òàêèõ,
êàê «Ìàòåìàòè÷åñêàÿ ñòàòèñòèêà», «Àðõèòåêòóðà ÝÂÌ, ñèñòåì è
ñåòåé», «Áàçû äàííûõ», «Êîìïüþòåðíîå ìîäåëèðîâàíèå», «Àâòîìàòèçèðîâàííûå ñèñòåìû», «Òåõíîëîãèÿ ðàçðàáîòêè ïðîãðàììíûõ
ïðîäóêòîâ», «Îñíîâû àëãîðèòìèçàöèè è ïðîãðàììèðîâàíèÿ».
Ïðåäëîæåííûé âàðèàíò ó÷åáíîé äèñöèïëèíû ìîæíî íàçâàòü
«êóðñîì íà ìåæïðåäìåòíîé îñíîâå». Åãî ñîçäàíèå èìåëî öåëüþ
ñôîðìèðîâàòü ïðîôåññèîíàëüíî-ïðèêëàäíóþ êîìïåòåíöèþ áóäóùèõ ïðîãðàììèñòîâ. Äëÿ ýòîãî ìàòåìàòè÷åñêèå çíàíèÿ áûëè
óâÿçàíû ñ îáùåíàó÷íûìè è ó÷òåíû ñîâðåìåííûå ïðåäñòàâëåíèÿ î ôóíêöèîíàëüíîé ðîëè ìàòåìàòè÷åñêîãî îáðàçîâàíèÿ. Êóðñ
ôîðìèðóåò ó ó÷àùèõñÿ ñèñòåìó óìåíèé è íàâûêîâ ñàìîñòîÿòåëüíîãî èçáèðàòåëüíîãî âîñïðèÿòèÿ èíôîðìàöèè è åå ïåðåðàáîòêè. Åãî çàäà÷è — íàó÷èòü ñèñòåìàòèçàöèè, îáîáùåíèþ, ñòðóêòóðèðîâàíèþ çíàíèé, à òàêæå èõ àäåêâàòíîìó ïðèìåíåíèþ êàê
â ïðåäìåòíûõ îáëàñòÿõ, òàê è â ïðàêòè÷åñêîé äåÿòåëüíîñòè. Ñî÷åòàíèå ôóíäàìåíòàëüíûõ òåîðåòè÷åñêèõ çíàíèé ñ èõ ôóíêöèîíàëüíîé íàïðàâëåííîñòüþ ïðèçâàíî ïîêàçàòü ó÷àùèìñÿ èñïîëüçîâàíèå óíèâåðñàëüíîãî ìàòåìàòè÷åñêîãî àïïàðàòà ïðèìåíèòåëüíî ê ðàçëè÷íûì ïðåäìåòíûì îáëàñòÿì è ðàçíîîáðàçíûì âèäàì
äåÿòåëüíîñòè. Àêöåíò äåëàåòñÿ íà çíàêîìñòâî ñ ðàçíûìè ïðèåìàìè ñèñòåìàòèçàöèè çíàíèé è ïðåäñòàâëåíèÿ èíôîðìàöèè â
ñæàòîì âèäå.
3
Ãëàâíîé îñîáåííîñòüþ äàííîé êíèãè ÿâëÿåòñÿ èçáûòî÷íîñòü
èíôîðìàöèè â èçëîæåíèè òåîðåòè÷åñêîãî ìàòåðèàëà è â ïðåäëîæåííîé ñèñòåìå óïðàæíåíèé. Îïûò ïðåïîäàâàíèÿ äèñêðåòíîé ìàòåìàòèêè ñòóäåíòàì Òîëüÿòòèíñêîãî ïîëèòåõíè÷åñêîãî êîëëåäæà ïîêàçûâàåò, ÷òî èíòåðåñ ê ýòîé òåìå ïðèîáðåòàåòñÿ ïîðîé â
ïðîöåññå åå èçó÷åíèÿ. Ñîäåðæàíèå è ÿçûê, áëèçêèå ê ïîçíàâàòåëüíîé ëèòåðàòóðå, ñïîñîáñòâóþò íå òîëüêî îñâîåíèþ ïðîãðàììû, íî è óñòàíîâëåíèþ ñîáñòâåííîãî îòíîøåíèÿ ê ïðèîáðåòåíèþ çíàíèé.
 ó÷åáíèê âêëþ÷åíî áîëüøîå êîëè÷åñòâî ðàçëè÷íûõ çàíèìàòåëüíûõ çàäà÷. Îíè ñïîñîáñòâóþò ïðîáóæäåíèþ ó ÷èòàòåëÿ èíòåðåñà ê ïðîöåññó ïîçíàíèÿ, ê èññëåäîâàòåëüñêîé äåÿòåëüíîñòè. Èçáûòî÷íîñòü òåîðåòè÷åñêîé èíôîðìàöèè è ïðàêòè÷åñêèõ çàäàíèé
îïðàâäàíà ñîâðåìåííîé óñòàíîâêîé íà óâåëè÷åíèå äîëè ñàìîñòîÿòåëüíîé äåÿòåëüíîñòè ñòóäåíòîâ.
Äëÿ ïîääåðæàíèÿ èíòåðåñà ê ïðåäìåòó â êíèãå èñïîëüçîâàíû
ìíîãî÷èñëåííûå èñòîðè÷åñêèå ýêñêóðñû, ñî÷åòàíèå ìàòåìàòè÷åñêîãî ñîäåðæàíèÿ ñ ýëåìåíòàìè êëàññè÷åñêîé ëîãèêè, ïðèìåðû
æèçíåííîãî îïûòà ó÷àùèõñÿ è ò. ä.
Âîïëîùàÿ íà ïðàêòèêå èäåþ ïåðåõîäà îò ìàòåìàòèêè ôóíäàìåíòàëüíîé ê ìàòåìàòèêå ôóíêöèîíàëüíîé, àâòîðû ñ÷èòàþò íåîáõîäèìûì íàéòè êîìïðîìèññ ìåæäó ýòèìè ïðîòèâîïîëîæíûìè
ïîçèöèÿìè.  ó÷åáíèêå íà äîñòàòî÷íîì äëÿ ó÷ðåæäåíèé ñèñòåìû
ñðåäíåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ óðîâíå ïðåäñòàâëåí òåîðåòè÷åñêèé ìàòåðèàë. Ñ äðóãîé ñòîðîíû, ñîâðåìåííóþ ìàòåìàòèêó ÷àñòî îïðåäåëÿþò êàê íàóêó, ðàáîòàþùóþ ñ ãîòîâûìè ìîäåëÿìè è ñîçäàþùóþ íîâûå. Ïîýòîìó àâòîðû ñòðåìèëèñü ïîêàçàòü øèðîêèå âîçìîæíîñòè ïðèìåíåíèÿ ìàòåìàòèêè, åå óíèâåðñàëüíîñòü.
 ñîâðåìåííîì ìèðå ìàòåìàòèêà ñòàíîâèòñÿ ìåòîäîì ìûøëåíèÿ,
è àâòîðû ñ÷èòàëè íåîáõîäèìûì ïîêàçàòü, êàêèì îáðàçîì ñ ïîìîùüþ ÿçûêà ìàòåìàòèêè ôîðìèðóþòñÿ íîâûå ïîíÿòèÿ. Ýòîìó ñïîñîáñòâóåò ââåäåíèå ýëåìåíòîâ êëàññè÷åñêîé ëîãèêè, èçó÷åíèå êîòîðîé ïîìîãàåò óñòàíîâëåíèþ ñâÿçåé ìåæäó ðàçëè÷íûìè è íà ïåðâûé âçãëÿä äàëåêèìè ïîíÿòèÿìè. Ñ ïîìîùüþ áîëüøîãî êðóãà
íåìàòåìàòè÷åñêèõ çàäàíèé ìû ôîðìèðóåì èíòåðåñ ê ïðåäìåòó,
îêàçûâàÿ âëèÿíèå íà èíòåëëåêòóàëüíûé ïîòåíöèàë ÷èòàòåëÿ.
Òåîðåòè÷åñêèé ìàòåðèàë ñîñòîèò èç áîëüøîãî ÷èñëà ôîðìóëèðîâîê âíîâü ââîäèìûõ ïîíÿòèé. Äëÿ îáëåã÷åíèÿ ðàáîòû ñ ó÷åáíèêîì êàæäîå íîâîå ïîíÿòèå âûäåëÿåòñÿ ïîëóæèðíûì øðèôòîì, à
òàêæå âêëþ÷àåòñÿ â ïðåäìåòíûé óêàçàòåëü. Ñîäåðæàòåëüíàÿ ÷àñòü
ìîæåò èçó÷àòüñÿ íà äâóõ óðîâíÿõ ñëîæíîñòè: îáëåã÷åííîì è ãëóáîêîì. ×èòàòåëü ñàì âïðàâå ñäåëàòü âûáîð ãëóáèíû ïîãðóæåíèÿ â
ïðåäìåò äèñêðåòíîé ìàòåìàòèêè.
Ïðàêòè÷åñêèå çàäàíèÿ ïðåäñòàâëåíû â áîëüøîì îáúåìå, íî
èõ èçáûòî÷íîñòü îïðàâäàíà òåìè öåëÿìè, êîòîðûå ïðåñëåäîâàëè
àâòîðû.
4
Ïîäáîð çàäà÷ â óïðàæíåíèÿõ ê ãëàâàì (êðîìå àâòîðñêèõ) îñóùåñòâëÿëñÿ ñ èñïîëüçîâàíèåì ðàçëè÷íûõ èñòî÷íèêîâ, ïðèâåäåííûõ â ñïèñêå ëèòåðàòóðû, à òàêæå ìàòåðèàëîâ æóðíàëà «Êâàíò» è
ãàçåòû «Ìàòåìàòèêà» — åæåíåäåëüíîãî ó÷åáíî-ìåòîäè÷åñêîãî ïðèëîæåíèÿ ê ãàçåòå «Ïåðâîå ñåíòÿáðÿ».
Äëÿ ëó÷øåãî óñâîåíèÿ îïðåäåëåíèé àíàëîãè÷íûõ è ïðîòèâîïîëîæíûõ ïîíÿòèé èñïîëüçóåòñÿ ìåòîä óêðóïíåííûõ äèäàêòè÷åñêèõ
åäèíèö Ï. Ì. è Á. Ï. Ýðäíèåâûõ. Îïðåäåëåíèÿ ïðåäñòàâëåíû â âèäå
äðîáåé: èõ îáùàÿ ÷àñòü çàïèñàíà ëèíåéíî, òîãäà êàê ÷èñëèòåëè è
çíàìåíàòåëè äðîáåé ñîîòâåòñòâóþò îòëè÷èòåëüíûì îñîáåííîñòÿì.
âõîäà
âåðøèíû îðèåíòèðîâàííîÍàïðèìåð, çàïèñü «Ñòåïåíüþ
âûõîäà
ãî ãðàôà íàçûâàåòñÿ ÷èñëî ðåáåð, äëÿ êîòîðûõ ýòà âåðøèíà ÿâëÿêîíöîì
åòñÿ
» ñîäåðæèò äâà ñëåäóþùèõ îïðåäåëåíèÿ:
íà÷àëîì
Ñòåïåíüþ âõîäà âåðøèíû îðèåíòèðîâàííîãî ãðàôà íàçûâàåòñÿ
÷èñëî ðåáåð, äëÿ êîòîðûõ ýòà âåðøèíà ÿâëÿåòñÿ êîíöîì;
Ñòåïåíüþ âûõîäà âåðøèíû îðèåíòèðîâàííîãî ãðàôà íàçûâàåòñÿ ÷èñëî ðåáåð, äëÿ êîòîðûõ ýòà âåðøèíà ÿâëÿåòñÿ íà÷àëîì.
Ñëåäóåò îáðàòèòü âíèìàíèå íà ýïèãðàôû è âîïðîñû äëÿ ðàçìûøëåíèÿ. Îíè ñïîñîáñòâóþò ïðèîáðåòåíèþ ñàìîñòîÿòåëüíîñòè
ìûøëåíèÿ, äàþò âîçìîæíîñòü ôîðìèðîâàòü ñîáñòâåííîå îòíîøåíèå ê èçó÷àåìîìó ïðåäìåòó è îêðóæàþùåé äåéñòâèòåëüíîñòè.
Ïðåäëîæåííûé â ó÷åáíèêå ìàòåðèàë îñíîâàí íà òùàòåëüíîì
àíàëèçå è îòáîðå ñîäåðæàíèÿ ñ ãëóáèííûì ïîíèìàíèåì èñõîäíûõ
öåëåé îáðàçîâàíèÿ. Íàäååìñÿ, ÷òî îí áóäåò ñïîñîáñòâîâàòü ñòàíîâëåíèþ íîâîãî ïîêîëåíèÿ — ïîêîëåíèÿ ìíîãîãðàííûõ, ýðóäèðîâàííûõ, êîìïåòåíòíûõ, òâîð÷åñêè ìûñëÿùèõ ñïåöèàëèñòîâ.
Àâòîðû ïðèíîñÿò áëàãîäàðíîñòü ñòóäåíòàì ôàêóëüòåòà ïðîãðàììèðîâàíèÿ Òîëüÿòòèíñêîãî ïîëèòåõíè÷åñêîãî êîëëåäæà 1998 —
2002 ãã. îáó÷åíèÿ çà ïîìîùü â ñîçäàíèè ýòîãî ó÷åáíèêà.
ÏÅÐÅ×ÅÍÜ ÌÀÒÅÌÀÒÈ×ÅÑÊÈÕ ÑÈÌÂÎËÎÂ
È ÑÎÊÐÀÙÅÍÈÉ
Ñèìâîëû è îáîçíà÷åíèÿ
⊂ — âêëþ÷åíèå;
∈ — ïðèíàäëåæíîñòü ýëåìåíòà ìíîæåñòâó;
∉ — íåïðèíàäëåæíîñòü ýëåìåíòà ìíîæåñòâó;
U — îáúåäèíåíèå ìíîæåñòâ;
I — ïåðåñå÷åíèå ìíîæåñòâ;
∑ — ñóììèðîâàíèå;
× — äåêàðòîâî ïðîèçâåäåíèå;
∀ — êâàíòîð îáùíîñòè;
∃ — êâàíòîð ñóùåñòâîâàíèÿ;
|M |, n(Ì ) — ìîùíîñòü ìíîæåñòâà Ì;
U — óíèâåðñàëüíîå ìíîæåñòâî;
U Ai — îáúåäèíåíèå ìíîæåñòâ Ai ;
i
I Ai — ïåðåñå÷åíèå ìíîæåñòâ Ai ;
i
n
⟨⟩ — êîðòåæ;
deg(A) — ñòåïåíü âåðøèíû A;
n! — ôàêòîðèàë ÷èñëà n, ò. å. ïðîèçâåäåíèå íàòóðàëüíûõ ÷èñåë îò
1 äî n;
∃! — ñóùåñòâóåò åäèíñòâåííûé;
A \B — ðàçíîñòü ìíîæåñòâ A è B;
À ∆  — ñèììåòðè÷åñêàÿ ðàçíîñòü;
−
¬à, à — îòðèöàíèå à;
&, ⋅ , ∧ — êîíúþíêöèÿ;
∨ — äèçúþíêöèÿ;
, ⊕ — ñòðîãàÿ äèçúþíêöèÿ, ñóììà ïî ìîäóëþ äâà;
p — ÷àñòè÷íûé ïîðÿäîê;
∅ — ïóñòîå ìíîæåñòâî;
→ — èìïëèêàöèÿ;
↔, ≡ — ýêâèâàëåíöèÿ;
⇒ — ëîãè÷åñêîå ñëåäîâàíèå;
⇔ — ðàâíîñèëüíîñòü âûñêàçûâàòåëüíûõ ôîðì;
def
= — ðàâíî ïî îïðåäåëåíèþ;
|= — íåïîñðåäñòâåííàÿ âûâîäèìîñòü;
6
|− — âûâîäèìîñòü;
M — äåëåíèå íàöåëî;
2Ì — áóëåàí ìíîæåñòâà M;
Anm — ÷èñëî ðàçìåùåíèé èç n ïî m;
Cnm — ÷èñëî ñî÷åòàíèé èç n ïî m;
Pn — ÷èñëî ïåðåñòàíîâîê èç n ýëåìåíòîâ;
B n — n-ÿ äåêàðòîâà ñòåïåíü ìíîæåñòâà B;
¥ — ìíîæåñòâî íàòóðàëüíûõ ÷èñåë;
¢ — ìíîæåñòâî öåëûõ ÷èñåë;
¤ — ìíîæåñòâî ðàöèîíàëüíûõ ÷èñåë;
¡ — ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë;
£ — ìíîæåñòâî êîìïëåêñíûõ ÷èñåë.
Ñîêðàùåíèÿ
ÄÍÔ — äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà;
ÄÑÑ — äåñÿòè÷íàÿ ñèñòåìà ñ÷èñëåíèÿ;
ÊÍÔ — êîíúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà;
ÌÇÐ — ìëàäøèé çíà÷àùèé ðàçðÿä;
ÌÌÈ — ìåòîä ìàòåìàòè÷åñêîé èíäóêöèè;
ÏÑÑ — ïîçèöèîííàÿ ñèñòåìà ñ÷èñëåíèÿ;
ÑÄÍÔ — ñîâåðøåííàÿ äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà;
ÑÊÍÔ — ñîâåðøåííàÿ êîíúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà.
ÂÂÅÄÅÍÈÅ
¾È â ìèðå íåò òàêèõ âåðøèí,
×òî âçÿòü íåëüçÿ.
Ñðåäè íåõîæåíûõ ïóòåé
Îäèí — ïóñòü ìîé.
Ñðåäè íåâçÿòûõ ðóáåæåé
Îäèí — çà ìíîé.
Â. Âûñîöêèé
? ×òî èçó÷àåò äèñêðåòíàÿ ìàòåìàòèêà?
Ñî øêîëüíîé ñêàìüè íàì èçâåñòíî, ÷òî íåêîòîðûå ÿâëåíèÿ â
îêðóæàþùåì ìèðå ìîæíî îïèñàòü ñ ïîìîùüþ ïîíÿòèé äåéñòâèòåëüíîãî ÷èñëà è íåïðåðûâíîãî òðåõìåðíîãî ïðîñòðàíñòâà. Ìàòåìàòè÷åñêèå ìîäåëè, ñâÿçàííûå ñî ñâîéñòâàìè íåïðåðûâíîñòè èçó÷àåìûõ îáúåêòîâ, ðàñêðûâàþò ìíîãèå çàêîíîìåðíîñòè ìàòåðèàëüíîãî ìèðà.
Äèñêðåòíàÿ ìàòåìàòèêà èëè äèñêðåòíûé àíàëèç — ñðàâíèòåëüíî íîâîå íàïðàâëåíèå â ìàòåìàòèêå, îáúåäèíÿþùåå îòäåëüíûå
åå ðàçäåëû, ðàíåå ñôîðìèðîâàííûå êàê ñàìîñòîÿòåëüíûå òåîðèè.
Ê íèì îòíîñÿòñÿ ìàòåìàòè÷åñêàÿ ëîãèêà è òåîðèè ìíîæåñòâ, ãðàôîâ, êîäèðîâàíèÿ, àâòîìàòîâ.
×òî îáùåãî ìåæäó ýòèìè, ðàçëè÷íûìè íà ïåðâûé âçãëÿä, òåîðèÿìè?
Äèñêðåòíîé ìàòåìàòèêîé íàçûâàþò ñîâîêóïíîñòü ìàòåìàòè÷åñêèõ äèñöèïëèí, èçó÷àþùèõ ñâîéñòâà àáñòðàêòíûõ äèñêðåòíûõ
îáúåêòîâ, ò. å. ñâîéñòâà ìàòåìàòè÷åñêèõ ìîäåëåé îáúåêòîâ, ïðîöåññîâ, çàâèñèìîñòåé, ñóùåñòâóþùèõ â ðåàëüíîì ìèðå, êîòîðûìè îïåðèðóþò â ðàçëè÷íûõ îáëàñòÿõ çíàíèé. Òàêèì îáðàçîì, äèñêðåòíûé àíàëèç — ñàìîñòîÿòåëüíûé ðàçäåë ñîâðåìåííîé ìàòåìàòèêè, èçó÷àþùèé ñâîéñòâà ðàçëè÷íûõ ñòðóêòóð, èìåþùèõ êîíå÷íûé õàðàêòåð. Îíè ìîãóò âîçíèêàòü êàê â ñàìîé ìàòåìàòèêå,
òàê è â åå ïðèëîæåíèÿõ. Ê èõ ÷èñëó ïðèíÿòî îòíîñèòü îáúåêòû,
èìåþùèå ïðåðûâíûé (äèñêðåòíûé) õàðàêòåð â îòëè÷èå îò îáúåêòîâ, èçó÷àåìûõ êëàññè÷åñêîé ìàòåìàòèêîé è íîñÿùèõ íåïðåðûâíûé õàðàêòåð.
Ìàòåìàòè÷åñêèé àïïàðàò äèñêðåòíîãî àíàëèçà ìîæíî îïðåäåëèòü êàê âçàèìîñâÿçàííóþ ñîâîêóïíîñòü ÿçûêà, ìîäåëåé è ìåòîäîâ ìàòåìàòèêè, îðèåíòèðîâàííóþ íà ðåøåíèå ðàçëè÷íûõ, â òîì
÷èñëå èíæåíåðíûõ, çàäà÷. Èñïîëüçîâàíèå òàêîãî àïïàðàòà ñâÿçàíî ñ õàðàêòåðîì èññëåäóåìûõ ìîäåëåé — îòäåëüíûõ ýëåìåíòîâ
àáñòðàêòíûõ ìíîæåñòâ, îòäåëüíûõ ÷èñåë â ðàçëè÷íûõ ñèñòåìàõ
ñ÷èñëåíèÿ, îòäåëüíûõ çíà÷åíèé 0 è 1 (èñòèíà è ëîæü), áóëåâûõ
ôóíêöèé è ò. ä.
8
Âîîáùå ãîâîðÿ, äåëåíèå ìàòåìàòèêè íà äèñêðåòíóþ è êëàññè÷åñêóþ äîñòàòî÷íî óñëîâíî. Íàïðèìåð, àïïàðàò òåîðèè ìíîæåñòâ è
òåîðèè ãðàôîâ èñïîëüçóåòñÿ ïðè èçó÷åíèè íå òîëüêî äèñêðåòíûõ,
íî è íåïðåðûâíûõ îáúåêòîâ. Ñ äðóãîé ñòîðîíû, ñàìà äèñêðåòíàÿ
ìàòåìàòèêà èñïîëüçóåò ñðåäñòâà, ðàçðàáîòàííûå â êëàññè÷åñêîé
ìàòåìàòèêå. Îäíàêî õàðàêòåð îáúåêòîâ, èññëåäóåìûõ äèñêðåòíîé
ìàòåìàòèêîé, íàñòîëüêî ñâîåîáðàçåí, ÷òî ìåòîäîâ êëàññè÷åñêîé
ìàòåìàòèêè íå âñåãäà äîñòàòî÷íî äëÿ èõ èçó÷åíèÿ. Ïîýòîìó òå ñïåöèôè÷åñêèå ìåòîäû, êîòîðûå ïðèìåíÿþòñÿ äëÿ î÷åíü øèðîêîãî
êëàññà êîíå÷íûõ (ôèíèòíûõ) äèñêðåòíûõ îáúåêòîâ, è áûëè îáúåäèíåíû â îáùåå íàïðàâëåíèå — äèñêðåòíóþ ìàòåìàòèêó.
Íåñìîòðÿ íà òî ÷òî îòäåëüíûå íàïðàâëåíèÿ äèñêðåòíîé ìàòåìàòèêè çàðîäèëèñü â ãëóáîêîé äðåâíîñòè è ñîâåðøåíñòâîâàëèñü
ïàðàëëåëüíî ñ êëàññè÷åñêîé ìàòåìàòèêîé, íàèáîëåå èíòåíñèâíî äèñêðåòíàÿ ìàòåìàòèêà ñòàëà ðàçâèâàòüñÿ â ïîñëåäíåå ñòîëåòèå.  íàñòîÿùåå âðåìÿ çíàíèå äèñêðåòíîé ìàòåìàòèêè íåîáõîäèìî ñïåöèàëèñòàì â ðàçëè÷íûõ îáëàñòÿõ äåÿòåëüíîñòè.
XXI â. íàçûâàþò âåêîì èíôîðìàòèçàöèè, êîãäà îñíîâíîé îáúåì
èíôîðìàöèè õðàíèòñÿ â ïàìÿòè ÝÂÌ. Ëþáîìó ÷åëîâåêó, ñòðåìÿùåìóñÿ åþ âîñïîëüçîâàòüñÿ, íåîáõîäèìî îñâîèòü àçû «áåçáóìàæíîé èíôîðìàòèêè». Ïðèìåíåíèå ÝÂÌ äëÿ êîìïëåêñíîé àâòîìàòèçàöèè èíôîðìàöèîííîé äåÿòåëüíîñòè ïðèíöèïèàëüíî èçìåíèëî õàðàêòåð âçàèìîîòíîøåíèé ÷åëîâåêà è ìàøèíû. Åñëè ðàíüøå
êîìïüþòåð îñâàèâàëè òîëüêî òå, êòî íåïîñðåäñòâåííî åãî îáñëóæèâàë: ïðîãðàììèñòû, ýëåêòðîíùèêè, îïåðàòîðû, òî â XXI â. áåç
ìàøèííîé îáðàáîòêè èíôîðìàöèè íå îáîéäåòñÿ íè îäíà îòðàñëü
äåÿòåëüíîñòè.
Ñòèìóëîì äëÿ ðàçâèòèÿ ìíîãèõ íàïðàâëåíèé äèñêðåòíîé ìàòåìàòèêè ÿâèëèñü çàïðîñû òåîðåòè÷åñêîé êèáåðíåòèêè, íåïîñðåäñòâåííî ñâÿçàííîé ñ ðàçâèòèåì ÝÂÌ.
Òåîðåòè÷åñêàÿ êèáåðíåòèêà çàíèìàåòñÿ èçó÷åíèåì ðàçíîîáðàçíûõ ïðàêòè÷åñêèõ ïðîáëåì ñðåäñòâàìè äèñêðåòíîé ìàòåìàòèêè:
ðàñòóùèé ïîòîê èíôîðìàöèè è ïðîáëåìû åå ïåðåäà÷è, îáðàáîòêè è õðàíåíèÿ ïðèâåëè ê âîçíèêíîâåíèþ è ðàçâèòèþ òåîðèè
êîäèðîâàíèÿ;
ðàçëè÷íûå ýêîíîìè÷åñêèå çàäà÷è, çàäà÷è ýëåêòðîòåõíèêè ñòèìóëèðîâàëè ñîçäàíèå è ðàçâèòèå òåîðèè ãðàôîâ;
ñâÿçü ðåëåéíî-êîíòàêòíûõ ñõåì ñ ôîðìóëàìè àëãåáðû ëîãèêè
è èõ èñïîëüçîâàíèå äëÿ îïèñàíèÿ ôóíêöèîíèðîâàíèÿ àâòîìàòîâ
äàëè íà÷àëî ðàçâèòèþ è ïðèìåíåíèþ ìàòåìàòè÷åñêîé ëîãèêè è
òåîðèè àâòîìàòîâ. Ìàòåìàòè÷åñêàÿ ëîãèêà â øèðîêîì ñìûñëå
èçó÷àåò îñíîâàíèÿ ìàòåìàòèêè, ïðèíöèïû ïîñòðîåíèÿ ìàòåìàòè÷åñêèõ òåîðèé.
Äèñêðåòíàÿ ìàòåìàòèêà èçó÷àåò îáúåêòû, êîòîðûå ïîðîé íå
èìåþò íè ôèçè÷åñêîé, íè ÷èñëîâîé èíòåðïðåòàöèè.  êëàññè÷åñêîé ìàòåìàòèêå õàðàêòåðèñòèêè ðåàëüíûõ îáúåêòîâ ìîæíî ïðåä9
ñòàâèòü â âèäå ÷èñåë, à çàêîíîìåðíîñòè — â âèäå ñîîòíîøåíèé.
 îòëè÷èå îò ðåàëüíûõ õàðàêòåðèñòèêàìè èíôîðìàöèîííûõ îáúåêòîâ ìîãóò ñëóæèòü ïîíÿòèÿ «ñòðóêòóðà», «îòíîøåíèå», «ñâÿçü».
Îáû÷íî îáúåêòû èíôîðìàòèêè ðàññìàòðèâàþò êàê êîìáèíàöèè
íåêîòîðûõ àáñòðàêòíûõ ñèìâîëîâ, íàä êîòîðûìè ïðîèçâîäÿòñÿ
íåêèå ìàíèïóëÿöèè.
 ïîñëåäíåå âðåìÿ ðàçäåë ìàòåìàòèêè, íàçûâàåìûé «Äèñêðåòíûé àíàëèç», âñå ÷àùå ââîäèòñÿ â ïðîãðàììû ïîäãîòîâêè íå òîëüêî
ìàòåìàòèêîâ, èíæåíåðîâ, ïðîãðàììèñòîâ, íî äàæå þðèñòîâ. Èíòåðåñ ê ýòîé äèñöèïëèíå íå ñëó÷àåí, òàê êàê ïîòðåáíîñòü â çíàíèÿõ ýòîé îáëàñòè ìàòåìàòèêè îáúÿñíÿåòñÿ øèðîêèì êðóãîì åå
ïðèìåíåíèÿ: ýëåêòðîíèêà è èíôîðìàòèêà, âîïðîñû îïòèìèçàöèè
è ïðèíÿòèÿ ðåøåíèé.
Âçàèìîñâÿçü äèñêðåòíîé ìàòåìàòèêè ñ äðóãèìè íàóêàìè. Êèáåðíåòè÷åñêèå îáëàñòè èíôîðìàòèêè èñïîëüçóþò â êà÷åñòâå àïïàðàòà ÿçûê êàê ôóíäàìåíòàëüíîé, òàê è ïðèêëàäíîé ìàòåìàòèêè. Îäíàêî íàäî ó÷èòûâàòü, ÷òî ýòè íàóêè ñâÿçàíû ìåæäó ñîáîé è èõ
äåëåíèå óñëîâíî. Êèáåðíåòèêà — íàóêà îá îáùèõ ïðèíöèïàõ óïðàâëåíèÿ â æèâûõ, íåæèâûõ è èñêóññòâåííûõ ñèñòåìàõ. Ðåøàÿ ìíîæåñòâî ðàçíîîáðàçíûõ çàäà÷, êèáåðíåòèêà èìååò îáùèé ñòåðæåíü,
îáùóþ ìåòîäîëîãèþ, â îñíîâå êîòîðîé ëåæèò ïîíÿòèå ñèñòåìû.
Ïîä ñèñòåìîé ïîíèìàþò íåêóþ ñòðóêòóðó, îáúåäèíåíèå íåêîòîðîãî êîëè÷åñòâà îáîñîáëåííûõ ýëåìåíòîâ, ïîä÷èíåííûõ åäèíîé
âçàèìîñâÿçè, îïðåäåëåííûì îòíîøåíèÿì. Êèáåðíåòèêà ÿâëÿåòñÿ
íàóêîé îá óïðàâëÿåìûõ ñèñòåìàõ ëþáîãî õàðàêòåðà: áèîëîãè÷åñêèõ, ñîöèàëüíûõ, òåõíè÷åñêèõ, ýêîíîìè÷åñêèõ.  ñâÿçè ñ ýòèì â
ðàçëè÷íûõ ñèñòåìàõ âûäåëÿþò òàê íàçûâàåìûé êèáåðíåòè÷åñêèé
ïîäõîä, ñìûñë êîòîðîãî çàêëþ÷àåòñÿ â íàëè÷èè ìåõàíèçìà óïðàâëåíèÿ ýòîé ñèñòåìîé, â ñóùåñòâîâàíèè îáðàòíîé ñâÿçè.
Ìåòîäû, ðàçðàáàòûâàåìûå äèñêðåòíîé ìàòåìàòèêîé, ÷àñòî èñïîëüçóþòñÿ â ðàçëè÷íûõ íàïðàâëåíèÿõ èíôîðìàòèêè. Òàê, òåîðåòè÷åñêàÿ èíôîðìàòèêà (èëè òåîðåòè÷åñêàÿ êèáåðíåòèêà) èñïîëüçóåò ìàòåìàòè÷åñêèå ìåòîäû äëÿ ïîñòðîåíèÿ è èçó÷åíèÿ ìîäåëåé
îáðàáîòêè, ïåðåäà÷è è èñïîëüçîâàíèÿ èíôîðìàöèè. Îáúåêòû åå
èçó÷åíèÿ — äèñêðåòíûå ìíîæåñòâà. Òåîðåòè÷åñêàÿ èíôîðìàòèêà
ÿâëÿåòñÿ êàê ïîñòàâùèêîì çàäà÷, òàê è ïîòðåáèòåëåì ìåòîäîâ
äèñêðåòíîé ìàòåìàòèêè.
Äîñòèæåíèÿ ìàòåìàòè÷åñêîé ëîãèêè èñïîëüçóþòñÿ äëÿ àíàëèçà ïðîöåññîâ ïåðåðàáîòêè èíôîðìàöèè ñ ïîìîùüþ ÝÂÌ. Òåîðèÿ àâòîìàòîâ ðàçðàáàòûâàåò ìåòîäû, ñ ïîìîùüþ êîòîðûõ ìîæíî íà îñíîâå ìîäåëåé ëîãè÷åñêîãî òèïà èçó÷àòü ïðîöåññû, ïðîòåêàþùèå â ñàìîé ìàøèíå âî âðåìÿ åå ðàáîòû. Äëÿ ðàáîòû íà
êîìïüþòåðå èíôîðìàöèþ ïðåäñòàâëÿþò â äèñêðåòíîé ôîðìå,
ïîçâîëÿþùåé ïåðåâîäèòü åå â ïðîãðàììû, ïîíÿòíûå ÝÂÌ.
Òåîðèÿ èíôîðìàöèè èçó÷àåò âèä òåõ ôîðì, â êîòîðûõ èíôîðìàöèÿ ïðåäñòàâëÿåòñÿ â êîìïüþòåðå. Ôîðìàëèçàöèÿ ëþáîé èí10
ôîðìàöèè, ðåàëüíî ñóùåñòâóþùåé â æèâîé è íåæèâîé ïðèðîäå,
ïðîèñõîäèò ÷åðåç êîìïüþòåðíîå ìîäåëèðîâàíèå. Ñèñòåìíûé àíàëèç èçó÷àåò ñòðóêòóðó ðåàëüíûõ îáúåêòîâ è äàåò ñïîñîáû èõ ôîðìàëèçîâàííîãî îïèñàíèÿ. Îáùàÿ òåîðèÿ ñèñòåì êàê ÷àñòü ñèñòåìíîãî àíàëèçà èçó÷àåò ðàçëè÷íûå ïî õàðàêòåðó ñèñòåìû ñ îáùèõ
ïîçèöèé. Òåîðèÿ ìàññîâîãî îáñëóæèâàíèÿ èçó÷àåò øèðîêèé êëàññ
ìîäåëåé ïåðåäà÷è è ïåðåðàáîòêè èíôîðìàöèè â ñèñòåìàõ ìàññîâîãî îáñëóæèâàíèÿ (ÑÌÎ).
 íàñòîÿùåå âðåìÿ íàøëà øèðîêîå ïðèìåíåíèå íàóêà ñåìèîòèêà, êîòîðàÿ èññëåäóåò çíàêîâûå ñèñòåìû ñàìîé ðàçëè÷íîé
ïðèðîäû. ×åòêî ðàçëè÷àÿ ïîíÿòèå çíàêà è çíàêîâîé ñèòóàöèè, ñåìèîòèêà âêëþ÷àåò òàêèå ðàçäåëû, êàê ñèíòàêòèêà (÷òî ñâÿçûâàåò
çíàê), ñåìàíòèêà (÷òî âûðàæàåò çíàê), ñèãìàòèêà (÷òî îáîçíà÷àåò
çíàê) è ïðàãìàòèêà (÷òî äàåò çíàê). Ñèíòàêòè÷åñêèé àñïåêò èíôîðìàöèè, ñâÿçàííûé ñî ñòðóêòóðíûìè è ñòàòèñòè÷åñêèìè îöåíêàìè, â îñíîâíîì ðàññìàòðèâàåòñÿ â èíôîðìàòèêå è âû÷èñëèòåëüíîé òåõíèêå. Ñèãìàòè÷åñêèé àñïåêò ðàññìàòðèâàåò òåîðèÿ ñèãíàëîâ è êîäèðîâàíèÿ. Çíàêîâûå ñèñòåìû áëàãîäàðÿ ñâîåé ãèáêîñòè
ñïîñîáíû îáåñïå÷èòü ðàçíîîáðàçíûå çàïðîñû ïîëüçîâàòåëåé. Ôóíêöèîíàëüíîå åäèíñòâî ñåìàíòèêè è ïðàãìàòèêè èìååò øèðîêèå ïåðñïåêòèâû: ïîÿâëÿåòñÿ âîçìîæíîñòü óñòàíîâëåíèÿ àíàëîãèé ìåæäó
ôóíêöèîíèðîâàíèåì ñèñòåì åñòåñòâåííîãî è èñêóññòâåííîãî ïðîèñõîæäåíèÿ.
ßðêèì ïðèìåðîì âçàèìîäåéñòâèÿ åñòåñòâåííûõ, îáùåñòâåííûõ
è òåõíè÷åñêèõ íàóê ÿâëÿåòñÿ ðàçðàáîòêà ëèíãâèñòè÷åñêîãî îáåñïå÷åíèÿ êîìïüþòåðèçàöèè.
Èìèòàöèîííîå ìîäåëèðîâàíèå — íàóêà, â êîòîðîé ñîçäàþòñÿ è
èñïîëüçóþòñÿ ñïåöèàëüíûå ïðèåìû âîñïðîèçâåäåíèÿ ïðîöåññîâ,
ïðîòåêàþùèõ â ðåàëüíûõ îáúåêòàõ, â òåõ ìîäåëÿõ ýòèõ îáúåêòîâ,
êîòîðûå ðåàëèçóþòñÿ â âû÷èñëèòåëüíûõ ìàøèíàõ.
Òåîðèÿ ïðèíÿòèÿ ðåøåíèé èçó÷àåò îáùèå ñõåìû, èñïîëüçóåìûå
ïðè âûáîðå ðåøåíèÿ èç àëüòåðíàòèâíûõ âîçìîæíîñòåé (â óñëîâèÿõ íåîïðåäåëåííîñòè). Òåîðèÿ èãð èçó÷àåò ìîäåëè, â êîòîðûõ âûáîð ïðîèñõîäèò â óñëîâèÿõ êîíôëèêòà èëè ïðîòèâîáîðñòâà. Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå ðàññìàòðèâàåò ïðîáëåìû ïðèíÿòèÿ
îïòèìàëüíûõ ðåøåíèé ñ ïîìîùüþ ìàòåìàòè÷åñêîãî àïïàðàòà.
Èñêóññòâåííûé èíòåëëåêò — îäíî èç ìîëîäûõ è ïåðñïåêòèâíûõ íàïðàâëåíèé èíôîðìàòèêè, ïîÿâèâøååñÿ âî âòîðîé ïîëîâèíå XX â. íà áàçå âû÷èñëèòåëüíîé òåõíèêè, ìàòåìàòè÷åñêîé ëîãèêè, ïðîãðàììèðîâàíèÿ, ïñèõîëîãèè, ëèíãâèñòèêè è äðóãèõ îòðàñëåé çíàíèé. Îáúåêòàìè åãî èçó÷åíèÿ ÿâëÿþòñÿ ìåæïðåäìåòíûå
ïðîöåäóðû (ìåòàïðîöåäóðû), èñïîëüçóåìûå ïðè ðåøåíèè çàäà÷,
òðàäèöèîííî íàçûâàåìûõ èíòåëëåêòóàëüíûìè. Ïðîíèêàÿ â òàéíû
òâîð÷åñêîé äåÿòåëüíîñòè ëþäåé, èñêóññòâåííûé èíòåëëåêò ñîçäàåò ïðîãðàììíûå è ïðîãðàììíî-àïïàðàòíûå ìîäåëè òàêèõ ìåòàïðîöåäóð.
11
Èíôîðìàöèîííûå ñèñòåìû ïðèìåíÿþòñÿ äëÿ àíàëèçà è ïðîãíîçèðîâàíèÿ ïîòîêà èíôîðìàöèè, èññëåäîâàíèÿ ñïîñîáîâ åå
ïðåäñòàâëåíèÿ, õðàíåíèÿ è èçâëå÷åíèÿ. Àêòóàëüíûì ÿâëÿåòñÿ òàêæå ñîçäàíèå èíôîðìàöèîííî-ïîèñêîâûõ ñèñòåì, ñèñòåì õðàíåíèÿ, îáðàáîòêè ïåðåäà÷è èíôîðìàöèè, â ñîñòàâ êîòîðûõ âõîäÿò
èíôîðìàöèîííûå áàçû äàííûõ, òåðìèíàëû, ñðåäñòâà ñâÿçè. Îïåðàöèîííûå ñèñòåìû ñâÿçàíû ñ ðàçðàáîòêîé è ïðîèçâîäñòâîì êîìïüþòåðîâ.
Ìû ñòîèì íà ïîðîãå èíôîðìàöèîííîé èíäóñòðèàëèçàöèè îáùåñòâà. Îòñþäà âîçíèêàþò ñîöèàëüíûå, ïðàâîâûå, òåõíè÷åñêèå
ïðîáëåìû, òàêèå, íàïðèìåð, êàê íîâûå êîìïüþòåðíûå òåõíîëîãèè îáó÷åíèÿ, àâòîìàòèçèðîâàííûå îáó÷àþùèå ñèñòåìû, àâòîìàòèçèðîâàííûå ðàáî÷èå ìåñòà è äð.
Äëÿ íàñ ïðåäñòàâëÿþò èíòåðåñ âñå ýòè íàïðàâëåíèÿ ñîâðåìåííîé èíôîðìàòèêè. Òåïåðü ìû ñìîæåì îñîçíàòü ìåñòî äèñêðåòíîé
ìàòåìàòèêè â ñèñòåìå çíàíèé, íåîáõîäèìûõ äëÿ òåõ, êòî ñâÿçàë
ñâîþ æèçíü ñ êîìïüþòåðîì.
Äëÿ ïðåäñòàâèòåëåé ìíîãèõ ñïåöèàëüíîñòåé, îñîáåííî äëÿ ïðîãðàììèñòîâ, ñóùåñòâåííîå çíà÷åíèå â áóäóùåé ïðîôåññèîíàëüíîé äåÿòåëüíîñòè èìååò çíàíèå êëàññè÷åñêîé ëîãèêè, òàê êàê îíà
îáðàçóåò ìàòåìàòè÷åñêóþ îñíîâó èíôîðìàòèêè.
Íà çíàíèÿõ çàêîíîâ ëîãèêè áàçèðóþòñÿ ïðèíöèïû àëãîðèòìèçàöèè, êîòîðûå ëåæàò â îñíîâå ïðîãðàììèðîâàíèÿ. Ôóíäàìåíòîì
âñåé âû÷èñëèòåëüíîé òåõíèêè è àâòîìàòèêè ÿâëÿåòñÿ ïðåîáðàçîâàíèå äâîè÷íûõ ñèãíàëîâ, àíàëèç, ïðîåêòèðîâàíèå è èñïîëüçîâàíèå ëîãè÷åñêèõ ñõåì. Îñíîâó ñîâðåìåííîé ìàòåìàòè÷åñêîé ëîãèêè ñîñòàâëÿþò èñ÷èñëåíèå âûñêàçûâàíèé è èñ÷èñëåíèå ïðåäèêàòîâ. Ëþáîé ÿçûê ïðîãðàììèðîâàíèÿ áàçèðóåòñÿ íà èñ÷èñëåíèè
âûñêàçûâàíèé è èñ÷èñëåíèè ïðåäèêàòîâ.  ÷àñòíîñòè, íà ÿçûêå ïðîãðàììèðîâàíèÿ «Ïðîëîã» àíàëèçèðóþòñÿ ðàçëè÷íûå âèäû äåäóêòèâíûõ óìîçàêëþ÷åíèé, âûâîäÿòñÿ äîñòîâåðíûå ñëåäñòâèÿ èç íèõ.
Øèðîêî ïðèìåíÿþòñÿ ëîãè÷åñêèå ìåòîäû äëÿ ïîñòðîåíèÿ áàç äàííûõ. Àêòèâíî èñïîëüçóþòñÿ çíàíèÿ ëîãèêè â ðàçâèòèè ñîâðåìåííûõ íàïðàâëåíèé èíôîðìàöèîííûõ íàóê. Íàïðèìåð, ðÿä ïðîáëåì
èñêóññòâåííîãî èíòåëëåêòà íåâîçìîæíî ðåøèòü áåç çíàíèé îñíîâ
êëàññè÷åñêîé ëîãèêè. Ðàññìîòðèì èõ áîëåå ïîäðîáíî.
Ïðåäñòàâëåíèå çíàíèé — ìåòîäû è ïðèåìû ôîðìàëèçàöèè èíôîðìàöèè èç ðàçëè÷íûõ îáëàñòåé çíàíèé äëÿ èõ õðàíåíèÿ, êëàññèôèêàöèè, îáîáùåíèÿ è ïðèìåíåíèÿ ïðè ðåøåíèè êîíêðåòíûõ
çàäà÷.
Ìîäåëèðîâàíèå ðàññóæäåíèé — èçó÷åíèå è ôîðìàëèçàöèÿ ðàçëè÷íûõ óìîçàêëþ÷åíèé è èõ èñïîëüçîâàíèå ïðè ðåøåíèè çàäà÷
ñðåäñòâàìè ÝÂÌ.
Ìåòîäû äèàëîãîâîãî îáùåíèÿ ÷åëîâåêà è ìàøèíû. Ñïåöèôèêà
ðàáîòû ïðîãðàììèñòîâ çàêëþ÷àåòñÿ â òîì, ÷òî îïïîíåíòîì â äèàëîãå âûñòóïàåò êîìïüþòåð.  íåãî çàëîæåíû ïðîãðàììû, îáðàáà12
òûâàþùèå òîëüêî òî÷íî ñôîðìóëèðîâàííóþ èíôîðìàöèþ.  ïðîöåññå åå îáðàáîòêè âîçíèêàþò äâà âàðèàíòà äèàëîãîâîãî îáùåíèÿ:
• ÝÂÌ ñàìîñòîÿòåëüíî çàäàåò âîïðîñû ïî ïîëó÷åííîé èíôîðìàöèè ñîãëàñíî çàëîæåííîé â íåå ïðîãðàììå;
• êîìïüþòåð çàäàåò âîïðîñû, êîòîðûå çàëîæåíû çàðàíåå â çàãîòîâëåííóþ ïðîãðàììèñòîì ìîäåëü áåñåäû.
 ïðîöåññå äèàëîãîâîãî îáùåíèÿ ïðîãðàììèñò äîëæåí çíàòü âèäû
âîïðîñîâ è îòâåòîâ äëÿ ñîñòàâëåíèÿ ïðîãðàììû, âëàäåòü ïðàâèëàìè ïîñòðîåíèÿ òî÷íûõ, íåïðîòèâîðå÷èâûõ, ëîãè÷åñêè âûñòðîåííûõ è àäåêâàòíûõ ñèòóàöèÿì ôîðìóëèðîâîê.
×àñòî ïðèõîäèòñÿ îáðàáàòûâàòü èíôîðìàöèþ, ïîëó÷åííóþ â
ðåçóëüòàòå âñåâîçìîæíûõ ñòàòèñòè÷åñêèõ îáîáùåíèé, ñîöèîëîãè÷åñêèõ îïðîñîâ è ò. ä., ñ ïîìîùüþ ñðåäñòâ òåîðèè âåðîÿòíîñòåé è
ìàòåìàòè÷åñêîé ñòàòèñòèêè. Ïðè ýòîì ïîíàäîáÿòñÿ óìåíèÿ ôîðìóëèðîâàòü ãèïîòåçû î âèäàõ ðàñïðåäåëåíèé, ïðîâåðÿòü èõ æèçíåñïîñîáíîñòü, èñòèííîñòü, îòðàæåíèå ðåàëüíîñòè. Ïîýòîìó ïðîãðàììèñòàì âàæíî îðèåíòèðîâàòüñÿ â ðàçëè÷íûõ âèäàõ èíäóêòèâíûõ
óìîçàêëþ÷åíèé è óìåòü îòëè÷àòü äîñòîâåðíûå âûâîäû îò âåðîÿòíîñòíûõ, ò. å. ïðèìåíÿòü â ðàáîòå çíàíèÿ êëàññè÷åñêîé ëîãèêè.
Îáúåêòîì èññëåäîâàíèÿ äèñêðåòíîé ìàòåìàòèêè ÿâëÿþòñÿ äèñêðåòíûå ìíîæåñòâà — ñîâîêóïíîñòü, íàáîð íåêîòîðûõ ýëåìåíòîâ.
Ïîýòîìó íà÷íåì ñ ñàìîãî îáùåãî ãëóáîêî àáñòðàêòíîãî ðàçäåëà
ýòîé íàóêè — òåîðèè ìíîæåñòâ è îòíîøåíèé, êîòîðàÿ ñòàëà èíòåíñèâíî ðàçâèâàòüñÿ ñ âíåäðåíèåì âû÷èñëèòåëüíîé òåõíèêè.
Ïðîñòåéøèå ïðåäñòàâëåíèÿ î ìíîæåñòâàõ âïåðâûå ïîÿâèëèñü â
ñâÿçè ñ èññëåäîâàíèÿìè â îáëàñòè êàðòî÷íûõ èãð è âîçíèêíîâåíèåì êîìáèíàòîðèêè è äèñêðåòíîé òåîðèè âåðîÿòíîñòåé.
Ãëàâà 1
ÌÍÎÆÅÑÒÂÀ
 ýòîé ãëàâå ìû ñèñòåìàòèçèðóåì èìåþùèåñÿ ñî øêîëû ïðåäñòàâëåíèÿ îá óíèâåðñàëüíîì ÿçûêå òåîðèè ìíîæåñòâ, ïîçíàêîìèìñÿ ñ âèäàìè ìíîæåñòâ è îòíîøåíèé ìåæäó íèìè, óçíàåì, êàê
ñðàâíèâàòü êîíå÷íûå è áåñêîíå÷íûå ìíîæåñòâà è êàê ïîäñ÷èòûâàòü ÷èñëî èõ ýëåìåíòîâ. Ýòà ãëàâà äîëæíà ñòàòü òåì ñëîâàðåì, ñ
ïîìîùüþ êîòîðîãî ìîæíî ñâîáîäíî ïîíèìàòü ýòó êíèãó è äðóãèå
ìàòåìàòè÷åñêèå òåêñòû.
1.1. Îáùèå ïîíÿòèÿ òåîðèè ìíîæåñòâ
Ñåãîäíÿ ìû çíàåì, ÷òî, ëîãè÷åñêè
ãîâîðÿ, âîçìîæíî âûâåñòè ïî÷òè âñþ
ñîâðåìåííóþ ìàòåìàòèêó èç åäèíîãî
èñòî÷íèêà — òåîðèè ìíîæåñòâ.
Í. Áóðáàêè
ßçûê òåîðèè ìíîæåñòâ. Ìíîæåñòâî — îäíî èç îñíîâíûõ ïîíÿòèé ñîâðåìåííîé ìàòåìàòèêè, ñ êîòîðûì êàæäûé ÷åëîâåê çíàêîì
ñî øêîëüíîé ñêàìüè. «Ìíîæåñòâî ðåøåíèé óðàâíåíèÿ èëè íåðàâåíñòâà», «ìíîæåñòâî òî÷åê íà ïëîñêîñòè», «ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë» è ò. ä. — ïðèâû÷íûå ñëîâîñî÷åòàíèÿ, íå òðåáóþùèå äîïîëíèòåëüíûõ ðàññóæäåíèé è îïðåäåëåíèé.
? ×òî æå òàêîå ìíîæåñòâî?
Ïîíÿòèÿ ìíîæåñòâî, ýëåìåíòû ìíîæåñòâà — ïåðâè÷íûå áàçèñíûå íåîïðåäåëÿåìûå ïîíÿòèÿ, íà êîòîðûõ ñòðîèòñÿ òåîðèÿ ìíîæåñòâ.
Ñîâîêóïíîñòü ýëåìåíòîâ, îáúåäèíåííûõ íåêîòîðûì ïðèçíàêîì,
ñâîéñòâîì, ñîñòàâëÿåò ïîíÿòèå ìíîæåñòâî. Íàïðèìåð, ìíîæåñòâî
êíèã â áèáëèîòåêå, ìíîæåñòâî ñòóäåíòîâ â ãðóïïå, ìíîæåñòâî
íàòóðàëüíûõ ÷èñåë ¥ è ò. ä.
Çàïèñü a ∈ M îçíà÷àåò: ýëåìåíò a ïðèíàäëåæèò ìíîæåñòâó M,
ò. å. ýëåìåíò a îáëàäàåò íåêîòîðûì ïðèçíàêîì. Àíàëîãè÷íî a ∉ M
÷èòàåì êàê: ýëåìåíò a íå ïðèíàäëåæèò ìíîæåñòâó M.
14
Ìíîæåñòâî ñ÷èòàåòñÿ çàäàííûì, åñëè èëè ïåðå÷èñëåíû âñå åãî
ýëåìåíòû, èëè óêàçàíî ñâîéñòâî, êîòîðûì îáëàäàþò òå è òîëüêî
òå ýëåìåíòû, êîòîðûå ïðèíàäëåæàò äàííîìó ìíîæåñòâó. Ïåðâûé
âàðèàíò áóäåì çàïèñûâàòü òàê: M = {m1, m2, ¾, mk}, íàïðèìåð,
M = {0, 1}. Ïîñëåäíèé âàðèàíò áóäåì çàïèñûâàòü òàê: M = {b |P (b)}.
Òàêàÿ çàïèñü ÷èòàåòñÿ êàê: M ñîñòîèò èç òåõ (âñåõ) ýëåìåíòîâ b,
êîòîðûå îáëàäàþò ïðèçíàêîì P. Íàïðèìåð, M = {n n ∈ ¥, n < 5}
îçíà÷àåò: M ñîñòàâëÿþò òîëüêî òå íàòóðàëüíûå ÷èñëà, ÷òî ìåíüøå
ïÿòè. Ñàìî ñâîéñòâî P áóäåì íàçûâàòü õàðàêòåðèñòè÷åñêèì.  êà÷åñòâå õàðàêòåðèñòè÷åñêîãî ñâîéñòâà ìîæåò âûñòóïàòü óêàçàííàÿ äëÿ
ýòîãî ñâîéñòâà ïîðîæäàþùàÿ ïðîöåäóðà, êîòîðàÿ îïèñûâàåò ñïîñîá ïîëó÷åíèÿ ýëåìåíòîâ íîâîãî ìíîæåñòâà èç óæå ïîëó÷åííûõ
ýëåìåíòîâ èëè èç äðóãèõ îáúåêòîâ. Òîãäà ýëåìåíòàìè ìíîæåñòâà
ñ÷èòàþòñÿ âñå îáúåêòû, êîòîðûå ìîãóò áûòü ïîëó÷åíû ñ ïîìîùüþ
ýòîé ïðîöåäóðû. Íàïðèìåð, ìíîæåñòâî Ì2n = {1, 2, 4, 8, 16, 32, ¾}
âñåõ ÷èñåë, ÿâëÿþùèõñÿ íåîòðèöàòåëüíûìè ñòåïåíÿìè ÷èñëà 2
(Ì2n = {2i i ∈ ¢, i ≥ 0}), ìîæíî çàäàòü ñ ïîìîùüþ ïîðîæäàþùåé
ôóíêöèè ïî èíäóêòèâíûì (ïîäðîáíî ñì. â ãë. 5) ïðàâèëàì:
• 1 ∈ Ì2n;
• åñëè k ∈ Ì2n, òî (2k) ∈ Ì2n.
Èòàê, çàïèñü M = {x P (x)} îçíà÷àåò: ìíîæåñòâî M ñîñòîèò èç
âñåõ ýëåìåíòîâ x, îáëàäàþùèõ ïðèçíàêîì P . Íàïðèìåð, çàïèñü
M = {x x3 + 3x2 + 2x = 0} îçíà÷àåò, ÷òî ìíîæåñòâî M ñîäåðæèò
òîëüêî êîðíè äàííîãî óðàâíåíèÿ, ò. å. ÷èñëà {0; −1; −2}. Çàïèñü
Z = {X |ÎÕ | ≤ 4} îçíà÷àåò, ÷òî äëÿ ëþáûõ X ðàññòîÿíèå ÎÕ ìåíüøå
èëè ðàâíî 4, ò.å. ìíîæåñòâî âñåõ òî÷åê, äëÿ êîòîðûõ ðàññòîÿíèå äî
X íå áîëüøå 4, åñòü øàð ñ öåíòðîì â òî÷êå O è ðàäèóñîì R = 4.
Çàïèñü A = {x x ≥ 7, x ∈ ¥} ÷èòàåòñÿ òàê: äëÿ ëþáûõ íàòóðàëüíûõ x,
íà÷èíàÿ ñ 7. Îòìåòèì, ÷òî â çàïèñè M = {x P (x)} ïåðåìåííàÿ x
ÿâëÿåòñÿ «íåìîé», ò.å. íåñóùåñòâåííîé: îò íåå íè÷åãî íå çàâèñèò.
Ìîæíî áûëî áû óïîòðåáèòü ëþáóþ äðóãóþ áóêâó, íàïðèìåð ó, è
âñå ðàâíî ýòî áûëî áû «ìíîæåñòâî âñåõ ýëåìåíòîâ, îáëàäàþùèõ
ïðèçíàêîì P », à êàê íàçûâàòü ýëåìåíòû — íåñóùåñòâåííî: ãëàâíîå, ÷òîáû îíè îáëàäàëè ïðèçíàêîì.
Åñëè ìíîæåñòâî íå ñîäåðæèò ýëåìåíòîâ, îáëàäàþùèõ õàðàêòåðèñòè÷åñêèì ïðèçíàêîì, òî îíî íàçûâàåòñÿ ïóñòûì è îáîçíà÷àåòñÿ ∅. Íàïðèìåð, ìíîæåñòâî öåëûõ ðåøåíèé íåðàâåíñòâà 5 < x < 6
ÿâëÿåòñÿ ïóñòûì: K = {x x ∈ ¢, 5 < x < 6} = ∅. Ïóñòûì áóäåò ìíîæåñòâî äåéñòâèòåëüíûõ ðåøåíèé óðàâíåíèé õ2 + 25 = 0 è 52õ − 3 = −1.
Ìíîæåñòâî, íå ÿâëÿþùååñÿ ïóñòûì, íàçûâàåòñÿ íåïóñòûì.
? Âñåãäà ëè óäàåòñÿ, ñîáëþäàÿ âñå ïðàâèëà, çàäàòü ìíîæåñòâî? Íàïðèìåð, êàê çàäàòü ìíîæåñòâî âñåõ ìíîæåñòâ? Áóäåò ëè òàêîå ìíîæåñòâî
ñîäåðæàòü ñåáÿ êàê îòäåëüíûé ýëåìåíò, âåäü ïî óêàçàííîìó õàðàêòåðèñòè÷åñêîìó ñâîéñòâó îíî äîëæíî ñîäåðæàòü âñå âîçìîæíûå ìíîæåñòâà, à
çíà÷èò, è ñåáÿ?
15
Èçîáðàæåíèå ìíîæåñòâ. Ìíîæåñòâà
óäîáíî èçîáðàæàòü ñ ïîìîùüþ êðóãîâ
Ýéëåðà (äèàãðàìì Âåííà). Ýëåìåíòû
ìíîæåñòâà èçîáðàæàþòñÿ òî÷êàìè
âíóòðè êðóãà, åñëè îíè ïðèíàäëåæàò
ìíîæåñòâó (a ∈ M íà ðèñ. 1.1, à), è
òî÷êàìè âíå êðóãà, åñëè îíè ìíîæåñòâó íå ïðèíàäëåæàò (b ∉ M).
Ðèñ. 1.1. Èëëþñòðàöèÿ
Áóäåì òàêæå èñïîëüçîâàòü ñèìâîêðóãàìè Ýéëåðà:
à — ýëåìåíò à ïðèíàäëåæèò ëû ∀õ âìåñòî ñëîâ «äëÿ ëþáûõ õ»,
ìíîæåñòâó Ì, ýëåìåíò b íå «êàæäûé ýëåìåíò õ» è ∃õ âìåñòî ñëîâ
ïðèíàäëåæèò ìíîæåñòâó Ì; á — «ñóùåñòâóåò õ». Çíà÷åíèå ýòèõ ñèìïîäìíîæåñòâî Ê ìíîæåñòâà Ì
âîëîâ è ïðàâèëà èõ óïîòðåáëåíèÿ áóäóò ïîäðîáíî ðàçúÿñíåíû â ãë. 4 è 5.
Èç ìíîæåñòâà M ìîæíî âûäåëèòü åãî ÷àñòü (òàêæå âûäåëåíèåì
íîâîãî õàðàêòåðèñòè÷åñêîãî ñâîéñòâà èëè ïåðå÷èñëåíèåì ýëåìåíòîâ) — ìíîæåñòâî Ê, âñå ýëåìåíòû êîòîðîãî îáëàäàþò òàêèì æå
ïðèçíàêîì, êàê è ýëåìåíòû ìíîæåñòâà M. Ìíîæåñòâî Ê íàçûâàþò
ïîäìíîæåñòâîì ìíîæåñòâà M è îáîçíà÷àþò Ê ⊂ M (ðèñ. 1.1, á ).
Áîëåå ñòðîãî: ìíîæåñòâî Ê íàçûâàåòñÿ ïîäìíîæåñòâîì ìíîæåñòâà
M (Ê ⊂ M), åñëè äëÿ ëþáîãî x ∈ K âûïîëíÿåòñÿ x ∈ M (ò. å. ∀x ∈ K
âëå÷åò x ∈ M).
Íàïðèìåð, äîáàâëÿÿ ê ìíîæåñòâó îäíîçíà÷íûõ öåëûõ ÷èñåë
A = {0, 1, ¾, 9} ïðèçíàê «÷èñëî äåëèòñÿ íà 3», ïîëó÷àåì ìíîæåñòâî B = {0, 3, 6, 9} ⊂ A.
Òàê, ìíîæåñòâî öåëûõ ÷èñåë ¢ ÿâëÿåòñÿ ïîäìíîæåñòâîì ìíîæåñòâà ðàöèîíàëüíûõ ÷èñåë ¤. Äëÿ ÷èñëîâûõ ìíîæåñòâ ñïðàâåäëèâî ñîîòíîøåíèå: ¥ ⊂ ¢ ⊂ ¤ ⊂ ¡ ⊂ £, ãäå ¥ — ìíîæåñòâî íàòóðàëüíûõ ÷èñåë, ¤ — ðàöèîíàëüíûõ, ¡ — äåéñòâèòåëüíûõ, £ —
êîìïëåêñíûõ ÷èñåë. Äëÿ ëþáîãî íåïóñòîãî ìíîæåñòâà M ìîæíî
ñðàçó óêàçàòü äâà åãî ïîäìíîæåñòâà íåçàâèñèìî îò ñîñòàâà è ñòðóêòóðû M : ýòî îíî ñàìî è ïóñòîå. Î÷åâèäíî, ïóñòîå ìíîæåñòâî ñîäåðæèòñÿ (ÿâëÿåòñÿ ïîäìíîæåñòâîì) â ëþáîì ìíîæåñòâå.
Òàêæå íåîáõîäèìî ó÷èòûâàòü ðàçëè÷èå â óïîòðåáëåíèè çíàêîâ
âêëþ÷åíèÿ (⊂) è ïðèíàäëåæíîñòè (∈) äëÿ ìíîæåñòâà ìíîæåñòâ.
Íàïðèìåð, M — ìíîæåñòâî âñåõ ôàêóëüòåòîâ â íàøåì êîëëåäæå, à Ê — ôàêóëüòåò ïðîãðàììèðîâàíèÿ. Õîòÿ Ê ñàìî ÿâëÿåòñÿ ìíîæåñòâîì (ñîñòîèò èç ñòóäåíòîâ è ñîòðóäíèêî⠗ ïðåïîäàâàòåëåé,
àäìèíèñòðàöèè è äð.), âåðíà çàïèñü K ∈ M, òàê êàê ôàêóëüòåò K
ÿâëÿåòñÿ ýëåìåíòîì âñåãî ìíîæåñòâà M. Çàïèñü K ⊂ M íåâåðíà, òàê
êàê ìíîæåñòâà K è M ñîäåðæàò ðàçíûå ýëåìåíòû: K — ëþäåé, M —
ôàêóëüòåòû. Îäíàêî, åñëè ðàññìîòðèì ìíîæåñòâî O — ñîâîêóïíîñòü ëþäåé ñî âñåõ ôàêóëüòåòîâ (íàïðèìåð, ïðè âñåîáùåì ãîëîñîâàíèè ïî íàñóùíîìó âîïðîñó), òî, áåçóñëîâíî, K ⊂ O.
Óíèâåðñàëüíûì íàçûâàþò ìíîæåñòâî U, ñîñòîÿùåå èç âñåõ âîçìîæíûõ ýëåìåíòîâ, îáëàäàþùèõ äàííûì ïðèçíàêîì. Íàïðèìåð,
16
ìíîæåñòâî ïëàíåò Ñîëíå÷íîé ñèñòåìû U = {Çåìëÿ, Ìàðñ, Âåíåðà, Þïèòåð, Ñàòóðí, Óðàí, Ìåðêóðèé, Íåïòóí}. Çàìåòèì, ÷òî
ïîíÿòèå óíèâåðñàëüíîãî ìíîæåñòâà ÷åòêî íå îïðåäåëåíî, ò. å. íåêîððåêòíî. U ìîæíî âêëþ÷èòü â äðóãîå ìíîæåñòâî W, è îíî òîæå
áóäåò óíèâåðñàëüíûì. Íàïðèìåð, äîëãî ñ÷èòàëîñü, ÷òî ìíîæåñòâî
äåéñòâèòåëüíûõ ÷èñåë ¡ óíèâåðñàëüíî (ò. å. îïèñûâàåò âñþ ìàòåìàòèêó), ïîêà íå îòêðûëè ïîëå êîìïëåêñíûõ ÷èñåë £ è íàäêîìïëåêñíûå ÷èñëà è íå ïîíÿëè, ÷òî íå ñóùåñòâóåò óíèâåðñàëüíîãî
÷èñëîâîãî ìíîæåñòâà. Òåì íå ìåíåå òàì, ãäå îáëàñòü îáúåêòîâ íå
âûõîäèò çà ðàìêè íåêîåãî ìíîæåñòâà, èíîãäà áûâàåò óäîáíî îïåðèðîâàòü ñ ýòèì òåðìèíîì. Âåäü ðæàíîå ïîëå — âñåëåííàÿ äëÿ
ìûøè.
Ðàâíûìè íàçûâàþò äâà ìíîæåñòâà A è B, ñîñòîÿùèå èç îäèíàêîâûõ ýëåìåíòîâ: A = B. Íàïðèìåð, ðàâíû ìíîæåñòâà ðåøåíèé
óðàâíåíèé 4õ − 8 = 16, õ/15 = 2/5 è 5õ − 3 = 125, òàê êàê èõ ðåøåíèåì
ÿâëÿåòñÿ îäíî è òî æå ÷èñëî 6.
Ðàâíû ìíîæåñòâà áóêâ, èç êîòîðûõ ñîñòàâëåíû ñëîâà «íàâåñ» è
«âåñíà». Ðàâíû ìíîæåñòâà êîðíåé óðàâíåíèÿ õ2 = 1 è ìíîæåñòâî
M = {(−1)k, k = 0, 1, 2, ¾}. Ïîýòîìó çàäà÷à «ðåøèòü óðàâíåíèå»,
çíàêîìàÿ ñ äåòñòâà, â ðåàëüíîñòè îçíà÷àåò «ðåøèòü óðàâíåíèå â
êàêîì-òî ìíîæåñòâå». Òàê, óðàâíåíèå õ2 + 1 = 0 íå èìååò äåéñòâèòåëüíûõ êîðíåé: {x õ2 + 1 = 0, x ∈ ¡} = ∅, íî èìååò äâà êîìïëåêñíûõ êîðíÿ x = i, x = −i: {x õ2 + 1 = 0, x ∈ £} = {i, −i}.
Ðàâåíñòâî äâóõ ìíîæåñòâ A è B îçíà÷àåò òàêæå, ÷òî A ⊂ B è
B ⊂ A. È íàîáîðîò, âûïîëíåíèå ñâîéñòâ A ⊂ B è B ⊂ A îçíà÷àåò
âûïîëíåíèå ðàâåíñòâà A = B. Ýòè óòâåðæäåíèÿ ðàâíîñèëüíû.
×èñëî ýëåìåíòîâ ìíîæåñòâà A íàçûâàåòñÿ ìîùíîñòüþ ìíîæåñòâà è îáîçíà÷àåòñÿ | A | èëè n ( A ). Òàê, ìîùíîñòü ïóñòîãî ìíîæåñòâà ðàâíà 0: n(∅) = 0, à ìîùíîñòü ìíîæåñòâà ïëàíåò Ñîëíå÷íîé
ñèñòåìû n(U ) = 8 èëè |U | = 8.
1.2. Îñíîâíûå îïåðàöèè íàä ìíîæåñòâàìè
Âñå ïðàâèëà äîñòîéíîãî ïîâåäåíèÿ
äàâíûì-äàâíî èçâåñòíû, îñòàíîâêà çà
ìàëûì — çà óìåíèåì èìè ïîëüçîâàòüñÿ.
Á. Ïàñêàëü
Ââåäåíèå îïåðàöèé íàä ìíîæåñòâàìè. Èç äàííûõ ìíîæåñòâ A è B
ìîæíî ïîñòðîèòü íîâûå ìíîæåñòâà ñ ïîìîùüþ îïåðàöèé îáúåäèíåíèÿ, ïåðåñå÷åíèÿ, âû÷èòàíèÿ è äð. (òàáë. 1.1).
Ïðèìåð ïåðâûé. Îêðóæíîñòü — ìíîæåñòâî òî÷åê ïëîñêîñòè,
ðàâíîóäàëåííûõ îò äàííîé (íàïðèìåð, O ), íàçûâàåìîé öåíòðîì.
Ìàòåìàòè÷åñêè äëÿ åå íàõîæäåíèÿ íàäî çàäàòü óðàâíåíèå ðàâíî17
18
Òå è òîëüêî òå ýëåìåíòû, êîòîðûå íå ïðèíàäëåæàò ìíîæåñòâó A (ò. å. äîïîëíÿþò åãî äî
óíèâåðñàëüíîãî U )
Òå è òîëüêî òå ýëåìåíòû, êîòîðûå ïðèíàäëåæàò îäíîìó èç
ìíîæåñòâ: A ëèáî Â, íî íå ÿâëÿþòñÿ îáùèìè ýëåìåíòàìè
A = A′ =
= U\A
A∆Â
Ñèììåòðè÷åñêàÿ
ðàçíîñòü
Äîïîëíåíèå
ê ìíîæåñòâó A
Òå è òîëüêî òå ýëåìåíòû ìíîæåñòâà A, êîòîðûå íå ïðèíàäëåæàò Â
A\Â
Ðàçíîñòü
ìíîæåñòâ
A I Â = {x x ∈ A è x ∈ Â }
Ñèìâîëè÷åñêàÿ çàïèñü
A ∆ Â = (A\Â ) U (Â \ A ) =
= (A U Â )\(A I Â )
—
A ={x x ∉ A} = U \ A
A\Â = {x x ∈ A è x ∉ Â }
Òå è òîëüêî òå ýëåìåíòû, êî- A U B = {x x ∈ A èëè x ∈ Â }
òîðûå ïðèíàäëåæàò õîòÿ áû
îäíîìó èç ìíîæåñòâ A è Â
AUB
Òå è òîëüêî òå ýëåìåíòû, êîòîðûå ïðèíàäëåæàò îäíîâðåìåííî A è Â
Îïðåäåëåíèå
Îáúåäèíåíèå
ìíîæåñòâ
Èçîáðàæåíèå
êðóãàìè Ýéëåðà
AIÂ
Îáîçíà÷åíèå
Ïåðåñå÷åíèå
ìíîæåñòâ
Íàçâàíèå
îïåðàöèè
Îñíîâíûå îïåðàöèè íàä ìíîæåñòâàìè
Ò à á ë è ö à 1.1
óäàëåííîñòè L = {M (x, y, z) (x − a)2 + (y − b)2 + (z − c)2 = r2} (à ýòî
óðàâíåíèå ñôåðû) è óðàâíåíèå ïëîñêîñòè, ïðîõîäÿùåé ÷åðåç öåíòð
Î ñ êîîðäèíàòàìè (a; b; c): P = {M (x, y, z) A (x − a) + B (y − b) + C (z −
− c) = 0}. Îêðóæíîñòüþ (E ) áóäåò ìíîæåñòâî òî÷åê, ïðèíàäëåæàùèõ è ñôåðå (L), è ïëîñêîñòè (P ), ò. å. èõ ïåðåñå÷åíèå: E = L I P.
Ïîýòîìó äëÿ íàõîæäåíèÿ ýòèõ òî÷åê íàäî ðåøèòü ñèñòåìó äâóõ óðàâíåíèé. Èòàê, îêðóæíîñòü E = {M(x, y, z) (x − a)2 + (y − b)2 + (z − c)2 =
= r2, A(x − a) + B (y − b) + C (z − c) = 0}.
Ïðèìåð âòîðîé. Ïóñòü A = {a, b, c, g, å}, B = {a, c, å, f, r, m}, òîãäà
A U B = {a, b, c, g, å, f, r, m}, A I B = {a, c, å}, A \ B = {b, g}, B \ A =
= {f, r, m}, A Δ B = {b, g, f, r, m}. Îáðàòèì âíèìàíèå, ÷òî äëÿ ðàçíîñòè
äâóõ ìíîæåñòâ íå âûïîëíÿåòñÿ ïåðåìåñòèòåëüíûé çàêîí: A \ B ≠
≠ B \ A. Ýòî ñòàíîâèòñÿ î÷åâèäíûì, åñëè îäíî ìíîæåñòâî ïóñòîå
(íàïðèìåð, A ), à äðóãîå — íåïóñòîå.
Ñâîéñòâà îïåðàöèé íàä ìíîæåñòâàìè. Îïåðàöèè íàä ìíîæåñòâàìè îáëàäàþò ðÿäîì ñâîéñòâ, ïîõîæèõ íà ñâîéñòâà îïåðàöèé ñëîæåíèÿ è óìíîæåíèÿ ÷èñåë. Ðàññìîòðèì çàêîíû, ñïðàâåäëèâûå äëÿ
ëþáûõ ìíîæåñòâ A, B, C.
1. A U B =B U A, A I B = B I A — ïåðåìåñòèòåëüíûé çàêîí (êîììóòàòèâíîñòü) äëÿ îïåðàöèé îáúåäèíåíèÿ è ïåðåñå÷åíèÿ. Ïîñêîëüêó (à ýòî íåòðóäíî äîêàçàòü) ýòî ñâîéñòâî ñïðàâåäëèâî äëÿ ëþáîãî êîíå÷íîãî ÷èñëà ìíîæåñòâ, òî óäîáíî èñïîëüçîâàòü çíàêè U è
I äëÿ îáîçíà÷åíèÿ îáúåäèíåíèÿ è ïåðåñå÷åíèÿ ìíîãèõ ìíîæåñòâ.
n
Íàïðèìåð, 7 Ai îçíà÷àåò îáúåäèíåíèå n ìíîæåñòâ âíå çàâèñèìîi =1
ñòè îò òîãî, êàêîå èç íèõ ñ÷èòàòü ïåðâûì, âòîðûì è ò. ä.
2. (A U B ) U C = A U (B U C ); (A I B) I C = A I (B I C ) — ñî÷åòàòåëüíûé çàêîí (àññîöèàòèâíîñòü) äëÿ îïåðàöèé îáúåäèíåíèÿ è
ïåðåñå÷åíèÿ.
3. (A U B ) I C = (A I C ) U (B I C ) — ðàñïðåäåëèòåëüíûé çàêîí (äèñòðèáóòèâíîñòü) ïåðåñå÷åíèÿ îòíîñèòåëüíî îáúåäèíåíèÿ ìíîæåñòâ.
4. (A I B ) U C = (A U C ) I (B U C ) — ðàñïðåäåëèòåëüíûé çàêîí
îáúåäèíåíèÿ îòíîñèòåëüíî ïåðåñå÷åíèÿ ìíîæåñòâ.
5. A U A = A, A I A = A, A ⊂ (A U B ) — çàêîíû ïîãëîùåíèÿ.
6. U = ∅′ è ∅ = U ′, ò. å. óíèâåðñàëüíîå è ïóñòîå ìíîæåñòâà ÿâëÿþòñÿ äîïîëíåíèÿìè äðóã äðóãà.
7. Åñëè îáîçíà÷èòü ÷åðåç Ài âñå ïîäìíîæåñòâà À1, À2, À3, ¾, Àn
ìíîæåñòâà A, òî áóäóò ñïðàâåäëèâû ðàâåíñòâà: ) = 7 )E è
) \ 1 )E = 7 ( ) \ )E ).
E
E
E
Îïåðàöèÿ äîïîëíåíèÿ îáëàäàåò ðÿäîì õàðàêòåðíûõ ñâîéñòâ.
–
8. Äëÿ ëþáîãî ìíîæåñòâà Õ ⊂ U ñïðàâåäëèâî X ′ = (X ′)′ = X.
9. Äëÿ ëþáûõ äâóõ ìíîæåñòâ X è Y ñïðàâåäëèâî: åñëè X ⊂ U,
Y ⊂ U, òî (X I Y )′ = X ′ U Y ′ èëè (X U Y )′ = X ′ I Y ′.
19
Äîêàæåì ïîñëåäíåå ñâîéñòâî.
Ïóñòü a ∈ (X I Y )′, ÷òî ðàâíîñèëüíî a ∉ (X I Y ). Ýòî çíà÷èò,
÷òî a ∉ X èëè a ∉ Y, ò. å. a ∈ X ′ èëè a ∈ Y ′, ïîýòîìó a ∈ (X ′ U Y ′).
10. Ìíîæåñòâî A ìîæíî ðàçáèòü íà êëàññû íåïåðåñåêàþùèõñÿ
ïîäìíîæåñòâ Ài, åñëè:
• îáúåäèíåíèå âñåõ ïîäìíîæåñòâ ñîâïàäàåò ñ ìíîæåñòâîì A:
A = U Ai ;
i
• ïåðåñå÷åíèå ëþáûõ äâóõ ðàçëè÷íûõ ïîäìíîæåñòâ ïóñòî, ò.å.
äëÿ ëþáûõ i ≠ j âûïîëíÿåòñÿ Ài I Aj = ∅.
Ðàññìîòðèì ïðèìåðû.
1. Ïðîèçâîëüíîå ìíîæåñòâî A ðàçáèâàåòñÿ íà äâà äîïîëíÿþùèõ
äðóã äðóãà ïîäìíîæåñòâà A1 è A2 = A \ A1, òàêèõ, ÷òî A1 U A2 = A è
A1 I A2 = ∅.
2. Ìíîæåñòâî äâóçíà÷íûõ ÷èñåë U = {10, 11, 12, ¾, 98, 99}
ìîæíî ðàçáèòü íà êëàññû ïî ïðèçíàêó îñòàòêà îò äåëåíèÿ íà 4:
êëàññ, ïîðîæäåííûé îñòàòêîì 0: À0 = {12, 16, 20, ¾, 96}. Àíàëîãè÷íî À1 = {13, 17, 20, ¾, 97}; À2 = {10, 14, 18, ¾, 98}; À3 = {11, 15,
19, ¾, 99}.
Ðàçáèåíèå íà êëàññû èñïîëüçóåòñÿ äëÿ êëàññèôèêàöèè îáúåêòîâ (ñì. ãë. 2 è 3). Òàê, ìíîæåñòâî êâàðòèð äîìà ìîæåò áûòü ðàçáèòî
íà ïîäìíîæåñòâî êâàðòèð îòäåëüíûõ ïîäúåçäîâ, à ìíîæåñòâî êâàðòèð êàæäîãî ïîäúåçäà — íà ïîäìíîæåñòâî êâàðòèð îäíîãî ýòàæà.
1.3. Ñîîòâåòñòâèÿ ìåæäó ìíîæåñòâàìè. Îòîáðàæåíèÿ
Íàêîíåö Äðîíò ñêàçàë:
— Ïîáåäèëè âñå! È âñå ïîëó÷àò ïðèçû, — äîáàâèë îí.
¾ âñå íàïåðåáîé çàêðè÷àëè:
— Ïðèçû! Ãäå ïðèçû? Äàâàé ïðèçû!
Áåäíàÿ Àëèñà íå çíàëà, ÷òî åé äåëàòü; â ðàñòåðÿííîñòè îíà ñóíóëà ðóêó
â êàðìàøåê è âûòàùèëà îòòóäà êîðîáî÷êó öóêàòîâ¾ Îíà ñòàëà ðàçäàâàòü
êîíôåòû âñåì ó÷àñòíèêàì ñîðåâíîâàíèé, è êàê ðàç õâàòèëî íà âñåõ, êðîìå
ñàìîé Àëèñû¾
Ë. Êýððîëë
Îñíîâíûå ïîíÿòèÿ. Ïóñòü äàíû äâà ìíîæåñòâà A = {à1, à2, ¾} è
B = {b1, b2, ¾}. Òîãäà ïàðû (ài, bj) çàäàþò ñîîòâåòñòâèå ìåæäó ìíîæåñòâàìè A è B, åñëè óêàçàíî ïðàâèëî R, ïî êîòîðîìó äëÿ ýëåìåíòà ài ìíîæåñòâà A âûáèðàåòñÿ ýëåìåíò bj èç ìíîæåñòâà B.
Íàïðèìåð, ñîîòâåòñòâèå ìåæäó ýëåìåíòàìè ìíîæåñòâ õ ∈ ¡ è
y ∈ ¡ çàäàåò òî÷å÷íîå ìíîæåñòâî (xi; yi) êîîðäèíàò òî÷åê íà ïëîñ20
Ðèñ. 1.2. Èëëþñòðàöèÿ ñîîòâåòñòâèÿ R — «âåðøèíà ïàðàáîëû»
Ðèñ. 1.3. Çàäàíèå îòîáðàæåíèÿ xRy ñ ïîìîùüþ ìåòîäà êîîðäèíàò
êîñòè; ðóññêî-àíãëèéñêèé ñëîâàðü óñòàíàâëèâàåò ñîîòâåòñòâèå çíà÷åíèé è íàïèñàíèé ñëîâ ðóññêîãî è àíãëèéñêîãî ÿçûêîâ.
Ïóñòü çàäàíî ñîîòâåòñòâèå R ìåæäó ìíîæåñòâàìè A è B, ò. å. R :
(a; b), a ∈ A, b ∈ B. Äëÿ íåêîòîðîãî ýëåìåíòà a ìíîæåñòâà A ïîñòàâëåí â ñîîòâåòñòâèå íåêîòîðûé ýëåìåíò b èç ìíîæåñòâà B, êîòîðûé íàçûâàåòñÿ îáðàçîì ýëåìåíòà a è çàïèñûâàåòñÿ b = R (a). Òîãäà
a = R −1(b) — ïðîîáðàç ýëåìåíòà b ∈ B ïðè ñîîòâåòñòâèè R . Ìíîæåñòâî Ba = {b b = R (a)} íàçûâàåòñÿ ïîëíûì îáðàçîì ýëåìåíòà a (ïðè
ýòîì, Ba ⊂ B ), à ìíîæåñòâî Ab = {a R (a) = b} ⊂ A íàçûâàåòñÿ
ïîëíûì ïðîîáðàçîì ýëåìåíòà b ïðè ñîîòâåòñòâèè R.
Íàïðèìåð, åñëè A — ìíîæåñòâî ïàðàáîë, B — ìíîæåñòâî òî÷åê
ïëîñêîñòè, à R — ñîîòâåòñòâèå «âåðøèíà ïàðàáîëû», òî R (a) —
òî÷êà, ÿâëÿþùàÿñÿ âåðøèíîé ïàðàáîëû a, à R −1(b) ñîñòîèò èç
âñåõ ïàðàáîë ai ñ âåðøèíîé â òî÷êå b (ðèñ. 1.2).
Îáðàç ìíîæåñòâà A ïðè ñîîòâåòñòâèè R íàçûâàåòñÿ ìíîæåñòâîì
çíà÷åíèé ýòîãî ñîîòâåòñòâèÿ è îáîçíà÷àåòñÿ R (A ), åñëè R(A ) ñîñòîèò èç îáðàçîâ âñåõ ýëåìåíòîâ ìíîæåñòâà A. Çàïèñü: R (A ) =
= {b ∀a ∈ A, b = R (a)}.
Ïðîîáðàç ìíîæåñòâà B ïðè íåêîòîðîì ñîîòâåòñòâèè R íàçûâàþò îáëàñòüþ îïðåäåëåíèÿ ýòîãî ñîîòâåòñòâèÿ è îáîçíà÷àþò R −1(B ),
ò. å. R −1(B ) = {a ∀b ∈ B, ∃a ∈ A: R(a) = b}; R −1 ÿâëÿåòñÿ îáðàòíûì
ñîîòâåòñòâèåì äëÿ R.
Òàê, äëÿ ñîîòâåòñòâèÿ R, çàäàííîãî òî÷êàìè êîîðäèíàòíîé
ïëîñêîñòè, îáëàñòüþ îïðåäåëåíèÿ ÿâëÿåòñÿ ìíîæåñòâî òî÷åê îñè
àáñöèññ, à ìíîæåñòâîì çíà÷åíèé — ïðîåêöèè òî÷åê íà îñü îðäèíàò
(ðèñ. 1.3). Ïîýòîìó äëÿ íåêîòîðîé òî÷êè M(x; y) y ÿâëÿåòñÿ îáðàçîì, à õ — ïðîîáðàçîì ïðè íåêîòîðîì ñîîòâåòñòâèè R : Y = R (X ),
X = R −1(Y ). Ñîîòâåòñòâèå ìåæäó ìíîæåñòâàìè X, Y ⊂ ¡ óäîáíî ïðåäñòàâèòü â âèäå òî÷êè íà ïëîñêîñòè ñ ïîìîùüþ ìåòîäà äåêàðòîâûõ
êîîðäèíàò.
Ïóñòü çàäàíî ñîîòâåòñòâèå R è Y = R (X ). Åìó ñîîòâåòñòâóåò òî÷êà M ñ êîîðäèíàòàìè (x; y) (ñì. ðèñ. 1.3). Òîãäà ìíîæåñòâî òî÷åê
ïëîñêîñòè, âûäåëÿåìîå îòîáðàæåíèåì R, áóäåò ãðàôèêîì.
21
Çàäàíèå îòîáðàæåíèé. Äëÿ îïèñàíèÿ ñîîòâåòñòâèé ìåæäó ìíîæåñòâàìè èñïîëüçóþò ïîíÿòèå îòîáðàæåíèÿ (ôóíêöèè) îäíîãî
ìíîæåñòâà íà äðóãîå.
Äëÿ çàäàíèÿ îòîáðàæåíèÿ íåîáõîäèìî óêàçàòü:
• ìíîæåñòâî, êîòîðîå îòîáðàæàåòñÿ (îáëàñòü îïðåäåëåíèÿ äàííîãî îòîáðàæåíèÿ, ÷àñòî îáîçíà÷àåòñÿ D ( f ));
• ìíîæåñòâî, â (íà) êîòîðîå îòîáðàæàåòñÿ äàííàÿ îáëàñòü îïðåäåëåíèÿ (ìíîæåñòâî çíà÷åíèé ýòîãî îòîáðàæåíèÿ, ÷àñòî îáîçíà÷àåòñÿ E ( f ));
• çàêîí èëè ñîîòâåòñòâèå ìåæäó ýòèìè ìíîæåñòâàìè, ïî êîòîðîìó äëÿ ýëåìåíòîâ ïåðâîãî ìíîæåñòâà (ïðîîáðàçîâ, àðãóìåíòîâ)
âûáðàíû ýëåìåíòû (îáðàçû) èç âòîðîãî ìíîæåñòâà. Ïðèíÿòû çàf
ïèñè A ⎯⎯⎯
→ B èëè f : A → B.
Âåçäå ïðè çàïèñè f : A → B áóäåì ïîäðàçóìåâàòü, ÷òî îòîáðàæåíèå f îïðåäåëåíî âñþäó íà A, ò. å. A — ïîëíûé ïðîîáðàç îòîáðàæåíèÿ f, õîòÿ äëÿ B òàêîãî ñâîéñòâà ïîëíîòû ïîäðàçóìåâàòü íå áóäåì.
Çàïèñü f (A ) îçíà÷àåò, ÷òî ýòî ìíîæåñòâî ñîñòîèò èç îáðàçîâ âñåõ
ýëåìåíòîâ ìíîæåñòâà A: f ( A ) = { f (a) a ∈ A}. Î÷åâèäíî, ÷òî f (A ) ⊂ B.
Äàëåå áóäåì èìåòü äåëî â îñíîâíîì ñ îäíîçíà÷íûìè îòîáðàæåíèÿìè, ãäå êàæäîìó àðãóìåíòó ïîñòàâëåíî â ñîîòâåòñòâèå íå áîëåå
îäíîãî îáðàçà.
Ñïîñîá çàäàíèÿ îòîáðàæåíèé â âèäå ôîðìóë íàçûâàåòñÿ àíàëèòè÷åñêèì. Ñóùåñòâóþò òàêæå òàáëè÷íûé è ãðàôè÷åñêèé ñïîñîáû çàäàíèÿ.
Äëÿ çàäàíèÿ îòîáðàæåíèÿ ìíîæåñòâ òàáëè÷íûì ñïîñîáîì ïðèíÿòî ñòðîèòü òàáëèöó, â êîòîðîé ïåðâóþ ñòðîêó ñîñòàâëÿþò ýëåìåíòû îáëàñòè îïðåäåëåíèÿ (ïðîîáðàçû âèäà a), à âòîðóþ ñòðîêó — èõ îáðàçû, ò. å. ýëåìåíòû âèäà γ(x) ïðè îòîáðàæåíèè γ: a → γ(a),
ãäå a ∈ A (òàáë. 1.2). Òàêîé ñïîñîá óäîáåí ïðè äîñòàòî÷íî ìàëîé
ìîùíîñòè ïðîîáðàçà (íå áîëåå 10). Íî âñå æå èíîãäà òàêîé ñïîñîá
çàäàíèÿ ôóíêöèè ÿâëÿåòñÿ åäèíñòâåííî âîçìîæíûì. Íàïðèìåð,
ïóáëèêàöèÿ â ãàçåòå ìíîãîòûñÿ÷íîé àðìèè ïîáåäèòåëåé ëîòåðåè:
àðãóìåíòîì ÿâëÿåòñÿ ëîòåðåéíûé íîìåð, îáðàçîì — ïðèç.
Ãðàôè÷åñêîå ïðåäñòàâëåíèå îòîáðàæåíèÿ ñâÿçàíî ñî ñòðåëî÷íûìè ñõåìàìè (äèàãðàììàìè èëè ãðàôàìè), êîòîðûå ïîäðîáíî ðàññìàòðèâàþòñÿ â ãë. 2. Íà ðèñ. 1.4 ïîêàçàí ïðèìåð ãðàôè÷åñêîãî çàäàíèÿ îòîáðàæåíèÿ ìíîæåñòâà A = {a1, a2, a3 } â B = {b1, b2, b3, b4, b5 }.
Ò à á ë è ö à 1.2
Òàáëè÷íîå çàäàíèå îòîáðàæåíèÿ
22
x
a1
a2
...
an
¾
γ(x)
γ(a1)
γ(a2)
...
γ(an)
¾
Ðèñ. 1.4. Ãðàôè÷åñêîå çàäàíèå èíúåêòèâíîãî îòîáðàæåíèÿ ìíîæåñòâà
ÀâÂ
Îòîáðàæåíèÿ f : A → B è g : A → B íàçûâàþòñÿ ðàâíûìè, åñëè
∀õ ∈ A f (õ) = g(õ).
Âèäû îòîáðàæåíèé. Ðàçëè÷àþò äâà îñíîâíûõ âèäà îäíîçíà÷íûõ
îòîáðàæåíèé (ôóíêöèé). Ïî ìîùíîñòè îíè äåëÿòñÿ íà ñþðúåêòèâíûå è èíúåêòèâíûå (ðèñ. 1.5).
Îòîáðàæåíèå ìíîæåñòâà A íà ìíîæåñòâî B, ïðè êîòîðîì êàæäîìó ýëåìåíòó ìíîæåñòâà B ñîîòâåòñòâóåò åäèíñòâåííûé ýëåìåíò
ìíîæåñòâà A, íàçûâàåòñÿ âçàèìíî-îäíîçíà÷íûì ñîîòâåòñòâèåì ìåæäó äâóìÿ ìíîæåñòâàìè, èëè áèåêöèåé.
Íà ðèñ. 1.6 èçîáðàæåí ãðàôèê áèåêòèâíîãî îòîáðàæåíèÿ ó = f (x),
f : ¡ → ¡.
Ïóñòü ìíîæåñòâî A îòîáðàæàåòñÿ âçàèìíî-îäíîçíà÷íî íà ìíîæåñòâî B, ò. å. f : A → B. Òîãäà îòîáðàæåíèå f −1, ïðè êîòîðîì êàæäîìó ýëåìåíòó ìíîæåñòâà B ñòàâèòñÿ â ñîîòâåòñòâèå åãî ïðîîáðàç
èç ìíîæåñòâà A, íàçûâàåòñÿ îáðàòíûì îòîáðàæåíèåì äëÿ f è çàïè−1
f
A èëè f −1: B → A. Òàê êàê îäíîìó îáðàçó ïðè
ñûâàåòñÿ B ⎯⎯⎯→
áèåêöèè ñîîòâåòñòâóåò â òî÷íîñòè îäèí ïðîîáðàç, îáðàòíîå îòîáðàæåíèå áóäåò îïðåäåëåíî âñþäó íà B è îäíîçíà÷íî (îòñþäà íàf
⎯⎯⎯
→ B.
çâàíèå). Äëÿ áèåêöèè ïðèíÿòà çàïèñü: A ←⎯⎯⎯
−1
f
Ðèñ. 1.5. Êëàññèôèêàöèÿ îòîáðàæåíèé ïî ìîùíîñòè
23
Ãîâîðÿò, ÷òî ìåæäó äâóìÿ ìíîæåñòâàìè
A è B óñòàíîâëåíî âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå f, åñëè ýëåìåíòû ýòèõ ìíîæåñòâ
ìîæíî ïðåäñòàâèòü â âèäå ïàð (ai, bk ), äëÿ
êîòîðûõ âûïîëíÿþòñÿ äâà óñëîâèÿ:
• ∀ai ∈ A ∃bk ∈ B òàê, ÷òî f (ai) = bk; ∀bj ∈
∈ B ∃al ∈ A òàê, ÷òî f (al) = bj: âñå ýëåìåíòû
ìíîæåñòâ ïîïàëè õîòÿ áû â îäíó èç ïàð;
Ðèñ. 1.6. Ãðàôèê íåïðå• êàæäûé ýëåìåíò ai è bi ïîïàë òîëüêî â
ðûâíîãî áèåêòèâíîãî îäíó èç ïàð.
îòîáðàæåíèÿ y = f (x)
Åñëè ìåæäó ýëåìåíòàìè ìíîæåñòâ óñòàíîâëåíî âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå,
òî ýòè ìíîæåñòâà èìåþò îäèíàêîâîå êîëè÷åñòâî ýëåìåíòîâ. Ãîâîðÿò, ÷òî îíè ðàâíîñèëüíû, ðàâíîìîùíû, èëè ýêâèâàëåíòíû. Íà
ðèñ. 1.7 ïîêàçàíû ïðèìåðû ïðÿìîãî è îáðàòíîãî áèåêòèâíîãî îòîáðàæåíèÿ.
Ðàññìîòðèì ïðèìåðû îòîáðàæåíèé.
1. Îòîáðàæåíèå γ: a → a / 2, ãäå a ∈ ¢, ÿâëÿåòñÿ áèåêöèåé ìíîæåñòâà ¢ öåëûõ ÷èñåë íà íåêîòîðîå ìíîæåñòâî B. Òàáëè÷íîå çàäàíèå òàêîé áèåêöèè ìîæíî ïðåäñòàâèòü â âèäå òàáë. 1.3.
Èç òàáë. 1.3 âèäíî, ÷òî êàæäîìó ýëåìåíòó ìíîæåñòâà ¢ ñòàâèòñÿ â ñîîòâåòñòâèå åäèíñòâåííûé ýëåìåíò ìíîæåñòâà B. È íàîáîðîò, êàæäîìó ýëåìåíòó ìíîæåñòâà B ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå åäèíñòâåííûé ýëåìåíò èç ¢. Îáðàòíîå îòîáðàæåíèå ìîæíî
ïðåäñòàâèòü àíàëèòè÷åñêè: γ−1: a → 2a è òàáëè÷íî, ïîìåíÿâ ìåñòàìè ñòðîêè â òàáëèöå.
2. Êàæäîìó äåéñòâèòåëüíîìó ÷èñëó ïîñòàâèì â ñîîòâåòñòâèå åãî
êâàäðàò. Îòîáðàæåíèå õ → õ2 íå ÿâëÿåòñÿ âçàèìíî-îäíîçíà÷íûì
ñîîòâåòñòâèåì, òàê êàê äëÿ ëþáîãî îáðàçà y = õ2 ìîæíî íàéòè äâà
ïðîîáðàçà â îáëàñòè îïðåäåëåíèÿ: x = + y è x = − y .
3. Àíãëî-ðóññêèé ñëîâàðü óñòàíàâëèâàåò ñîîòâåòñòâèå ìåæäó
ìíîæåñòâàìè ñëîâ àíãëèéñêîãî è ðóññêîãî ÿçûêîâ. Òàêîå ñîîòâåòñòâèå íå ÿâëÿåòñÿ îäíîçíà÷íûì, òàê êàê êàæäîìó àíãëèéñêîìó
ïîíÿòèþ ñîîòâåòñòâóþò ðàçëè÷íûå âàðèàíòû ïåðåâîäà íà ðóññêèé
ÿçûê, è íàîáîðîò.
4. Ðàçëè÷íûå âèäû êîäèðîâàíèÿ (àçáóêà Ìîðçå, ïðåäñòàâëåíèå
÷èñåë â ðàçëè÷íûõ ñèñòåìàõ ñ÷èñëåíèÿ, øèôðîâàííûå ñîîáùåÒ à á ë è ö à 1.3
Òàáëè÷íîå çàäàíèå áèåêöèè γ : a → a/2
24
x
¾
−2
−1
0
1
2
¾
γ(x)
¾
−1
−0,5
0
0,5
1
¾
Ðèñ. 1.7. Èëëþñòðàöèÿ áèåêöèè:
à — ïðÿìîå îòîáðàæåíèå À â Â; á — îáðàòíîå îòîáðàæåíèå  â À
íèÿ) ÿâëÿþòñÿ ÷àùå âñåãî ïðèìåðàìè âçàèìíî-îäíîçíà÷íîãî ñîîòâåòñòâèÿ ìåæäó ìíîæåñòâàìè.
Êîìïîçèöèÿ ôóíêöèé. Ïóñòü çàäàíû îòîáðàæåíèÿ f1: A → B è
f2: B → C. Îòîáðàæåíèå f : A → C, ïðè êîòîðîì êàæäîìó ýëåìåíòó õ ∈ A ñîîòâåòñòâóåò îïðåäåëåííûé ýëåìåíò z ∈C, òàêîé, ÷òî
z = f2(y), ãäå y = f1(x), íàçûâàåòñÿ ïðîèçâåäåíèåì, êîìïîçèöèåé,
èëè ñóïåðïîçèöèåé îòîáðàæåíèé f1 è f2. Òàêæå ÷àñòî óïîòðåáëÿþò
ñèíîíèì «ñëîæíàÿ ôóíêöèÿ». Îáîçíà÷àåòñÿ êîìïîçèöèÿ äâóõ îòîáðàæåíèé f1 è f2 êàê f = f2 o f1, ïðè÷åì èìåííî â òàêîì ïîðÿäêå,
ïîñêîëüêó ïî îïðåäåëåíèþ äîëæíî áûòü z = f (x) = ( f2 o f1)(x) =
= f2( f1(x)), ò. å. ñíà÷àëà ïðîèçâîäèòñÿ ïåðâîå îòîáðàæåíèå (ñòîèò
ñïðàâà è äåéñòâóåò íà àðãóìåíò x), çàòåì âòîðîå (ñëåâà).
Ïóñòü h = g o f. Ðàññìîòðèì ñíà÷àëà çíà÷åíèå ôóíêöèè h(x)
ïðè x = x0:
f (x0) = y0, f îïðåäåëåíà â òî÷êå x0 è îòîáðàæàåò åå â òî÷êó y0;
z0 = g (y0) = g ( f (x0)), g îïðåäåëåíà â òî÷êå y0 è îòîáðàæàåò åå â
òî÷êó z0.
Òàêèì îáðàçîì, ôóíêöèÿ h «òðàíçèòîì» ÷åðåç òî÷êó y0 îòîáðàæàåò òî÷êó x0 â òî÷êó z0: h(x0) = g (y0) = g ( f (x0)).
Ñ ïîìîùüþ òåðìèíîâ è ñèìâîëîâ ñîîòâåòñòâèé ìåæäó ìíîæåñòâàìè òàêóþ çàâèñèìîñòü ìîæíî èçîáðàçèòü â âèäå ñõåìû
(ðèñ. 1.8).
Òåïåðü ðàññìîòðèì âñþ ñîâîêóïíîñòü òî÷åê èç îáëàñòè îïðåäåëåíèÿ ïåðâîé ôóíêöèè f. Çäåñü âñå ïðèâåäåííûå ôîðìóëû äîëæíû
âûïîëíÿòüñÿ â êàæäîé òî÷êå. Íà ðèñ. 1.9 ñ ïîìîùüþ êðóãîâ Ýéëåðà ïîêàçàíî ïðîèçâåäåíèå äâóõ îòîáðàæåíèé f1 è f2, êàæäîå èç
êîòîðûõ ÿâëÿåòñÿ èíúåêöèåé. Ïóíêòèðíûìè ëèíèÿìè èçîáðàæåíà ñâÿçü îáðàçîâ è ïðîîáðàçîâ. Îáëàñòü îïðåäåëåíèÿ ôóíêöèè
f 1 D ( f1) = A, îáëàñòü çíà÷åíèé ôóíêöèè
f1 E (f1) = H ⊂ B, îáëàñòü îïðåäåëåíèÿ ôóíêöèè f2 D ( f2) = B, îáëàñòü çíà÷åíèé ôóíêöèè f2 E ( f2) = G ⊂ C, îáëàñòü çíà÷åíèé ôóíêöèè f2 o f1 E ( f2 o f1) = f2 o f1(A) = F ⊂ G.
Ðèñ. 1.8. Ñõåìà ñóïåðÐàññìîòðèì ñóïåðïîçèöèþ ÷èñëîâûõ ïîçèöèè ôóíêöèè h =
ôóíêöèé. Ïóñòü äàíû ïðîèçâîëüíûå ÷èñëî= g o f â òî÷êå x0
25
Ðèñ. 1.9. Ñõåìà, èëëþñòðèðóþùàÿ êîìïîçèöèþ äâóõ èíúåêöèé
âûå ôóíêöèè f (x), g (x): ¡ → ¡. Ñóïåðïîçèöèåé g o f ôóíêöèé f (x)
è g (x) áóäåò íîâàÿ ôóíêöèÿ h(x), äëÿ êîòîðîé:
• îáëàñòü îïðåäåëåíèÿ h(x) ñîñòîèò èç ÷èñåë x0, äëÿ êîòîðûõ
f (x0) ïðèíàäëåæèò îáëàñòè îïðåäåëåíèÿ g(x): D (h(x)) = {x0 f(x0) ∈
∈ D (g(x))};
• çíà÷åíèå ôóíêöèè h(x) ∀x0 ∈ D (h(x)) ñâÿçàíî ñî çíà÷åíèÿìè
f (x) è g (x) ðàâåíñòâîì h(x0) = g ( f (x0)).
Òàêèì îáðàçîì, òîëüêî ìíîæåñòâî D (g(x)) I E ( f (x)) áóäåò äàëåå îòîáðàæàòüñÿ ïîñðåäñòâîì ôóíêöèè g, ò. å. áóäåò ïîëíûì ïðîîáðàçîì g−1(E (h)).
Ðàññìîòðèì ïðèìåðû êîìïîçèöèé.
1. Ïóñòü f (x) = ñîs x, g (x) = ln x, òîãäà h(x) = g o f. Ðàçáåðåì
ïîäðîáíåå. Êàæäîìó õ ñîîòâåòñòâóåò çíà÷åíèå õ → f (x) = ñîs x.
Äàëåå, êàæäîìó ÷èñëó ó ñîîòâåòñòâóåò ó → g (ó) = ln ó. Íî ó = ñîs x,
ïîýòîìó, ïîäñòàâëÿÿ çíà÷åíèå ó ÷åðåç õ, ïîëó÷àåì g (ó) = ln ó =
= ln (ñîs x) = g ( f (x)) = h(x). Èòàê, h(x): õ → ln (ñîs x). Íàéäåì îáëàñòü îïðåäåëåíèÿ è çíà÷åíèÿ ýòîé ôóíêöèè: D ( f ) = ¡, E ( f ) =
= [−1, 1], D (g) = (0, +∞), E (g) = ¡. Ïîëíûì ïðîîáðàçîì g áóäåò
G = E ( f ) I D (g) = [−1, 1] I (0, +∞) = (0, 1]. Ïîëíûì îáðàçîì òîãäà
áóäåò (òàê êàê ln — ìîíîòîííàÿ ôóíêöèÿ) H = g (G ) = (−∞, 0].
Îáëàñòüþ îïðåäåëåíèÿ áóäåò ïîëíûé ïðîîáðàç ìíîæåñòâà G —
ìíîæåñòâî I = f −1(G ) = {x 0 < cos x ≤ 1} = (−π/2 + 2πn; π/2 + 2πn],
n ∈ ¢.
Äëÿ ñðàâíåíèÿ íàïèøåì â ÿâíîì âèäå îòîáðàæåíèå t(x) = f o g.
Àíàëîãè÷íî ïðåäûäóùèì ðàññóæäåíèÿì ïîëó÷èì t(x): õ → ños (ln õ).
Äëÿ òîãî ÷òîáû äîêàçàòü íåòîæäåñòâåííîñòü äâóõ îòîáðàæåíèé, äîñòàòî÷íî óêàçàòü òàêîå õ, ÷òî t(x) ≠ h(x). Íàïðèìåð, t(1) = ños (ln 1) =
= ños 0 = 1. Îäíàêî h(1) = ln (ñîs 1) ≈ −0,62.
Ïîýòîìó ñóïåðïîçèöèÿ äâóõ ôóíêöèé çàâèñèò îò ïîðÿäêà çàïèñè, ò. å. íå ïîä÷èíÿåòñÿ ïåðåìåñòèòåëüíîìó çàêîíó.
Ñëåäóåò ñðàçó óêàçàòü ðàñïðîñòðàíåííóþ îøèáêó: çàïèñü âèäà
s (x) = f (x) ⋅ g(x), ãäå çíàê « ⋅ » — óìíîæåíèå â ¡ (íàïðèìåð, (ñîs x) ×
× (ln x)), íå ÿâëÿåòñÿ êîìïîçèöèåé èëè ñóïåðïîçèöèåé ýòèõ ôóíêöèé. Äåëî â òîì, ÷òî ïðîèçâåäåíèå ôóíêöèé îïðåäåëåíî íà ìíîæåñòâå ôóíêöèé, à âûðàæåíèå f(x) ⋅ g(x), çíàêîìîå ñî øêîëû, îáî26
çíà÷àåò ïðîèçâåäåíèå çíà÷åíèé êàæäîé èç ôóíêöèé â êàæäîé êîíêðåòíîé òî÷êå (x = x0). Äëÿ ñðàâíåíèÿ íàéäåì s (x) = (ñîs x) ⋅ (ln x)
ïðè x0 = 1: s (1) = (ñîs 1) ⋅ (ln 1) = 0, ò. å. ýòî çíà÷åíèå íå ñîâïàäàåò
ñ óæå íàéäåííûìè çíà÷åíèÿìè t(1) è h(1).
Ñëîæíûå ôóíêöèè ïðåäñòàâëÿþò ñîáîé êîìïîçèöèþ íåñêîëüêèõ ïðîñòûõ ôóíêöèé. Íî âñÿêàÿ ñëîæíàÿ ôóíêöèÿ, çàäàííàÿ
÷åðåç áîëåå ïðîñòûå, ðàçëàãàåòñÿ â ïðîèçâåäåíèå îòîáðàæåíèé,
ò.å. ìîæåò áûòü âûðàæåíà àíàëèòè÷åñêè. Äëÿ ëþáûõ îòîáðàæåíèé f,
g, h ñïðàâåäëèâî ãðóïïîâîå ñâîéñòâî áèíàðíîé îïåðàöèè êîìïîçèöèè: f o (g o h) = (f o g) o h, íàçûâàåìîå ñî÷åòàòåëüíûì çàêîíîì,
ò. å. äëÿ ëþáîãî õ èç îáëàñòè îïðåäåëåíèÿ âûïîëíÿåòñÿ f (g (h(õ))) =
= (f o g)(h(õ)). Ýòî ðàâåíñòâî ñïðàâåäëèâî äëÿ òåõ ýëåìåíòîâ èç D (h),
äëÿ êîòîðûõ f ( g (h(õ))) = (f o g)h(õ) èìååò ñìûñë, ò. å. îïðåäåëåíû
h(x), g (h(õ)), f ( g (h(õ))) è h(õ) ∈ D (f o g).
2. Ïóñòü A — ýòî ìíîæåñòâî ëþäåé. Îáîçíà÷èì ÷åðåç f1 îòîáðàæåíèå ìíîæåñòâà A â A, ïðè êîòîðîì êàæäîìó ÷åëîâåêó ñòàâèòñÿ
â ñîîòâåòñòâèå åãî ìàòü, à ÷åðåç f2 — åãî îòåö. Òîãäà ñóïåðïîçèöèè
îòîáðàæåíèé f1 è f2 êàæäîìó ÷åëîâåêó ñòàâÿò â ñîîòâåòñòâèå:
g1 = f2 o f1 — äåä ïî ìàòåðèíñêîé ëèíèè (îòåö ìàòåðè);
g2 = f1 o f2 — áàáóøêà ïî îòöîâñêîé ëèíèè (ìàòü îòöà);
g3 = f1 o f1 — áàáóøêà ïî ìàòåðèíñêîé ëèíèè (ìàòü ìàòåðè);
g4 = f2 o f2 — äåä ïî îòöîâñêîé ëèíèè (îòåö îòöà).
? Êàêèìè îòîáðàæåíèÿìè — èíúåêòèâíûìè, ñþðúåêòèâíûìè èëè áèåêòèâíûìè — ÿâëÿþòñÿ îòîáðàæåíèÿ f2, f1 è g1 — g4?
Îòîáðàæåíèå å: A → A íàçûâàåòñÿ òîæäåñòâåííûì (åäèíè÷íûì),
åñëè êàæäîìó àðãóìåíòó îíî ñòàâèò â ñîîòâåòñòâèå ñåáÿ. Î÷åâèäíî, òàêîå îòîáðàæåíèå ìîæíî çàäàòü íà ëþáîì íåïóñòîì ìíîæåñòâå. Åñëè å (õ) = õ, òî E (e) = D (e) = A. Î÷åâèäíî, ÷òî îòîáðàæåíèå, îáðàòíîå åäèíè÷íîìó, òàêæå åäèíè÷íîå. Ðàññìîòðèì ïðîèçâîëüíóþ ôóíêöèþ f : A → C. Ïîñêîëüêó è íà A, è íà C ìîæíî
ââåñòè òîæäåñòâåííîå îòîáðàæåíèå, òî, áåðÿ êîìïîçèöèþ îòîáðàæåíèé å è f, ïîëó÷èì äâà îòîáðàæåíèÿ f1 = å o f è f2 = f o e.
Äîêàæåì, ÷òî, õîòÿ â ïåðâîì ñëó÷àå å îïðåäåëåíî íà C, à âî âòîðîì — íà A, îòîáðàæåíèÿ f2 è f1 ðàâíû. Êàê ãîâîðèëîñü, ðàâåíñòâî
ôóíêöèé îïðåäåëÿåòñÿ äåéñòâèåì èõ íà âñåõ ýëåìåíòàõ. Ïðîâåðèì:
∀õ ∈ A f1(õ) = å ( f (õ)) = f (õ); è f2 = f ( e (õ)) = f (õ). Ïîýòîìó ôóíêöèè ðàâíû. Ïîëó÷åííîå ðàâåíñòâî ïîçâîëÿåò ñäåëàòü âûâîä, ÷òî
äëÿ òàêîé êîìïîçèöèè ëþáîé ôóíêöèè ñ òîæäåñòâåííîé ñïðàâåäëèâ ïåðåìåñòèòåëüíûé çàêîí: f o e = e o f.
Åäèíè÷íîå îòîáðàæåíèå, åñòåñòâåííî, ïîëó÷àåòñÿ êàê êîìïîçèöèÿ ïðîèçâîëüíîé ôóíêöèè f : A → B è åé îáðàòíîé: e = f −1 o f. Äåéñòâèòåëüíî, ∀õ ∈ A f −1( f (õ)) = õ = e (õ). Íî ýòî ñïðàâåäëèâî, òîëüêî åñëè îáðàòíîå îòîáðàæåíèå ÿâëÿåòñÿ îäíîçíà÷íûì. Íàïðèìåð,
ïðè f (õ) = åx, x ∈ ¡, f −1(õ) = ln (åx).  ïðîòèâíîì ñëó÷àå, åñëè ∃ x,
27
y ∈ A òàêèå, ÷òî x ≠ y, íî f (x) = f (y), îêàæåòñÿ íå òîëüêî f −1( f (õ)) =
= õ = e(õ), íî è f −1( f (õ)) = y ≠ e(õ). Íàïðèìåð, x = x ≠ x . Ïîýòîìó ìîæíî îãðàíè÷èòü îáëàñòü îïðåäåëåíèÿ òàê, ÷òîáû ïðÿìîå è
îáðàòíîå îòîáðàæåíèÿ áûëè âçàèìíî-îäíîçíà÷íûìè. Òîãäà áóäåò
ñïðàâåäëèâî e = f −1 o f = f o f −1.
Ðàññìîòðèì ïðèìåðû òîæäåñòâåííûõ îòîáðàæåíèé.
( )
1. x = x = x , x ∈ [0, +∞).
2. x = ln (åx), x ∈ ¡ è x = eln x, x ∈ (0, +∞).
3. arcsin (sin x) = sin (arcsin x) = x, x ∈ [−π/2, π/2].
Ñóïåðïîçèöèÿ îáëàäàåò âàæíûì ñâîéñòâîì: ÷àñòî, åñëè ôóíêöèè f (x) è g (x) ïðèíàäëåæàò îïðåäåëåííîìó êëàññó, òî è èõ ñóïåðïîçèöèÿ (f o g)(x) ïðèíàäëåæèò ýòîìó êëàññó.
Íàïðèìåð, ïóñòü f (x) = 9x + 1, g (x) = 5x − 2 — ëèíåéíûå îòîáðàæåíèÿ, îïðåäåëåííûå íà ¡. Ðàññìîòðèì z = (g o f ). Òîãäà ∀õ0
èìååì: z(x0) = g (y0) = g ( f (x0)) = 5(9x0 + 1) − 2 = 45x0 + 5 − 2 = 45x0 + 3.
Ðåçóëüòàò òàêæå ÿâëÿåòñÿ ëèíåéíîé ôóíêöèåé.
 îáùåì âèäå äëÿ ëèíåéíûõ ôóíêöèé f (x) = ax + b è g (x) = cx + d
ñóïåðïîçèöèÿ h(x) = (g o f )(x) = c(ax + b) + d = (ac)x + bc + d
ÿâëÿåòñÿ ëèíåéíîé ôóíêöèåé.
Ïîíÿòèå ñóïåðïîçèöèè îòîáðàæåíèé è ñîîòâåòñòâèé èãðàåò âàæíóþ ðîëü, òàê êàê äàåò âîçìîæíîñòü óñòàíîâëåíèÿ îïðåäåëåííîé
çàâèñèìîñòè îäíîãî îáúåêòà Z îò äâóõ äðóãèõ Õ è Y.
1.4. Êëàññèôèêàöèÿ ìíîæåñòâ. Ìîùíîñòü ìíîæåñòâà
— Ñêàæèòå, ïîæàëóéñòà, êóäà ìíå
îòñþäà èäòè?
— Ýòî âî ìíîãîì çàâèñèò îò òîãî,
êóäà òû õî÷åøü ïðèéòè, — îòâåòèë Êîò.
— Äà ìíå ïî÷òè âñå ðàâíî, — íà÷àëà Àëèñà.
— Òîãäà âñå ðàâíî, êóäà èäòè, —
ñêàçàë Êîò.
— Ëèøü áû ïîïàñòü êóäà-íèáóäü, —
ïîÿñíèëà Àëèñà.
— Íå áåñïîêîéñÿ, êóäà-íèáóäü òû
îáÿçàòåëüíî ïîïàäåøü, — êîíå÷íî,
åñëè íå îñòàíîâèøüñÿ íà ïîëïóòè.
Ë. Êýððîëë
Îñíîâíîé õàðàêòåðèñòèêîé ìíîæåñòâ ÿâëÿåòñÿ êîëè÷åñòâî ýëåìåíòîâ, ñîäåðæàùèõñÿ â ýòîì ìíîæåñòâå.
Êàê èçâåñòíî, ÷èñëî ýëåìåíòîâ ìíîæåñòâà M íàçûâàåòñÿ åãî
ìîùíîñòüþ è îáîçíà÷àåòñÿ |M |. Ìíîæåñòâà A è B íàçûâàþòñÿ ýêâè28
âàëåíòíûìè, èëè ðàâíîìîùíûìè, A ∼ B, åñëè ìåæäó èõ ýëåìåíòàìè
ìîæíî óñòàíîâèòü âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå (áèåêöèþ).
Òîãäà |A| = |B |.
Ïóñòü äàíû äâà ìíîæåñòâà A è B.
? Êàê ñðàâíèòü ýòè ìíîæåñòâà? Êàêîâû êðèòåðèè îöåíêè ìíîæåñòâ?
Åñëè îíè êîíå÷íû, òî ñðàâíèâàþò èõ ìîùíîñòè, ò. å. êîëè÷åñòâî ýëåìåíòîâ ýòèõ ìíîæåñòâ. Îáîçíà÷èì ÷åðåç A, B, C, D ñîîòâåòñòâåííî ìíîæåñòâà áóêâ ñëîâ «êðîò», «êîðò», «êðàí» è «ðîò». Òîãäà |A| = |B | = |C | = 4, |D | = 3. Îòñþäà äåëàåì âûâîä, ÷òî A, B è C èìåþò
ðàâíûå ìîùíîñòè, à ìîùíîñòü D ìåíüøå, ÷åì, íàïðèìåð, ìîùíîñòü A: |D | < |A|, òàê êàê 3 < 4. Ìíîæåñòâà A, B è C ðàâíîìîùíû.
Ïîíÿòèå «ðàâíîìîùíûå ìíîæåñòâà» íå îçíà÷àåò, ÷òî îíè îáÿçàòåëüíî ðàâíû. Íàïðèìåð, ñðåäè ïåðå÷èñëåííûõ ðàâíîìîùíûõ ìíîæåñòâ A, B è C ìíîæåñòâà A è B ðàâíû, òàê êàê îíè ñîñòîÿò èç
îäíèõ è òåõ æå ýëåìåíòîâ, à ìíîæåñòâà A è C ðàçëè÷íû. Ãîâîðÿò,
÷òî òàêèå ðàâíîìîùíûå, íî íå ðàâíûå ìíîæåñòâà ýêâèâàëåíòíû
ìåæäó ñîáîé.
Ýòàëîíîì äëÿ ñðàâíåíèÿ ìíîæåñòâ ñëóæèò íàòóðàëüíûé ðÿä
÷èñåë. Ïîýòîìó âñå ÷èñëîâûå ïîñëåäîâàòåëüíîñòè, ñîäåðæàùèå
ðàçëè÷íûå ýëåìåíòû, ýêâèâàëåíòíû íàòóðàëüíîìó ðÿäó ÷èñåë,
÷òî âèäíî ïî èíäåêñàì èõ ÷ëåíîâ. Åñëè f : A → B — èíúåêöèÿ
ìíîæåñòâà A â B, áóäåò ñïðàâåäëèâî íåðàâåíñòâî | A | ≥ |B |, à åñëè
f : A → B — ñþðúåêöèÿ ìíîæåñòâà A íà B, òî ñïðàâåäëèâî íåðàâåíñòâî | A | ≤ |B |.
Ìíîæåñòâà ìîæíî êëàññèôèöèðîâàòü â çàâèñèìîñòè îò êîëè÷åñòâà ýëåìåíòîâ (èõ ìîùíîñòè) è õàðàêòåðà ñîîòâåòñòâèÿ íàòóðàëüíîìó ðÿäó ÷èñåë (ðèñ. 1.10).
Ìíîæåñòâî, ñîäåðæàùåå êîíå÷íîå ÷èñëî ýëåìåíòîâ, íàçûâàåòñÿ êîíå÷íûì. Íàïðèìåð, êîíå÷íûì ÿâëÿåòñÿ ìíîæåñòâî îäíîçíà÷íûõ íàòóðàëüíûõ ÷èñåë {1, 2, 3, 4, 5, 6, 7, 8, 9}. Ìîùíîñòü
êîíå÷íîãî ìíîæåñòâà èç n ýëåìåíòîâ ðàâíà n. Ïóñòîå ìíîæåñòâî ∅
ïî îïðåäåëåíèþ íå ñîäåðæèò ýëåìåíòîâ. Îíî òàêæå ÿâëÿåòñÿ êîíå÷íûì è èìååò ìîùíîñòü, ðàâíóþ íóëþ, ò. å. |∅| = 0. Ìíîæåñòâî,
íå ÿâëÿþùååñÿ êîíå÷íûì, íàçûâàåòñÿ áåñêîíå÷íûì.
? Íî êàê ñðàâíèòü áåñêîíå÷íûå ìíîæåñòâà? Âåäü äëÿ íèõ íåëüçÿ óêàçàòü òî÷íîå ÷èñëî ýëåìåíòîâ!
Áåñêîíå÷íîå ìíîæåñòâî, ýêâèâàëåíòíîå ìíîæåñòâó íàòóðàëüíûõ
÷èñåë ¥, íàçûâàåòñÿ ñ÷åòíûì. Ãîâîðÿò, ÷òî âñå ýëåìåíòû ñ÷åòíîãî
ìíîæåñòâà ìîæíî ïðîíóìåðîâàòü.  ïðîòèâíîì ñëó÷àå áåñêîíå÷íîå
ìíîæåñòâî áóäåò íåñ÷åòíûì. Ã. Êàíòîð (1878) äîêàçàë, ÷òî íåñ÷åòíî ìíîæåñòâî òî÷åê, ðàñïîëîæåííûõ íà îòðåçêå ìåæäó 0 è 1. Ïî
îïðåäåëåíèþ Á. Áîëüöàíî (1837) è Ð. Äåäåêèíäà (1887) ìíîæåñòâî íàçûâàåòñÿ áåñêîíå÷íûì, åñëè îíî ðàâíîìîùíî îäíîìó èç
ñâîèõ ñîáñòâåííûõ ïîäìíîæåñòâ. Ìîæíî äîêàçàòü ýêâèâàëåíòíîñòü
29
Ðèñ. 1.10. Êëàññèôèêàöèÿ ìíîæåñòâ â çàâèñèìîñòè îò èõ ìîùíîñòè
è õàðàêòåðà ñîîòâåòñòâèÿ íàòóðàëüíîìó ðÿäó ÷èñåë
ýòèõ îïðåäåëåíèé äàííîìó íàìè, íî â ðàìêàõ íåêîòîðûõ äîïóùåíèé (ïîäðîáíåå î ïîäîáíûõ äîêàçàòåëüñòâàõ ñì. â ãë. 5).
Ìíîæåñòâî A ìîæíî îòîáðàçèòü âî ìíîæåñòâî B ðàçëè÷íûìè
ñïîñîáàìè. Íàéäåì, ñêîëüêî ñóùåñòâóåò ðàçëè÷íûõ îòîáðàæåíèé
A â B.
Ïóñòü A è B êîíå÷íû, ïðè÷åì | A | = n, à |B | = k. Êàæäûé èç n
àðãóìåíòîâ ìîæåò íåçàâèñèìî îòîáðàçèòüñÿ â ëþáîé èç k ýëåìåíòîâ B. Ïîñêîëüêó õàðàêòåð ìíîæåñòâà B íå âëèÿåò íà ÷èñëî ôóíêöèé, âîçüìåì äëÿ óäîáñòâà çàïèñè ñèìâîëîâ ìíîæåñòâî B = {1,
2, ¾, k}. Çàäàäèì ôóíêöèþ g òàêèì îáðàçîì, ÷òî íà ïåðâîì ìåñòå
ñòîèò g (a1), ¾, íà n-ì g (an). Òàêèì îáðàçîì, ôóíêöèÿ ìîæåò ìåíÿòüñÿ ïî n «íàïðàâëåíèÿì» (ïîñëåäíèå äâà — â ïëîñêîñòè ëèñòà)
è ïðèíèìàòü ëþáûå èç k çíà÷åíèé. Ïîýòîìó âñåãî òàêèõ çàïèñåé
ìîæåò áûòü k14243
⋅ k ⋅ K ⋅ k = k n . Ýòî è åñòü èñêîìîå ÷èñëî ôóíêöèé.
n
(1, 1, ¾, 1, 1, 1)
(1, 1, ¾, 1, 1, 2)
¾
(1, 1, ¾, 1, 1, k)
30
(1, 1, ¾, 1, 2, 1)
(1, 1, ¾, 1, 2, 2)
¾
(1, 1, ¾, 1, 2, k)
¾
¾
¾
¾
(1, 1, ¾, 1, k, 1)
(1, 1, ¾, 1, 2, 2)
¾
(1, 1, ¾, 1, 2, k)
Ýòó æå âàæíóþ ôîðìóëó ìîæíî äîêàçàòü, èñïîëüçóÿ äëÿ êàæäîãî ýëåìåíòà ìíîæåñòâà A îòäåëüíûé ñèìâîë (ïîäðîáíåå îá àëôàâèòàõ ñì. â ãë. 6).
Áóëåàíîì ìíîæåñòâà M íàçîâåì ìíîæåñòâî âñåõ åãî ïîäìíîæåñòâ, êîòîðîå îáîçíà÷àåòñÿ 2M, ò. å. 2M = {A A ⊂ M }. Ìîæíî äîêàçàòü, ÷òî äëÿ êîíå÷íîãî ìíîæåñòâà M ìîùíîñòü áóëåàíà |2M | = 2|M |.
 ÷àñòíîñòè, ìíîæåñòâî âñåõ ïîäìíîæåñòâ ëþáîãî êîíå÷íîãî
ìíîæåñòâà, ñîñòîÿùåãî èç n ýëåìåíòîâ, ÿâëÿåòñÿ êîíå÷íûì ìíîæåñòâîì, ñîñòîÿùèì èç 2n ýëåìåíòîâ. Òàê êàê ìíîæåñòâî öåëûõ
÷èñåë ¢ ñ÷åòíî, òî íàäî ïîêàçàòü, ÷òî îíî ýêâèâàëåíòíî íàòóðàëüíîìó ðÿäó ÷èñåë, ò. å. íàäî ïðîíóìåðîâàòü âñå åãî ýëåìåíòû.
? Íî êàê ýòî ñäåëàòü, åñëè ÷èñëîâàÿ ïðÿìàÿ áåñêîíå÷íà è âëåâî îò íóëÿ,
è âïðàâî: (¢ = { , −3, −2, −1, 0, 1, 2, 3, })?
Äëÿ óñòàíîâëåíèÿ ñîîòâåòñòâèÿ ìåæäó öåëûìè è íàòóðàëüíûìè ÷èñëàìè áóäåì ÷åðåäîâàòü ïîëîæèòåëüíûå è îòðèöàòåëüíûå
÷èñëà, íà÷èíàÿ îò íóëÿ. Òîãäà èíäåêñ ýëåìåíòîâ ïîëó÷åííîé ïîñëåäîâàòåëüíîñòè óêàçûâàåò íà ñîîòâåòñòâóþùåå íàòóðàëüíîå ÷èñëî:
a1 = 0, a2 = 1, a3 = −1, a4 = 2, a5 = −2, a6 = 3, a7 = −3, ¾, a2n = n,
a2n + 1 = −n¾
Äëÿ êîíå÷íûõ ìíîæåñòâ ñïðàâåäëèâî óòâåðæäåíèå, êîòîðîå
íàçûâàåòñÿ îñíîâíîé òåîðåìîé î êîíå÷íûõ ìíîæåñòâàõ.
Òåîðåìà. Ëþáîå êîíå÷íîå ìíîæåñòâî íå ýêâèâàëåíòíî íèêàêîìó
åãî ñîáñòâåííîìó ïîäìíîæåñòâó, êðîìå ñàìîãî ñåáÿ.
Ñëåäñòâèå. Âñÿêîå íåïóñòîå êîíå÷íîå ìíîæåñòâî ýêâèâàëåíòíî
îäíîìó è òîëüêî îäíîìó îòðåçêó íàòóðàëüíîãî ðÿäà ÷èñåë (1, ¾, n).
Òîãäà ìîùíîñòü êîíå÷íîãî ìíîæåñòâà ñîâïàäàåò ñ êîëè÷åñòâîì
åãî ýëåìåíòîâ. Íàïðèìåð, ìîùíîñòü ìíîæåñòâà ñòîðîí ïÿòèóãîëüíèêà ðàâíà 5.
Èç ëþáîãî áåñêîíå÷íîãî ìíîæåñòâà ìîæíî âûäåëèòü ñ÷åòíîå
ïîäìíîæåñòâî. Òàê, ñ÷åòíûìè ÿâëÿþòñÿ ìíîæåñòâî ¢ öåëûõ ÷èñåë
è ¤ ðàöèîíàëüíûõ ÷èñåë. Íî ìíîæåñòâî ¡ äåéñòâèòåëüíûõ ÷èñåë
íåñ÷åòíî. Ñ÷åòíûì áóäåò è ìíîæåñòâî êâàäðàòîâ íàòóðàëüíûõ ÷èñåë {1, 4, 9, 16, ¾}, òàê êàê êàæäîìó êâàäðàòó ìîæíî ïîñòàâèòü â
ñîîòâåòñòâèå åäèíñòâåííîå íàòóðàëüíîå ÷èñëî n, ñîîòâåòñòâóþùåå åãî ïîðÿäêîâîìó íîìåðó.
Ïîñêîëüêó äëÿ áåñêîíå÷íûõ ìíîæåñòâ íåëüçÿ óêàçàòü ÷èñëî,
êîòîðîå ÿâëÿåòñÿ åãî ìîùíîñòüþ, òî áóäåì èõ ñðàâíèâàòü ïî ýêâèâàëåíòíûì èì îñíîâíûì ìíîæåñòâàì ¥ è ¡.
Âñÿêîå áåñêîíå÷íîå ìíîæåñòâî, ðàâíîñèëüíîå ìíîæåñòâó äåéñòâèòåëüíûõ ÷èñåë, íàçûâàåòñÿ ìíîæåñòâîì ìîùíîñòè êîíòèíóóìà (îò ëàò. continuum — íåïðåðûâíûé). Ïîýòîìó äëÿ ñðàâíåíèÿ
ìîùíîñòè ìíîæåñòâ ñ ìíîæåñòâîì äåéñòâèòåëüíûõ ÷èñåë ¡ áóäåì óïîòðåáëÿòü óñëîâíîå îáîçíà÷åíèå |¡| êàê ñèìâîë ìîùíîñòè
êîíòèíóóìà.
31
Òàê, ìíîæåñòâî òî÷åê ïðÿìîé íåñ÷åòíî è èìååò ìîùíîñòü êîíòèíóóìà.
? Ìîæåò ëè ÷àñòü áûòü ýêâèâàëåíòíîé
öåëîìó?
Ñðàâíèì ìîùíîñòè ìíîæåñòâà ¢ —
öåëûõ è ìíîæåñòâà ¤ — ðàöèîíàëüíûõ
Ðèñ. 1.11. Áèåêöèÿ ìåæäó
÷èñåë. Òàê êàê îáà îíè ñ÷åòíûå, òî èìåñðåäíåé ëèíèåé è îñíîþò îäèíàêîâóþ ìîùíîñòü. Íî ¢ ⊂ ¤, è
âàíèåì òðåóãîëüíèêà
ïîëó÷àåòñÿ, ÷òî ÷àñòü (¢) ýêâèâàëåíòíà
öåëîìó (¤)!
Ýòîò óäèâèòåëüíûé ïàðàäîêñàëüíûé âûâîä ïðèâåë â çàìåøàòåëüñòâî ìàòåìàòèêîâ íà ðóáåæå XIX è XX ââ. È ýòî íå åäèíñòâåííûé ïàðàäîêñ òåîðèè ìíîæåñòâ.
? Ìîæåò ëè îòðåçîê áûòü ýêâèâàëåíòíûì ñâîåé ïîëîâèíå?
Åùå äðåâíåãðå÷åñêèé ìûñëèòåëü Çåíîí îáðàòèë âíèìàíèå íà óäèâèòåëüíûé ôàêò, êîòîðûé ñëåäóåò èç ñðàâíåíèÿ äëèí ñðåäíåé ëèíèè òðåóãîëüíèêà è òîé ñòîðîíû, êîòîðîé ýòà ñðåäíÿÿ ëèíèÿ ïàðàëëåëüíà (ðèñ. 1.11).
Îí ïðîâåë ëó÷è èç âåðøèíû B íà ñòîðîíó ÀÑ è êàæäîé òî÷êå ó îòðåçêà ÀÑ ïîñòàâèë â ñîîòâåòñòâèå òî÷êó õ íà ñðåäíåé ëèíèè. Âèäíî, ÷òî ëó÷è
Çåíîíà çàäàþò îòîáðàæåíèå îòðåçêà ÀÑ â ñðåäíþþ ëèíèþ, ïðè÷åì íåòðóäíî äîêàçàòü åãî áèåêòèâíîñòü. Ñëåäîâàòåëüíî, îäíîé òî÷êå ó ñîîòâåòñòâóåò åäèíñòâåííàÿ òî÷êà õ, è íàîáîðîò. Çíà÷èò, îòðåçêè ýêâèâàëåíòíû
è ìîùíîñòè ìíîæåñòâà òî÷åê, íà íèõ ðàñïîëîæåííûõ, ðàâíû. Íî èç ãåîìåòðèè èçâåñòíî, ÷òî ñðåäíÿÿ ëèíèÿ A′C ′ = ÀÑ / 2. Ïîëó÷àåòñÿ, ÷òî îòðåçîê «ðàâåí» ñâîåé ïîëîâèíå! Àíàëèòè÷åñêè òàêîå îòîáðàæåíèå âûãëÿäèò
åùå ïðîùå: ó = 2õ èëè õ = ó / 2. Çàìåòèì, ÷òî íåëüçÿ ïóòàòü îáîçíà÷åíèå
| |, ñèìâîëèçèðóþùåå äëèíó (ìîäóëü) â àëãåáðå, ñ òàêèì æå çíàêîì,
óïîòðåáëÿåìûì äëÿ îáîçíà÷åíèÿ ìîùíîñòè ìíîæåñòâà.
Åùå áîëåå óäèâèòåëüíûé âûâîä ïîëó÷àåòñÿ ïðè ñðàâíåíèè êîëè÷åñòâà âñåõ òî÷åê îòðåçêà è êâàäðàòà. Ãåîðã Êàíòîð (1845 — 1918) äîêàçàë,
÷òî ìíîæåñòâà òî÷åê îòðåçêà è êâàäðàòà ðàâíîìîùíû. Ìîæíî çàíóìåðîâàòü äàæå òî÷êè ïëîñêîñòè, èìåþùèå öåëî÷èñëåííûå êîîðäèíàòû. Âîñïîëüçóåìñÿ äëÿ ýòîãî ìåòîäîì ðåøåòêè: ïàðå íàòóðàëüíûõ ÷èñåë áóäåì
ñòàâèòü â ñîîòâåòñòâèå íîìåð òàê, êàê ïîêàçàíî â òàáë. 1.4. Ïðè òàêîé
íóìåðàöèè óãîëêîì íè îäíà êëåòêà íå îñòàíåòñÿ áåç íîìåðà. Òàêèì îáðàçîì äîêàçàíà ñ÷åòíîñòü ýòîãî ìíîæåñòâà.
Ò à á ë è ö à 1.4
Ìåòîä ðåøåòêè äëÿ íóìåðàöèè òî÷åê ïëîñêîñòè
1
32
2
3
4
¾
f (1, 4) = 7
¾
1
f (1, 1) = 1
f (1, 2) = 2
f (1, 3) = 4
2
f (2, 1) = 3
f (2, 2) = 5
¾
3
f (3, 1) = 6
¾
¾
¾
Çàäîëãî äî ñîçäàíèÿ ñàìîé òåîðèè ìíîæåñòâ, åùå â XVIII â., âûäàþùèéñÿ ìàòåìàòèê, ÷ëåí Ïåòåðáóðãñêîé àêàäåìèè íàóê, óðîæåíåö Øâåéöàðèè Ëåîíàðä Ýéëåð (1707 — 1783) ïðåäëîæèë èçîáðàæàòü ìíîæåñòâà â
âèäå êðóãîâ. Çàòåì Êàíòîð îòêðûë, ÷òî íå âñå áåñêîíå÷íûå ìíîæåñòâà
èìåþò îäèíàêîâóþ ìîùíîñòü (ò. å. ýêâèâàëåíòíû ìåæäó ñîáîé). Ñóùåñòâóþò ðàçíûå ñòåïåíè ýêâèâàëåíòíîñòè, ïðè÷åì ìîùíîñòü ëþáîãî ñ÷åòíîãî ìíîæåñòâà ìåíüøå ìîùíîñòè íåñ÷åòíîãî. Òàê, ìîùíîñòü ìíîæåñòâà äåéñòâèòåëüíûõ ÷èñåë ¡ áîëüøå ìîùíîñòè ìíîæåñòâà ðàöèîíàëüíûõ ÷èñåë ¤.
? Êàê æå ïðàêòè÷åñêè ñðàâíèâàòü ìíîæåñòâà?
Ïðÿìûì îáðàçîì óñòàíîâèòü ðàâíîìîùíîñòü ìîæíî, åñëè òîëüêî ìíîæåñòâà äåéñòâèòåëüíî ðàâíîìîùíû. Íî ðåàëüíî íå âñåãäà
âîçìîæíî, êàê ó÷èëè â øêîëå, ñîâìåñòèòü è ïðîâåðèòü èõ ðàâåíñòâî.
Äëÿ ýòîãî ìîãóò ïîìî÷ü íåêîòîðûå òåîðåìû î ìîùíîñòè ìíîæåñòâ:
1. Åñëè A ⊂ B, òî |A| ≤ |B |.
2. Åñëè A ∼ C ⊂ B, B ∼ D ⊂ A, òî |A| = |B |.
3. Åñëè K ⊂ M è K íåñ÷åòíî, òî M òîæå íåñ÷åòíî.
? Êàêîé âûâîä ñäåëàëè ó÷åíûå, ñðàâíèâ ìîùíîñòè ìíîæåñòâ ¢ è ¤?
Ñðàâíèòå ìîùíîñòè ìíîæåñòâ òî÷åê åäèíè÷íîãî îòðåçêà è ìíîæåñòâà
òî÷åê åäèíè÷íîãî êâàäðàòà (a = 1). Ãäå áîëüøå òî÷åê — íà îòðåçêå (îäíîìåðíûé êîíòèíóóì) èëè íà ïëîñêîñòè — â êâàäðàòå èëè êðóãå ðàäèóñà r = 1
(äâóìåðíûé êîíòèíóóì)?
Òàê âîçíèêàåò åùå îäèí ïàðàäîêñ òåîðèè ìíîæåñòâ. Íàñ ïîäâîäèò íàøà èíòóèöèÿ, òàê êàê â òåîðèè ìíîæåñòâ íå ñðàáàòûâàþò
àíàëîãèè. Îêàçûâàåòñÿ, ìåæäó îòðåçêîì è êâàäðàòîì ìîæíî óñòàíîâèòü âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå, è ýòè ìíîæåñòâà áóäóò ýêâèâàëåíòíû.
Êðîìå ìàòåìàòè÷åñêèõ ïàðàäîêñîâ, òåîðèÿ ìíîæåñòâ ñîäåðæèò
è îáùåëîãè÷åñêèå ïàðàäîêñû (ðèñ. 1.12).
Ïðîáëåìû áåñêîíå÷íîñòè, äèñêðåòíîñòè è íåïðåðûâíîñòè èíòåðåñîâàëè äðåâíåãðå÷åñêèõ ôèëîñîôîâ íà÷èíàÿ ñ VI â. äî í. ý. Îñíîâíûå ïîëîæåíèÿ òåîðèè ìíîæåñòâ áûëè çàëîæåíû â êîíöå XIX â. Ãåîðãîì Êàíòîðîì (1845 — 1918). Âàæíûå ðåçóëüòàòû â îáëàñòè òåîðèè ìíîæåñòâ áûëè
ïîëó÷åíû Ðè÷àðäîì Äåäåêèíäîì (1831 — 1916). Íî àáñòðàêòíàÿ òåîðèÿ
ìíîæåñòâ âñòðåòèëà ðåçêîå íåïðèÿòèå â ìàòåìàòè÷åñêèõ êðóãàõ êîíöà
XIX â., òàê êàê ïðîòèâîðå÷èëà ïðèâû÷íûì ìàòåìàòè÷åñêèì ïðåäñòàâëåíèÿì. Íà ðóáåæå XIX è XX ââ. ìàòåìàòèêè ñòîëêíóëèñü ñ òàê íàçûâàåìûìè ïàðàäîêñàìè òåîðèè
ìíîæåñòâ, êîòîðûå ïðîòèâîðå÷èëè çäðàâîìó
ñìûñëó. Ñëåäñòâèåì áóðíîãî îáñóæäåíèÿ âîïðîñà î ïðîòèâîðå÷èÿõ, ñâÿçàííûõ ñ òåîðèåé ìíîæåñòâ, áûë ãëóáîêèé êðèçèñ îñíîâ ìàòåìàòèêè, Ðèñ. 1.12. Îáùåëîãè÷åñêèé ïàðàäîêñ
êîòîðûé çàòðîíóë âåñü íàó÷íûé ìèð. Íà ïîïûòêè
33
íåêîòîðûõ ìàòåìàòèêîâ îòêàçàòüñÿ îò èñïîëüçîâàíèÿ òåîðèè ìíîæåñòâ â
ìàòåìàòè÷åñêèõ ðàññóæäåíèÿõ îäèí èç ñàìûõ èçâåñòíûõ ó÷åíûõ ýòîãî ïåðèîäà Ä. Ãèëüáåðò çàÿâèë: «Íèêòî íå ìîæåò èçãíàòü íàñ èç ðàÿ, êîòîðûé
ñîçäàë íàì Êàíòîð¾»
Òåîðèÿ ìíîæåñòâ ÿâèëàñü îñíîâîé äëÿ ðàçâèòèÿ íàóêè â XX â.
Åå ìåòîäû èñïîëüçóþòñÿ â ðàçëè÷íûõ ìàòåìàòè÷åñêèõ äèñöèïëèíàõ: òåîðèè ôóíêöèé äåéñòâèòåëüíîãî ïåðåìåííîãî, ôóíêöèîíàëüíîì àíàëèçå è ò. ä.  íàñòîÿùåå âðåìÿ ñ íåå íà÷èíàåòñÿ ñåðüåçíîå
èçó÷åíèå ìàòåìàòèêè, ïîñêîëüêó ìíîãèå ìàòåìàòè÷åñêèå äèñöèïëèíû èñïîëüçóþò åå àïïàðàò.
1.5. Êîðòåæè. Äåêàðòîâû ïðîèçâåäåíèÿ
Èíà÷å ðàññòàâëåííûå ñëîâà îáðåòàþò äðóãîé ñìûñë, èíà÷å ðàññòàâëåííûå
ìûñëè ïðîèçâîäÿò äðóãîå âïå÷àòëåíèå.
Á. Ïàñêàëü
 ïîâñåäíåâíîé æèçíè è ìàòåìàòèêå íàì ÷àñòî ïðèõîäèòñÿ
èìåòü äåëî ñ óïîðÿäî÷åííûìè ìíîæåñòâàìè — êîðòåæàìè. Ñëîâî êîðòåæ ïåðåâîäèòñÿ ñ ôðàíöóçñêîãî cortege êàê òîðæåñòâåííàÿ ïðîöåññèÿ (íàïðèìåð, ñâàäåáíûé êîðòåæ). Òðåóãîëüíèê ÀÂÑ
íà ïëîñêîñòè çàäàåòñÿ êîðòåæåì èç 6 ÷èñåë ⟨x1, y1, x2, y2, x3, y3⟩,
ãäå A (x1; y1), B (x2; y2), C (x3; y3) — êîîðäèíàòû âåðøèí. Ñëîâà â
ïðåäëîæåíèè, áóêâû â ñëîâå, ïðåäëîæåíèÿ â òåêñòå — âñå ýòî
ïðèìåðû êîðòåæåé. Äâîè÷íûé êîä ÿâëÿåòñÿ êîðòåæåì, ñîñòîÿùèì
èç öèôð 0 è 1.
Ïóñòü A — êîíå÷íîå ìíîæåñòâî, ñîñòîÿùåå èç n ýëåìåíòîâ,
f : A → {1, 2, ¾, n} — ôóíêöèÿ, çàäàþùàÿ ïîðÿäîê íà A, ò. å. ïðàâèëî, ïî êîòîðîìó êàæäîìó ýëåìåíòó ìíîæåñòâà A ñòàâèòñÿ â ñîîòâåòñòâèå íàòóðàëüíîå ÷èñëî îò 1 äî n, ïðè÷åì îäíîìó ÷èñëó èç
{1, 2, ¾, n} ñîîòâåòñòâóåò îäèí ýëåìåíò èç A.
Ïàðó ⟨A, f ⟩ íàçîâåì óïîðÿäî÷åííûì ìíîæåñòâîì, èëè ïåðåñòàíîâêîé, èç n ýëåìåíòîâ. Êîðòåæåì äëèíû n èç ýëåìåíòîâ ìíîæåñòâà A (èëè n-êîé) íàçûâàåòñÿ óïîðÿäî÷åííàÿ ïîñëåäîâàòåëüíîñòü
⟨à1, à2, ¾, àn⟩ ýëåìåíòîâ ýòîãî ìíîæåñòâà, ïðè÷åì íà ïåðâîì ìåñòå ñòîèò ïðîîáðàç åäèíèöû: à1 = f −1(1), à2 = f −1(2), ¾, àn = f −1(n),
àk ∈ A, ∀k ≤ n.
Êîðòåæè ⟨à1, à2, ¾, àk⟩ è ⟨b1, b2, ¾, bn⟩ íàçûâàþòñÿ ðàâíûìè,
åñëè îíè èìåþò îäèíàêîâóþ äëèíó è èõ ýëåìåíòû ñ îäèíàêîâûìè íîìåðàìè ñîâïàäàþò, ò. å. ⟨à1, à2, ¾, àk⟩ = ⟨b1, b2, ¾, bn⟩, åñëè
(k = n) è äëÿ ∀i ài = bi.
Íàïðèìåð, ðàâíû êîðòåæè ⟨21, 22, 23, 24, 25⟩ = ⟨2, 4, 8, 16, 32⟩,
òàê êàê îáà êîðòåæà äëèíû 5 è ðàâíû âñå ïàðû ñîîòâåòñòâóþùèõ
ýëåìåíòîâ äàííûõ ìíîæåñòâ, 21 = 2, 22 = 4, 23 = 8, 24 = 16, 25 = 32.
34
Èç äâóõ äàííûõ êîðòåæåé ⟨à1, à2, ¾, ai, ¾, àk⟩, ãäå ai ∈ A, äëèíû
k è ⟨b1, b2, ¾, bj, ¾, bm⟩, ãäå bj ∈ B, äëèíû m ìîæíî ñîñòàâèòü íîâûé
êîðòåæ äëèíîé k + m, ýëåìåíòû êîòîðîãî ⟨à1, à2, ¾, àk, b1, b2, ¾,
bm⟩ ïðèíàäëåæàò ìíîæåñòâó A U B. Ýòà îïåðàöèÿ íàçûâàåòñÿ ñîåäèíåíèåì êîðòåæåé. Êîðòåæ ìîæíî îáðàçîâàòü äâóìÿ ñïîñîáàìè, ïîýòîìó âàæíî, êàêîé êîðòåæ íàçâàí ïåðâûì. Òàê, ñîåäèíèâ êîðòåæè
÷åòíûõ è íå÷åòíûõ îäíîçíà÷íûõ ÷èñåë ⟨0, 2, 4, 6, 8⟩ è ⟨1, 3, 5, 7, 9⟩,
ïîëó÷èì êîðòåæ âñåõ îäíîçíà÷íûõ ÷èñåë ⟨0, 2, 4, 6, 8, 1, 3, 5, 7, 9⟩.
Ïóñòü A — êîíå÷íîå ìíîæåñòâî, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ
íåêîòîðûå ñèìâîëû, íàïðèìåð öèôðû, áóêâû, çíàêè ïðåïèíàíèÿ.
Òàêèå ìíîæåñòâà ïðèíÿòî íàçûâàòü àëôàâèòîì íàä çàäàííûì ìíîæåñòâîì ñèìâîëîâ. Àëôàâèò åñòü êîðòåæ ïîïàðíî ðàçëè÷èìûõ ñèìâîëîâ, íàçûâàåìûõ áóêâàìè àëôàâèòà. Ýëåìåíòû ìíîæåñòâà Àn ïðèíÿòî íàçûâàòü ñëîâàìè äëèíû n â àëôàâèòå A. Ñëîâî íàä àëôàâèòîì
åñòü ïðîñòî íåêîòîðàÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ. Òàê,
øåñòèçíà÷íûé òåëåôîííûé íîìåð ÿâëÿåòñÿ ñëîâîì äëèíû 6 íàä
àëôàâèòîì öèôð {0, 1, 2, ¾, 9}.
Åñëè ÷èñëî ýëåìåíòîâ êîðòåæà äëèíû n ìîæíî ïðåäñòàâèòü â
âèäå ñóììû n = n1 + n2 + ¾ + nk, òî êîðòåæ äëèíû n ìîæíî ðàçáèòü
íà k êîðòåæåé, èìåþùèõ ñîîòâåòñòâåííî äëèíû n1, n2, ¾, nk.
Ðàññìîòðèì ìíîæåñòâî B, ñîñòîÿùåå èç äâóõ ýëåìåíòîâ: 0 è 1.
Êîðòåæè äëèíû m èç ýòèõ ýëåìåíòîâ îáîçíà÷èì B m. Òîãäà n(B m) =
= 2m. Òàêèå êîðòåæè íàçûâàþò óïîðÿäî÷åííûìè íàáîðàìè èëè âåêòîðàìè. Îíè èìåþò øèðîêîå ïðèìåíåíèå â äèñêðåòíîé ìàòåìàòèêå.
Êàæäûé òàêîé n-ìåðíûé âåêòîð åäèíñòâåííûì îáðàçîì îïðåäåëÿåò âåðøèíó êóáà, ïîñòðîåííîãî íà åäèíè÷íûõ âåêòîðàõ (ðèñ. 1.13).
 çàâèñèìîñòè îò âåëè÷èíû n êóáû ìîãóò áûòü îäíîìåðíûìè
(à), äâóìåðíûìè (á ), òðåõìåðíûìè (â) è ò. ä.
Âåêòîð èç íóëåé è åäèíèö ìîæíî ðàññìàòðèâàòü êàê äâîè÷íîå
ïðåäñòàâëåíèå íàòóðàëüíîãî ÷èñëà.
Âåêòîð, ñîñòîÿùèé èç åäèíèö è íóëåé, îïèñûâàåò ñîñòîÿíèå
ïàìÿòè âû÷èñëèòåëüíûõ ìàøèí, ïðè÷åì ïàìÿòü ìîæåò ñîäåðæàòü
÷èñëà, òåêñòû, êîìàíäû è ò. ä.
Ðèñ. 1.13. Èëëþñòðàöèÿ n-ìåðíîãî êóáà:
à — îäíîìåðíîãî; á — äâóìåðíîãî; ⠗ òðåõìåðíîãî
35
Êîðòåæè èç íóëåé è åäèíèö ìîãóò
áûòü ñîîáùåíèÿìè, ïåðåäàâàåìûìè
ïî íåêîòîðîìó êàíàëó ñâÿçè ñ ïîìîùüþ èìïóëüñîâ, êàæäûé èç êîòîðûõ
ïðèíèìàåò îäíî èç äâóõ çíà÷åíèé. Ñîîáùåíèÿ ìîãóò õàðàêòåðèçîâàòü ðåçóëüòàòû ýêñïåðèìåíòîâ: óñïåõ (1)
èëè íåóäà÷ó (0).
Ìîæíî îïèñàòü ïóòü ïî íåêîòîðîé
Ðèñ. 1.14. Äâèæåíèå ïî
ïðÿìîóãîëüíîé ðåøåòêå, îïðåäåëèâ,
ïðÿìîóãîëüíîé ðåøåòêå
íàïðèìåð, øàã íàïðàâî ÷åðåç åäèíèöó, à øàã íàâåðõ — ÷åðåç íóëü. Òîãäà ëþáîé ïóòü ïî òàêîé ïðÿìîóãîëüíîé ðåøåòêå ìîæíî çàäàòü êîðòåæåì (ðèñ. 1.14).
Êîðòåæ èç íóëåé è åäèíèö èñïîëüçóåòñÿ òàêæå äëÿ êîäèðîâêè
ãåîìåòðè÷åñêîãî èçîáðàæåíèÿ. Òàêàÿ äâóõöâåòíàÿ ÷åðíî-áåëàÿ ïðÿìîóãîëüíàÿ ñåòêà, ñîñòîÿùàÿ èç ÷åðíûõ ñòîëáöîâ íà áåëîì ôîíå,
ìîæåò áûòü ïðåäñòàâëåíà â âèäå âåêòîðà.  âû÷èñëèòåëüíîé òåõíèêå
øèðîêî èñïîëüçóåòñÿ òî÷å÷íîå ðèñîâàíèå êàê ðàñòðîâûé ðèñóíîê.
Ïðàêòè÷åñêèé ïðèêëàäíîé õàðàêòåð êîðòåæåé ïðîÿâëÿåòñÿ â
èñïîëüçîâàíèè øòðèõîâûõ êîäîâ (barcodes), êîòîðûå øèðîêî ïðèìåíÿþòñÿ â ðàçëè÷íûõ èíôîðìàöèîííûõ ñèñòåìàõ äëÿ ñîîáùåíèÿ
îïðåäåëåííîé èíôîðìàöèè î õàðàêòåðèñòèêå îáúåêòà. Íàïðèìåð,
øòðèõ-êîäîì ñíàáæåíû òîâàðû íà áàçå èëè â ìàãàçèíå. Êàññîâûé
êîìïüþòåð áûñòðî ñ÷èòûâàåò çàøèôðîâàííóþ â íèõ èíôîðìàöèþ.
Êàæäûé ñèìâîë ñïåöèàëüíûì îáðàçîì îäíîçíà÷íî êîäèðóåòñÿ ñ
ïîìîùüþ ïîëîñîê áåëîãî è ÷åðíîãî öâåòà. Êîðòåæ òàêèõ ïîëîñîê
îäíîçíà÷íî ïåðåâîäèòñÿ â âåêòîð èç 0 è 1.
Äåêàðòîâî ïðîèçâåäåíèå. Ïóñòü çàäàíû ìíîæåñòâà A1, A2, ¾, An.
Äåêàðòîâûì (ïðÿìûì) ïðîèçâåäåíèåì ýòèõ ìíîæåñòâ íàçûâàåòñÿ
ìíîæåñòâî A1 ½ A2 ½ ¾ ½ An, ñîñòîÿùåå èç âñåõ êîðòåæåé ⟨a1, a2, ¾,
an⟩ äëèíû k, â êîòîðûõ ak ∈ Ak, ãäå 1 ≤ k ≤ n. Ïîñêîëüêó äëÿ çàäàíèÿ
êîðòåæà âàæåí ïîðÿäîê, òî ïîðÿäîê ìíîæèòåëåé âàæåí è â äåêàðòîâîì ïðîèçâåäåíèè.
Íàïðèìåð, äåêàðòîâûì ïðîèçâåäåíèåì ìíîæåñòâ A = {0,1} è
B = {X, Y, Z } áóäåò ÿâëÿòüñÿ ìíîæåñòâî ïàð A × B = ⟨(0; X ), (0; Y ),
(0; Z ), (1; X ), (1; Y ), (1; Z )⟩. Ñêîáêè äëÿ óêàçàíèÿ ïàð îïóñêàþò
òàì, ãäå ýòî íå ìîæåò ïðèâåñòè ê çàòðóäíåíèÿì: A × B = ⟨0X, 0Y,
0Z, 1X, 1Y, 1Z ⟩. Åñëè ìíîæåñòâà A = {a1, à2, ¾, àk} è B = {b1, b2, ¾,
bm} êîíå÷íû, òî èõ äåêàðòîâî ïðîèçâåäåíèå ìîæåò áûòü ïðåäñòàâëåíî â îáùåì âèäå òàáëèöåé èç m ñòîëáöîâ è k ñòðîê.
36
(à1, b1)
(à1, b2)
...
(à1, bm)
(à2, b1)
(à2, b2)
...
(à2, bm)
...
...
...
...
(àk, b1)
(àk, b2)
...
(àk, bm)