Учебник

Москва
КУРС 

ИНФРА-М 

2017

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

а.и. ГУсева 
в.с. киреев 

а.н. тихомирова

Рекомендовано 

Экспертным советом при ГБОУ УМЦ ПО ДОгМ для использования 

в образовательном процессе профессиональных образовательных 

организаций города Москвы в качестве учебника для студентов 

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

09.02.01 «Компьютерные системы и комплексы», 

09.02.05 «Прикладная информатика (по отраслям)», 

09.03.03 «Прикладная информатика»

Среднее профеССиональное образование

УДк 519.1(075.8)
ббк 22.174я73

Г96

Гусева а.и.
Дискретная математика : учебник / А.И. Гусева, В.С. Киреев, 

А.Н. Тихомирова. — М.: КУРС: ИНФРА-М, 2017. — 208 с. — 
(Среднее профессиональное образование).

ISBN 978-5-906818-21-8 (КУРС)
ISBN 978-5-16-011675-4 (ИНФРА-М, print)
ISBN 978-5-16-105603-5 (ИНФРА-М, online)
Данный учебник представляет собой углубленный курс по таким разде-

лам дискретной математики, как теория множеств и бинарных отношений, 
математическая логика и логика предикатов, теория графов, элементы тео-
рии и практики кодирования, элементы теории автоматов. Основная задача 
курса — формирование прочной теоретической основы, необходимой для 
дальнейшей  профессиональной работы. Каждый раздел содержит подроб-
ный разбор практических задач и методов их решения, набор упражнений 
для самостоятельной работы.

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

профессионального образования по направлениям подготовки «Компью-
терные системы и комплексы» и «Прикладная информатика».

УДК 519.1(075.8)
ББК 22.174я73

Р е ц е н з е н т ы:
О.Н. Ромашкова — д-р техн. наук, профессор, заведующий кафедрой 

прикладной математики ГАОУ ВО МГПУ;

М.И. Смирнов — д-р техн. наук, профессор, генеральный директор 

ООО «Нафтам-ИНПРО»

Г96

© Гусева А.И., Киреев В.С., 

Тихомирова А.Н., 2016

© КУРС, 2016

ISBN 978-5-906818-21-8 (КУРС)
ISBN 978-5-16-011675-4 (ИНФРА-М, print)
ISBN 978-5-16-105603-5 (ИНФРА-М, online)

ФЗ 

№ 436-ФЗ

Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11

Оригинал-макет подготовлен в Издательстве «КУРС»

Подписано в печать 25.11.2016.

Формат 60×90/16. Бумага офсетная. Гарнитура Newton.

Печать цифровая. Усл. печ. л. 13,0.

Тираж 500 экз. Заказ № 00000

ТК 646563-761307-251116

ООО Издательство «КУРС»

127273, Москва, ул. Олонецкая, д. 17А, офис 104.
Тел.: (499) 709-16-28.
E-mail: kursizdat@gmail.com

ООО «Научно-издательский центр ИНФРА-М»

127282, Москва, ул. Полярная, д. 31В, стр. 1

Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29

E-mail: books@infra-m.ru
http://www.infra-m.ru

ВВедение

Данный учебник предназначен для учащихся среднего профессио-

нального образования по направлениям подготовки 09.02.01 «Ком-
пьютерные системы и комплексы» и 09.02.03 «Прикладная информа-
тика (по отраслям)». При подборе учебного материала использовался 
многолетний опыт преподавания дискретной математики на кафедре 
кибернетики в Национальном исследовательском ядерном универ-
ситете «МИФИ», рекомендации Computing Curricula 2013 и требова-
ния российских профессиональных стандартов в области ИТ.

Книга содержит разделы дискретной математики как одного 

из разделов области знаний под названием «компьютинг» (comput-
ing). К сожалению, для компьютинга нет устоявшегося русскоязыч-
ного наименования. Так, при переводе международных рекоменда-
ций по преподаванию компьютинга в учебных заведениях Computing 
Curricula 2013 на русский язык использовалось понятие «информа-
тика», а при разработке российских образовательных стандартов 
на основе Computing Curricula было применено наименование «ин-
формационные технологии». В данном учебнике для устранения 
разных толкований используется транслитерация «компьютинг».

Основы компьютинга включают в себя основы информатики 

и математики, необходимые для проектирования и разработки прог-
раммных продуктов, что составляет базовые компетенции учащихся 
по направлениям подготовки в области компьютерных систем и ком-
плексов и прикладной информатики. Данная область знаний вклю-
чает в себя также знания о трансформации проекта в реализацию, 
используемых при этом средствах и о формальных методах создания 
программного обеспечения. Основываясь на математике и компью-
тинге, программная инженерия занимается разработкой системати-
ческих моделей и надежных методов производства высококачествен-
ного программного обеспечения, и данный подход распространяется 
на все уровни — от теории и принципов до реальной практики со-
здания программного обеспечения, которая лучше всего заметна 
сторонним наблюдателям.

Программная инженерия посвящена систематическим, управля-

емым и эффективным методам создания высококачественного прог-
раммного обеспечения. Поэтому особое внимание уделяется анализу 
и оценке, спецификации, проектированию и эволюции программ-
ного обеспечения. Кроме того, в рамки данной дисциплины попа-

дают вопросы, связанные с управлением и качеством, новизной 
и творчеством, стандартами, индивидуальными навыками и ко-
мандной работой, а также профессиональной деятельностью, кото-
рые играют жизненно важную роль в программной инженерии. Про-
граммная инженерия является такой формой инженерии, которая 
применяет принципы информатики (computer science) и математики 
для получения рентабельных решений в области программного обес-
печения.

Программная инженерия как наука обладает рядом особенностей:

• основанием программной инженерии является информатика, 

а не естественные науки;

• основной упор делается на дискретную, а не на непрерывную ма-

тематику;

• производится абстрактными/логическими объектами вместо кон-

кретных/физических установок;

• отсутствие «производственной» фазы в традиционном промыш-

ленном смысле;

• «сопровождение» программного обеспечения в основном связано 

с продолжающейся разработкой или эволюцией, а не с традици-
онным физическим износом.
Дискретная математика является фундаментом для всего ком-

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

Данный курс знакомит с основами дискретной математики и ме-

тодами их использования в компьютинге. Основная задача курса — 
формирование прочной теоретической основы, необходимой для 
дальнейшей профессиональной работы. Он включает в себя следу-
ющие темы: множества, отношения, функции, булеву алгебру, логику 
высказываний, логику предикатов, теорию графов, основы теории 
автоматов и теории кодирования.

В результате освоения данного учебника обучающийся должен 

знать и уметь применять методы дискретной математики для реше-
ния практических задач.

Глава 1

Теория множесТВ

и бинарных оТношений

Многие первичные понятия дискретной математики, как и мате-

матики вообще, даются на интуитивном уровне. К ним добавляется 
система аксиом — утверждений, которые всегда верны, и правила 
вывода, следуя которым мы получаем возможность строить сколь 
угодно сложные утверждения, доказывать теоремы, решать задачи 
и т.д.

В течение своей жизни мы сталкивались с таким подходом неод-

нократно. Используя понятие числа и операций над ним (сложение, 
умножение, деление, вычитание), мы изучали арифметику. Исполь-
зуя понятие точки, прямой, угла и плоскости, мы изучали геометрию. 
Алгебра и стереометрия, основы математического анализа изучались 
нами похожим образом.

Такой подход называется аксиоматическим [1].
При изучении всех разделов дискретной математики, в том числе 

и элементов теории множеств и бинарных отношений, мы также ис-
пользуем аксиоматический подход [1–6, 11].

1.1. основные понятия теории множеств

Множество — совокупность объектов, хорошо различимых нашей 

интуицией или мыслью, обладающих неким сходством и объединен-
ных в одно общее.

Элементы множества обозначаются маленькими латинскими бук-

вами, сами множества — заглавными. Например, чтобы показать, 
что элемент a принадлежит множеству A, мы пишем a
A
∈
, в против-

ном случае a
A
∉
.

Во множество можно объединять самые разные объекты. Напри-

мер, множество натуральных чисел N, множество целых чисел Z, 
множество действительных чисел R, множество предметов в вашей 
комнате W и т.д.

Элементами множества могут выступать другие множества, на-

пример D = {{синий, красный, зеленый}, {шар, куб, цилиндр, пира-
мида}}. Такое множество D называется классом или семейством [2].

Количество элементов во множестве называется мощностью или 

кардинальным числом. Например, мощность множества M = {a, b, c} 
равна 3, |M| = 3. В зависимости от мощности множества могут быть 
конечные и бесконечные. Множество, в состав которого не входит 
ни одного элемента, называется пустым и обозначается как ∅. Мощ-
ность пустого множества равна нулю. Но мощность множества С, 
элементом которого является пустое множество, равна единице, 
C = ∅
{ }, C = 1.
Множества равномощны, если их мощности равны. Например, 

множества D = {{синий, красный, зеленый}, {шар, куб, цилиндр, пи-
рамида}} и К = {a, b} равномощны.

Определим, что конечное множество — множество, состоящее 

из конечного числа элементов, т.е. его мощность представима кар-
динальным числом, совпадающим с одним из натуральных чисел. 
В противном случае множество называется бесконечным.

Если каждому элементу бесконечного множества можно поста-

вить в соответствие натуральное число n
N
i ∈
, причем только одно ni, 

без пропусков и повторений, то это множество называется счетно-
бесконечным и его мощность равна N = A0 (алеф-нуль), первому 
трансфинитному числу. Второе трансфинитное число A, алеф, равно 
мощности множества R действительных чисел. Известно и третье 

трансфинитное число A
A
A
=
=
2
22
0 , алеф-один, равное множеству 

точек в пространстве, заданных координатами (x, y, z). Трансфинит-
ные числа обозначают буквами еврейского алфавита.

Кантор создал шкалу трансфинитных чисел: алеф-ноль, алеф, 

алеф-один, … .

Считаем, что множество счетное, если выполняется один из двух 

случаев:
• множество состоит из конечного числа элементов, т.е. его карди-

нальное число совпадает с одним из натуральных чисел;

• множество счетно-бесконечное, т.е. его мощность совпадает 

с мощностью множества натуральных чисел.
Множество несчетное, если оно бесконечно и неравномощно 

множеству натуральных чисел.

Множество A называется подмножеством B, если каждый эле-

мент ai из A, a
A
i ∈
, принадлежит одновременно и множеству B, 

a
B
i ∈
, A
B
⊆
. В предельном случае множества А и В могут состоять 

из одних и тех же элементов.

Если во множестве B найдется хотя бы один элемент xi, который 

не принадлежит A, ∃xi, x
B
i ∈
, x
A
i ∉
, то A — собственное подмноже-

ство B, A
B
⊂
. Пустое множество ∅ всегда является подмножеством 

любого множества B.

Между понятиями «подмножество» и «собственное подмноже-

ство» существует значительная разница. Так, подмножество А может 
совпадать с самим множеством В, т.е. A
B
≤
, но собственное под-

множество С всегда состоит из меньшего количества элементов, 
чем В, т.е. C
B
<
.

Например, рассмотрим два множества М1 = {a, b, c} и M2 = {a, b, c, d}. 

Множество М1 является собственным подмножеством М2, так как 
в М2 имеется элемент d, не принадлежащий множеству М1.

Множество B в приведенных выше определениях часто называют 

надмножеством (собственным надмножеством) множества A.

Множества A и B равны, если являются подмножествами (надмно-

жествами) друг друга.

Для каждого множества М можно построить новое множество, 

элементами которого являются все подмножества М и только они. 
Тогда множество М называется универсумом и обозначается как I, 
а множество всех его подмножеств — булеаном B(I).

В некоторых случаях под универсумом можно понимать множе-

ство всех возможных элементов.

Например, возьмем в качестве универсума I множество натураль-

ных чисел на отрезке [1, 3], I = {1, 2, 3}, тогда булеан B(I) = {∅, {1}, 
{2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Если мощность универсума равна 
m, то мощность его булеана всегда B I
m
( ) = 2 .

теорема 1.1. основная теорема о конечных множествах
Любое конечное множество не может быть эквивалентно никакому 

своему собственному подмножеству.

При определении множеств и подмножеств можно столкнуться 

с парадоксом Рассела, который заключается в следующем. Рас-
смотрим множество A всех множеств B, не содержащих себя в каче-
стве элементов, A
B B
B
=
∉
{
}. Если множество A существует, то со-

держит ли A в качестве элемента самого себя, т.е. A
A
∈
? При ответе 

на этот вопрос мы сталкиваемся с логическим противоречием: если 
A
A
∈
, то по определению элементов множества A
A
∉
. Если A
A
∉
, 

то A
A
∈
.

Для задания множеств необходимо указать элементы, которые 

ему принадлежат. Это можно сделать следующим образом [3]:
• перечислить элементы множества, например M = {1, 2, 3, 4, 5};
• использовать характеристический предикат, задающий свойства 

элементов, например M = {x/x ∈ N и x < 6};

• с помощью производящей функции, которая помогает вычислить 

каждый элемент рассматриваемого множества, например M = 
= {x / for I := 1 to 5 do x := i}.
Во всех трех случаях мы задаем множество М, содержащее пять 

натуральных чисел от 1 до 5.

1.2. операции над множествами

Любая операция представляет собой результат отображения мно-

жества самого на себя. Мы будем рассматривать операции над мно-
жествами одноместные и двуместные. Все эти операции определя-
ются на некотором универсуме I. К ним относятся объединение, 
пересечение, дополнение, разность и симметрическая разность.

Объединением двух множеств А и B называется новое множество С, 

элементы которого удовлетворяют следующему условию:

С
A
B
x
x
A
x
B
=
∪
=
∈
∈
{
/
}
 или
.
(1.1)

Новое множество С состоит из тех и только тех элементов, кото-

рые или принадлежат А, или принадлежат В, или обоим множествам 
одновременно.

Пересечением двух множеств A и B называется новое множество C, 

элементы которого удовлетворяют следующему условию:

С
A
B
x
x
A
x
B
=
∩
=
∈
∈
{
/
}
 и
.
(1.2)

Новое множество С состоит из тех и только тех элементов, кото-

рые принадлежат обоим множествам А и В одновременно.

Дополнением множества A называется новое множество C, эле-

менты которого удовлетворяют следующему условию:

С
A
x
x
A
I
A
=
=
∉
=
{
/
}
\
.
(1.3)

Таким образом, в новом множестве С содержатся те и только 

те элементы из универсума, которые не принадлежат А.

Разностью двух множеств A и B называется новое множество C, 

элементы которого удовлетворяют следующему условию:

C
A
B
x
x
A
x
B
=
=
∈
∉
\
{
/
}
 и
.
(1.4)

Таким образом, в новом множестве С содержатся только те эле-

менты из А, которые не принадлежат В.

Симметрической разностью двух множеств A и B называется новое 

множество C, элементы которого удовлетворяют следующему 
условию:

C
A B
x
x
A
x
B
x
A
x
B
=
=
∈
∉
∉
∈
D
{
/ (
)
(
)}
 и
или 
 и
.
(1.5)

Новое множество С состоит из тех и только тех элементов, кото-

рые принадлежат А и не принадлежат В или принадлежат В, но не 
принадлежат А.

Используя операции объединения, пересечения и дополнения, 

операцию симметрической разности можно записать в виде

A B
A
B
A
B
D
=
∩
∪
∩
(
)
(
).
(1.6)

Результаты применения рассмотренных выше операций удобно 

отображать графически с помощью диаграмм Эйлера—Венна 
(рис. 1.1). Квадрат с 1 обозначает универсум, круги — множества 
А и В, результат операции представлен заштрихованными фрагмен-
тами.

При выполнении вычислений множественных выражений самой 

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

Перечисленные операции получили название теоретико-множе-

ственных операций. Результаты всех этих операций над подмноже-
ствами универсума I дают также подмножества I.

Рассмотрим решение несколько задач.

Задача 1.1
Даны множества I = {1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {1, 3, 5, 7, 9}, B = {1, 2, 

3, 8, 9}, C = {2, 3, 5, 6, 9}.

Найти:
1) A
B
C
∩
∪
;

2) A
B
C
∩
∪
;

3) A
B
C
∩
∪
;

4) A
B
C
∩
∪
.

Решение.
Учитывая старшинство операций, получаем:

1
1
1
1
1

а) A ∩ B
б) A ∪ B
в) A \ B
г) B \ A
д) A

рис. 1.1. Диаграммы Эйлера—Венна

1) A
B
C
∩
∪
=
∪
=
{ , ,
}
{ , , , ,
}
{ , , , , ,
}
1 3 9
2 3 5 6 9
1 2 3 5 6 9 ;

2) A
B
C
C
∩
∪
=
∪
=
∪
=
{ , ,
}
{ ,
, , , , }
{ , , , ,
}
1 3 9
2 4 5 6 7 8
2 3 5 6 9

= { , ,
, , , , ,
}
2 3 4 5 6 7 8 9 ;

3) A
B
C
∩
∪
= { }
7 ;

4) A
B
C
∩
∪
=
=
{ , , , , ,
}
{ , , }
1 2 3 5 6 9
4 7 8 .

Некоторые рассмотренные выше двухместные операции обладают 

свойствами идемпотентности, коммутативности и ассоциативности.

В табл. 1.1 приведены основные свойства операций над множе-

ствами.

Результаты всех этих операций над подмножествами универсума I

дают также подмножества I. По этой причине мы вправе с помощью 
рассмотренных операций определить алгебру A на I.

Под алгеброй A = <M, S> понимается совокупность множества М

с заданными на нем операциями S = {O1, O2, ..., On}.

Алгебра A = <B(I); ∪ ∩
,
,
> называется алгеброй Кантора, где 

в качестве множества используется булеан B(I), а в качестве опера-

Таблица 1.1

свойства операций над множествами

Идемпотентность
A
A
A
∩
=
A
A
A
∪
=

Коммутативность
A
B
B
A
∩
=
∩
A
B
B
A
∪
=
∪

Ассоциативность
A
B
С
A
B
С

A
B
C

∩
∩
=
∩
∩
=

=
∩
∩

(
)

(
)

A
B
С
A
B
С

A
B
C

∪
∪
=
∪
∪
=

=
∪
∪

(
)

(
)

Дистрибутивность
A
B
С

A
B
A
С

∪
∩
=

=
∪
∩
∪
(
)
(
)

A
B
С

A
B
A
С

∩
∪
=

=
∩
∪
∩

(
)

Поглощение
(
)
A
B
A
A
∩
∪
=
(
)
A
B
A
A
∪
∩
=

Действия 
с универсумом

A
I
A
∩
=
A
I
I
∪
=

Действия с пустым 
множеством

A ∩ ∅ = ∅
A
A
∪ ∅ =

Свойства 
дополнения

A
A
∩
= ∅
A
A
I
∪
=

Двойное 
дополнение

A
A
=

Законы 
де Моргана

A
B
A
B
∪
=
∩
A
B
A
B
∩
=
∪

Выражение 
для разности

A
B
A
B
\
=
∩

Выражение для 
симметрической 
разности

A B
A
B
A
B
A
B
A
B
D
=
∪
∩
=
∩
∪
∩
(
) \ (
)