Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

С. Д. Данилова
С. С. Михайлова
Улан-Удэ 2022
ДИСКРЕТНАЯ
МАТЕМАТИКА

1
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Восточно-Сибирский государственный университет технологий и управления»
(ВСГУТУ)
С. Д. Данилова
С. С. Михайлова
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Улан-Удэ
Издательство ВСГУТУ
2022

2
УДК 519.1
ББК 22 176 2я73
Д 183
Печатается по решению редакционно-издательского совета ВСГУТУ
Рецензенты:
Л. В. Антонова, канд. физ.-мат. наук, проф. БГУ
В. В. Убодоев, канд. физ.-мат. наук, доц. ВСГУТУ
Данилова С. Д., Михайлова С. С.
Д 183 Дискретная математика: учеб. пособие. – Улан-Удэ: Изд-во ВСГУТУ, 2022. –
186 с. ISBN 978-5-907331-88-4
Учебное пособие предназначено для студентов направлений подготовки бакалавров
«Математическое обеспечение и администрирование информационных систем», «Про- граммная инженерия», «Информатика и вычислительная техника», «Информационные си- стемы и технологии», «Прикладная информатика», изучающих дисциплину «Дискретная математика».
Пособие состоит из теоретического курса и практикума с разделами по теории мно- жеств, алгебре логики, теории графов. Изложение каждой темы сопровождается необходи- мым теоретическим материалом, примерами решения типовых задач, контрольными вопро- сами для самопроверки.
Практикум связан с теоретическим курсом и предназначен для практической прора- ботки основных положений курса.
ISBN 978-5-907331-88-4
ББК 22.176.2я73
© С. Д. Данилова, С. С. Михайлова, 2022
© ВСГУТУ, 2022

3
ВВЕДЕНИЕ
Дискретная математика – область математики, занимающаяся изучением свойств дис- кретных структур, которые возникают как внутри математики, так и в ее приложениях.
Дискретная математика сегодня является не только фундаментом математической ки- бернетики, но и важным звеном математического образования.
Главной целью курса является развитие логического и алгоритмического мышления студентов, позволяющего повысить их способность к самоорганизации и самообразованию.
К основным задачам курса относятся формирование основных понятий дискретной математики; освоение приемов исследования и решения формализованных задач дискрет- ной математики; развитие умений применять знания дискретной математики в профессио- нальной деятельности; овладение основными концепциями, принципами, теориями и фак- тами, связанными с дискретной математикой.
Знание основ дискретной математики является важной составляющей общей инфор- мационной культуры выпускника. Эти знания необходимы как при проведении теоретиче- ских исследований в различных областях математики и информатики, так и при решении практических задач из разнообразных прикладных областей.
Учебное пособие представляет собой единый методически взаимоувязанный мате- риал и состоит из следующих взаимосвязанных разделов «Множества, отношения и функ- ции», «Алгебра логики», «Теория графов».
Знание теории множеств, алгебры логики и теории графов необходимо для четкой формулировки понятий и постановок различных прикладных задач, их формализации и компьютеризации, а также для усвоения и разработки современных информационных тех- нологий. Понятия и методы дискретной математики лежат в основе современной теории и практики программирования.

4
РАЗДЕЛ 1. МНОЖЕСТВА, ОТНОШЕНИЯ, ФУНКЦИИ
Тема 1.1. Введение в дискретную математику. Теория множеств
1.1.1. Семантика дисциплины «Дискретная математика»
Дискретная математика – область математики, которая занимается исследованием структур и задач на конечных или счетных множествах. Считается общепринятым деление математики на непрерывную и дискретную. Дискретность – это прерывность, которая про- тивопоставляется непрерывности и означает скачкообразное (дискретное) изменение ка- кой-либо величины во времени. Для компьютерных технологий «дискретный» является си- нонимом «целочисленный». Например, любое действительное число имеет форму дискрет- ных чисел в виде двоичных кодов.
Дискретность – это свойство, позволяющее различать однотипные или однородные объекты.
Специфика задач дискретной математики в первую очередь предполагает отказ от ос- новных понятий классической математики – предела и непрерывности. Вместе с задачами о существовании, имеющими общематематический характер, важное место в дискретной математике занимают задачи, связанные с алгоритмической разрешимостью и построением конкретных алгоритмов.
При исследовании, анализе и решении управленческих проблем, моделировании объ- ектов исследования и анализа широко используются дискретные методы формализован- ного представления, являющиеся предметом рассмотрения в дискретной математике. К ним относятся методы, основанные на теоретико-множественных представлениях, графы, алго- ритмы, математическая логика и др.
Дискретная математика предлагает:
− универсальные средства (языки) формализованного представления;
− способы корректной переработки информации, представленной на этих языках;
− возможности и условия перехода с одного языка описания явлений на другой с со- хранением содержательной ценности моделей.
Дискретная математика, по существу, стала активно развиваться с начала XX в., когда стали изучаться возможности формализации математики и были получены фундаменталь- ные результаты в области математической логики. Это результаты Поста, Клини и особенно
Геделя. Теорема неполноты Геделя имеет мировоззренческое значение – она показывает ограниченность формальных методов построения математической теории.
Информатизация и компьютеризация общества во второй половине XX в. в значитель- ной степени стимулировала развитие дискретной математики. Сегодня дискретная матема- тика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов
– обязательное квалификационное требование к специалистам в области информатики.
1.1.2. Понятие множества и способы представления множеств
Раздел математики, занимающийся множествами, называется теорией множеств. Ее основоположником был немецкий математик Георг Кантор (1845–1918).

5
Понятие множества является первоначальным понятием теории множеств, и ему нельзя дать определение через другие понятия этой теории.
Интуитивно понятие множества в математике выведено из понятия совокупностей, образуемых из ограниченного количества предметов, сведенных к единице по тем или иным признакам.
Множества обозначаются прописными латинскими буквами, и при необходимости ис- пользуются натуральные индексы:
????, ????, … , ????, ????
1
, ????
1
, … , ????
1
, ????
2
, ????
2
, … , ????
2
, …
Предметы, собранные во множество, называются элементами множества. Элементы множества обозначаются строчными латинскими буквами.
Принадлежность элемента а множеству ???? обозначается ???? ∈ ????, читается
«а принадлежит ????»; непринадлежность обозначается ???? ∉ ????.
Примеры множеств:
1. Множество студентов группы.
2. Числовые множества:
???? – множество натуральных чисел,
Z – множество целых чисел,
???? – множество рациональных чисел,
????– множество действительных чисел,
???? – множество комплексных чисел.
3. Множество всех решений уравнения sin ???? = 1. Элементы этого множества – дей- ствительные числа, общий признак – обращение данного уравнения в верное равенство.
Способы з ад ания множест в :
1. Перечисление элементов множества. В этом случае элементы множества перечис- ляются через запятые и заключаются в фигурные скобки. Например, множество чисел, яв- ляющихся делителями числа 20:
???? = {1, 2, 4, 5, 10, 20}.
2. Задание множества порождающей процедурой. Здесь порождающая процедура описывает способ получения элементов множества из уже полученных элементов этого множества либо из других объектов. Элементами множества считаются все объекты, кото- рые могут быть получены с помощью этой процедуры.
Например
???? = {????|????
2
− 4 = 0, ???? ∈ ???? }.

6
Здесь исходными объектами для построения множества ???? являются элементы множе- ства действительных чисел ℝ, а порождающей процедурой – вычисление, описываемое формулой ????
2
− 4 3. Задание множества описанием свойств его элементов. В этом случае описыва- ются характеристические свойства элементов множества. Например,
???? = {????|20 < ???? < 57, ???? ∈ ???? }.
Здесь элементами множества ???? являются действительные числа больше числа 20 и меньше числа 57.
1.1.3. Мощность множества, пустое множество, универсальное множество
Множества могут быть конечными, т. е. состоять из конечного числа элементов, и бес-
конечными.
Определение 1.1. Количество элементов конечного множества ???? называется мощно-
стью множества ???? и обозначается |????|.
Пример
???? = {1, 2, 4, 5, 10, 20}, |????| = 6.
Определение 1.2. Множество мощности 0 (т. е. не содержащее элементов) называется
пустым множеством, обозначается .
Определение 1.2. Множество всех рассматриваемых в данной задаче элементов назы- вается универсальным множеством и обозначается U.
Пример
Если задача состоит в нахождении корней квадратных уравнений на множестве дей- ствительных чисел ℝ, то ℝ и будет универсальным множеством.
1.1.4. Подмножество, отношения включения и равенства множеств, булеан
Определение 1.3. Множество ????называется подмножеством множества????, если вся- кий элемент множества ????является элементом множества????, обозначается ???? ⊆ ????. При этом говорят, что множество ???? содержит или покрывает множество ????.
Знак ⊆ называется знаком (нестрогого) включения. Если ???? ⊆ ????, то говорят, что мно- жества ???? и ???? находятся в отношении (нестрогого) включения.
Определение 1.5. Множество всех подмножеств множества ???? называется булеаном множества ????, обознается 2
????
или
????(????).
Относительно любого булеана справедливо следующее утверждение.
Для любого конечного множества A верно равенство:

7
|2
????
| = 2
|????|
Пример
???? = {????, ????, ????}, |????| = 2.
????(????) = {, {????}, {????}, {????}, {????, ????}, {????, ????}, {????, ????}, {????, ????, ????}}, |????(????)| = 2 3
= 8.
Определение 1.6. Множества ???? и ???? называются равными, если их элементы совпа- дают, иначе говоря, если ???? ⊆ ???? и ???? ⊆ ????, обозначается ???? = ????.
Пример
Даны множества:
???? = {????, ????, ????}, ???? = {????, ????, ????, ????, ????, ????},
Эти два множества равны, так как их элементы совпадают.
Приведенный пример наглядно показывает два очевидных факта:
− множество – это структура, в которой элементы не упорядочены;
− во множестве все элементы различны: сколько бы раз элемент ни был перечислен во множестве, он – единственный.
Определение 1.7. Множество ????называется строгим (истинным, собственным) под-
множеством множества????, если ???? ⊆ ????, ???? ≠ ????, обозначается ???? ⊂ ????.
Знак ⊂ называется знаком строгого включения. Если ???? ⊂ ????, то говорят, что множе- ства ???? и ???? находятся в отношении строгого включения.
Пример
1.
ℕ ⊂ ℤ ⊂ ℚ.
2. Пусть
???? – множество всех марок автомобилей. Тогда множество
???? = {????????????????, ????????????????????????, ????????????????????????} будет собственным подмножеством множества ????.
1.1.5. Операции над множествами и их основные свойства. Диаграммы Венна
Операции над множествами (или теоретико-множественные операции) и связанные с ними соотношения представляются наглядно с помощью диаграмм Венна, названных име- нем английского ученого Джона Венна (1834–1923). На этих диаграммах универсальное множество
U
изображается прямоугольником, а множества – кругами (или какими-нибудь другими замкнутыми фигурами). Точки, лежащие внутри круга, рассматриваются как эле- менты множества, представленного этим кругом. Общая часть двух кругов, пересекающих друг друга, представляет общие элементы двух множеств. Имея построенную диаграмму
Венна, можно заштриховать (или закрасить) определенные области для обозначения вновь образованных множеств.
Операции над множествами рассматриваются как получение новых множеств из уже существующих. Приведем определения известных теоретико-множественных операций.

8
Определение 1.8. Объединением множеств ????и ???? называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств ????или ????:
????⋃???? = {????|???? ∈ ???? или ???? ∈ ????}.
На диаграмме Венна (рис. 1.1) вся закрашенная область иллюстрирует операцию объ- единения ????⋃????.
Рисунок 1.1 – Диаграмма Венна объединения ????⋃????
Аналогично определяется объединение произвольной совокупности множеств. Если совокупность содержит небольшое количество множеств, то их объединение описывается явно: ????⋃????⋃????⋃???? и т. д.
В общем случае используется обозначение, которое читается как «объединение всех множеств ????, принадлежащих совокупности ????»: ⋃
????
????∈????
Если множества совокупности занумеровать индексами, т. е. ???? = {????
1
, … , ????
????
}, то объ- единение будет обозначаться как: ⋃
????
????
????
????=1
Если же совокупность множеств бесконечная, то используется обозначение: ⋃
????
????
∞
????=1
Пример
1. Даны множества
???? = {????, ????, ????} и ???? = {????, ????, ????, ℎ}. Тогда:
????⋃???? = {????, ????, ????, ????, ℎ}
2. На факультете имеется 25 академических групп. Обозначим группы как множества
????
????
, ???? = 1, … , 25. Тогда множество студентов факультета – это ⋃
????
????
25
????=1
, а множество групп студентов – это совокупность ???? = {????
1
, . . . , ????
25
}
Исходя из последнего примера, отметим, что всегда ???? ⊆ ????⋃???? , но неверно, что ???? ∈ ????⋃????.
Определение 1.9. Пересечением множеств ????и ???? называется множество, состоящее из тех и только тех элементов, которые принадлежат и множеству ????, и множеству ???? (рис. 1.2):
????⋂???? = {????|???? ∈ ???? и ???? ∈ ????}.
U
B
A

9
Рисунок 1.2 – Диаграмма Венна пересечения AB
Аналогично объединению для пересечения произвольной совокупности множеств ис- пользуются обозначения:
????⋂????⋂????⋂????, ⋂
????
????∈????
,
⋂
????
????
????
????=1
, ⋂
????
????
∞
????=1
Пример
1. Для множеств
???? = {????, ????, ????} и ???? = {????, ????, ????, ℎ}:
????⋂???? = {????, ????}
2. Для групп студентов:
⋂
????
????
25
????=1
=
,

более того, для любых ???? ≠ ????:
????
????
⋂????
????
=
.
Определение 1.10. Разностью множеств ????и ???? называется множество тех и только тех элементов множества ????, которые не принадлежат множеству ???? (рис. 1.3):
????\???? = {????|???? ∈ ???? и ???? ∉ ????}.
Рисунок 1.3 – Диаграмма Венна разности ????\????
В отличие от двух предыдущих операций разность строго двуместна: определена только для двух множеств.
Пример
Для множеств ???? = {????, ????, ????} и ???? = {????, ????, ????, ℎ}:
????\???? = {????}, ????\???? = {????, ????, ℎ}

10
Определение 1.11. Дополнением множества ???? (доуниверсального множества ????) назы- вается множество всех элементов ????, не принадлежащих множеству ???? (рис. 1.4):
???? = ????\????.
Рисунок 1.4 – Диаграмма Венна операции дополнения ????
Пример
Пусть ???? = {????, ????, ????, ????, ????, ????, ℎ, ????}, ???? = {????, ????, ????}, ???? = {????, ????, ????, ℎ}.
Тогда:
???? = {????, ????, ????, ℎ, ????};
???? = {????, ????, ????, ????}.
Определение 1.12. Симметрической разностью множеств ????и ???? называется множе- ство (рис. 1.5):
???? ∸ ???? = (????\????)⋃(????\????).
Рисунок 1.5 – Диаграмма Венна симметрической разности A B-
Пример
Для множеств ???? = {????, ????, ????} и ???? = {????, ????, ????, ℎ}:
???? ∸ ???? = {????, ????, ℎ}.
U
A

11
Свойства операций над множествами :
Для произвольных множеств ????, ????, ???? справедливы следующие соотношения.
1. Коммутативность объединения, пересечения и симметрической разности:
????⋃???? = ????⋃????;
????⋂???? = ????⋂????;
???? ∸ ???? = ???? ∸ ????.
2. Ассоциативность объединения, пересечения и симметрической разности:
????⋃(????⋃????) = (????⋃????)⋃????;
????⋂(????⋂????) = (????⋂????)⋂????;
???? ∸ (???? ∸ ????) = (???? ∸ ????) ∸ ????.
3. Дистрибутивность объединения относительно пересечения и пересечения относи- тельно объединения:
????⋃(????⋂????) = (????⋃????)⋂(????⋃????);
????⋂(????⋃????) = (????⋂????)⋃(????⋂????).
4. Идемпотентность объединения и пересечения:
????⋃???? = ????;
????⋂???? = ????.
5. Законы поглощения:
(????⋃????)⋂???? = ????;
(????⋂????) ⋃ ???? = ????.
6. Свойства нуля:
???? ⋃  = A;
????⋂ = .
7. Свойства единицы:
???? ⋃ ???? = ????;
????⋂???? = A.

12 8. Закон двойного отрицания (или инволютивность):
????̿ = ????.
9. Законы де Моргана:
????⋃???? = ????⋂????;
????⋂???? = ????⋃????.
10. Свойства дополнения:
????⋃???? = ????;
????⋂???? = .
11. Выражение для разности:
????\???? = ????⋂????.
Каждое из написанных выше равенств, верное для любых входящих в них множеств, часто называют теоретико-множественным тождеством.
Доказательство теоретико -множественных тождеств
Если требуется доказать теоретико-множественное тождество, то стандартным спосо- бом является доказательство двух утверждений о включениях, основанных на определении равенства множеств:
???? = ???? ????  ???? и ????  ????.
Доказательства этих включений проводятся по следующей схеме: полагается, что про- извольный элемент принадлежит меньшему по мощности множеству (слева от знака ), и устанавливается, что он также принадлежит большему по мощности множеству (справа от знака ).
Пример
Доказать равенство множеств: ???? ∪ ???? = ???? ∪ (????\????).
Решение:
Докажем, что ???? ∪ ????  ???? ∪ (????\????).
Пусть ???? ∈ ???? ∪ ????, тогда по определению объединения ???? ∈ ???? или ???? ∈ ????. Рассмотрим два случая:
1. Если
???? ∈ ????, то по определению объединения можем сказать ???? ∈  ∪ (????\????).
2. Если
????  ???? и ???? ∈ ????, то по определению разности множеств получим ???? ∈ ????\????. Зна- чит, ???? ∈  ∪ (????\????).
Докажем, что ???? ∪ (????\????)  ???? ∪ ????.