Дискретная математика в пакете MATLAB

К.Э. Плохотников 

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

MATLAB 

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

Москва 
Издательство «ФЛИНТА» 
2020  

Таблица №2. Перечень булевых функций двух переменных 

Переменная ���� 0 0 1 1 
Переменная ���� 0 1 0 1 

№№ Название 
Обозначение 
Несущественные 

1 
Нуль 
0 0 0 0 
����, ����  

2 
Конъюнкция 
×,∙,∧, &  
0 0 0 1 

3 
0 0 1 0 

4 
0 0 1 1 
����  

5 
0 1 0 0 

6 
0 1 0 1 
����  

7 
Сложение по модулю 2 
+, +2, ⨁  
0 1 1 0 

8 
Дизъюнкция 
∨  
0 1 1 1 

9 
Стрелка Пирса1 
↓  
1 0 0 0 

10 
Эквивалентность  
≡  
1 0 0 1 

11 
1 0 1 0 
����  

12 
1 0 1 1 

13 
1 1 0 0 
����  

14 
Импликация 
→, ⇒, ⊃  
1 1 0 1 

15 
Штрих Шеффера2 
|  
1 1 1 0 

16 
Единица 
1 1 1 1 
����, ����  

 

Таблица №3. Истинность (ложность) базовых 

логических операций 

���� 
���� 
¬���� 
����&���� 
���� ∨ ���� 
���� ⇒ ���� 

���� 
���� 
���� 
���� 
���� 
���� 

���� 
���� 
���� 
���� 
���� 
���� 

���� 
���� 
���� 
���� 
���� 
���� 

���� 
���� 
���� 
���� 
���� 
���� 

УДК 519.17 
ББК 22.176 
  П 39 

Рецензенты: 

док. физ.-мат. наук, профессор П.Е. Рябов, 
канд. физ.-мат. наук, доцент С.А. Зададаев 

Плохотников К.Э.  
Дискретная математика в пакете MATLAB [Электронный ресурс]: учеб. 
пособие. — Москва: ФЛИНТА, 2020. — 533с. 

ISBN 978-5-9765-4431-4 

В учебном пособии изложены некоторые классические разделы дискретной математики на 
базе широко известного пакета прикладных программ MATLAB. Материалы учебного пособия разделены на две части, относимые к лекциям и семинарам соответственно. Лекционная часть не предполагает использование пакета MATLAB и представляет собой набор из семи разделов, составленных в виде набора презентаций. Семинарская часть учебного пособия опирается на использование 
компьютерного класса с предустановленным пакетом MATLAB. Если читателя интересует только 
теоретическая часть курса, то он может игнорировать вторую часть курса, состоящую из семинарских занятий. Если же читатель хочет получить оперативный навык расчета, зачастую сводимый к 
получению числа или графика, то ему необходимо освоить семинары, в которых лекционный материал дублируется вместе с набором программ, запускаемых с помощью пакета MATLAB. 
В рамках данного учебного пособия удалось охватить следующие темы, традиционно относимые к дискретной математике: теория множеств, алгебраические структуры, булевы функции, логические исчисления, комбинаторика, кодирование и теория графов. Следует отметить особую роль 
метода Монте-Карло в связи с преподаванием не только дискретной математики, но и других математических дисциплин на базе различного рода пакетов прикладных программ, подобных 
MATLAB. В частности, особая роль метода Монте-Карло выражается в активном использовании 
всевозможных генераторов псевдослучайных чисел, имеющихся в ассортименте в современных пакетах прикладных программ, а также идеологии статистических испытаний. 
Данный курс получил учебную апробацию на примере бакалавров первого года обучения 
Факультета прикладной математики и информационных технологий Финансового университета 
при Правительстве РФ в 2019 году. Курс может быть рекомендован студентам младших курсов тех 
вузов, где дискретная математика излагается с опорой на методы программирования по направлениям: прикладная математика, математическое моделирование, информационные технологии, информационная безопасность и ряд других направлений. 

ISBN  978-5-9765-4431-4 
© Плохотников К.Э., 2020 
© Издательство «ФЛИНТА», 2020 

П 39 

УДК 519.17
ББК 22.176 

— 3 — 

ОГЛАВЛЕНИЕ 

ЧАСТЬ I (ЛЕКЦИИ) .................................................................... 7

ЛЕКЦИЯ №1 ................................................................................. 8

ТЕОРИЯ МНОЖЕСТВ .............................................................................. 8

§1. Введение .................................................................................................................. 8 
§2. Форматы задания дискретных множеств ............................................................ 10 
§3. Операции над множествами ................................................................................. 13 
§4. Мощность множества ........................................................................................... 15 
§5. Декартово произведение множеств ..................................................................... 19 
§6. Бинарные отношения между множествами ........................................................ 22 
§7. Функциональное отношение между множествами............................................ 24 

ЛЕКЦИЯ №2 ............................................................................... 28

АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ .................................................... 28

§1. Введение ................................................................................................................ 28 
§2. Алгебра с одной операцией .................................................................................. 33 
§3. Группы ................................................................................................................... 37 
§4. Алгебра с двумя операциями ............................................................................... 41 
§5. Векторное пространство ....................................................................................... 46 
§6. Решетки и булева алгебра .................................................................................... 49 

ЛЕКЦИЯ №3 ............................................................................... 54

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

§1. Введение ................................................................................................................ 54 
§2. Булевы функции одной и двух переменных ....................................................... 56 
§3. Реализация функций формулами ......................................................................... 59 
§4. Алгебра булевых функций ................................................................................... 62 
§5. Нормальные формы .............................................................................................. 65 
§6. Минимальные дизъюнктивные формы ............................................................... 69 
§7. Полнота .................................................................................................................. 74 

ЛЕКЦИЯ №4 ............................................................................... 79

ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ ........................................................... 79

§1. Пропозициональная логика .................................................................................. 79 
§2. Интерпретация логических формул .................................................................... 83 
§3. Формальные теории .............................................................................................. 86 
§4. Исчисление высказываний как формальная теория .......................................... 92 
§5. Исчисление предикатов первого порядка ........................................................... 99 
§7. Иллюстрация теорем Геделя .............................................................................. 102 

— 4 — 

ЛЕКЦИЯ №5 ............................................................................. 112

КОМБИНАТОРИКА .............................................................................. 112

§1. Введение .............................................................................................................. 112 
§2. Размещения, перестановки и сочетания ........................................................... 114 
§3. Биномиальные коэффициенты ........................................................................... 120 
§4. Комбинаторные задачи с ограничениями ......................................................... 123 
§5. Производящие функции ..................................................................................... 129 

ЛЕКЦИЯ №6 ............................................................................. 132

КОДИРОВАНИЕ ..................................................................................... 132

§1. Введение .............................................................................................................. 132 
§2. Алфавитное кодирование ................................................................................... 134 
§3. Минимизация длины кода сообщения .............................................................. 138 
§4. Помехоустойчивое кодирование ....................................................................... 145 
§5. Код Хэмминга для исправления одной ошибки замещения ........................... 151 
§6. Криптография в части шифрования .................................................................. 155 
§7. Шифрование с открытым ключом ..................................................................... 160 

ЛЕКЦИЯ №7 ............................................................................. 165

ТЕОРИЯ ГРАФОВ .................................................................................. 165

§1. Введение .............................................................................................................. 165 
§2. Иные формы графов ........................................................................................... 167 
§3. Изоморфизм графов ............................................................................................ 170 
§4. Характеристики графов и его составные элементы......................................... 171 
§5. Виды графов и операции над графами .............................................................. 175 
§6. Представление графов на компьютере ............................................................. 180 
§7. Эйлеровы и гамильтоновы графы ..................................................................... 186 

ЧАСТЬ II (СЕМИНАРЫ) ....................................................... 193 

СЕМИНАР №1 .......................................................................... 194

ТЕОРИЯ МНОЖЕСТВ .......................................................................... 194

§1. Введение .............................................................................................................. 194 
§2. Форматы задания дискретных множеств .......................................................... 196 
§3. Операции над множествами ............................................................................... 200 
§4. Мощность множества ......................................................................................... 205 
§5. Декартово произведение множеств ................................................................... 210 
§6. Бинарные отношения между множествами ...................................................... 214 
§7. Функциональное отношение между множествами.......................................... 218 
§8. Дополнительные задачи ..................................................................................... 222 

СЕМИНАР №2 .......................................................................... 229

АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ .................................................. 229

§1. Введение .............................................................................................................. 229 

— 5 — 

§2. Алгебра с одной операцией ................................................................................ 236 
§3. Группы ................................................................................................................. 240 
§4. Алгебра с двумя операциями ............................................................................. 245 
§5. Векторное пространство ..................................................................................... 252 
§6. Решетки и булева алгебра .................................................................................. 255 
§7. Дополнительные задачи ..................................................................................... 261 

СЕМИНАР №3 .......................................................................... 276

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

§1. Введение .............................................................................................................. 276 
§2. Булевы функции одной и двух переменных ..................................................... 280 
§3. Реализация функций формулами ....................................................................... 284 
§4. Алгебра булевых функций ................................................................................. 288 
§5. Нормальные формы ............................................................................................ 292 
§6. Минимальные дизъюнктивные формы ............................................................. 297 
§7. Полнота ................................................................................................................ 303 
§8. Дополнительные задачи ..................................................................................... 309 

СЕМИНАР №4 .......................................................................... 318

ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ ......................................................... 318

§1. Пропозициональная логика ................................................................................ 318 
§2. Интерпретация логических формул .................................................................. 323 
§3. Формальные теории ............................................................................................ 326 
§4. Исчисление высказываний как формальная теория ........................................ 333 
§5. Исчисление предикатов первого порядка ......................................................... 342 
§6. Иллюстрация теорем Геделя .............................................................................. 344 
§7. Дополнительные задачи ..................................................................................... 356 

СЕМИНАР №5 .......................................................................... 370

КОМБИНАТОРИКА .............................................................................. 370

§1. Введение .............................................................................................................. 370 
§2. Размещения, перестановки и сочетания ........................................................... 372 
§3. Биномиальные коэффициенты ........................................................................... 381 
§4. Комбинаторные задачи с ограничениями ......................................................... 386 
§5. Производящие функции ..................................................................................... 394 
§6. Дополнительные задачи ..................................................................................... 397 

СЕМИНАР №6 .......................................................................... 407

КОДИРОВАНИЕ ..................................................................................... 407

§1. Введение .............................................................................................................. 407 
§2. Алфавитное кодирование ................................................................................... 410 
§3. Минимизация длины кода сообщения .............................................................. 415 
§4. Помехоустойчивое кодирование ....................................................................... 425 
§5. Код Хэмминга для исправления одной ошибки замещения ........................... 435 
§6. Криптография в части шифрования .................................................................. 441 
§7. Шифрование с открытым ключом ..................................................................... 447 

— 6 — 

§8. Дополнительные задачи ..................................................................................... 454 

СЕМИНАР №7 .......................................................................... 472

ТЕОРИЯ ГРАФОВ .................................................................................. 472

§1. Введение .............................................................................................................. 472 
§2. Иные формы графов ........................................................................................... 475 
§3. Изоморфизм графов ............................................................................................ 480 
§4. Характеристики графов и его составные элементы......................................... 482 
§5. Виды графов и операции над графами .............................................................. 491 
§6. Представление графов на компьютере ............................................................. 499 
§7. Эйлеровы и гамильтоновы графы ..................................................................... 508 
§8. Дополнительные задачи ..................................................................................... 520 

Плохотников К.Э. Дискретная математика в пакете MATLAB 

— 7 — 

Часть I (Лекции) 

Плохотников К.Э. Дискретная математика в пакете MATLAB 

— 8 — 

Лекция №1 

ТЕОРИЯ МНОЖЕСТВ 

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

§1. Введение

По теме дискретной математики существует множество учебников и учебных 
пособий 1. Все они в разном отношении соотносятся с теми или иными пакетами прикладных программ. Предлагаемое учебное пособие, наиболее тесно 
переплетено с таким пакетом прикладных программ, как MATLAB. Выбор пакета MATLAB связан с авторским предпочтением данного пакета2. 
Дискретная математика в отличие от непрерывной математики имеет 
дело с такими понятиями, как множество, элемент множества и пр. При этом 
как множества, так и соответствующие элементы должны быть отчетливо 
определены и отделены друг от друга. В дискретной математике множества, 
как правило состоят либо из конечного числа элементов, либо из счетно-бесконечного набора. Последнее свойство означает, что элементы множества могут быть перенумерованы, например, в формате 1, 2, … , ����, … Дать более конкретные определения каждому из понятий множество, элемент без относительно другого не представляется возможным. 
Приведем пример того, как трудно в реальности определить конкретное 
множество и его элементы. Пусть таким множеством выступает человечество. 
Возникает вопрос: каков элемент человечества? Если в качестве элемента человечества выступает отдельный человек, то как их различить? Если в качестве элемента человечества выступает этнос (народ), то как быть с теми, кто 
затрудняется в отнесении себя к тому или иному этносу. Если элементом человечества выступает отдельное государство, то человечество, как множество 

1 Новиков Ф.А. Дискретная математика: Учебник для вузов. 2- изд. Стандарт третьего поколения, — 
СПб.: Питер, 2013. — 432с.; Хаггарти Р. Дискретная математика для программистов. М.: Техносфера, 
2003.  — 320с.; Чашкин А.В. Лекции по дискретной математике: учеб. пособие. — М.: МГУ, мехмат, 2007. — 
261с.; Лорьер Ж.-Л. Системы искусственного интеллекта. — М.: Мир, 1991. — 568с.; Аршинов М.Н., Садовский Л.Е. Коды и математика (Рассказы о кодировании). — М.: Наука, 1983. — 144с.; Ерош И.Л., Сергеев М.Б., 
Соловьев Н.В. — Дискретная математика: учеб. пособие. — СПб: СПбГУАП, 2005. — 144с.; Макоха А.Н., 
Сахнюк П.А., Червяков Н.И. Дискретная математика: учеб. пособие. — М.: ФИЗМАТЛИТ, 2005. — 368с.; 
Редькин Н.П. Дискретная математика. — М.: ФИЗМАТЛИТ, 2009. — 264с.; Соболева Т.С., Чечкин А.В. Дискретная математика: учеб. для студ. вузов. — М.: Изд. центр “Академия”, 2006. — 256с.; Судоплатов С.В., 
Овчинникова Е.В. Дискретная математика. — Новосибирск, 2011. — 143с.; Яблонский С.В. Введение в дискретную математику: учеб. пособие для вузов. — М.: Наука, Гл. ред. Физ.-мат. лит., 1986. — 384с. 
2 Плохотников К.Э. Вычислительные методы. Теория и практика в среде MATLAB: курс лекций. 
Учебное пособие для вузов. — 2-е изд., испр. — М.: Горячая линия – Телеком, 2013. — 496с.; Плохотников 
К.Э. Методы разработки математических моделей и вычислительный эксперимент на базе пакета 
MATLAB.  — Курс лекций. — М.: СОЛОН-Пресс, 2017. — 628с.; Плохотников К.Э. Базовые разделы математики для бакалавров в среде MATLAB: учебное пособие / Плохотников К.Э., – 2-е изд. – М.: НИЦ ИНФРАМ, 2018. – 1114 с. 

Плохотников К.Э. Дискретная математика в пакете MATLAB 

— 9 — 

становится иным, скорее это глобальное геополитические целое. Таким образом, очевидно, что, меняя толкование элемента, можно поменять смысл исходного множества и, наоборот. 
Дискретная математика3 как математическая дисциплина имеет дело с 
вполне определенными множествами, когда соответствующие элементы 
также вполне хорошо определены. Роль дискретной математики4 как отдельной дисциплины заметно возросла в последнее время в связи с наступлением 
компьютерной индустрии вообще и программирования в частности. Наши занятия по дискретной математике будут проходить в пакете прикладных программ MATLAB5. 
Множества можно создать, перечисляя его элементы. Построим, используя средства пакета прикладных программ MATLAB все слова, состоящие из 
двух букв русского алфавита. 

Пример №1. Построить множество слов, ���� состоящих из двух букв русского алфавита. 

Решение. Нетрудно сообразить, что всего таких слов будет 332 = 1089. 
На семинаре №1 разобрана подходящая программа, которая генерирует все 
двухбуквенные слова и составляет соответствующее множество ����. Итог работы программы приведен на рис.1. Программа создала множество ����, состоящего из 1089 двухбуквенных слов, которые все выведены в командное окно 
MATLAB. 
 

 
Рис.1. Множество двухбуквенных слов русского алфавита  
 
Принадлежность элемента ���� множеству ���� записывается в виде ���� ∈ ����. 
Наоборот, когда ���� не принадлежит множеству ���� пишут: ���� ∉ ����. Например, элемент ���� = ′яя′ принадлежит двухбуквенному множеству слов русского алфавита, ����, т.е. ���� = ′яя′ ∈ ����, а элемент ����2 = ′я′ не принадлежит, т.е. ����2 = ′я′ ∉ ����. 
Набор элементов некоторого множества, зачастую, помещается в фигурные скобки. Так, согласно примеру №1, множество ���� = {аа, аб, … , яя} состоит 

 

3 Новиков Ф.А. Дискретная математика: Учебник для вузов. 2- изд. Стандарт третьего поколения, — 
СПб.: Питер, 2013. — 432с. 
4 Хаггарти Р. Дискретная математика для программистов. М.: Техносфера, 2003. — 320с. 
5 MATLAB — это высокоуровневый язык и интерактивная среда для программирования, численных 
расчетов и визуализации результатов. С помощью MATLAB можно анализировать данные, разрабатывать 
алгоритмы, создавать модели и приложения: https://matlab.ru/products/matlab  

Плохотников К.Э. Дискретная математика в пакете MATLAB 

— 10 — 

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

Пример №2. Построить график зависимости числа простых чисел из 
набора {1, … , ����} в зависимости от ����. 

Решение. Так, в наборе {1, … ,5} простыми являются числа 2,3,5 соответственно, а в наборе {1, … ,10} — 2,3,5,7. На рис.2 приведен итог работы соответствующей программы. С учетом графика рис.2 оказывается, что в наборе 
{1,2, … , 103} содержится 168 простых чисел. 
 

 
Рис.2. Зависимость числа простых чисел из набора 1, … , ���� от ���� 
 

§2. Форматы задания дискретных множеств 

Различают несколько способов задания дискретных множеств. Рассмотрим более подробно три способа: 1) путем прямого перечисления элементов множества; 2) с помощью характеристического предиката; 3) путем использования 
некоторой порождающей процедуры.