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

ФЕДЕРАЛЬНАЯ СЛУЖБА ИСПОЛНЕНИЯ НАКАЗАНИЙ 
ФЕДЕРАЛЬНОЕ КАЗЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 
ВЫСШЕГО ОБРАЗОВАНИЯ 
ВОРОНЕЖСКИЙ ИНСТИТУТ ФСИН РОССИИ 
 
Кафедра математики и естественно-научных дисциплин 
 
 
 
 
 
 
 
 
 
ДИСКРЕТНАЯ МАТЕМАТИКА 
 
Практикум 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Воронеж  
2019 

УДК 519.1(076.5) 
ББК 22.176 
     Д48 
 
Рекомендовано методическим советом ФКОУ ВО Воронежский институт 
ФСИН России 25 ноября 2019 г., протокол № 3. 
 
Р е ц е н з е н т ы: 
начальник кафедры информационной безопасности 
телекоммуникационных систем ФКОУ ВО Воронежский институт ФСИН 
России канд. техн. наук, доцент А. С. Кравченко; 
и.о. заведующего кафедрой радиоэлектронных устройств и систем 
ФГБОУ ВО «Воронежский государственный технический университет» канд. 
техн. наук, доцент Д.В. Журавлев. 
 
 
Дискретная математика : практикум / [сост. Е. В. Корчагина,  
Р. В. Кузьменко, Н. А. Андреева] ; ФКОУ ВО Воронежский институт 
ФСИН России. – Воронеж, 2019. – 162 с. 
 
Практикум 
является 
дополнением 
к 
основной 
литературе 
дисциплины. Создан на базе прочитанного материала. Содержит базовые 
знания по разделам «Теория множеств и отношений», «Математическая 
логика», 
«Комбинаторный 
анализ», 
«Элементы 
теории 
графов» 
и «Алгоритмы и конечные автоматы», а также большое число 
рассмотренных задач. 
Предназначен для всех технических специальностей и направлений 
подготовки, 
включающих 
реализацию 
дисциплины 
«Дискретная 
математика». 
УДК 519.1(076.5) 
ББК 22.176 
 
Издано в авторской редакции 
 
 
 
 
 
 
© Составление. Корчагина Е.В., 
Кузьменко Р.В., Андреева Н.А., 2019 
© ФКОУ ВО Воронежский 
институт ФСИН России, 2019 

ВВЕДЕНИЕ 

Дискретная математика – это область современной математики, которая 
занимается изучением свойств дискретных объектов, имеющих место 
в многочисленных практических приложениях. В частности, дискретная 
математика 
является 
основой 
для 
изучения 
компьютерных 
наук 
и информационных 
технологий 
(теоретическая 
информатика, 
теория 
алгоритмов, теория кодирования, создание прикладного математического 
и программного обеспечения), для решения задач комбинаторики, теории 
графов, для дискретного имитационного моделирования и пр. 
Материалы, представленные в данном практикуме, позвалят овладеть 
навыками 
решения 
задач 
по 
дисциплине 
«Дискретная 
математика», 
предусмотренными образовательными программами, а также развить умение 
использования полученных теоретический знаний по дисциплине «Дискретная 
математика» в дальнейшей профессиональной деятельности. 

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

математическая логика, комбинаторный анализ, элементы теории графов, 
теория алгоритмов и конечных автоматов.  

В начале каждого раздела практикума приводится необходимый, 
изложенный в максимально простой форме теоретический материал, овладение 
которым будет необходимым для решения практических задач. Изложение 
теоретического материала сопровождается доступными для понимания 
примерами и задачами. Затем, в каждом разделе приводится подробный анализ 
решения 
типовых 
задач, 
а 
в 
завершение 
приведены 
задачи 
для 
самостоятельного решения разного уровня сложности. Причем количество 
задач 
таково, 
что, 
с 
одной 
стороны, 
обучающиеся, 
справившиеся 
с поставленными 
задачами, 
получат 
твердые 
навыки 
в 
решении 
соответствующих задач, а, с другой стороны, практикум также может быть 
с успехом использован преподавателями на семинарских и практических 
занятиях, а также для проведения контрольных работ.  
Авторы надеются, что настоящий практикум поможет обучающимся 
освоить фундаментальные основы «Дискретной математики» и успешно 
применять полученные знания на практике. 

РАЗДЕЛ 1. ТЕОРИЯ МНОЖЕСТВ И ОТНОШЕНИЙ 
1.1. Множества и операции над ними 

Множество – это одно из главных понятий большого числа наук. Обычно 

под множеством понимают некоторую совокупность объектов любой 

природы, которую создают на основании какого-то одного общего свойства или 

признака или их совокупности (сравните, например, множество натуральных 

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

делятся и на три, и на пять). Входящие во множество объекты принято называть 

элементами множества. Различают как реально существующие множества 

(множество курсантов вуза), так и множества из идеальных объектов 

(множество теорем дискретной математики).  

Для обозначений множества обычно используют большие буквы 

латинского или греческого алфавита. Напротив, элементы множества 

обозначаются соответствующей маленькой буквой (элемент m множества М). 

Запись 
m
M
∈
означает, 
что 
соответствующий 
элемент 
принадлежит 

соответствующему множеству. Запись 
M
a∉
, напротив, означает, что данный 

элемент а множеству М не принадлежит. 

Чтобы задать множество, надо назвать все его элементы. Тем самым 

простейшим способом задания множества будет перечисление всех его 

элементов. При этом запись 
{
}
0, 2, 4,7
М =
будет означать, что множество М 

образуют четыре элемента. В некоторых случаях такой способ задания 

множества не удобен (например, если множество состоит из большого числа 

объектов). В этом случае множество определяют с помощью некоторого 

образующего правила или свойства R, при помощи которого можно определить 

принадлежность элемента к множеству. Соответствующая запись имеет вид: 

{
}
:
( )
М
x R x
=
(множество М состоит из таких элементов х, для которых 

образующее множество правило R(x) истинно). Если говорят, что конкретный 

элемент х относится к элементам данного множества М, то используют запись 

{
}
:
( )
x
М R x
∈
. Например, множество из 5 элементов a, b, c, d, e можно задать с 

помощью следующей записи:  

[
]
{
}
e
a
интервала
из
буква
x
x
,
:
−
. 

Пример. Назовите образующее правило для множества курсантов вуза. 

Решение. Рассмотрим, какими общими признаками обладают все 

курсанты вуза. Очевидно, что к общим признакам не могут относиться ни пол, 

ни факт присутствия на занятиях. Также факт отсутствия задолженностей по 

предметам не может служить образующим признаком, поскольку некоторые 

курсанты вуза могут иметь задолженности. Таким образом, формально 

к курсантам вуза мы должны отнести все лица, которые были зачислены 

соответствующим приказом и не отчислены на текущий момент. 

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

элементов, то его называют пустым. Для его обозначения используется символ 

Ø. Введение понятия пустого множества имеет вполне логичное обоснование: 

например, множество, которое было наполнено элементами, оказывается 

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

его правило осталось. 

Пример. Приведите примеры образования пустых множеств. 

Решение. Используем правило, согласно которому пустое множество 

может образоваться путем опустошения множества, ранее наполненного 

элементами. Возьмем, например, множество курсантов какой-то группы, 

имеющих задолженности после сессии. Очевидно, что с течением времени это 

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

а какие-то, возможно, будут отчислены за неуспеваемость. Однако множество 

продолжит существовать, поскольку результаты новой сессии вполне возможно 

вновь приведут к его наполнению. 

Часть элементов множества принято называть его подмножеством. При 

этом подмножество одновременно является самостоятельным множеством, 

поскольку вновь может быть задано образующее правило, которое отбирает 

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

мужского пола всей совокупности курсантов). Для обозначения отношения 

"подмножество – множество" используется символика A
B
⊆
. Данная запись 

означает, что А является подмножеством множества B, и, следовательно, 

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

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

Если элементы двух множеств А и B совпадают, то говорят о равенстве 

этих двух множеств. Из равенства двух множеств автоматически вытекает 

выполнение их включений: A
B
⊆
 и B
A
⊆
. 

Если 
элементы 
какого-то 
множества 
М 
обладают 
несколькими 

признаками, то на основании этого множества могут быть образованы 

несколько подмножеств, в которые могут входить разные комбинации из 

элементов множества. 

Пример. Приведите несколько образующих правил для создания 

подмножеств на примере множества "группа курсантов". 

Решение. Рассмотрим, какими признаками обладает элемент множества 

"группа курсантов". Он обладает биологическими (полом, ростом, весом и т.п.) 

и социальными признаками (мыслительные способности, успеваемость). 

Соответственно, беря каждый из этих признаков или их комбинацию в качестве 

образующего правила, мы получим разные подмножества на основании одного 

и того же множества. 

Число элементов множества М называют его мощностью и обозначают 

│М│(не путать с понятием модуля). В этом случае равномощными будут 

называть множества, которые содержат одинаковое число элементов. Если два 

множества равномощны, это не означает, что множества равны. Равными 

множества будут только в том случае, если они будут содержать одинаковые 

элементы.  

Если число элементов подмножества А меньше числа элементов множества 

В, т.е. имеет место A
B
⊆
, но A
B
≠
, то говорят, что А есть собственное 

подмножество B и пишут A
B
⊂
.  

В принципе, множество также является подмножеством самого себя, 

а пустое множество является подмножеством любого множества.  Семейство 

всевозможных подмножеств множества М, включая пустое подмножество 

и само множество М, называют булеаном множества и обозначают В{М}. 

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

элементов множества мощность булеана будет определяться по формуле 2│М│, 

где │М│ – мощность множества М. Например, мощность булеана на основании 

множества из трех разных элементов будет равна 8.  

Пример. Определите мощность множества и мощность булеана множества 

из трех элементов, представляющего из себя произвольную комбинацию 1 и 0. 

Решение. Очевидно, что поскольку множество состоит их трех элементов, 

его мощность будет равна 3. Булеан будет представлять собой совокупность 

подмножеств, образованных на основании множества. Для любого конечного 

множества мощность булеана будет определяться по формуле 2│М│, где │М│ – 

мощность множества М. Следовательно, в данном случае мощность булеана 

должна быть равна 8. Однако сложность данной задачи заключается в том, что 

множество М формируется на основании 2-х элементов – 0 и 1. Т.е., 

принципиально возможны четыре комбинации элементов, образующих 

множество: {0,0,0}, {0,0,1), {0, 1, 1}, {1, 1, 1}. Порядок следования элементов 

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

важен только элементный состав. Однако форму расчета мощности булеана 

предполагает, что все элементы множества различны. В нашем случае 

элементы множества повторяются. Это означает, что, если, например, 

множества заданы как {a, b, c} или {1, 0, 1}, то в случае образования 

подмножеств на основании правил выбора комбинации 1-го и 2-го и 3-го и 2-го 

элементов множества в случае 1-го множества мы получаем два разных 

подмножества {a, b} и {c, b}, то в случае второго подмножества мастерскую 

получим два одинаковых подмножества  {1, 0}, поскольку 1-й и 3-й элементы 

множества {1, 0, 1} внешне неразличимы. Таким образом, ответ на вторую 

часть задания зависит от конкретного элементного состава множества, однако 

число в ответе в любом случае будет меньше 2│М│. 

Все 
подмножества 
некоторого 
множества 
обладают 
следующими 

свойствами: 

1. Рефлексивность. Любое множество Х является подмножеством самого 

себя: X
X
⊆
. 

2. Транзитивность.  В случае, если множество X есть подмножество 

некоторого множества Y, а множество Y есть подмножество некоторого 

множества Z, то множество X обязательно является подмножеством множества 

Z: если 
,
X
Y
Y
Z
⊆
⊆
, то X
Z
⊆
. 

3. 
Принцип 
объемности. 
Если 
некоторое 
множество 
X 
есть 

подмножество множества  Y, а множество Y есть подмножество множества Х, 

то множество X равно множеству Y: если 
,
X
Y
Y
X
⊆
⊆
, то X
Y
=
. 

Необходимо обратить внимание на то, что понятия принадлежности 

и включения не обладают свойством транзитивности. Так, если 
{}
{}
{}
{ }
1
1
,
1
1
∈
∈
, 

то это не означает, что 
{}
{ }
1
1∈
, поскольку единственный элемент множества 

{}
{ }
1  – это {}
1 . 

В теории множеств также вводится понятие универсального множества. 

Универсальным множеством будем называть любое множество U, которое 

включает в себя все элементы, обладающие данным свойством. Например, 

универсальным множеством будет множество всех курсантов ФСИН. 

Интересно, что подмножества универсального множества вновь могут быть 

универсальными множествами. Так универсальным будет множество курсантов 

ФСИН мужского пола. Также если все рассматриваемые в рамках какой-то 

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

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

Над множествами могут предприниматься различные операции по их 

преобразованию. Основные операции над множествами по аналогии операции над 

числами получили названия алгебраических. Обычно к таким операциям относят: 

Объединение множеств: объединением множеств А и B называется новое 

множество, обозначаемое как A
B
∪
, все элементы которого являются либо 

элементами множества А, либо элементами множества B: 

{
}
:
или
A
B
x x
A
x
B
∪
=
∈
∈
. 

Очевидно, что мощность нового множества будет равно сумме 

мощностей каждого из образующих его старых множеств. 

Пересечение множеств: пересечением множеств А и B называется 

множество,   обозначаемое   как   A
B
∩
,  элементы  которого   одновременно 

являются и элементами из множества А, и элементами из множества B: 

{
}
:
и
A
B
x x
A
x
B
∩
=
∈
∈
. 

Для пересечения множеств выполняется операция включения  

A
B
A
A
B
∩
⊆
⊆
∪
 и A
B
B
A
B
∩
⊆
⊆
∪
. 

Очевидно, что мощность нового множества не будет превосходить 

мощность меньшего по числу элементов множества.   

Разность множеств: разностью множеств А и B называется такое 

обозначаемое как 
\
A B множество, которое будет содержать элементы из А, 

которых нет в B: 
{
}
\
:
и
A B
x x
A
x
B
=
∈
∉
. 

Очевидно, что мощность нового множества не будет превосходить 

мощность множества А.   

Симметричная разность множеств: Симметричной разностью множеств 

А и B называется такое обозначаемое как 
B
A
или
B
A
+
∆
 множество, элементы 

которого принадлежат А и не принадлежат В и принадлежат В, но не 

принадлежат А, т.е. 
\
\
A
B
A B
B A
+
=
∪
. 

Очевидно, что мощность нового множества может быть любой вплоть от 

нуля до суммы мощностей  множеств А и B.   

Дополнением множества: дополнением множества Α  называется 

множество, 
в 
которое 
входят 
все 
элементы, 
которые 
принадлежат 

универсальному множеству, но не принадлежат А 
\
A
U
A
=
. 

Пример. Даны два множества А={a, b, c, d}, B={a, b, c}. Найти A
B
∪
, 

A
B
∩
, 
\
A B , 
B
A∆
, А. 

Решение. Путем сравнения элементного состава  множеств А и B могут 

быть легко получены следующие результаты. 

A
B
∪
 ={a, b, c, d}  

A
B
∩
 ={a, b, c},  

\
A B = {d},  

B
A∆
= {d},  

А = {d},  

Множество 
А 
всегда 
можно 
разбить 
на 
некоторые 
классы 

непересекающихся подмножеств таким образом, что, пересечение любых 

двух подмножеств, относящихся к данным классам, даст пустое множество, 

а объединение всех подмножеств из разных классов совпадет с множеством А. 

Если множество содержит конечное число элементов, то его называют 

называется конечным, причем мощность конечного множества из n элементов 

будет всегда равняться n. Поскольку пустое множество не содержит элементов, 

то его мощность будет равна 0. Однако пустое множество также относится к 

конечным 
множествам. 
Конечные 
множества 
обладают 
следующими 

очевидными свойствами: 

1. Любое конечное множество счетно, т.е. все его элементы могут быть 

пронумерованы целыми числами.  

2. Любое подмножество, образуемое из конечного множества, всегда 

будет конечным. 

3. Любое конечное множество содержит конечное, т.е. счетное число 

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

4. Сумма конечного числа конечных множеств всегда будет образовывать 

конечное множество.  

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

множества, состоящие из бесконечного числа элементов. Такие множества