Сборник задач по дискретной математике

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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Е. Н. Порошенко

Сборник задач
по дискретной математике

Утверждено Редакционно-издательским советом университета
в качестве учебного пособия

2-е издание, исправленное и дополненное

НОВОСИБИРСК
2018

УДК
519.1(076.1)
П598

Рецензенты:
д-р физ.-мат. наук, профессор C. В. Судоплатов,
канд. физ.-мат. наук, доцент Е. В. Грачёв

Порошенко Е. Н.
П598
Сборник задач по дискретной математике: учеб. пособие/
Е. Н. Порошенко. — 2-е изд., испр. и доп. — Новосибирск: Изд-во НГТУ,
2018. — 132 c.

ISBN 978-5-7782-3562-5

В пособии подобраны задачи по курсу дискретной математики, читаемому на
I–II курсах НГТУ. Кроме того, в нем содержится большое количество примеров,
способствующих самостоятельной работе и приобретению навыков решения задач.

Работа подготовлена на кафедре алгебры и математической логики

В авторской редакции

УДК 519.1(076.1)

ISBN 978-5-7782-3562-5
c⃝Порошенко Е. Н., 2013, 2018

c⃝Новосибирский государственный
технический университет, 2013, 2018

Предисловие ко второму изданию

Предыдущее издание сборника задач появилось около пяти лет назад. Как зачастую бывает в первых изданиях, в нем было обнаружено довольно большое количество опечаток и неточностей. С накоплением некоторой критической массы
опечаток и неточностей возникла необходимость в новом издании, в котором они
были бы исправлены. Тем не менее, автор будет признателен читателям за помощь
в обнаружении незамеченных ранее опечаток.
Кроме того, во втором издании расширен набор задач для работы на практических занятиях, а также для самостоятельной работы студентов. В основном задачи
были добавлены в разделы первых четырех глав. В подавляющем большинстве случаев новые задачи либо помещены в конце списка раздела, (в случае если задача
принципиально отличается от приведенных ранее), либо (в случае, когда задача
носит технический характер и добавляется к набору задач на ту же тему) добавлены в тот же номер в качестве новых пунктов, причем эти пункты также обычно
размещены в конце номера.
Нумерация глав и разделов сохранена как в первом издании, как и способ нумерации задач (каждая задача нумеруется тремя числами, первое из которых задает
номер главы, второе — номер раздела, третье — номер задачи в разделе). Во втором
издании сохранен также и список основных обозначений, претерпевший незначительные изменения и помещенный, как и в первом издании, в начало сборника
задач.

E. Н. Порошенко

Предисловие к первому изданию

Данное пособие возникло, как естественное продолжение сборника задач [4], имевшего целью осуществить подборку задач по основным темам, традиционно входящим в курс дискретной математики, читаемый в НГТУ.
Следует отметить, что автор не преследовал цели создавать теоретический учебник. Таковые учебники уже существуют, в частности, можно отметить учебник
С. В. Судоплатова и Е. В. Овчинниковой [5]. Кстати говоря, данное пособие следует
использовать как раз вместе с этим учебником.
В данном же пособии автор ставит гораздо менее глобальную цель: восполнить
недостаток в примерах, который обычно возникает при преподавании почти всех
математических (и не только) курсов и, в частности, курса дискретной математики.
Таким образом, автор попытался использовать подход, наиболее удачно применяемый при обучении студентов технических (то есть прикладных) специальностей,
разбив каждый раздел данного пособия. В первой части разбираются примеры более или менее типичных задач из раздела, при этом делаются акценты на методы,
используемые при решении стандартных задач того или иного раздела. Во второй
части предлагаются задачи для решения на практических занятиях и в процессе
самостоятельной подготовки студентов. При этом, кроме типовых задач приведены
и задачи, требующие более глубокого понимания материала, в частности, так называемые “задачи на доказательство”. В конце пособия приведены ответы ко всем
“вычислительным” задачам.

Как уже отмечалось, наибольший эффект от самостоятельной работы по освоению курса “Дискретная математика” достигается, если использовать данное пособие вместе с учебником [5]. Вначале следует внимательно изучить теоретический
материал по этому учебнику, после чего следует переходить к разбору примеров
настоящего учебного пособия, возвращаясь по мере необходимости к тому или иному разделу учебника [5]. Для удобства читателя, в решениях примеров содержатся
ссылки на теоремы, формулировки которых приведены в [5] или на разделы, в которых излагается материал, необходимый для решения той или иной задачи. Также
ссылки на учебник [5] содержатся и в прилагаемом списке основных обозначений,
по причине краткости комментариев к обозначениям в данном пособии. Лишь после
того, как достигнуто принципиальное понимание методов, используемых при решении примеров, следует переходить к самостоятельному решению задач из второй
части соответствующего раздела.
Учебное пособие содержит шесть глав, разбитых на разделы и охватывающих
следующую тематику.

1. Основы теории множеств. Отношения и функции.

2. Алгебраические системы.

3. Дистрибутивные решетки и булевы алгебры.

4. Системы счисления. Основы теории чисел.

5. Избранные разделы теории графов.

6. Алгебра логики.

К сожалению, задачников, охватывающих все перечисленные разделы, очень
мало. В качестве исключения можно привести, пожалуй, только задачник
Г. П. Гаврилова и А. А. Сапоженко [2, 3], однако, он предназначен скорее для
студентов-математиков, к тому же со времени последнего издания этого задачника прошло уже 20 лет. Так что данное пособие в какой-то степени закрывает этот
пробел.
В заключение, автор хотел бы выразить искреннюю благодарностью А. В. Чехонадских, любезно предоставившему часть задач для этого пособия. Кроме того,
автор будет благодарен за предложения и замечания, высказанные по поводу данного учебного пособия. Их можно отправлять по адресу algebra@nstu.ru.

E. Н. Порошенко

Список обозначений

δP — область определения отношения P (стр. 12, 21∗1);
ρP — область значений отношения P (стр. 12, 21∗);
idA —тождественное отношение, то есть отношение {(x, x) | x ∈ A}
(стр. 21, 21∗);
[P] — матрица бинарного отношения P (стр. 17, 34∗);
P(A) — булеан (множество всех подмножеств) множества A (стр. 30,
15∗);
A1 × A2 × · · · × An — декартово произведение множеств, то есть множество {(a1, a2, . . . an) | a1 ∈ A1, . . . , an ∈ An} упорядоченных наборов
длины n, первый элемент каждого из которых лежит в множестве A1,
второй — в множестве A2 и так далее. (стр. 10, 19∗);
An — декартова степень множества. По определению
An = A × A × · · · × A
n раз
. (стр. 12, 19∗);

BA — множество всех функций f : A → B (стр. 39, 25∗);
N = {0, 1, 2, . . . } — множество натуральных чисел (стр. 10, 14∗);
Z = {. . . , −2, −1, 0, 1, 2, . . . } — множество целых чисел (стр. 8, 14∗);

Q =
x
x = p

q; p, q ∈ Z, q ̸= 0
— множество рациональных чисел

(стр. 29, 14∗);
R — множество действительных чисел (стр. 9, 14∗);
C = {x + yi | x, y ∈ R} — множество комплексных чисел (стр. 24, 14∗);
P + Si = {x + yi | x ∈ P, y ∈ S} (стр. 42), где P и S — некоторые числовые множества;
P+ — множество всех положительных чисел из P (стр. 14);
P+
0 — множество всех неотрицательных чисел из P (стр. 14);
P− — множество всех отрицательных чисел из P (стр. 16), в последних
трех обозначениях P = N, Z, Q, R;
P∗ — множество всех ненулевых чисел из P (стр. 20), здесь P =

1Здесь и далее знаком ∗ отмечены номера страниц, из книги [5]

Список обозначений

N, Z, Q, R, C;
nP+r — множество всех чисел множества P, дающих при делении на n
остаток r (стр. 30), где P = N или Z; в частности, nP — это множество
чисел множества P кратных n (стр. 8);
Zn — алгебра ⟨{0, 1, 2, . . . , n−1}; ⊕, ∗⟩, где a⊕b и a∗b определены, как
остатки от деления соответственно a + b и ab на n (стр. 45, 102∗),
Z∗
n — группа всех обратимых (по умножению) элементов множества Zn
(стр. 46),
в двух последних обозначениях n — целое число, большее 1;
H — группа кватернионов, то есть группа, носителем которой является
восьмиэлементное множество {±1, ±i, ±j, ±k} с операцией умножения,
определенной следующим образом: i2 = j2 = k2 = −1, ij = −ij = k,
jk = −kj = i, ki = −ik = j; (стр. 46);
Cn — циклическая группа c n элементами (стр. 45), где n — целое число большее 1;
F[x] — множество многочленов от переменной x с коэффициентами из
множества F (стр. 42);
Fn[x] — множество многочленов степени n от переменной x с коэффициентами из множества F (стр. 42);
F⩽n[x] — множество многочленов степени не выше n от переменной x с
коэффициентами из множества F (стр. 42);
M(F) — множество всех матриц с элементами из множества F (стр. 42);
Mn×m(F) — множество матриц размера n × m с элементами из множества F (стр. 42);
Mn(F) — множество квадратных матриц n × n с элементами из множества F (стр. 42);
det — определитель матрицы (стр. 23);
O — нулевая матрица (стр. 43);
Tn — группа симметрий правильного n-угольника (стр. 46);
V3 — множество векторов в пространстве (стр. 23);
{x} — дробная часть числа x (стр. 47);
(n, m) — наибольший общий делитель чисел m и n (стр. 61, 97∗);
[n, m] — наименьшее общее кратное чисел m и n (стр. 61, 98∗);
(u, v) — дуга в графе, идущая из вершины u в вершину v (стр. 75,
118∗);
[u, v] — ребро в графе, соединяющее вершины u и v (стр. 75, 119∗);
AG — матрица смежности графа G, то есть матрица, в которой для
любой пары чисел i и j на пересечении i-ой строки и j-го столбца стоит

Список обозначений
7

единица тогда и только тогда, когда в графе G есть дуга (i, j), а на
остальных местах стоят нули. (стр. 76, 121∗);
AG,k — матрица маршрутов длины k графа G, то есть матрица, в которой для любой пары чисел i и j на пересечении i-ой строки и j-го
столбца стоит число маршрутов длины k, начинающихся в i-ой вершине
и заканчивающихся в j-ой. (стр. 87, 131∗);
BG — матрица инцидентности графа G (стр. 77, 122∗);
e(v) — эксцентриситет вершины v (стр. 91, 134∗);
ρ(v, u) — расстояние между вершинами v и u (стр. 94, 135∗).
r(G) — радиус графа G (стр. 91, 135∗);
d(G) — диаметр графа G (стр. 91, 134∗);
Kn — полный n-вершиник, то есть граф, у которого каждая его вершина смежна со всеми остальными вершинами G (стр. 95, 135∗);
Km,n — полный двудольный (m, n)-вершинник, то есть граф, вершины
которого разбиваются на два множества, содержащие, соответственно,
n и m вершин, причем каждая его вершина из первого множества смежна со всеми вершинами из второго. (стр. 94, 164∗).

Глава 1

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

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

Пример 1.1. Множество A = {понедельник, вторник, среда, четверг,
пятница, суббота, воскресенье} состоит из всех дней недели, а множество B = {x ∈ Z | x = 3y для некоторого y ∈ Z} — это множество всех
целых чисел, кратных трем.
□

Пример 1.2. Перечислить все элементы множества

A =
1, 2, {1, 2}, {1}
.

Решение. Множество A состоит из четырех элементов: 1; 2; множество,
состоящее из 1, 2; множество, состоящее из 1. Следует отметить, что
1 и множество, состоящее из 1, — это различные элементы множества
A1.

Пример 1.3. Для множества A = {1, 2, 3} найти его булеан

Доказательство. Очевидно, что булеаном множества A, то есть множеством его подмножеств является

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

Пример 1.4. Доказать, что множество 6Z является подмножеством
множества 3Z.

Решение. Пусть x — элемент множества 6Z, то есть x делится на 6,
тогда x = 6y для некоторого целого числа y. Имеем 6y = 3(2y), причем

1Удобно рассматривать множество, например, как мешок, в котором “лежат” его элементы.
Тогда 1 это просто элемент “лежащий” в мешке, символизирущем множество A, а множество,
состоящее из 1 —- это мешок, в котором “лежит” 1, который, в свою очередь, “лежит” мешке,
символизирующем множество A.

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

2y целое. Отсюда следует, что x делится на 3 и, следовательно, является
элементом множества 3Z, что и требовалось доказать.

Пример 1.5. Доказать, что множества A = {x ∈ R | | tg x| = 1} и

B =
x
x = (2m + 1)π

4
для некоторого целого числа m
равны.

Доказательство. Пусть x ∈ A. Тогда | tg x| = 1, то есть tg x = 1 или
tg x = −1. В первом случае, решая уравнение, получаем

x = π

4 + πn = (4n + 1)π

4
= (2(2n) + 1)π

4
.

Во втором случае —

x = 3π

4 + πk = (2(2k + 1) + 1)π

4
.

Таким образом, доказано, что A ⊆ B.

Пусть теперь x ∈ B, то есть x = (2m + 1)π

4
для некоторого целого
числа m. Вычислив значение tg x, получаем, tg x = 1, если m четно
или tg x = −1, если m нечетно. Следовательно, B ⊆ A, что и завершает
доказательство.

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

Пример 1.6. Доказать, что для любых множеств A, B и C выполняется равенство A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Доказательство. Для доказательства необходимо проверить, что имеют место два включения: A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C) и
(A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C).
Пусть x ∈ A ∪ (B ∩ C). Тогда x ∈ A, или x ∈ B ∩ C.
Если x ∈ A, то очевидно, x ∈ A ∪ B и x ∈ A ∪ C. Следовательно,
x ∈ (A ∪ B) ∩ (A ∪ C).
Если же x ̸∈ A, то x ∈ B ∩ C. Значит x ∈ B и x ∈ C. Получаем
x ∈ A ∪ B и x ∈ A ∪ C, то есть x ∈ (A ∪ B) ∩ (A ∪ C). Таким образом,
A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C).
Пусть теперь x ∈ (A ∪ B) ∩ (A ∪ C). Тогда x ∈ A ∪ B и x ∈ A ∪ C.
Так как x ∈ A ∪ B, получаем x ∈ A или x ∈ B.
Если x ∈ A, то x ∈ A ∪ (B ∩ C).
Если же x ̸∈ A, то x ∈ B и в силу того, что x ∈ A∪C, получаем x ∈ C.
Значит x ∈ B ∩ C, то есть x ∈ A ∪ (B ∩ C). То есть (A ∪ B) ∩ (A ∪ C) ⊆
A ∪ (B ∩ C).
Из доказанного получаем A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

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

Пример 1.7. Доказать, что для любых множеств A и B справедливо
равенство A ∩ (B\A) = ∅.

Доказательство. Так как пустое множество является подмножеством
любого множества, нам осталось доказать, что A ∩ (B\A) не содержит
ни одного элемента, а значит является подмножеством ∅.
Пусть x ∈ A ∩ (B\A). Тогда x ∈ A и x ∈ B\A. Однако, из второго
выражения следует, что x ∈ B и x ̸∈ A, что противоречит первому
выражению. Таким образом, доказано включение A ∩ (B\A) ⊆ ∅, а
вместе с ним и равенство A ∩ (B\A) = ∅.

Пример 1.8. Доказать, что для любых множеств A, B и C выполнено
равенство (A ∩ B) × C = (A × C) ∩ (B × C).

Доказательство. Пусть x ∈ (A ∩ B) × C. Тогда x = (y, z), причем y ∈
(A ∩ B), а z ∈ C. Отсюда следует, что y ∈ A и y ∈ B. Соответственно,
x = (y, z) ∈ A × C и x ∈ B × C. Следовательно, x ∈ (A × C) ∩ (B × C).
Таким образом, доказано, что (A ∩ B) × C ⊆ (A × C) ∩ (B × C)
Пусть x ∈ (A × C) ∩ (B × C), тогда x ∈ A × C и x ∈ B × C. Отсюда
следует, что x = (y, z). Из первого утверждения получаем y ∈ A и
z ∈ C, а из второго, что y ∈ B и z ∈ C. Таким образом, y ∈ A ∩ B и
z ∈ C, следовательно x ∈ (A∩B)×C. Получили, что (A×C)∩(B×C) ⊆
(A ∩ B) × C. Следовательно, (A ∩ B) × C = (A × C) ∩ (B × C), что и
требовалось доказать.

1.1. Задачи

1.1.1. Перечислить элементы множеств:

а) A = {x ∈ N | x2 − 5x ⩽ 14};
б) B =
x ∈ Z
1
5 < 3x ⩽ 9
;

в) A ∪ B;
г) A ∩ B;
д) A\B;
е) B\A.
1.1.2. Перечислить элементы множеств:

а) A =
x ∈ Z
log3 |x| ⩽ 1, 2x > 1

6

;
б) B = {x ∈ N
|x − 2| < 4};

в) A ∪ B;
г) A ∩ B;
д) A\B;
е) B\A.
1.1.3. Даны множества A = [−2, 4), B = [0, 6). Найти:
a) A ∪ B;
б) A ∩ B;
в) A\B;
г) B\A.
1.1.4. Даны множества A = [−3, 5), B = (−1, 2]. Найти:
a) A ∪ B;
б) A ∩ B;
в) A\B;
г) B\A.