Основы дискретной математики

УЧЕБНОЕ ПОСОБИЕ

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

ОСНОВЫ 
ДИСКРЕТНОЙ 
МАТЕМАТИКИ

В.А. Осипова

Рекомендовано УМО в области экономики, менеджмента, логистики 
и бизнес-информатики в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся по направлению подготовки 
38.03.01 «Экономика»

Москва                                        2020

ИНФРА-М

УДК 519.1(075.8)
ББК 22.176я73
 
О74

Р е ц е н з е н т:
О.П. Кузнецов — доктор технических наук, профессор Национального исследовательского университета «Высшая школа экономики» 

А в т о р:
Виктория Аркадьевна Осипова — кандидат физико-математических 
наук, доцент, профессор Московского авиационного института (национального исследовательского университета)

Осипова В.А.
О74  
Основы дискретной математики : учебное пособие / В.А. Осипова. — 2-е изд., доп. — Москва : ФОРУМ : ИНФРА-М, 2020. — 157 с. — 
(Высшее образование: Бакалавриат). — DOI 10.12737/textbook_58f08ea0
01c1b1.88073569.

ISBN 978-5-00091-404-5 (ФОРУМ)
ISBN 978-5-16-012860-3 (ИНФРА-М, print)
ISBN 978-5-16-105297-6 (ИНФРА-М, online)

Излагаются основы современной дискретной математики. Рассматриваются вопросы, связанные с комбинаторикой, математической логикой, 
теорией графов. Приводятся практические задачи и даются алгоритмы их 
решения.
Соответствует требованиям Федерального государственного образовательного стандарта высшего образования последнего поколения.
Учебное пособие предназначено для студентов, обучающихся по специальностям, связанным с экономикой, логистикой, бизнес-информатикой. 
Оно может оказаться полезным и студентам технических специальностей, 
изучающим курс «Дискретная математика».

УДК 519.1(075.8)
ББК 22.176я73

ISBN 978-5-00091-404-5 (ФОРУМ)
ISBN 978-5-16-012860-3 (ИНФРА-М, print)
ISBN 978-5-16-105297-6 (ИНФРА-М, online)

© Осипова В.А., 2006
© Осипова В.А., 2017,
 
с изменениями
© ФОРУМ, 2017

Оглавление

Предисловие
5

Глава 1.
МНОЖЕСТВА И ОТНОШЕНИЯ
7
1.1. Начальные понятия теории множеств
. . . . . . . . . .
7
1.1.1. Понятие множества
. . . . . . . . . . . . . . . . .
7
1.1.2. Операции над множествами. Алгебра множеств .
10
1.1.3. Упорядочение. Прямое произведение множеств .
13
1.2. Бинарные отношения. Специальные
бинарные отношения
. . . . . . . . . . . . . . . . . . . .
16
1.2.1. Общее понятие отношения . . . . . . . . . . . . .
16
1.2.2. Специальные бинарные отношения . . . . . . . .
17
1.3. Алгебраические операции . . . . . . . . . . . . . . . . . .
24

Глава 2.
ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
28
2.1. Логика высказываний . . . . . . . . . . . . . . . . . . . .
29
2.1.1. Высказывания. Логические операции. Формулы
логики высказываний . . . . . . . . . . . . . . . .
29
2.1.2. Равносильность формул . . . . . . . . . . . . . . .
35
2.1.3. Булевы алгебры
. . . . . . . . . . . . . . . . . . .
39
2.1.4. Тождественно-истинные формулы. Проблема разрешимости
. . . . . . . . . . . . . . . . . . . . . .
42
2.1.5. Двойственность. Закон двойственности . . . . . .
43
2.1.6. Нормальные формы формул . . . . . . . . . . . .
45
2.2. Булевы функции . . . . . . . . . . . . . . . . . . . . . . .
55
2.2.1. Представление булевой функции формулой логики высказываний
. . . . . . . . . . . . . . . . .
55
2.2.2. Полные системы булевых функций . . . . . . . .
60
2.2.3. Минимизация в классе дизъюнктивных нормальных форм . . . . . . . . . . . . . . . . . . . .
63
2.3. Логика предикатов
. . . . . . . . . . . . . . . . . . . . .
67
2.3.1. Предикаты, кванторы. Формулы логики предикатов . . . . . . . . . . . . . . . . . . . . . . . . . .
67
2.3.2. Равносильность формул . . . . . . . . . . . . . . .
73
2.3.3. Выполнимость и общезначимость. Проблема разрешимости
. . . . . . . . . . . . . . . . . . . . . .
75

Глава 3.
ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ
79
3.1. Комбинаторные схемы
. . . . . . . . . . . . . . . . . . .
79
3.1.1. Правила суммы и произведения . . . . . . . . . .
79
3.1.2. Размещения и сочетания
. . . . . . . . . . . . . .
80
3.1.3. Разбиения. Полиномиальная формула
. . . . . .
84
3.1.4. Классифицирование. Урновые схемы . . . . . . .
86
3.2. Некоторые методы пересчета . . . . . . . . . . . . . . . .
88
3.2.1. Формула включений и исключений . . . . . . . .
88
3.2.2. Рекуррентные соотношения и производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . . .
92

Оглавление

Глава 4.
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
96
4.1. Ориентированные и неориентированные графы. Основные понятия. Примеры приложений теории графов
96
4.2. Матричное задание графа
. . . . . . . . . . . . . . . . . 104
4.2.1. Матрицы смежности и матрицы инциденций
. . 104
4.2.2. Матрицы связности и расстояний . . . . . . . . . 106
4.3. Поиск путей в графе
. . . . . . . . . . . . . . . . . . . . 112
4.3.1. Алгоритмы нахождения путей и экстремальных
путей в графе. Примеры прикладных задач . . . 112
4.3.2. Специальные цепи в графе. Задача о коммивояжере . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.4. Устойчивые подмножества графа. Ядра . . . . . . . . . 121
4.4.1. Внутренне и внешне устойчивые множества . . . 121
4.4.2. Ядра графа. Уровни графа . . . . . . . . . . . . . 125
4.5. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.5.1. Определение и свойства деревьев
. . . . . . . . . 129
4.5.2. Остовное дерево графа
. . . . . . . . . . . . . . . 131
4.6. Плоские графы . . . . . . . . . . . . . . . . . . . . . . . . 134
4.7. Потоки в сетях . . . . . . . . . . . . . . . . . . . . . . . . 140
4.7.1. Транспортные сети
. . . . . . . . . . . . . . . . . 140
4.7.2. Максимальный поток в сети . . . . . . . . . . . . 142
4.7.3. Паросочетания в двудольных графах . . . . . . . 145

Приложение
148
Π.1. Бинарные отношения и проблема выбора
. . . . . . . . 148

Библиографический список . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  156

Предисловие

Во взаимоотношениях математики и ее приложений в середине XX века произошел существенный перелом. Математические
методы, традиционно используемые в таких областях, как
физика, механика, инженерные науки, стали вторгаться в самые
различные сферы науки и практики — от биологии, экономики,
социологии, психологии до компьютерных технологий. Эти
приложения требуют изменить представление о математике как
о вычислительной теории, обращаются к восприятию абстрактной природы ее основных понятий и методов, что позволяет
мыслить более ясно и последовательно при решении научных
проблем.
Начиная с XVII века, в математике в основном занимались
изучением функций непрерывно меняющегося аргумента, что
являлось основой для всех ее приложений. Однако изучение
моделей, имеющих принципиально дискретный (где дискретность понимается как понятие, противоположное непрерывности), ≪конечный≫ характер привело к необходимости обратиться к разделам математики, идущим в основном от математической логики и традиционно включающим комбинаторный анализ, теорию графов, теорию алгоритмов, теорию алгебраических систем и ряд других. В современной математической науке,
а также в ее приложениях, исследования в этих областях занимают все более заметное место.
Наряду с использованием дискретных математических методов для решения аналитических и прикладных задач в
гуманитарных и естественнонаучных дисциплинах, важным
аспектом их применения является также формирование методологических и языковых навыков, позволяющих формализовать
и структурировать проблемы в соответствующей предметной
области. Уместно напомнить высказывание известного экономиста Дж. М. Кейнса, который говорил, что
≪экономическая
теория является скорее методом, чем учением, интеллектуальным инструментом, техникой мышления, позволяя тому, кто
владеет ею, приходить к правильным заключениям≫. Форми

Предисловие

рование ≪техники мышления≫ является важной составляющей
для любой научной теории.
В новое издание добавлен раздел, отражающий использование понятия бинарного отношения в моделировании задач поддержки принятия решений, а также внесены некоторые изменения в текст.
В предлагаемом учебном пособии освещены те вопросы, которые можно отнести к началам изучения дисциплины ≪Дискретная математика≫: оно базируется на лекционном курсе, читаемом в течение ряда лет для экономических специальностей Московского авиационного института. В то же время это пособие
может использоваться студентами, обучающимися по специальности прикладная математика и информатика, хотя программа
этой дисциплины для них значительно шире.
Автор выражает благодарность С. Смерчинской за техническое оформление рукописи.

Глава 1

МНОЖЕСТВА И ОТНОШЕНИЯ

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

≪нечислового≫ характера.

1.1.
Начальные понятия теории множеств

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

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

Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ

живущих на Земле. Заметим, что канторовская формулировка
позволяет рассматривать множества, элементы которых по той
или иной причине нельзя точно указать (например, множество
простых чисел, множество русских воинов, погибших в битве на
Куликовом поле, и т. д.).
Символом ∈ обозначается отношение принадлежности. Запись x ∈ S означает, что элемент x принадлежит множеству S.
Если элемент x не принадлежит множеству S, то пишут x ∈ S.
Г. Кантором сформулировано несколько интуитивных принципов, которые естественно считать выполняющимися для произвольных множеств.
Интуитивный принцип объемности. Множества A и B
считаются равными, если они состоят из одних и тех же
элементов.
Записывают A = B, если A и B равны, и A ̸= B — в
противном случае.
Пример 1.1.
Проиллюстрируем
принцип
объемности.
Множество A всех положительных четных чисел равно множеству B положительных целых чисел, представимых в виде
суммы двух положительных нечетных чисел. Действительно,
если x ∈ A, то для некоторого целого положительного числа
m x = 2m; тогда x = (2m−1)+1, т. е. x ∈ B. Если x ∈ B, то для
некоторых целых положительных p и q x = (2p − 1) + (2q − 1) =
= 2(p + q − 1), т. е. x ∈ A.
Множество, элементами которого являются объекты a1, a2, ...
... , an и только они, обозначают {a1, a2, ... , an}.
Пример 1.2.
В силу принципа объемности {2, 4, 6}
=
= {4, 2, 6} = {2, 4, 4, 6}; {{1, 2}} ̸= {1, 2}, так как единственным элементом множества {{1, 2}} является множество {1, 2},
а множество {1, 2} состоит из двух элементов: чисел 1 и 2.
При рассмотрении способов задания множеств возникает проблема их эффективного описания. Ее решение обычно основано на интуитивном понятии
≪формы от x≫. Под формой от
x будем понимать конечную последовательность, состоящую из
слов и символа x, такую, что если каждое вхождение x в эту
последовательность заменить одним и тем же именем некоторого предмета соответствующего рода, то в результате получится истинное или ложное предложение. Например, формами от
x являются следующие предложения: ≪3 делит x≫, ≪x2 = 4≫,

≪x2+2x+1 > x≫, ≪x — родственник Иванова≫. Напротив, предложения ≪для всех x x2 = (x − 2)(x + 2)≫ и ≪существует такое

1.1. Начальные понятия теории множеств
9

x, что x > 0≫ не являются формами от x.
Обозначим форму от x через P(x).
Интуитивный принцип абстракции. Любая форма P(x)
определяет некоторое множество A, а именно множество
тех и только тех предметов a, для которых P(a) — истинное
предложение.
Для множества A, определяемого формой P(x), принято
обозначение A = {x|P(x)}.
Пример 1.3.
1. {x|x — положительное число, меньшее 9} = {1, 2, 3, 4, 5,
6, 7, 8}.
2. {x|x — четное число} — множество четных чисел.
Описанные выше понятия теории множеств с успехом могут
быть использованы в началах анализа, алгебры, математической логики и т. д. Однако надо иметь в виду, что при более строгих рассмотрениях такое интуитивное восприятие может оказаться неудовлетворительным.
Несовершенство интуитивных представлений о множествах, их недостаточность иллюстрируются, например, известным парадоксом Б. Рассела. Приведем этот парадокс. Можно
указать такие множества, которые принадлежат самим себе
как элементы, например множество всех множеств, и такие
множества, которые не являются элементами самих себя,
например множество {1, 2}, элементами которого являются
числа 1 и 2. Рассмотрим теперь множество A всех таких
множеств X, что X не есть элемент X. Тогда, если A не есть
элемент A, то, по определению, A также есть и элемент A.
С другой стороны, если A есть элемент A, то A — одно из тех
множеств X, которые не есть элементы самих себя, т. е. A
не есть элемент A. В любом случае A есть элемент A и A не
есть элемент A.
Этот парадокс свидетельствует о том, что широко используемая теория множеств в ее интуитивном, ≪наивном≫ изложении
является противоречивой. Формализация теории множеств,
связанная, в частности, с устранением парадоксов, способствовала развитию не только методов теории множеств, но и такой
науки, как математическая логика.
Через ⊆ обозначим отношение включения между множествами, т. е. A ⊆ B, если каждый элемент множества A есть
элемент множества B. Тогда говорят, что A есть подмножество
множества B. Если A ⊆ B и A ̸= B, то говорят, что A есть

Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ

собственное подмножество B, и пишут A ⊂ B.
Пример 1.4.
Множество четных чисел есть подмножество
множества целых чисел; множество рациональных чисел есть
подмножество множества действительных чисел; {1, 2} ⊆ {1, 2,
3, 4}.
Заметим, что: а) X ⊆ X; б) если X ⊆ Y , Y ⊆ Z, то X ⊆ Z;
в) если X ⊆ Y и Y ⊆ X, то X = Y .
Не надо смешивать отношения принадлежности и включения. Хотя 1 ∈ {1}, {1} ⊆ {{1}}, не верно, что 1 ∈ {{1}}, так как
единственным элементом множества {{1}} является {1}.
Множество, не содержащее элементов, называется пустым и
обозначается
⃝. Пустое множество есть подмножество любого
множества.
Множество всех подмножеств A называется множествомстепенью и обозначается P(A).
Пример 1.5.
Если A = {1, 2, 3}, то P(A) = {
⃝, {1}, {2},
{3}, {1, 2}, {1, 3}, {2, 3}, A}.
В дальнейшем мы неоднократно будем пользоваться утверждением, что если множество A состоит из n элементов, то
множество P(A) состоит из 2n элементов (см. задачу 3).

1.1.2.
Операции над множествами. Алгебра
множеств

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

Пересечением множеств A и B называется множество A ∩ B,
элементы которого являются элементами обоих множеств A и
B:
A ∩ B = {x|x ∈ A и x ∈ B}.

Очевидно, что выполняются включения A ∩ B ⊆ A ⊆ A ∪ B
и A ∩ B ⊆ B ⊆ A ∪ B.
Относительным дополнением множества A до множества
X (или разностью множеств X и A) называется множество

1.1. Начальные понятия теории множеств
11

X\A всех тех элементов множества X, которые не принадлежат
множеству A:
X \ A = {x|x ∈ X и x ∈ A}.

Симметрической разностью множеств A и B называется
множество
A + B = (A \ B) ∪ (B \ A).

Если все рассматриваемые в ходе данного рассуждения
множества являются подмножествами некоторого множества U,
то это множество U называется универсальным для данного
рассуждения.
Абсолютным дополнением множества A называется множество A всех тех элементов x, которые не принадлежат
множеству A:

A = U \ A.

Заметим, что X \ A = X ∩ A.

Рис. 1.1.

Для наглядного представления отношении между подмножествами какого-либо универсального множества используют
диаграммы Эйлера—Венна. Само универсальное множество U
изображают в виде прямоугольника, а его подмножества — в виде кругов, расположенных внутри прямоугольника. На рис. 1.1,
а подмножество A универсального множества U изображено в
виде заштрихованного круга. На рис. 1.1, б —е изображены соответственно объединение, пересечение, относительное дополнение, симметрическая разность, абсолютное дополнение.

Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ

Утверждение 1.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)∩
3′. A ∩ (B ∪ C) = (A ∩ B)∪
∩(A ∪ C) (дистрибутив∪(A ∩ C) (дистрибутивность ∪ относительно ∩);
ность ∩ относительно ∪);
4. A ∪
⃝ = A;
4′. A ∩ U = A;
5. A ∪ A = U;
5′. A ∩ A =
⃝;
6. A ∪ A = A;
6′. A ∩ A = A;
7. A ∪ U = U;
7′. A ∩
⃝ =
⃝;
8. A ∪ B = A ∩ B (закон
8′. A ∩ B = A ∪ B (закон
де Моргана);
де Моргана);
9. A ∪ (A ∩ B) = A (закон
9′. A ∩ (A ∪ B) = A (закон
поглощения);
поглощения).

Докажем тождество 3. Сначала покажем, что A∪(B∩C) ⊆
⊆ (A ∪ B) ∩ (A ∪ C). Действительно, если x ∈ A ∪ (B ∩ C), то
x ∈ A или x ∈ B ∩ C. Если x ∈ A, то x ∈ A ∪ B и x ∈ A ∪ C.
Следовательно, x ∈ (A ∪ B) ∩ (A ∪ C). Если x ∈ B ∩ C, то
x ∈ B и x ∈ C. Отсюда x ∈ B ∪ A и x ∈ C ∪ A, а значит,
x ∈ (A ∪ B) ∩ (A ∪ C). Теперь покажем, что (A ∪ B) ∩ (A ∪ C) ⊆
⊆ A∪(B∩C). Если x ∈ (A∪B)∩(A∪C), то x ∈ A∪B и x ∈ A∪C.
Следовательно, x ∈ A или x ∈ B и x ∈ C, т. е. x ∈ B∩C. Отсюда
x ∈ A ∪ (B ∩ C).
Докажем тождество 8. Пусть x ∈ A ∪ B. Тогда x ∈ U и
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 ∈ U и x ∈ A и x ∈ B.
Значит, x ∈ A ∪ B, т. е. x ∈ A ∪ B. Итак, A ∩ B ⊆ A ∪ B.
Остальные тождества доказываются аналогично.

Утверждение 1.2. Предложения о произвольных множествах A и B попарно эквивалентны:

1) A ⊆ B;
2) A ∩ B = A;
3) A ∪ B = B.