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

УЧЕБНИК

Москва
КУРС
ИНФРА-М
2022

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

А.И. ГУСЕВА
В.С. КИРЕЕВ
А.Н. ТИХОМИРОВА

Рекомендовано 
Экспертным советом при ГБОУ УМЦ ПО ДОгМ для использования 
в образовательном процессе профессиональных образовательных
организаций города Москвы в качестве учебника для студентов
среднего профессионального образования по специальности
2.09.02.01 «Компьютерные системы и комплексы»,
2.09.02.05 «Прикладная информатика (по отраслям)»,
2.09.03.03 «Прикладная информатика»

СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ

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

Гусева А.И.
Дискретная математика : учебник / А.И. Гусева, В.С. Киреев, А.Н. Тихомирова. — Москва : КУРС: ИНФРА-М, 2022. —
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.06.2018.
Формат 6090/16. Бумага офсетная. Гарнитура Newton.
Печать цифровая. Усл. печ. л. 13,0.
Доп. тираж 100 экз. Заказ № 
ТК 646563-761307-251116
ООО Издательство «КУРС»
127273, Москва, ул. Олонецкая, д. 17А, офис 104.
Тел.: (495) 203-57-83. 
E-mail: kursizdat@gmail.com   http://www.kursizdat.ru
ООО «Научно-издательский центр ИНФРА-М»
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 и требования российских профессиональных стандартов в области ИТ.
Книга содержит разделы дискретной математики как одного 
из разделов области знаний под названием «компьютинг» (computing). К сожалению, для компьютинга нет устоявшегося русскоязычного наименования. Так, при переводе международных рекомендаций по преподаванию компьютинга в учебных заведениях 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 = Α0 (алеф-нуль), первому 
трансфинитному числу. Второе трансфинитное число Α, алеф, равно 
мощности множества R действительных чисел. Известно и третье 

трансфинитное число Α
Α
Α
=
=
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
=
=
∈
∉
∉
∈
Δ
{
/ (
)
(
)}
 и 
 или 
 и 
. 
(1.5)

Новое множество С состоит из тех и только тех элементов, которые принадлежат А и не принадлежат В или принадлежат В, но не 
принадлежат А.
Используя операции объединения, пересечения и дополнения, 
операцию симметрической разности можно записать в виде

 
A B
A
B
A
B
Δ
=
∩
∪
∩
(
)
(
). 
(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
Δ
=
∪
∩
=
∩
∪
∩
(
) \ (
)