Дискретная математика для бакалавриата

УДК 519.854(073) 
ББК 22.176я73    
    Ш48 

Р е ц е н з е н т :  Заслуженный деятель науки Удмуртской Республики, 
доктор техн. наук, профессор  В. М. Колодкин 

Шептунов М. В. 

Ш48  Дискретная математика для бакалавриата. Учебное пособие 
для вузов. – М.: Горячая линия – Телеком, 2017. – 114 с.: ил. 

ISBN 978-5-9912-0659-4. 

В краткой форме доступно изложены основы дискретной матема-
тики. Рассмотрены основы теории множеств, уделено внимание ком-
бинаторному и теоретико-множественному подходам. Рассмотрены 
элементы математической логики. Изложены основные методы и под-
ходы теории графов. Рассмотрены специальные маршруты в графах и 
поиск путей. Раскрыты основные вопросы теории кодирования. Наря-
ду с основополагающими понятиями – кодами Грея и Хемминга уде-
лено внимание применению алгоритма RSA в режимах шифрования и 
электронной цифровой подписи.  
Пособие подготовлено в соответствии с разработанными автором 
рабочими программами Финансового университета (ФГОБУ ВО 
«Финансовый университет при Правительстве РФ»)
Для студентов, обучающихся по направлениям подготовки бака-
лавров 10.03.01 – «Информационная безопасность», 09.03.03 – «При-
кладная информатика», 38.03.05 – «Бизнес-информатика»  

ББК 22.176я73   

Учебное издание 

Шептунов Максим Валерьевич 
Дискретная математика для бакалавриата 
Учебное пособие для вузов 

Тиражирование книги начато в 2017 г. 

Все права защищены.
Любая часть этого издания не может быть воспроизведена в какой бы то ни было форме 
и какими бы то ни было средствами без письменного разрешения правообладателя
© ООО «Научно-техническое издательство «Горячая линия – Телеком»
www.techbook.ru
©  М. В. Шептунов  

Введение

Цель данного учебного пособия — изложение небольшого по объ-
ёму, но достаточного для понимания материала по дискретной ма-
тематике для студентов первого и второго курсов университета.
В основу учебного издания положен курс «Дискретная матема-
тика», читавшийся автором доцентом, канд. техн. наук М.В. Шеп-
туновым на протяжении ряда лет в Финансовом университете для
соответствующих направлений подготовки бакалавриата, также пре-
подававшийся им в РГГУ (ФГОБУ ВО «Российский государствен-
ный гуманитарный университет») и читаемый в МГЛУ (ФГОБУ ВО
«Московский государственный лингвистический университет»; быв-
ший им. Мориса Тореза) — для направления подготовки бакалаври-
ата «Информационная безопасность».
Издание подготовлено на основе Федеральных государственных
образовательных стандартов (ФГОС) в соответствии с рабочими
(учебными) программами Финансового университета для направле-
ний подготовки бакалавриата «Информационная безопасность»,
«Прикладная
информатика»,
«Бизнес-информатика»
(профиль
«ИТ-менеджмент в бизнесе») бакалавриата и пригодно для студен-
тов вузов Российской Федерации, осуществляющих подготовку ба-
калавров по указанным и другим смежным компьютерным направ-
лениям.
К сфере изучения дискретной математики относятся математи-
ческие вопросы, непосредственно не связанные с понятиями беско-
нечности, предела и непрерывности.
Материал учебного пособия структурирован следующим обра-
зом.
В первой главе изложены основы теории множеств как база кур-
са.
Внимание здесь в значительной степени уделено комбинатор-
ному, теоретико-множественному подходам. В том числе, уделено
внимание редко встречающемуся в учебных пособиях понятию сред-
невзвешенного по элементам множества.
Вторая глава посвящена элементам математической логики —
её методам, алгебре высказываний, предикатам. Рассмотрено при-
менение алгебры логики к релейно-контактным схемам.
В главе третьей — одной из наиболее ёмких — изложены элемен-
ты теории графов, её методы и подходы. Уделено внимание, в том

Введение

числе, метрическим характеристикам графов, имеющим непосредст-
венное отношение к задачам рационального размещения различных
объектов инфраструктуры. Рассмотрены специальные маршруты в
графах; поиск путей, обладающих латинскими свойствами — приме-
нение метода латинской композиции.
Четвёртая, завершающая глава направлена на раскрытие эле-
ментов теории кодирования. Наряду с основополагающими поняти-
ями — кодами Грея и Хемминга, внимание в ней частично уделено
также однонаправленным функциям и применению алгоритма RSA
в режимах шифрования и электронной цифровой подписи.
Рассмотрены некоторые (утверждённые Советом Департамента
математики и информатики Финансового университета) практико-
ориентированные задачи для развития регламентируемых соответ-
ствующими федеральными образовательными стандартами и про-
граммами дисциплины компетенций.
В завершение приведён пример выполнения приближенного к
типовому варианта контрольной работы, которая может проводить-
ся (с учётом соответствующего учебного плана) как домашней, так
и аудиторной.
Автор надеется, что изложенный в данном учебном издании ма-
териал окажется полезным студентам как при изучении собственно
дисциплины «Дискретная математика», так и при изучении последу-
ющих математических дисциплин, при изучении которых курс дис-
кретной математики является базовым. Соответствующая глава мо-
жет также использоваться в рамках дисциплины «Математическая
логика и теория алгоритмов».
Автор признателен обоим рецензентам, в том числе анонимно-
му рецензенту ФГАУ «ФИРО» за ценные замечания по улучшению
рукописи книги, а также сотрудникам Издательства «Горячая ли-
ния — Телеком» за их нелёгкий труд.

Множества, отношения и функции

1.1. Множества и способы их задания
1.1.1. Базовые понятия теории множеств
Понятие множества определяется, как несложно заметить, неко-
торым свойством, которым должен либо обладать, либо не обладать
каждый из рассматриваемых объектов.
Создателем теории множеств был немецкий учёный Георг Кан-
тор (1845–1918), утверждавший: «множество есть многое, мыслимое
нами как единое». Это утверждение, разумеется, не может служить
математически строгим определением множества. Существенно, что
такового на сегодняшний день просто не существует.
Определение 1.1 (нестрогое). Множество — это совокупность
объектов, обладающих одним и тем же определённым свойством.
Важно подчеркнуть, что говорить о множестве корректно лишь
тогда, когда элементы множества различимы между собой.
Можно говорить о множестве стульев в комнате, множестве на-
туральных чисел, множестве студентов в группе, множестве состо-
яний системы и т. д.
Но в качестве другого примера отметим, что будет некорректно
говорить о множестве капель в стакане воды, поскольку невозможно
чётко и ясно указать каждую отдельную каплю.
Определение 1.2.
Отдельные объекты, из которых состоит
множество, называются элементами множества.
Например, число 3 — элемент множества натуральных чисел,
буква «б» — элемент множества букв русского алфавита.
В то же время заметим — элементы множества также могут
являться множествами.
Например, множество групп студентов состоит из элементов, ко-
торые, в свою очередь, состоят из студентов.
Общим обозначением множества служит пара фигурных скобок:
{ }. Внутри этих скобок перечисляются элементы множества.

Г л а в а 1

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

A1, A2, ... .

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

b, t, x, ...,

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

b1, b2, ... .

Для указания того, что некоторый элемент a является элемен-
том множества S, используется символ ∈ принадлежности множест-
ву.
Запись

b ∈ S

означает, что элемент a принадлежит множеству S, а запись

y /∈ S

означает обратное. Запись

x1, x2, ..., xn ∈ S

используется в качестве сокращения отдельных записей

y1 ∈ S, y2 ∈ S, ..., yn ∈ S.

Примечание. Понятия множества, элемента и принадлежности,
которые на первый взгляд представляются интуитивно ясными, при
ближайшем рассмотрении такую ясность утрачивают.
Во-первых, проблематична отличимость элементов. В частнос-
ти, может возникнуть вопрос: символы a и α — это один элемент
множества A или же два разных элемента?
Во-вторых, проблематична возможность (без дополнительно
приложенных усилий) указать, принадлежит ли данный элемент данному 
множеству. В частности, является ли число 97654351047 простым?

Определение 1.3. Множество, содержащее все рассматриваемые 
элементы, природа которых безразлична, называется универсальным 
или универсумом. Чаще всего оно имеет обозначение U.
Определение 1.4. Пустым называется множество, не содержащее 
ни одного элемента.
Пустое множество имеет обозначение, скорее всего, встречавшееся 
читателю: H.

Множества, отношения и функции
7

Без указанного понятия нельзя было бы, например, говорить о
множестве всех корней какого-либо данного уравнения, если бы мы
заранее не знали о существовании хотя бы одного его корня.
Иногда бывает трудно определить, является ли то или иное множество 
пустым.
Далее, фундаментальными являются также понятия конечного
и бесконечного множества.
Определение 1.5. Непустое множество называется конечным,
если можно указать число его элементов. В противном случае множество 
называется бесконечным.
Например, множество китов в океане конечно, а множество ра-
циональных чисел бесконечно.
Пустое множество условно будем считать конечным.
Определение 1.6. Множества, состоящие из одних и тех же
элементов, называют равными (совпадающими).
Если два множества X и Y равны, т. е. состоят из одних и тех
же элементов, то пишут

X = Y.

В противном случае пишут

X ‰ Y.

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

{a, c, d} = {d, a, c}.

Отметим, что понятие равенства множеств обладает свойствами
рефлексивности, симметричности и транзитивности, а именно:
• X = X — рефлексивность;
• если X = Y , то Y = X — симметричность;
• если X = Y и Y = Z, то X = Z — транзитивность.
Как уже упоминалось, во множестве не должно быть неразли-
чимых элементов. По указанной причине во множестве не может
быть одинаковых элементов.
В частности, запись {3, 3, 2, 5} некорректна и её следует заме-
нить на {3, 2, 5}.
В теории множеств существует также понятие равномощных
множеств.

Г л а в а 1

Определение 1.7. Два конечных множества A и B называются
равномощными при условии равенства их мощностей.
Понятие равномощных множеств базируется на определении
мощности множества.
Определение 1.8. Мощностью конечного множества называ-
ется число его элементов, обозначаемое |M|.
Воспользовавшись понятием мощности множеств, рассмотрим
ещё два понятия — счётного и несчётного множеств.
Определение 1.9. Счётное множество — это такое конечное
либо перечислимое бесконечное множество, мощность которого не
превосходит мощности множества натуральных чисел.
Прочие бесконечные множества называются несчётными.

1.1.2. Кортежи и прямое произведение множеств

Определение 1.10. Кортежем (упорядоченным множеством)
называется последовательность элементов, т. е. такая их совокуп-
ность, в которой каждый элемент занимает определённое место.
Как таковые, элементы при этом называют компонентами кор-
тежа (первая компонента, вторая компонента, третья компонента
и т. д.).
Примеры кортежей:
• множество людей, стоящих в очереди;
• множество слов во фразе;
• числа, характеризующие долгот и широту какой-либо географической 
точки, и др.
Важно отметить, что во всех перечисленных множествах место
каждого элемента множества является вполне определённым и не
может произвольным образом меняться.
В практических задачах эта определённость часто является исключительно 
предметом договорённости. В частности, только договорённостью 
между людьми, специалистами можно объяснить, почему 
при описании географической точки долготу ставят на первое
место, а широту на второе.
Состояние той или иной кибернетической системы довольно часто 
описывают множеством параметров, принимающих числовые значения. 
Состояние таковой в этом случае представляет собой просто
некоторое множество чисел. Чтобы каждый раз не оговаривать, что
означает конкретное число множества, заранее определяют, какое
именно число считать первым, какое вторым и т. д. Налицо совокупность 
параметров, представленная в виде кортежа.
Здесь уместно рассмотреть пример с обозначением через h высоты 
полёта некоторого летательного аппарата, а через v — его ско-

Множества, отношения и функции
9

рости, соответственно, кортеж

X = (h, v)

будет описывать состояние самолёта.
Определение 1.11. Длиной кортежа называется число его элементов.

Например, множество

a = (a1, a2, ..., an)

является кортежем длины n с элементами a1, a2, ..., an.
Кортежи длины 2 называют парами, кортежи длины 3 — тройками, 
4 — четвёрками и т. д.
Для кортежей могут иметь место следующие частные случаи:
• кортеж (a) длиной 1;
• пустой кортеж длины 0, обозначаемый ().
Важно отметить, что, в отличие от обычного множества, в кортеже 
могут быть одинаковые элементы, например два одинаковых
элемента во фразе, одинаковые значения долготы и широты географической 
точки и проч.
Определение 1.12. Точками пространства либо векторами называются 
упорядоченные множества, элементами которых служат
вещественные числа.

Рис. 1.1. Проекции
2-элементного кортежа

Например, кортеж (a1, a2) может рассматриваться 
как точка на плоскости или
вектор, проведённый из начала координат в
данную точку (рис. 1.1). Компоненты a1 и
a2 будут являться проекциями вектора на
оси 1 и 2, т. е.

Пр1(a1, a2) = a1;
Пр2(a1, a2) = a2.

Рис. 1.2. Проекции 3-элементного 
кортежа

Соответственно, трёхэлементный
кортеж (a1, a2, a3) может рассматриваться 
как точка в трёхмерном прост-
ранстве или как трёхмерный вектор,
проведённый из начала координат в
эту точку (рис. 1.2). Компоненты a1,
a2, a3 будут проекциями вектора на
оси 1, 2 и 3, т. е.

Прi(a1, a2, a3) = ai,
i = 1, 2, 3.

В дальнейшем мы будем рассмат-
ривать компоненты n-элементного кортежа как проекции его на со-

Г л а в а 1

ответствующие оси, т. е.

Прia = ai,
i = 1, n.

Определение 1.13.
Прямым (декартовым) произведением
множеств X и Y называется множество, состоящее из всех тех и
только тех упорядоченных пар, первая компонента которых принад-
лежит множеству X, а вторая — множеству Y .
Таким образом, элементы декартового произведения множеств
представляют собой 2-элементные кортежи вида (x, y).
Формальное определение записывается следующим образом:

X × Y = {(x, y) | x ∈ X, y ∈ Y }.

Пример 1.1. Пусть X = {2, 4}, Y = {2, 6, 8}. Тогда декартово
произведение двух этих множеств будет следующим:

X × Y = {(2, 2), (2, 6), (2, 8), (4, 2), (4, 6), (4, 8)}.

Полученный результат проиллюстрирован на рис. 1.3,a.

Рис. 1.3. Геометрические иллюстрации прямого произведения множеств

Пример 1.2. Пусть X и Y — это отрезки вещественной оси.
Их декартово произведение, X × Y , отображается заштрихованным
прямоугольником, представленным на рис. 1.3,b.
Из этого примера со всей очевидностью можно заключить, что
свойства прямого произведения множеств несколько отличаются от
свойств обычного произведения в арифметическом смысле. В част-
ности, прямое произведение множеств изменяется при изменении по-
рядка сомножителей, т. е.

X × Y ‰ Y × X.

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