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

Министерство образования и науки Российской Федерации
Сибирский федеральный университет

А. В. Васильева, И. В. Шевелева

ДИСКРЕТНАЯ
МАТЕМАТИКА

Учебное пособие

Красноярск
СФУ
2016

УДК 519(07)
ББК 22.174я73

В191

Рецензенты: В. Р. Майер, доктор педагогических наук, заведующий
кафедрой алгебры, геометрии и методики их преподавания КГПУ
им. В. П. Астафьева;

Ю. В. Казаков, кандидат физико-математических наук, доцент кафедры высшей математики и информатики СибГТУ

Васильева, А. В.

В191
Дискретная математика : учеб. пособие / А. В. Васильева,
И. В. Шевелева. – Красноярск : Сиб. федер. ун-т, 2016. – 128 с.

ISBN 978-5-7638-3511-3

Изложен теоретический материал по разделам дискретной
математики: множества, отношения, математическая логика,
графы, который проиллюстрирован большим количеством примеров. Каждый раздел завершается вопросами и заданиями для самоконтроля. Приведены задания для самостоятельной работы.

Предназначено для студентов укрупненных групп направлений подготовки 11.00.00 «Электроника, радиотехника и системы связи»(11.03.01 «Радиотехника», 11.03.02 «Инфокоммуникационные технологии и системы связи», 11.03.03 «Конструирование
и технология электронных средств», 11.05.11 «Радиоэлектронные
системы и комплексы»), 12.00.00 «Фотоника, приборостроение,
оптические и биотехнические системы и технологии» (12.03.01
«Приборостроение»), направлений 09.03.03 «Прикладная информатика», 38.03.05 «Бизнес-информатика», 15.03.06 «Мехатроника и
робототехника», специальности 25.05.03 «Техническая эксплуатация транспортного радиооборудования».

Электронный вариант издания см.:
УДК 519(07)
http://catalog.sfu-kras.ru
ББК 22.174я73

ISBN 978-5-7638-3511-3
c⃝Сибирский федеральный
университет, 2016

ВВЕДЕНИЕ

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

3

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

4

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

1.1. Понятие
множества

Понятие множества является базовым в математике, на его основе
формируются другие понятия. В силу своей общности – это неопределяемое понятие.

Под множеством принято понимать любое собрание (совокупность)
определенных и различимых между собой объектов, мыслимое как единое целое. Эти объекты называются элементами данного множества.

В приведенном выше описании понятия множества, которое принадлежит основателю теории множеств немецкому математику Г. Кантору, существенным является то, что собрание объектов (множество) само
рассматривается как один предмет, как нечто целое. Относительно предметов, которые могут входить во множество, допускается значительная
свобода. Важно, что наша интуиция должна, во-первых, отделять их
один от другого даже тогда, когда их нельзя точно указать (например,
множество простых чисел), во-вторых, давать ответ на вопрос о принадлежности объекта данному множеству. Второе тесно связано со способами задания множеств.

Тот факт, что объект a является элементом множества A, другими
словами, a принадлежит множеству (содержится в множестве) A, символически обозначается: a∈A. В противном случае пишут a̸∈A.

Г. Кантор сформулировал несколько интуитивных принципов, которые естественно считать выполняющимися для произвольных множеств. В частности интуитивный принцип объемности, который оговаривает условия равенства объектов нашей теории, а следовательно, и их
различия.

Интуитивный принцип объемности. Множества A и B считаются равными, если они состоят из одних и тех же элементов. При этом
записывают A=B, если A и B равны, и A̸=B – в противном случае.

П р и м е р
1.1. Пусть множество A состоит из чисел 1 и 6, а B –
множество действительных корней уравнения x2−7x+6=0. Числа 1, 6 и
только они являются корнями данного уравнения, следовательно, в силу
принципа объемности заключаем, что множества равны, т. е. A=B.

Множество A, элементами которого являются объекты a1, a2, . . . ,
an и только они, обозначают A={a1, a2, . . . , an}.

5

1.2. Отношение
включения

Если каждый элемент множества A одновременно является элементом множества B, то A называют подмножеством множества B, и
пишут A⊆B. При этом множество B называют надмножеством множества A. Если A⊆B, но A̸=B, то A называют собственным подмножеством B, и обозначают A⊂B. Ясно, что для любых множеств A, B, C
справедливо:
1) A⊆A;
2) если A⊆B, B ⊆C, то A⊆C;
3) если A⊆B, B ⊆A, то A=B.
Таким образом, равенство двух множеств A и B равносильно двум
включениям: A⊆B, B ⊆A (A=B ⇔A⊆B, B ⊆A). Это используется при
доказательстве равенства множеств.
Нужно различать отношения принадлежности (∈) и включения
(⊆). Если множество A={a1, a2, . . . , an}, то a1∈A, но a1̸⊂A, так как
a1 не является подмножеством A. Однако, если ввести в рассмотрение
множество A1, состоящее из одного элемента a1, A1={a1}, то A1⊆A или
{a1}⊆A.
Множество, не содержащее элементов, называют пустым множеством и обозначают ∅. Например, множество действительных корней
уравнения x2 + 1=0 является пустым множеством. Этот простой пример иллюстрирует целесообразность введения понятия пустого множества. Пустое множество – подмножество любого множества, т. е. ∅⊆A
для любого множества A. Заметим, что множество C ={∅} не является
пустым, так как оно содержит элемент – ∅.
Сами множества могут быть элементами других множеств. Если
A={a1, a2}, B ={b1, b2}, то D={A, B} не содержит, например, в качестве
элементов a1 или b1, т. е. a1̸∈D, но A∈D, B ∈D.
Для множества A={a, b} рассмотрим все его подмножества: ∅, {a},
{b} и {a, b}. Тогда множество S(A)={∅, {a}, {b}, {a, b}} представляет собой «множество всех подмножеств» исходного множества A. Аналогично,
для любого множества A можно определить множество всех его подмножеств S(A), которое принято называть булеаном множества A или его
степенью.
Если множество A состоит из n элементов (обозначается: |A|=n),
то |S(A)|=2n. В частности, |∅|=0, |S(∅)|=|{∅}|=20=1.
Множество, элементами которого являются все возможные множества, принято называть универсальным множеством (универсумом) и

6

обозначать U. Таким образом, считают, что для любого множества A
справедливо: A⊆U. Однако на практике в качестве множества U выбирают подходящее для данной задачи множество. Например, если решается геометрическая задача, в которой рассматриваются только многоугольники, то имеет смысл в качестве множества U выбрать множество
всех многоугольников.

1.3. Способы
задания множеств

Все непустые множества можно разделить на конечные, которые
содержат конечное число элементов, и бесконечные, которые таковыми
не являются. Простейший способ задания множества – это перечисление
всех его элементов (точнее, «имен» этих элементов). Например, список
студентов учебной группы. Очевидно, что этим способом можно задать
только конечные множества. Например, множество A – всех целых чисел
на отрезке [1, 3] конечно, его можно задать перечислением A={1, 2, 3}.
Множество B – всех рациональных чисел этого отрезка задать перечисление нельзя, так как оно бесконечно.
Рассмотрим способы задания множеств, которые применимы к любым множествам. Множество можно задать с помощью порождающей
процедуры, т. е. указать правило, по которому из каких-то объектов строятся элементы данного множества. Например, множество натуральных
чисел N можно задать с помощью следующей порождающей процедуры:
1) 1∈N,
2) если x∈N, то x+1∈N.
Общепринятая запись: N={1, 2, ..., n, ...} не является заданием
множества N перечислением.
Еще одним способом задания множеств является задание множества с помощью характеристического свойства его элементов. Свойство,
которым обладают элементы множества A и только они, называется его
характеристическим свойством. Более точно этот способ задания можно описать, используя интуитивное понятие «формы от x». Под «формой от x» принято понимать конечную последовательность, состоящую
из слов и символа x, такую, что если каждое вхождение символа x заменить одним и тем же именем некоторого предмета, то в результате
получится истинное или ложное предложение. Например, формами от x
будут предложения: «5 делит x», «x – родственник Иванова». Напротив,
предложения «x2−4=(x−2)(x+2) для всех x» или «существует такое x,
что x>0» не являются формами от x. Форму от x обозначим через P(x).

7

Интуитивный принцип абстракции. Любая форма P(x) определяет некоторое множество A, а именно множество тех и только
тех предметов a, для которых P(a) – истинное предложение. Запись
A={x|P(x)} означает, что множество A определяется формой P(x). Например,
1) A={x|x – целое положительное число, меньшее 5}={1, 2, 3, 4};
2) A={x|x – буква русского алфавита, входящая в слово «мама»}=
={а, м};
3) A={x|x=2n, n∈N} – множество четных натуральных чисел.

1.4. Операции
над
множествами

Рассмотрим операции над множествами, которые представляют собой ряд правил, позволяющих получать новые множества из уже заданных.
Определение 1.1. Объединением (суммой) двух множеств A и B
называется множество A∪B, состоящее из тех и только тех элементов,
которые являются либо элементами множества A, либо элементами множества B:
A∪B ={x|x∈A или x∈B}.

Другими словами, в объединение A∪B входят все элементы как
множества A, так и множества B, и других элементов нет. При этом
всегда: A⊆A∪B, B ⊆A∪B.
Под объединением любой совокупности множеств будем понимать
новое множество, каждый элемент которого является элементом некоторого множества из данной совокупности, при этом любой элемент каждого множества совокупности есть элемент объединения. В частности,
для совокупности множеств: A1, A2, ..., An, ... имеем

A=

∞
i=1
Ai={x|x∈Ai, хотя бы для одного i=1, 2, . . . , n, . . . }.

Определение 1.2. Пересечением множеств A и B называется
множество A∩B, состоящее из тех и только тех элементов, которые являются как элементами множества A, так и элементами B.

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

Другими словами, в пересечение A∩B входят те и только те элементы множества A, которые входят в B. Если ни один элемент множества A не является элементом множества B, то A∩B =∅. В этом случае

8

говорят, что множества A и B не пересекаются. Ясно, что всегда справедливы включения: A∩B ⊆A, A∩B ⊆B.
Если множества A и B состоят из конечного числа элементов, то
справедливо следующее равенство

|A∪B|=|A|+|B|−|A∩B|.

Равенство |A∪B|=|A|+|B| выполняется только в случае, когда
множества A и B не пересекаются (A∩B =∅).
Для произвольной совокупности множеств под пересечением будем
понимать новое множество, состоящее из тех и только тех элементов,
которые входят во все множества данной совокупности. В частности,
для совокупности множеств: A1, A2, ..., An, ... имеем

A=

∞
i=1
Ai={x|x∈Ai, для всех i=1, 2, . . . , n, . . . }.

Определение 1.3. Разностью двух множеств A и B называется
множество A\B, элементами которого являются те и только те элементы
множества A, которые не принадлежат множеству B:

A\B ={x|x∈A, но x̸∈B}.

Очевидно, что A\B ⊆A.
Определение 1.4. Cимметрической разностью множеств A и B
называется множество A∆B =(A \ B) ∪ (B \ A). Другими словами, это
множество состоит из тех и только тех элементов A и B, которые не
входят в пересечение этих множеств.
Упражнение 1. Доказать, что A∆B =(A∪B)\(A∩B).
П р и м е р
1.2. Пусть A={1, 2, 3, a, b}, B ={a, b, c, 0, 1, 5}. Найти:
A∪B, A∩B, A\B, B \A, A∆B.
Согласно определениям 1.1 – 1.4: A∪B ={0, 1, 2, 3, 5, a, b, c}, A∩B =
={1, a, b}, A\B ={2, 3}, B \A={c, 0, 5}, A∆B ={0, 2, 3, 5, c}.
Определение 1.5. Дополнением множества A называется множество A всех тех элементов, которые не принадлежат A:

A={x|x̸∈A}.

Если U – универсальное множество, то A=U \A.
Разность X \A={x|x∈X, x̸∈A}, т. е. множество всех элементов
X, которые не принадлежат A, иногда называют относительным дополнением множества A до множества X. Отметим, что X \A=X ∩A.

9

Для наглядного представления отношений между подмножествами универсального множества используют диаграммы Эйлера – Венна.
Само универсальное множество U изображают в виде прямоугольника,
а его подмножества – в виде кругов, расположенных внутри прямоугольника.
На рис. 1 представлены диаграммы Эйлера – Венна, иллюстрирующие операции над множествами.

A\B
A∆B
A

A
A∪B
A∩B

A
B

U
A
B

U
A
U

A
U
A
B

U
A
B

U

Рис. 1

Сформулируем основные свойства операций объединения, пересечения и дополнения множеств.
Для любых подмножеств A, B, C и универсального множества
U выполняются следующие тождества:

Коммутативность:
1. A∪B =B ∪A;
1’. A∩B =B ∩A.
Ассоциативность:
2. A∪(B ∪C)=(A∪B)∪C;
2’. A∩(B ∩C)=(A∩B)∩C.
Дистрибутивность:
3. A∪(B ∩C)=(A∪B)∩(A∪C);
3’. A∩(B ∪C)=(A∩B)∪(A∩C).
Действия с константами:
4. A∪∅=A, A∪U =U;
4’. A∩∅=∅, A∩U =A.
5. A∪A=U;
5’. A∩A=∅.
Идемпотентность:
6. A∪A=A;
6’. A∩A=A.
Законы де Моргана:
7. A∪B =A∩B;
7’. A∩B =A∪B.

10