Дискретная математика. Сборник задач

СБОРНИК ЗАДАЧ

Москва
КУРС
ИНФРА-М
2021

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

А.И. ГУСЕВА
В.С. КИРЕЕВ
А.Н. ТИХОМИРОВА

Рекомендовано 
Экспертным советом при ГБОУ УМЦ ПО ДОгМ для использования 
в образовательном процессе профессиональных образовательных 
организаций города Москвы в качестве учебника для студентов 
среднего профессионального образования по специальностям 
2.09.02.01 «Компьютерные системы и комплексы», 
2.09.02.05 «Прикладная информатика (по отраслям)», 
2.09.03.03 «Прикладная информатика»

СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ

УДК 519.854(076.1)
ББК В174я73-4
 
Г96

Гусева А.И.,
Дискретная математика: сборник задач / А.И. Гусева, В.С. Киреев, А.Н. Тихомирова. — Москва : КУРС: ИНФРА-М, 2021. — 
224 с. — (Среднее профессиональное образование).

ISBN 978-5-906818-72-0 (КУРС)
ISBN 978-5-16-011887-1 (ИНФРА-М, print)
ISBN 978-5-16-105604-2 (ИНФРА-М, online)
Данный сборник задач предназначен для углубленного изучения таких 
разделов дискретной математики, как теория множеств и бинарных отношений, математическая логика и логика предикатов, теория графов, элементы 
теории и практики кодирования, элементы теории автоматов. Сборник задач ориентирован на студентов, а также преподавателей среднего профессионального образования по направлениям подготовки «Компьютерные 
системы и комплексы» и «Прикладная информатика».
При подборе учебного материала использовался многолетний опыт преподавания дискретной математики на кафедре кибернетики в Национальном исследовательском ядерном университете «МИФИ», рекомендации 
Computing Curricula 2013 и требования российских профессиональных стандартов в области ИТ.

УДК 519.854(076.1)
ББК В174я73-4

Р е ц е н з е н т ы:
О.Н. Ромашкова — д-р техн. наук, профессор, заведующий кафедрой 
прикладной математики ГАОУ ВО МГПУ;
М.И. Смирнов — д-р техн. наук, профессор, генеральный директор 
ООО «Нафтам-ИНПРО»

Г96

©  Гусева А.И., Киреев В.С., 
Тихомирова А.Н., 2016
© КУРС, 2016

ISBN 978-5-906818-72-0 (КУРС)
ISBN 978-5-16-011887-1 (ИНФРА-М, print)
ISBN 978-5-16-105604-2 (ИНФРА-М, online)

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11

Оригинал-макет подготовлен в Издательстве «КУРС»
Подписано в печать 15.08.2017.
Формат 6090/16. Бумага офсетная. Гарнитура Newton.
Печать цифровая. Усл. печ. л. 14,0.
Доп. тираж 20 экз. Заказ № 00000
ТК 646565-761310-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). К сожалению, для компьютинга нет устоявшегося русскоязычного наименования. Так, при переводе международных рекомендаций по преподаванию компьютинга в учебных заведениях Computing 
Curricula 2013 на русский язык использовалось понятие «информатика», а при разработке российских образовательных стандартов — 
наименование «информационные технологии». В данном задачнике 
для устранения разных толкований используется транслитерация 
«компьютинг».

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

При подборе учебного материала использовался многолетний 

опыт преподавания дискретной математики на кафедре кибернетики 
в Национальном исследовательском ядерном университете «МИФИ», 
рекомендации Computing Curricula 2013 и требования российских 
профессиональных стандартов в области ИТ. У разных глав — разные 
авторы. Главы 1, 3 и 4 написаны профессором А.И. Гусевой, глава 2 — 
доцентом А.Н. Тихомировой, главы 5 и 6 — доцентом В.С. Киреевым, глава 7 — общее творчество.

Глава 1

Теория множесТВ

и бинарных оТношений

1.1. основные понятия теории множеств

Теоретические сведения

Множество — совокупность объектов, хорошо различимых нашей 

интуицией или мыслью, обладающих неким сходством и объединенных в одно общее. Элементы множества обозначаются маленькими 
латинскими буквами, сами множества — заглавными. Например, 
чтобы показать, что элемент a принадлежит множеству A, мы пишем 
a
A
∈
, в противном случае a
A
∉
.

Количество элементов во множестве называется мощностью или 

кардинальным числом. В зависимости от мощности множества могут 
быть конечные и бесконечные. Множество, в состав которого не входит ни одного элемента, называется пустым и обозначается как ∅. 
Мощность пустого множества равна нулю. Но мощность множества С, элементом которого является пустое множество, равна единице, C = ∅
{ }, C = 1.

Множества равномощны, если их мощности равны. Определим, 

что конечное множество — множество, состоящее из конечного 
числа элементов, т.е. его мощность представима кардинальным 
числом, совпадающим с одним из натуральных чисел. В противном 
случае множество называется бесконечным.

Если каждому элементу бесконечного множества можно поста
вить в соответствие натуральное число n
N
i ∈
, причем только одно ni, 

без пропусков и повторений, то это множество называется счетнобесконечным и его мощность равна N = A0 (алеф-нуль), первому 
трансфинитному числу. Второе трансфинитное число A, алеф, равно 
мощности множества R действительных чисел. Известно и третье 

трансфинитное число A
A
A
=
=
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.

Множество B в приведенных выше определениях часто называют 

надмножеством (собственным надмножеством) множества A.

Множества A и B равны, если являются подмножествами (надмно
жествами) друг друга.

Для каждого множества М можно построить новое множество, 

элементами которого являются все подмножества М и только они. 
Тогда множество М называется универсумом и обозначается как I, 
а множество всех его подмножеств — булеаном B(I).

В некоторых случаях под универсумом можно понимать множе
ство всех возможных элементов.

теорема 1.1. основная теорема о конечных множествах
Любое конечное множество не может быть эквивалентно никакому 

своему собственному подмножеству.

Для задания множеств необходимо указать элементы, которые 

ему принадлежат. Это можно сделать следующим образом [3]: перечислить элементы множества, использовать характеристический 
предикат, задающий свойства элементов, с помощью производящей 
функции, которая помогает вычислить каждый элемент рассматриваемого множества [3].

Задачи

задача 1.1. Дано множество M = {a, b, c, d, e}. Найти все его под
множества.

задача 1.2. Дано множество M = {a, b, c, d, e}. Найти все его соб
ственные подмножества.

задача 1.3. Определить мощность булеана для M = {a, b, c, d, e}.

задача 1.4. Построить множество, равномощное M = {a, b, c, d, e}.

задача 1.5. Задать множество четных натуральных чисел от 2 до 20 

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

задача 1.6. Чему равна мощность множества натуральных чисел?

задача 1.7. Чему равна мощность множества натуральных чисел 

на отрезке [1, 1024]?

задача 1.8. Чему равна мощность множества рациональных чи
сел?

задача 1.9. Чему равна мощность множества вещественных чи
сел?

задача 1.10. Чему равна мощность множества точек на плоскости?

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 обозначает универсум, круги — множества 
А и В, результат операции представлен заштрихованными фрагментами.

В табл. 1.1 приведены основные свойства операций над множе
ствами.

При выполнении вычислений множественных выражений самой 

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

Перечисленные операции получили название теоретико-множе
ственных операций. Результаты всех этих операций над подмножествами универсума I дают также подмножества I.

1
1
1
1
1

а) A ∩ B
б) A ∪ B
в) A \ B
г) B \ A
д) A

рис. 1.1. Диаграммы Эйлера—Венна

Задачи

задача 1.11. Даны множества 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) A
B
∩
= { , ,
}
1 3 9 , 

A
B
C
∩
∪
=
∪
=
{ , ,
}
{ , , , ,
}
{ , , , , ,
}
1 3 9
2 3 5 6 9
1 2 3 5 6 9 ;

2) A
B
∩
= { ,
, , , , }
2 4 5 6 7 8 , 

A
B
C
∩
∪
=
∪
=

=

{ ,
, , , , }
{ , , , ,
}

{ , ,
, , ,

2 4 5 6 7 8
2 3 5 6 9

2 3 4 5 6  7 8 9
, ,
};

Таблица 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
∆
=
∪
∩
=
∩
∪
∩
(
) \ (
)

3) B
C
∪
=
=
{ , , , , , ,
}
{ ,
}
1 2 3 5 6 8 9
4 7 , 

A
B
C
∩
∪
=
∩
=
{ , , , ,
}
{ ,
}
{ }
1 3 5 7 9
4 7
7 ;

4) A
B
C
∩
∪
=
=
{ , , , , ,
}
{ , , }
1 2 3 5 6 9
4 7 8 .

Алгебра A = <B(I); ∪ ∩
,
,
> называется алгеброй Кантора, где

в качестве множества используется булеан B(I), а в качестве операций выступают объединение, пересечение, дополнение. Алгебру 
Кантора часто называют алгеброй множеств.

задача 1.12. С помощью законов алгебры Кантора упростить вы
ражения:

1) A
B
A
B
∩
∪
∩
;

2) A
B
A
∩
∪
; 

3) A
B
A
∩
∪
.

Решение.
Используя закон дистрибутивности, а затем действия с универсу
мом, получаем A
B
A
B
A
B
B
A
I
A
∩
∪
∩
=
∩
∪
=
∩
=
(
)
.

Используя закон де Моргана, а затем свойство дополнения и дей
ствия с универсумом, получаем 

A
B
A
A
B
A
A
A
B
I
B
I
∩
∪
=
∪
∪
=
∪
∪
=
∪
=
(
)
.

Применяя закон де Моргана, свойство дополнения и действия 

с пустым множеством, получаем

A
B
A
A
B
A
A
A
B
B
∩
∪
=
∩
∩
=
∩
∩
= ∅ ∩
= ∅
(
)
(
)
.

задача 1.13. С помощью законов алгебры Кантора показать, что 

произвольные множества A и B удовлетворяют следующему свойству:

A B
A
B
A
B
∆
=
∪
∩
∩
(
)
(
).

Решение.
Для решения задачи применяем закон де Моргана, два раза под
ряд закон дистрибутивности, закон дополнения и нормальный порядок скобок:

A B
A
B
A
B
A
B
A
B

A
A
B
B
A
B
A
A
A
B
B
A
B

∆
=
∪
∩
∩
=
∪
∩
∪
=

=
∩
∪
∪
∩
∪
=
∩
∪
∩
∪
∩
∪

(
)
(
)
(
)
(
)

(
)
(
)
∩
=

=
∩
∪
∩
=
∩
∪
∩

B

A
B
A
B
A
B
A
B
(
)
(
).

задача 1.14. Даны множества I = {a, b, c, d, e, f}, A = {a, c, e}, B = 

= {b, d, f }, C = {a, b, e, f}. Вычислить результат операций: 

1) A
B
C
∩
∩
; 

2) A
B
C
∪
∩
; 

3) A
B
C
∩
∪
; 

4) (
)
A
B
C
∪
∩
.

задача 1.15. Даны множества А (треугольник), В (квадрат) 

и С (круг). Определить через операции объединения, пересечения, 
дополнения, разности и симметрической разности, чему равна заштрихованная область в указанных четырех случаях а), б), в) и г) 
(рис. 1.2).

задача 1.16. Нарисовать круги Эйлера—Венна для A
B
C
∪ (
/
), 

A
B
C
/ (
/
), где А(треугольник), В (квадрат) иС(круг)— иззадачи1.12,а).

задача 1.17. Для заданных множеств 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.18. Для заданных множеств I = {1, 2, 3, 4, 5}, A = {1, 3, 5}, 

B = {1, 2, 4} и C = пустое множество вычислить результат операций:

1) (
)
A
B
С
∪
∩
; 

а)
б)

в)
г)

рис. 1.2. Условия задачи 1.15