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

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

В.Е. ХОДАКОВ 
Н.А. СОКОЛОВА

Рекомендовано Межрегиональным учебно-методическим советом 
профессионального образования в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся по техническим направлениям подготовки 
(квалификация (степень) «бакалавр») (протокол № 9 от 13.05.2019)

Москва
ИНФРА-М
2020

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

УДК 519.854(075.8)
ББК 22.176я73
 
Х69

Ходаков В.Е.
Х69 
 
Дискретная математика : учебное пособие / В.Е. Ходаков, Н.А. Соколова. — Москва : ИНФРА-М, 2020. — 542 с. — (Высшее образование: 
Бакалавриат). — DOI 10.12737/textbook_5cee60a3a9d469.63098074.

ISBN 978-5-16-013184-9 (print)
ISBN 978-5-16-105954-8 (online)
В учебном пособии изложены основы дискретной математики; рассмотрены основные понятия и научные результаты теории множеств, 
математической логики, отношений, формальных систем, алгоритмов, 
алгебр, комбинаторики, графов, фрактальных множеств; даны все определения, необходимые для выполнения заданий. Теоретический материал 
проиллюстрирован большим количеством примеров из разных областей 
знаний. Включает основные понятия и теоретические результаты, методы 
и алгоритмы решения прикладных зачач, а также исторические сведения 
об ученых, внесших вклад в историю развития дискретной математики. 
Содержит множество заданий для контроля знаний и системы их оценки. В каждой главе имеются двухуровневые тестовые задания. К первому 
уровню относятся тесты для проверки обязательного минимума знаний, 
ко второму — задания повышенной сложности. Тесты снабжены указателями и ответами.
Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения.
Адресовано преподавателям и студентам высших технических вузов, 
может быть полезно тем, кто интересуется дискретной математикой и желает изучать ее самостоятельно. 

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

Р е ц е н з е н т ы:
Мышко С.В., доктор технических наук, профессор;
Петров Э.Г., доктор технических наук, профессор

ISBN 978-5-16-013184-9 (print)
ISBN 978-5-16-105954-8 (online)
© Ходаков В.Е., 
 
Соколова Н.А., 2019

Предисловие

Дискретная математика — часть математики, зародившаяся 
в глубокой древности. Ее главным специфическим отличием является дискретность, т.е. противоположность непрерывности. Дискретная математика включает в себя традиционные, уже сформировавшиеся, разделы математики, такие как математическая логика, 
алгебры и алгебраические системы, теория чисел, и новые, интенсивно развивающиеся.
В более чем 2000-летней истории дискретной математики настоящее время представляет один из наиболее интенсивных периодов ее развития: очень быстро расширяется сфера применения, 
растут объемы новой информации и количество новых результатов. 
Если еще относительно недавно она была сферой интересов лишь 
сравнительно узкого круга специалистов, то теперь превратилась 
в научную дисциплину, очень важную и нужную многим, а в области современного образования — всем.
Массовое использование вычислительной техники значительно 
расширяет область прикладных исследований, при которых все 
больше используется аппарат дискретной математики.
До 2000 г. практически не издавалась удобная литература по дискретной математике. Можно выделить только две книги — учебные 
пособия Яблонского С.В. «Введение в дискретную математику» 
(М.: Изд-во Наука, 1979) и Нефедова В.Н., Осиповой В.А. «Курс 
дискретной математики» (М.: Изд-во МЭИ, 1992). В то же время 
инженеры-математики, программисты, занимающиеся прикладными исследованиями, проявляли все большую заинтересованность в использовании аппарата дискретной математики, что объясняется широким использованием компьютерной техники и информационных технологий. Исследования в областях дискретной 
математики играют все более весомую роль.
После 2000 г. положение с изданием литературы по дискретной 
математике улучшилось. Но следует учитывать, что дискретная математика — одна из самых динамично развивающихся областей современной математики; добавляющаяся к этому тотальная компьютеризация абсолютно всех областей экономики и жизни нашего 
общества приводит к постоянному росту спроса специалистов, 
занимающихся разработкой как программных средств, так и математических основ информационных технологий. Появляющиеся 
книги должны не только учить студентов основам дискретной ма

тематики, но и показывать ее роль в современных компьютерных 
технологиях, вооружать читателя методами, применяемыми для решения широкого круга задач.
Форма изложения материала при этом должна быть доступной, 
достаточно полной, но необходимо строгой.
Предлагаемое пособие включает не только основные понятия 
и теоретические результаты, но и методы и алгоритмы решения 
ряда прикладных задач.
Предлагаемая книга — учебное пособие, позволяющее составить 
целостное представление о всем комплексе возможностей этой 
удивительной науки.
Одна из главных целей создания данной книги — научить студентов и специалистов основам дискретной математики, содействовать более глубокому пониманию и усвоению отмеченных 
прикладных проблем, в свете которых и трактуется основное содержание разделов дискретной математики.
В главе 1 излагаются основные понятия теории множеств: способы задания множеств, понятие пустого подмножества, алгебра 
множеств, методы доказательства алгебры логики, обобщение операций над множествами, а также нечеткие множества, основные 
понятия и определения, нечеткие лингвистические переменные.
В главе 2 рассматриваются основы математической логики. Достаточно подробно и основательно излагаются булевы функции. 
Изложение начинается с определения основных понятий. Показываются способы задания булевых функций, представляются булевы 
функции одной, двух переменных, показываются область определения булевой функции, элементарные функции алгебры логики, 
свойства функций алгебры логики, реализация функций формулами, приводятся понятия о полноте, наборах полных систем, канонических формах переключательных функций, рассматриваются 
вопросы минимизации булевых функций, способы получения минимальных форм, геометрическое представление булевых функций.
В главе 3 излагаются отношения, объясняются основные понятия и свойства отношений, рассматриваются отношения эквивалентности, порядка, квазипорядка, равномощности.
Глава 4 посвящена такому важному разделу, как теория алгоритмов, которая, как и формальные системы, до недавнего времени 
относилась к «высокой науке». Рассмотрены свойства алгоритмов, 
машины Тьюринга и операции над ними, рекурсивные функции 
и связь рекурсивных функций с машинами Тьюринга.
Глава 5 посвящена формальным системам. В ней рассматриваются основные понятия, аксиоматический способ описания 

высказываний, свойства исчисления высказываний. На примере 
логики высказываний осуществляется знакомство со строгой формализацией математической теории — строится исчисление высказываний. Затрагиваются вопросы, связанные с эффективной вычислимостью. Рассматриваются система Поста и машина Тьюринга. 
С помощью машины Тьюринга и частично рекурсивных функций 
уточняются понятия алгоритма и вычислимости.
В главе 6 рассматриваются основные понятия, типы алгебр и алгебраические системы.
Глава 7 посвящена комбинаторике и перечислительной теории 
Пойа, использующей ряд результатов и методов теории групп.
В главе 8 излагаются основы теории графов (ориентированных 
и неориентированных). Часть материала, приведенная здесь, достаточно хорошо известна специалистам, часть же является оригинальной, полученной авторами.
Глава 9 посвящена более новому, современному материалу — 
фрактальным множествам.
Заключительный раздел книги — это тесты и ответы к ним.
Книга написана по материалам лекций, которые в течение 
ряда лет читались авторами в ряде технических вузов. По нашему 
мнению, книга написана в доступной форме, достаточно полно 
и строго. Надеемся, что она поможет формированию научного мировоззрения, взглядов на дискретную математику как фундаментальную науку, используемую для формализации знаний.
Н.А. Соколова, доктор технических наук, профессор, много 
и плодотворно работавшая как ученый-исследователь и лектор-педагог, была активнейшим инициатором создания данного учебного 
пособия и выполнила большую работу по подготовке его рукописи. 
Неожиданная смерть помешала продолжить эту работу. Памятью 
об этой светлой женщине и прекрасном ученом и является данная 
книга.
В результате изучения дысциплины бакалавр должен: 
знать основные понятия и методы дискретной математики: логические исчисления, функциональные системы с операциями, 
дискретные структуры (графы, сети, коды), дизъюнктивные нормальные формы и схемы из функциональных элементов, комбинаторику, основы теории алгоритмов, фракталов, графов, определения и свойства математических объектов, используемых в сферах 
их приложений;
уметь применять математическую символику для выражения 
количественных и качественных отношений объектов, применять 
теорию алгоритмов для разработки и анализа своих проектных ре

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

Глава 1. 

МНОЖЕСТВА

1.1. ЛОГИЧЕСКИЕ И ОДНОРОДНЫЕ ФУНКЦИИ

В основе всех разделов дискретной математики лежит понятие 
функции.
Функция — математическое понятие, выражающее зависимость 
одних переменных величин от других. Если величины х и у связаны так, что каждому значению х соответствует определенное 
значение у, то у называют функцией аргумента х. Записывают сказанное в общем виде так: у = f(x) или у = F(x).
Отличительной особенностью логической функции является 
то, что область ее значений всегда представляет собой конечную 
совокупность чисел, символов, понятий, свойств и вообще любых 
объектов. Если область значений функции содержит k различных 
элементов, то она называется k-значной функцией.
Логические функции могут зависеть от одной, двух и, вообще говоря, любого числа переменных (аргументов) х1, х2, ..., хп. В отличие 
от самой функции аргументы могут принимать значение элементов 
как конечных, так и бесконечных множеств. В теоретико-множественном смысле логическая функция n переменных y = f(x1, x2, ..., хп) 
представляет собой отображение множества наборов (n-мерных векторов, кортежей, последовательностей) вида (х1, х2, ..., хп), являющегося областью ее определения, на множество ее значений.
Логическую функцию f(x1, x2, ..., хп) можно рассматривать как 
операцию, заданную законом композиции x1  x2  ...  хп  x, где 
x1  X1, x2  X2, …, xn  Xn, «» — знак декартова произведения, 
а «» — знак принадлежности.
Если аргументы функции (x1, x2, ..., хп) принимают значения 
из того же множества, что и сама функция, то ее называют однородной. В этом случае X1 = Х2 = … = Хп = X — однородная функция, 
рассматриваемая как закон композиции Хп  Х, которая определяет 
некоторую n-местную операцию на конечном множестве Х.
Областью определения однородной функции y = f(x1, x2, ..., хп) 
является множество наборов {x1, x2, ..., хп}, называемых словами, где 
каждый аргумент x1, x2, ..., хп замещается буквами k-ичного алфавита {0, 1, ..., k – 1}. Количество n букв в данном слове определяет 
его длину.
Очевидно, что число всевозможных слов длины п в k-ичном алфавите равно kn. Так как каждому такому слову имеется возможность 

предписать одно из k значений множества X, общее количество однородных функций от n переменных определяется выражением

Хф = kп.

Если буквами алфавита служат символы от 0 до (k – 1), то 
каждое слово (x1, x2, ..., хп) символически представляется упорядоченной последовательностью n таких чисел и рассматривается 
как запись n-разрядного числа в позиционной системе счисления 
с основанием k, т.е.

(
)
−
−
−
⋅
+
⋅
+
+
⋅
+
⋅
=
…
1
2
1
0
1
2
1
.
n
n
n
n
x
k
x
k
x
k
x
k
q

1.2. БУЛЕВЫ ФУНКЦИИ

1.2.1. Основные понятия и определения
Булевы функции относятся к классу двузначных однородных 
функций. Это наиболее простой и в то же время важнейший класс 
однородных функций, которые используются для описания конечных автоматов, ЭВМ и вычислительных сетей. Последние, 
в свою очередь, предназначаются для переработки дискретной информации. В качестве модели средств переработки используется 
понятие автомата. Для формального описания цифрового автомата 
применяют аппарат алгебры логики (булевой алгебры). Булеву алгебру образуют множества всех булевых функций вместе с операциями отрицания, конъюнкции, дизъюнкции, импликации и т.п.
Основным понятием алгебры логики является высказывание. 
Образно говоря, высказывание — это некоторое утверждение, 
о котором можно сказать, что оно истинно или ложно. Например, 
«Нижний Новгород — город на Волге», «солнце всходит утром» — 
истинные высказывания, а «на улице идет дождь» — может быть 
высказыванием истинным или ложным в зависимости от дополнительных сведений. Любое высказывание можно обозначить символом x и считать, что x = 1 при истинности, а x = 0 при ложности 
высказывания.
Будем рассматривать функции вида f(x1, x2, ..., хп), аргументы 
которых определены на множестве В = {0,1} и таковы, что f(x1, x2, 
..., хп)  В, когда хi  B(i = 1, 2, ..., п). Эти функции будем называть функциями алгебры логики или булевыми функциями. Таким 
образом, запись f(x1, x2, ..., хп) понимается как запись функции, зависящей от произвольных фиксированных аргументов.
Логическими (булевыми) переменными в булевой алгебре называют величины, которые независимо от их конкретной сущности 

могут принимать лишь два значения из множества B. Эти два возможных значения будем обозначать «нулем» (0) и «единицей» (1). 
Если переменная x имеет единичное значение, мы записываем 
х = 1, если нулевое — х = 0. Булевой или переключательной функцией 
f(x1, x2, ..., хп –1) называют функцию, которая, как и ее n аргументов, 
может принимать лишь два значения — 0 или 1. В вычислительной 
технике булевы функции применяются для описания алгоритмов, 
средств вычислительной техники — дискретных устройств. Дискретные устройства предназначаются для преобразования дискретной информации, разлагающейся на элементарные единицы — 
биты. Биты в устройствах реализуются сигналами, которые описываются двоичными переменными — булевыми.
Совокупность значений аргументов является кортежем, точкой 
или набором. Функция, зависящая от n аргументов, называется 
n-местной и является полностью определенной, если указаны ее 
значения для всех наборов (кортежей, точек) значений аргументов. 
Каждому i-му кортежу можно поставить в соответствие «терм» — 
произвольное элементарное произведение двоичных переменных:

−
= …
1
2
1
0
i
m
m
t
x x
x x x . Если в i-м кортеже xj = 1, то в терме вместо jx  
стоит переменная xj, если xj = 0, то — 
jx .

1.2.2. Способы задания булевых функций
Существует три способа задания переключательной функции: 
вербальный (или словесный), аналитический и табличный. Аналитическое задание функции — описание ее аналитическим выражением (формулой). Например, 
(
)
=
+
+
1
1
2
3
1
2
2
3
1
(
)
;
f x x x
x x
x
x
x

=
+
2(
)
.
f abc
abc
abc  Одним из распространенных способов задания 
булевой функции является ее задание с помощью таблицы соответствия (истинности). В табл. 1.1 приведен пример. В колонках 
1, 2, 3 заданы все возможные кортежи значений трех аргументов, 
т.е. сочетание нулевых и единичных значений трех аргументов. 
В колонке 4 — значения функций.
Любое целое неотрицательное число N можно рассматривать 
в виде суммы:

−
−
−
=
+
+
+
+
1
2
1
0
1
2
1
1
,
n
n
n
n
N
g r
g r
g
r
g r

где r — основание системы счисления; g — множитель, который 
принимает значения от 0 до (r – 1). 
Количество слагаемых определяется разрядностью чисел.
Кортеж значений аргументов можно рассматривать как запись целого положительного числа в двоичной системе счисления 
(r = 2), тогда х0 — разряд единиц, х1 — разряд двоек, x2 — разряд 

четверок. Например, шестой набор 1 · 22 + 0 · 21 + 1 · 20. Первый 
набор называется нулевым, последний — единичным.

Таблица 1.1

x(2)
x(1)
x(0)
f(x(2), x(1), x(0))
кортеж (набор, точка)

1
2
3
4

0
0
0
0

0
0
1
1

0
1
0
0

0
1
1
1

1
0
0
1

1
0
1
1

1
1
0
0

1
1
1
0

Десятичный эквивалент двоичного представления числа называется номером кортежа.

1.2.3. Булевы функции одной переменной
Таблица (табл. 1.2) соответствия для булевых функций одной 
переменной имеет вид:

Таблица 1.2

x
y1 = f1(x)
y2 = f2(x)
y3 = f3(x)
y4 = f4(x)

0
1
0
1
0

1
1
0
0
1

Две функции y1 и y2 представляют собой функции-константы: 
f1(x) является абсолютно истинной (константа единицы); f2(x) — 
абсолютно ложной (константа нуля); f3(x) — логическое отрицание 
или НЕ инверсия х (читается как «не x», изображается как x), это 
единственная нетривиальная функция; f4(x) — переменная x (повторяет значения переменной x и поэтому просто совпадает с ней).

1.2.4. Булевы функции двух переменных
В табл. 1.3 представлены функции двух переменных. Данные 
функции используются как в математике, так и в программировании. Число функций — 16, из которых шесть f16(a, b) = 0, 
f11(a, b) = a, f13(a, b) = b, f12(a, b) = a, f14(f, b) = b, f15(a, b) = 1 являются константами или функциями одного аргумента. Остальные