Дискретная математика
Дискретная математика: Краткий обзор для начинающих
Эта книга представляет собой учебное пособие по дискретной математике, предназначенное для студентов среднего профессионального образования, изучающих компьютерные системы и прикладную информатику. Она охватывает ключевые разделы этой важной области, закладывая прочный теоретический фундамент для будущей профессиональной деятельности.
Теория множеств и бинарных отношений
Первый раздел посвящен основам теории множеств, включая основные понятия, операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность), а также метод включений-исключений. Рассматриваются понятия функций, отображений, бинарных отношений, их свойства и типы (отношения тождества, эквивалентности, упорядоченности, толерантности). Особое внимание уделяется комбинаторным задачам, таким как перестановки, размещения и сочетания, а также правилам суммы и произведения.
Теория графов
Второй раздел посвящен теории графов, которая является важным инструментом для моделирования и анализа дискретных систем. Рассматриваются основные понятия и определения графов, способы их задания (графический, матричный, функциональный), операции над графами (удаление вершин и ребер, дополнение, объединение, сложение). Изучаются понятия связности графов, деревьев, сетей, а также эйлеровы и гамильтоновы графы. Отдельное внимание уделяется вопросам устойчивости графов, включая вершинную и реберную связность, а также раскраске графов.
Математическая логика
Третий раздел посвящен математической логике, которая является основой для понимания принципов работы компьютеров и формальных систем. Рассматриваются алгебра высказываний, основные логические операции (дизъюнкция, конъюнкция, отрицание, импликация, эквивалентность, сложение Жегалкина), законы алгебры высказываний, таблицы истинности, равносильность и двойственность формул. Изучаются булевы (логические) функции, нормальные формы представления логических функций (ДНФ и КНФ), функционально полные системы логических функций и критерий Поста-Яблонского.
Формальные теории и исчисления
Четвертый раздел посвящен формальным теориям и исчислениям. Рассматриваются основные свойства формальных теорий (выводимость, интерпретация, общезначимость, разрешимость, непротиворечивость, полнота, независимость), исчисление высказываний, теорема о дедукции, связь между исчислением высказываний и алгеброй высказываний. Рассматриваются основы построения математических доказательств.
Элементы теории и практики кодирования
Пятый раздел посвящен основам теории и практики кодирования, включая алгебру вычетов, шифры замены (в частности, шифр Цезаря и шифр Вижинера), перестановочные шифры (включая шифр сциталы, шифр вертикальной перестановки, двойную перестановку и поворотную решетку), а также решение простейших задач шифрования.
- Среднее профессиональное образование
- 09.02.01: Компьютерные системы и комплексы
- 09.02.05: Прикладная информатика (по отраслям)
- 09.02.06: Сетевое и системное администрирование
- 09.02.07: Информационные системы и программирование
- 09.02.08: Интеллектуальные интегрированные системы
- 09.02.09: Веб-разработка
- 09.02.10: Разработка компьютерных игр, дополненной и виртуальной реальности
УЧЕБНИК Москва КУРС ИНФРА-М 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. Формат 6090/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
Δ
=
∪
∩
=
∩
∪
∩
(
) \ (
)