Элементы дискретной математики

Серия «Учебные издания для бакалавров» 
А. И. Новиков 
ЭЛЕМЕНТЫ 
ДИСКРЕТНОЙ 
МАТЕМАТИКИ 
Учебное пособие 
3-е издание
Рекомендовано   
федеральным государственным бюджетным учреждением  
«Федеральный институт развития образования» (ФГБУ «ФИРО»)  
в качестве учебного пособия для использования в образовательном процессе  
образовательных организаций, реализующих программы  
высшего образования по направлениям подготовки   
«Экономика», «Менеджмент»  
(уровень бакалавриата) 
Регистрационный номер рецензии 529 от 04 февраля 2018 г. 
Москва 
Издательско-торговая корпорация «Дашков и Кƒ» 
2021 
1 

УДК 510519.1 
ББК 22.1222.176 
Н73 
Автор: 
А. И. Новиков ² доктор физико-математических наук, профессор Российского университета кооперации. 
Рецензенты: 
В. А. Волочиенко ² доктор экономических наук, профессор; 
И. И. Постников ² доктор технических наук, профессор. 
Н73 
Новиков А. И. 
Элементы дискретной математики: Учебное пособие для бакалавров / А. И. Новиков. ² 3-е изд. ² М.: Издательско-торговая 
корпорация «Дашков и Кƒ», 2021. ² 209 с. 
ISBN 978-5-394-04430-4 
В учебном пособии рассмотрены основные методы и приемы 
дискретной математики, определяемые требованиями федеральных  
государственных образовательных стандартов высшего образования.  
В нем в краткой и доступной форме изложены основные разделы дискретной математики: алгебра логики, теория множеств, основные понятия теории графов и другие математические понятия, применяемые в 
экономике и вычислительной технике. 
Все излагаемые методы и подходы иллюстрируются примерами и 
упражнениями для закрепления знаний и формирования навыков их 
применения. 
Для студентов бакалавриата, обучающихся по направлениям подготовки «Экономика», «Менеджмент». 
ISBN 978-5-394-04430-4 
‹ Новиков А. И., 2019 
‹ Новиков А. И., 2020, с изменениями 
‹ ООО «ИТК «Дашков и Кƒ», 2020, 
    с изменениями 
2 

CОДЕРЖАНИЕ 
Глава 1. АЛГЕБРА ЛОГИКИ 
.............................................................. 6 
1.1. Логические функции 
................................................................... 6 
Основные понятия  ............................................................................ 6 
Существенные и несущественные переменные .............................. 9 
1.2. Элементарные булевы функции ............................................... 11 
1.3. Логические формулы ................................................................. 14 
Порядок выполнения логических операций в сложном  
логическом выражении 
................................................................ 19 
Построение таблицы истинности ............................................... 20 
1.4. Законы логики ............................................................................ 27 
1.5. Упрощение логических формул. Правила преобразования 
формул................................................................................................ 32 
1.6. Двойственные функции ............................................................. 37 
1.7. Полнота в логике высказываний .............................................. 42 
Глава 2. ПОСТРОЕНИЕ НОРМАЛЬНЫХ ФОРМ  
ЛОГИЧЕСКИХ ФУНКЦИЙ .............................................................. 46 
2.1. Понятие нормальной формы 
..................................................... 46 
2.2. Дизъюнктивная и конъюнктивная  нормальные формы ........ 46 
2.3. Алгоритмы построения ДНФ и КНФ ....................................... 49 
2.4. Алгоритмы переходов  от одной нормальной формы  
к другой 
.............................................................................................. 52 
Переход от ДНФ к КНФ .............................................................. 52 
Переход от КНФ к ДНФ .............................................................. 53 
2.5. Совершенные дизъюнктивные и конъюнктивные  
нормальные формы ........................................................................... 56 
2.6. Способы приведения  к совершенным нормальным  
формам ............................................................................................... 57 
Глава 3. МИНИМИЗАЦИЯ  НОРМАЛЬНЫХ ФОРМ 
.................. 66 
3.1. Проблема минимизации ............................................................ 66 
3.2. Минимизация дизъюнктивных нормальных форм ................. 67 
Первый этап (получение сокращенной формы) ........................ 69 
Второй этап (получение минимальной формы) ........................ 72 
3.3. Минимизация конъюнктивных нормальных форм 
................. 80 
3 

3.4. Минимизации функций в классе нормальных форм .............. 85 
3.5. Минимизация частично определенных функций 
.................... 86 
3.6. Минимизация логических функций  по картам Карно 
........... 90 
3.7. Карты Карно при минимизации не полностью  
определенных функций .................................................................. 101 
Глава 4. ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА ................ 104 
4.1. Базовые логические элементы (вентили).  
Функциональные схемы ................................................................. 104 
4.2. Виды задач на логические элементы 
...................................... 107 
Глава 5. МНОЖЕСТВО .................................................................... 116 
5.1. Понятие множества 
.................................................................. 116 
5.2. Операции над множествами 
.................................................... 119 
5.3. Свойства операций над множествами 
.................................... 125 
5.4. Формула включений и исключений ....................................... 133 
5.5. Отношения 
................................................................................ 135 
Декартово произведение множеств .......................................... 135 
Отношение множеств 
................................................................. 136 
Матрица отношения 
................................................................... 136 
Обратное отношение 
.................................................................. 138 
Композиция отношений 
............................................................. 139 
Свойства отношений 
.................................................................. 139 
Отношение эквивалентности .................................................... 144 
Отношение порядка ................................................................... 146 
Глава 6. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ 
................................. 148 
6.1. Основные понятия 
.................................................................... 148 
6.2. Способы задания графов ......................................................... 153 
Матрица смежности ................................................................... 154 
Матрица инцидентности 
............................................................ 155 
6.3. Маршруты, цепи, циклы 
.......................................................... 158 
Задача о кратчайшем пути между исходным узлом   
и любым другом узлом сети 
...................................................... 161 
Задача о кратчайшем пути между двумя пунктами ................ 167 
Задача определения максимального потока ............................ 172 
Задача о назначениях ................................................................. 177 
Дерево решений 
.......................................................................... 182 
4 

Глава 7. СЕТЕВОЕ ПЛАНИРОВАНИЕ  И УПРАВЛЕНИЕ ...... 184 
7.1. Основные понятия сетевой модели ........................................ 184 
7.2. Метод критического пути........................................................ 186 
Основные временные параметры сетевых графиков  ............. 187 
Построение предварительного временного графика  ............. 191 
Определение резервов (запасов) времени  
............................... 194 
7.3. Распределение ресурсов. Оптимизация сетевого графика 
... 196 
7.4. Стоимость проекта. Оптимизация сетевого графика  
........... 200 
7.5. Сетевые модели в условиях неопределенности  ................... 204 
ЛИТЕРАТУРА  
.................................................................................... 208 
5 

Глава 1. АЛГЕБРА ЛОГИКИ 
1.1. Логические функции 
Основные понятия 
Логика — наука о законах и формах правильного мышления. 
Различают формальную и математическую логику. 
Формальная логика связана с анализом наших обычных содержательных рассуждений, выражаемых разговорным языком. Основы 
формальной логики заложил Аристотель, который впервые отделил 
логические формы мышления от его содержания.  
Математическая логика, являясь частью формальной логики, 
изучает только высказывания и рассуждения, для которых можно однозначно решить: истинны они или ложны. В математической логике 
расширяется класс логических операций, которые используются в 
логических преобразованиях высказываний (алгебра логики). Создателем алгебры логики является английский математик Джордж Буль, 
в честь которого эта алгебра названа булевой алгеброй высказываний.  
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучают логические операции над высказываниями. 
Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Истинность или ложность, приписываемые некоторому высказыванию, называются его значением истинности, или истинностным значением.  
В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. 
Вопросительные, восклицательные предложения, а также определения не будем считать высказываниями, о них нельзя сказать, истинны они или ложны. Например, фразы: «куда ты пошел?», «стойте!», «результат сложения двух чисел называется их суммой» не 
являются высказываниями. 
Высказывания бывают простые и сложные. 
Простым называется высказывание, которое не содержит в себе 
других высказываний в качестве своих частей.  
6 

Будем обозначать простые высказывания малыми буквами латинского алфавита a, b, c,…, которые называют логическими переменными. Значением логической переменной могут быть только истина и ложь. Обозначение: истинное высказывание — цифра 1, 
ложное — цифра 0. 
Например, высказывание a = «Луна является спутником Зем- 
ли» — истинно (1), а высказывание b = «Москва — столица Германии» — ложно (0). 
Сложным называется высказывание, образованное из простых с 
помощью логических связок (или, и, не и др.).  
Например, из простых высказываний: «На улице идет дождь», 
«На улице светит солнце», «На улице пасмурная погода» можно составить сложные высказывания: «На улице идет дождь и на улице 
светит солнце», «На улице светит солнце или на улице пасмурная погода», «Неверно, что на улице идет дождь». 
В алгебре логики простые высказывания заменяются логическими переменными, логические связки — логическими операциями над 
высказываниями, которые имеют свое название и обозначение. При 
этом сложное высказывание превращается в логическую функцию. 
Булевой, или логической, переменной называется переменная, 
принимающая одно из двух значений 0 и 1.  
Булевой, или логической, функцией (ЛФ) называют функцию F(x1, 
x2,…, xn), аргументы которой x1, x2,…, xn (независимые переменные) и 
сама функция (зависимая переменная) принимают значения 0 или 1. 
Таким образом, сложное высказывание рассматривается как логическая функция F(x1, x2,…, xn), аргументами которой являются логические переменные x1, x2,…, xn (простые высказывания).  
Каждое из простых высказываний, входящих в сложное, может 
быть либо истинно, либо ложно. Значение истинности сложного высказывания зависит от истинности входящих в него простых высказываний и типа объединяющих их связок.  
Основная задача математической логики — на основании ложности или истинности простых высказываний определить значение 
сложного высказывания. 
Существуют два основных способа задания булевых функций — 
табличный и аналитический. При табличном способе булева функция 
7 

задается таблицей истинности, а при аналитическом способе — формулой, т. е. аналитическим выражением, построенным из операций 
булевой алгебры. 
Таблицу, показывающую, какие значения принимает логическая 
функция при всех сочетаниях (наборах) значений ее аргументов, называют таблицей истинности логической функции. Таблица истинности логической функции n аргументов содержит 2n строк, n столбцов значений аргументов и 1 столбец значений функции.  
Например, таблица истинности функции f (x1, x2, x3) трех переменных имеет вид 
 
1
x  
2
x  
3
x  
2
3
1,
,
(
)
f x x x
 
0 
0 
0 
(0,0,0)
f
 
0 
0 
1 
(0, 0,1)
f
0 
1 
0 
(0,1,0)
f
 
0 
1 
1 
(0,1,1)
f
 
1 
0 
0 
(1,0,0)
f
 
1 
0 
1 
(1,0,1)
f
 
1 
1 
0 
 
(1,1,0)
f
(1,1,1)
f
1 
1 
1 
 
 
Таблица истинности состоит из двух частей. В левой части таблицы содержатся наборы значений переменных 
, а в пра- 
1
2
3
,
,
x x x
вой — значения функции 
 на соответствующих наборах 
1
2
3
( ,
,
)
f x x x
1
2
3
,
,
x x
x
значений переменных. 
При перечислении наборов (
) использован лексикографический порядок, который совпадает с порядком возрастания наборов, понимаемых как двоичные числа. 
Таблицы истинности, задающие булевы функции от одного числа аргументов, отличаются лишь последним столбцом. Поэтому, зафиксировав лексикографический порядок перечисления наборов, булеву функцию от одного числа переменных можно также задавать в 
виде вектора значений функции, который выписывается по правому 
столбцу ее таблицы истинности.  
8 

Например, функцию f (x1, x2) двух переменных можно задать в 
виде следующей таблицы истинности 
 
 
 
 
1
x
2
x
1
2
f(x ,x )
0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
1 
0 
 
или в виде вектора значений функции f = (0110), т. е. f(0,0) = 0, f(0,1) = 1, 
f(1,0) = 1, f(1,1) = 0. 
Булеву функцию, определенную на всех своих наборах, называют полностью определенной. Булеву функцию n переменных называют не полностью определенной или частичной, если она определена 
не на всех двоичных наборах. 
Две булевы функции от одного и того же числа переменных n 
равны, если совпадают их таблицы истинности. 
Существенные и несущественные  
переменные 
Переменная 
 булевой функции 
 называется неi
x
1
2
( ,
,...,
)
n
f x x
x
существенной (фиктивной), если 
=
 
1
1
1
( ,...,
, 0,
,...,
)
i
i
n
f x
x
x
x


1
1
1
( ,...,
, 1,
,...,
)
i
i
n
f x
x
x
x


при любых значениях остальных переменных, т. е. изменение значения 
 не изменяет значения функции; иначе переменная xi называетi
x
i
x
ся существенной.  
Чтобы определить по таблице истинности булевой функции, что 
переменная 
является несущественной, нужно проверить, что на 
всех парах наборов, у которых одинаковы все компоненты, кроме i-й 
(i-я компонента в одном наборе равна 0, а в другом — 1), функция 
принимает равные значения. 
9 

2
3
( ,
,
)
f x x x
Например, пусть функция 
 задана таблицей истин- 
ности 
 
 
 
 
1
x
2
x
3
x
1
2
(
)
3
f x ,x ,x
0 
0 
0 
0 
0 
0 
1 
0 
0 
1 
0 
1 
0 
1 
1 
1 
1 
0 
0 
0 
1 
0 
1 
0 
1 
1 
0 
1 
1 
1 
1 
1 
 
Переменная 
является несущественной для 
, так как 
3
x
1
2
3
( ,
,
)
f x x x
=
. 
1
2
( ,
,0)
f x x
1
2
( ,
,1)
f x x
1
2
( ,
)
f x x
Удаляя ее, получим функцию 
: 
 
 
 
 
1
x
2
x
1
2
(
)
f x ,x
0 
0 
0 
0 
1 
1 
1 
0 
0 
1 
1 
1 
1
x
2
(0,
)
f
x
2
(1,
)
f
x
2
2
(
)
f x
x
 
1
1
( ,...,
)
k
f x
x
1
1
( ,...,
)
m
f x
x
 
Переменная 
 также является несущественной, так как 
= 
= 
. Удаляя ее, получим функцию 
. 
Булевы функции не изменяют свои значения путем введения 
(или удаления) несущественных переменных. 
Две функции 
и
 от разного количества 
переменных равны, если одна получается из другой путем удаления 
или введения несущественных переменных. 
Обозначим через Р2 множество всех булевых функций. Число 
n
всех булевых функций от n переменными равно 
. Число булевых 
2
2
функций при n = 1 равно 
, а при n = 2 равно 
.  
2
2
4
2
2
16
 
 
1
2
2
2
2
4
 
 
10