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

УДК 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.

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