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

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

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Е. Ф. Жигалова

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

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

Томск

«Эль Контент»
2014

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

Рецензенты:

Фофанов О. Б., канд. техн. наук, доцент, зав. кафедрой оптимизации систем
управления Томского политехнического университета;

Абдалова О. И., зам. зав. кафедрой прикладной математики и информатики
ТУСУРа.

Жигалова Е. Ф.
Ж 681
Дискретная математика : учебное пособие / Е. Ф.Жигалова. — Томск :
Эль Контент, 2014. — 98 с.

ISBN 978-5-4332-0167-5

Учебное пособие содержит традиционные разделы дискретной математики: основы теории множеств, булевой алгебры, теории графов и комбинаторики.

Наибольшее внимание в пособии уделено разделу о графах и их характеристиках.

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

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

ISBN 978-5-4332-0167-5
©
Жигалова Е. Ф., 2014

©
Оформление.
ООО «Эль Контент», 2014

ОГЛАВЛЕНИЕ

Введение
5

1
Основы теории множеств и отношений
8

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

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

1.3
Булевы выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11

2
Теория графов
14

2.1
Определение графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

2.2
Классы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16

2.3
Способы задания графов
. . . . . . . . . . . . . . . . . . . . . . . . . . .
17

2.4
Числовые характеристики вершин графа . . . . . . . . . . . . . . . . . .
19

2.5
Маршруты, цепи и циклы . . . . . . . . . . . . . . . . . . . . . . . . . . .
19

2.6
Определение числа маршрутов длины «L» на графе . . . . . . . . . . .
21

2.7
Части графа
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28

2.7.1
Подграф . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28

2.7.2
Частичный граф . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

2.8
Метрика графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30

2.9
Структурный анализ графов . . . . . . . . . . . . . . . . . . . . . . . . .
33

2.9.1
Раскраска графов. Правильная раскраска, хроматическое
число . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38

2.9.2
Компоненты связности графа . . . . . . . . . . . . . . . . . . . .
41

3
Экстремальные задачи на графах
46

3.1
Максимальное паросочетание в двудольном графе
. . . . . . . . . . .
46

3.2
Венгерский алгоритм нахождения максимального паросочетания
в двудольном графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47

3.3
Оптимальные потоки в транспортных/информационных сетях . . . .
52

4
Переключательные функции
62

4.1
Переключательные функции. Способы задания
. . . . . . . . . . . . .
62

4.2
Булевы функции (БФ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67

4.3
Аналитическое представление булевых функций . . . . . . . . . . . . .
68

4.3.1
Булева алгебра функций и эквивалентные преобразования
в ней . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72

4.3.2
Представление переключательных функций в виде
многочленов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73

Оглавление

4.4
Функционально полные системы . . . . . . . . . . . . . . . . . . . . . .
75

4.5
Минимизация булевых функций . . . . . . . . . . . . . . . . . . . . . . .
76

4.5.1
Алгебраический метод упрощения булевых функций . . . . .
77

5
Комбинаторика
83

5.1
Основные формулы комбинаторики . . . . . . . . . . . . . . . . . . . . .
84

5.2
Комбинаторика и теоретико-вероятностные задачи . . . . . . . . . . .
86

Заключение
94

Литература
95

Глоссарий
96

ВВЕДЕНИЕ

Дискретная математика — часть математики, которая зародилась в глубокой древности. Главной её спецификой является дискретность (антипод непрерывности).
В широком смысле дискретная математика включает в себя такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд
разделов, которые наиболее интенсивно стали развиваться в середине ХХ-го века
в связи с внедрением ЭВМ, например «теория графов».

Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования.

Главная задача курса — это обучение методам и мышлению, характерным для
дискретной математики.

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

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

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

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

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

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

Введение

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

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

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

Соглашения, принятые в книге

Для улучшения восприятия материала в данной книге используются пиктограммы и специальное выделение важной информации.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Этот блок означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает теорему.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Введение
7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает лемму.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает пример. В данном блоке автор может привести практический пример для пояснения и разбора основных моментов, отраженных в теоретическом материале.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .. . . . . . . . . . . . . . . . . . . . . .
Выводы
. . .. . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает выводы. Здесь автор подводит итоги, обобщает изложенный материал или проводит анализ.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Контрольные вопросы по главе
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Глава 1

ОСНОВЫ ТЕОРИИ МНОЖЕСТВ
И ОТНОШЕНИЙ

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

Понятие множества является основным, но трудно определяемым понятием,
поэтому его можно только пояснить.

Интуитивное определение множества, принадлежит немецкому математику Георгу Кантору (1845–1918 гг.): «Под множеством M будем понимать любое собрание определенных и различимых между собою объектов, мыслимое как единое
целое. Эти объекты называются элементами множества M».

Принято элементы множества обозначать строчными буквами латинского алфавита, а само множество — прописной буквой.

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

Если элемент m принадлежит множеству M, то используется запись m ∈ M,
в противном случае используется запись m ∉ M.

Множество, содержащее конечное число элементов, называется конечным. Если множество не содержит ни одного элемента, то оно называется пустым и обозначается ∅.

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

Множество может быть задано различными способами: перечислением элементов (конечные множества) или указанием их свойств (при этом для задания
множеств используют фигурные скобки).

Например, множество M цифр десятичного алфавита можно задать в виде M =
= {0,1,2,...,9} или M = {i/i — целое, 0 ⩽ i ⩽ 9}, где справа от наклонной черты
указано свойство элементов этого множества.

Множество M нечётных чисел можно записать в виде M = {m/m — чётное число}.
Множество Ma называется подмножеством множества M (Ma включено в M)
тогда и только тогда, когда любой элемент множества Ma принадлежит M:

Ma ⊂ M ↔ (m ∈ Ma → m ∈ M),

где ⊂ — знак включения подмножества; a → b означает: если a, то b; a ↔ b означает:
b, если и только если a. В частном случае множества M и Ma могут совпадать.

Невключаемое подмножество Ma в множество M обозначается:

Ma /⊂ M.

Множества Ma и Mb называются равными: Ma = Mb, если множество Ma является подмножеством множества Mb и множество Mb является подмножеством
множества Ma.

Если множество Ma является подмножеством множества M, а множество M не
является подмножеством множества Ma, то множество Ma называется собственным
подмножеством множества M. Это можно обозначать:

Ma ⊂⊂ M.

Множества можно задавать графически с помощью диаграмм Эйлера—Венна.
Например, множества M1 = {a,b,c,d} и M2 = {e,f ,c,g} на рисунке 1.1, заданы
диаграммами Эйлера—Венна.

Рис. 1.1 – Пример представления множеств диаграммами Эйлера—Венна

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

Выполнение операций над множествами позволяет получать новые множества
из уже существующих. Над множествами можно выполнять следующие основные
операции:

• объединение
A ∪ B ∶= {x∣x ∈ A ∨ x ∈ B};

• пересечение
A ∩ B ∶= {x∣x ∈ A ∧ x ∈ B};

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

• разность
A/B ∶= {x∣x ∈ A ∧ x /∈ B};

• симметрическая разность

A∆B ≡ A÷ ∶= (A ∪ B)/(A ∩ B) = {x∣(x ∈ A & x /∈ B) ∨ (x /∈ A & x ∈ B)};

• дополнение

A ∶= {x∣x /∈ A}.

Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A):

A ∶= {x∣x /∈ A}.

Указанные операции можно пояснить следующим образом:
• Объединением множеств 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 всех тех элементов множества X, которые не принадлежат
множеству A:

X/A = {x∣x ∈ X &x ∉ A} (также называют разностью множеств X и A).

Когда фиксирован универсум U, абсолютным дополнением множества A
называется множество всех тех элементов x, которые не принадлежат множеству A:
A = {x∣x ∈ U &x ∉ A}.

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

A ÷ B = (A/B) ∪ (B/A).

Заметим, что дополнение множества A = U/A. Часто вместо A будем писать ¬A
или A
′.

Первым стал использовать теперь общепринятые обозначения операций над
множествами Джузеппе Пеано (1888 г.).

Для наглядного представления отношений между подмножествами какого-либо
универсума используются диаграммы Эйлера. В этом случае множества обозначают областями на плоскости и внутри этих областей условно располагают элементы
множества.