Дискретная математика в примерах и задачах

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

Т. В. Моисеенкова

ДИСКРЕТНАЯ МАТЕМАТИКА 
В ПРИМЕРАХ И ЗАДАЧАХ

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

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

УДК 519.1(07)
ББК 22.174я73
М748

Р е ц е н з е н т ы: 
Я. Н. Нужин, доктор физико-математических наук, профессор Сибирского федерального университета;
И. В. Шевелева, кандидат физико-математических наук, доцент Сибирского федерального университета

Моисеенкова, Т. В.
М748
Дискретная математика в примерах и задачах : учеб. пособие / 
Т. В. Моисеенкова. – Красноярск : Сиб. федер. ун-т, 2018. – 132 с.
ISBN 978-5-7638-3967-8

Изложен краткий теоретический материал по разделам дискретной математики: множества, отношения, комбинаторика, математическая логика, графы. 
Приведены примеры и задачи с решениями. Даны задачи и упражнения для самостоятельной работы.
Предназначено студентам укрупненных групп направлений подготовки 
11.00.00 «Электроника, радиотехника и системы связи», 12.00.00 «Фотоника, приборостроение, оптические и биотехнические системы и технологии», 
направлений 27.03.05 «Инноватика», 09.03.03 «Прикладная информатика», 
38.03.05 «Бизнес-информатика» и специальности 25.05.03 «Техническая эксплуатация транспортного радиооборудования».

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

ISBN 978-5-7638-3967-8
© Сибирский федеральный
университет, 2018

ВВЕДЕНИЕ

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

3

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

4

В пособии будем использовать следующие обозначения:

N – множество натуральных чисел;
Z – множество целых чисел;
Q – множество рациональных чисел;
R – множество действительных чисел;
C – множество комплексных чисел;
P+ – множество всех положительных чисел из множества P;
P+
0 – множество всех неотрицательных чисел из множества P;
[x] – наибольшее целое число, не превосходящее x∈R;
⇒ – если . . . , то . . . ;
⇔ – . . . , тогда и только тогда . . . ;
C =(cij)m×n – матрица C размерности m×n, состоящая из
элементов cij; i=1, 2, . . . , m; j =1, 2, . . . , n.

5

1. Элементы теории множеств

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

Через ∈ обзначается отношение принадлежности, т. е. x∈A означает, что элемент x принадлежит множеству A. Если x не является элементом множества A, то это записывается x /∈A.

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

Свойство, которым обладают элементы множества A и только они,
называется характеристическим свойством множества A.
Под «формой от x» будем понимать конечную последовательность, состоящую из слов и символа x такую, что если каждое вхождение
x в эту последовательность заменить одним и тем же именем некоторого
предмета соответствующего рода, то в результате получится истинное
или ложное предложение. Обозначим форму от x через P(x).

Пример 1.1.1. «x2=4», «x – сосед Петрова» – формы от x, а выражение
«существует такой x, что x2−2x=4» не является формой от x.

Интуитивный принцип абстракции. Любая форма P(x) определяет некоторое множество A, а именно множество тех и только
тех предметов a, для которых P(a) — истинное предложение.

Множество A, определяемое формой P(x), обозначается

A={x|P(x)}.

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

Пример 1.1.2.
Множество A={1, 2, 3} можно следующим образом
представить формой P(x):

A={x|x — целое положительное число, меньшее 4},

A={x|x∈Z, 0<x<4},
A={x|x3−6x2+11x−6=0}.

Если каждый элемент множества A является одновременно элементом множества B, то B называют подмножеством множества A и
пишут A⊆B.

6

Если A⊆B, но A̸=B, то B называют
собственным подмножеством множества A и пишут A⊂B.
Множество, не содержащее элементов, называется пустым множеством и обозначается ∅. Все рассматриваемые множества являются подмножествами некоторого множества U — универсального множества.
Множество всех подмножеств множества A называется булеан или
множество степень множества A и обозначается B(A).

Пример 1.1.3. Если A={1, 2, 3}, то

B(A)={∅, {1}, {2}, {3}{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Заметим, что пустое множество является подмножеством любого множества, т. е. ∅⊆A, и что 1̸={1}, так как 1∈A, а {1}⊆A.

Операции на множествах

Для произвольных множеств A, B определяются операции:
Объединение множеств A и B:

A∪B ={x|x∈A или x∈B}.

Пересечение множеств A и B:

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

Разность множеств A и B:

A\B ={x|x∈A и x /∈B}.

Дополнение множества A:

A={x|x /∈A}.

Симметрическая разность множеств A и B:

A△B =(A\B)∪(B\A).

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

7

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

Пример 1.1.4. Дано:

a) A={1, 3, 4, 5, 9}, B ={2, 4, 5, 10}, U=Z;

б) A={x|x∈Z, −3<x<4 }, B ={x|x∈Z, |x−3|<2};

в) A={x|x∈R, −3<x<4 }, B ={x|x∈R, |x−3|<2}.

Найти A∪B, A∩B, A\B, B\A, A△B, B\A.

Решение. a) по определению операций на множествах получим

A∪B ={1, 2, 3, 4, 5, 9, 10}, A∩B ={4, 5}, A\B ={1, 3, 9},

B\A={2, 10}, A△B ={1, 2, 3, 9, 10}, B\A={4, 5}.

б) зададим множества перечислением элементов:

U=Z, A={−2, −1, 0, 1, 2, 3} B ={2, 3, 4}. Тогда

A∪B ={−2, −1, 0, 1, 2, 3, 4}, A∩B ={2, 3}, A\B ={−2, −1, 0, 1},

B\A={4}, A△B ={−2, −1, 0, 1, 4}, B\A={2, 3}.

в) A∪B ={x|x∈R, −3<x<5}, A∩B ={x|x∈R, 1<x<4},

A\B ={x|x∈R, −3<x<1}, B\A={x|x∈R, 4<x<5},

A△B ={x|x∈R, x∈(−3, 1)∪(4, 5)}, B\A={x|x∈R, 1<x<4}.

Свойства операций на множествах

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

8

Коммутативность:
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.
Законы поглощения:
8. A∪(A∩B)=A;
8∗. A∩(A∪B)=A.
Закон двойного дополнения:
9. A=A.

Для доказательства тождества A=B достаточно показать включения A⊆B и B ⊆A, используя определения операций над множествами.

Пример 1.1.5. Доказать тождество A∩B =A∪B (закон де Моргана).

Решение. Докажем, что A∩B ⊆A∪B.
Пусть x∈A∩B =⇒x /∈A∩B =⇒x /∈A или x /∈B =⇒x∈A или
x∈B =⇒x∈A∪B.
Докажем, что A∩B ⊆A∪B.
Пусть x∈A∪B =⇒x∈A или x∈B =⇒x /∈A или x /∈B =⇒
x /∈A∩B =⇒x∈A∩B.
Из A∩B ⊆A∪B и A∩B ⊆A∪B =⇒ A∩B =A∪B.

Декартово произведение множеств

Декартовым (прямым) произведением множеств A и B называется множество
A×B ={(a, b)|a∈A, b∈B}.

Декартово произведение A×A=A2 называется декартовым квадратом множества A.

Пример 1.1.6. Пусть A={1, 2, 3}, B ={a, b}. Тогда

A×B ={(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)}.

9

B ×A={(a, 1); (a, 2)(a, 3); (b, 1); (b, 2); (b, 3)}.

Пример 1.1.6 показывает, что A×B ̸=B ×A при A̸=B.
Декартовым (прямым) произведением множеств A1, A2, ..., An
называется множество

A1×A2×...×An={(a1, a2, ..., an)|ai∈Ai; i=1, 2, ..., n}.

Если A1=A2=...=An, то декартово произведение

A×A×...×A=An

называется n-й декартовой степенью множества A.

Конечные множества

Множество A называется конечным, если оно содержит конечное
число элементов. Это число называется
мощностью
множества A и
обозначается через |A|.
Для конечных множеств A и B справедливы следующие формулы:

|A∪B|=|A|+|B|−|A∩B|;
(1)

|A∪B ∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B ∩C|+|A∩B ∩C|; (2)

|B(A)|=2|A|;
(3)

|A×B|=|A|·|B|.
(4)

Пусть A1, A2, ..., An — конечные множества, тогда

|A1×A2×...×An|=|A1|·|A2|·...·|An|.
(5)

Пример 1.1.7. Пусть |A|=n, |B|=m, n≥m. Выразить через n и m
мощности следующих множеств: max |A∪B|, min |A∪B|, max |A∩B|,
min |A∩B|, max |A\B|, min |A\B|.

Решение. Покажем на диаграммах Эйлера — Венна (рис. 2), в каких случаях объединение, пересечение и разность множеств будут принимать максимальное и минимальное значения соответственно.
Получаем
max |A∪B|=n+m, min |A∪B|=n, max |A∩B|=m,
min |A∩B|=0, max |A\B|=n, min |A\B|=n−m.

10