Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Новинка
Артикул: 891187.01.99
Доступ онлайн
344 ₽
В корзину
В учебно-методическом пособии изложены основные сведения по дискретной математике. Учебно-методическое пособие содержит расширенный материал лекций по дисциплине «Дискретная математика», предусмотренных учебным планом и рабочей программой дисциплины. Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления».
13
111
201
Шабанова, Н. Ю. Дискретная математика : учебно-методическое пособие / Н. Ю. Шабанова, О. А. Ефремова, А. Д. Михед. - Москва : Директ-Медиа, 2025. - 253 с. - ISBN 978-5-4499-5111-3. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2275856 (дата обращения: 20.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Дискретная 
математика 
Учебно-методическое пособие  
для студентов  
направления подготовки  
09.03.01 «Информатика и вычислительная техника» 
Москва 
2025 


УДК 004.023 
ББК 32.973.02 
Д48 
Д48 
Дискретная математика : учебно-методическое пособие /
сост. Н. Ю. Шабанова, О. А. Ефремова, А. Д. Михед. —
Москва : Директ-Медиа, 2025. — 252 с. ; ил.  
ISBN 978-5-4499-5111-3 
В учебно-методическом пособии изложены основные сведения
по дискретной математике. Учебно-методическое пособие содержит расширенный материал лекций по дисциплине «Дискретная
математика», предусмотренных учебным планом и рабочей программой дисциплины. 
Учебно-методическое пособие предназначено для студентов
всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления». 
УДК 004.023 
ББК 32.973.02 
ISBN 978-5-4499-5111-3 
© Шабанова Н. Ю., Ефремова О. А., Михед А. Д., сост., 2025 
© Издательство «Директ-Медиа», оформление, 2025 


Оглавление 
Введение ................................................................................................... 7 
Часть 1. Множества и отношения .......................................................... 13 
1.1. Множества ................................................................................... 13 
1.1.1. Элементы и множества ........................................................ 14 
1.1.2. Задание множества ............................................................... 16 
1.1.3. Основные определения и понятия ....................................... 17 
1.1.4. Парадокс Рассела.................................................................. 21 
Контрольные вопросы и упражнения ........................................... 21 
1.2. Операции над множествами ........................................................ 22 
1.2.1. Сравнение множеств ............................................................ 22 
1.2.2. Операции над множествами................................................. 22 
1.2.2.1. Предварительные замечания ........................................ 22 
1.2.2.2. Объединение множеств ................................................. 24 
1.2.2.3. Пересечение множеств .................................................. 25 
1.2.2.4. Разность множеств ........................................................ 28 
1.2.2.5. Универсальное множество ............................................ 29 
1.2.2.6. Дополнение множества ................................................. 30 
1.2.2.7. Разбиение множества .................................................... 33 
1.2.2.8. Законы (тождества) алгебры множеств ........................ 34 
1.2.2.9. Аксиомы теории множеств ........................................... 35 
Контрольные вопросы и упражнения ........................................... 37 
1.3. Упорядоченное множество. 
Прямое произведение множеств. Проекции ..................................... 37 
1.3.1. Упорядоченные множества .................................................. 37 
1.3.2. Прямое произведение множеств .......................................... 39 
1.3.3. Проекция множества ............................................................ 41 
1.3.4. Кортеж кортежей .................................................................. 42 
1.3.5. Характеристический вектор множества .............................. 42 
Контрольные вопросы и упражнения ........................................... 43 
1.4. Соответствия ............................................................................... 43 
1.4.1. Определение соответствия ................................................... 43 
1.4.2. Обратное соответствие ......................................................... 46 
1.4.3. Композиция соответствий .................................................... 47 
Контрольные вопросы ................................................................... 49 
1.5. Отображения ................................................................................ 49 
1.5.1. Свойства отображений ......................................................... 50 
1.5.2. Отображения, заданные  на одном множестве .................... 50 


Контрольные вопросы ................................................................... 52 
1.6. Функция ....................................................................................... 53 
1.6.1. Обратная функция ................................................................ 56 
1.6.2. Функция времени ................................................................. 56 
1.6.3. Принцип Дирихле................................................................. 57 
1.6.4. Представление функции в компьютере ............................... 58 
Контрольные вопросы ................................................................... 59 
1.7. Понятие функционала ................................................................. 59 
Контрольные вопросы ................................................................... 61 
1.8. Понятие оператора ...................................................................... 61 
Контрольные вопросы ................................................................... 62 
1.9. Отношения ................................................................................... 62 
1.9.1. Общие сведения ................................................................... 62 
1.9.2. Свойства отношений ............................................................ 64 
1.9.3. Представление отношений в компьютере.  
Матрицы бинарных отношений.   
Специальные бинарные отношения .............................................. 66 
1.9.4. Отношения эквивалентности ............................................... 68 
1.9.5. Отношение порядка .............................................................. 70 
1.9.5.1. Решетки ......................................................................... 72 
1.9.5.2. Диаграммы Хассе .......................................................... 73 
1.9.6. Отношение доминирования ................................................. 74 
1.9.7. Отношения в базах данных (БД).......................................... 74 
1.9.7.1. Характеристика моделей данных ................................. 74 
1.9.7.2. Реляционная модель базы данных ................................ 76 
Контрольные вопросы ................................................................... 85 
1.10. Нечеткие множества .................................................................. 86 
1.10.1. Общие сведения.................................................................. 86 
1.10.2. Операции над нечеткими множествами ............................ 87 
1.10.3. Нечеткое включение и равенство множеств.  
Нечеткое бинарное отношение ...................................................... 94 
1.10.4. Нечеткая и лингвистическая переменные ......................... 97 
Контрольные вопросы ................................................................. 102 
1.11. Приложения теории множеств ................................................ 102 
1.11.1. Система управления базами данных ............................... 102 
1.11.2. Применение нечётких множеств ..................................... 108 
Контрольные вопросы ................................................................. 110 
Литература ........................................................................................ 110 


Часть 2. Элементы теории графов ....................................................... 111 
2.1. Основные сведения из теории графов ...................................... 112 
2.1.1. История теории графов ...................................................... 113 
2.1.2. Теоретико-множественное определение графа, 
основные понятия и определения ............................................... 116 
2.1.3. Операции над графами ....................................................... 124 
2.1.4. Математические структуры для представления графов ... 126 
2.1.4.1. Матрицы ...................................................................... 126 
2.1.4.2. Решение проблемы поиска путей в сетях 
с помощью вычисления матрицы достижимости  
по алгоритму Уоршелла .......................................................... 132 
Контрольные вопросы и задачи .................................................. 136 
2.1.4.3. Списки смежности ...................................................... 137 
2.1.4.4. Массив дуг ................................................................... 140 
2.1.5. Деревья ............................................................................... 141 
2.1.6. Лес. Разрезы ........................................................................ 142 
2.1.7. Эйлеровы и гамильтоновы графы...................................... 147 
2.1.8. Изоморфизм графов ........................................................... 148 
Контрольные вопросы и задачи .................................................. 150 
2.1.9. Отношения порядка и эквивалентности на графе ............. 157 
Контрольные вопросы ................................................................. 159 
2.2. Транспортные сети .................................................................... 160 
2.2.1. Нахождение максимального потока .................................. 161 
2.2.2. Транспортная задача .......................................................... 165 
2.3. Алгоритмы работы с графами ................................................... 167 
2.3.1. Алгоритмы анализа графов ................................................ 167 
2.3.1.1. Алгоритмы обхода графа ............................................ 167 
2.3.2. Алгоритмы оптимизации ................................................... 169 
2.3.2.1. Поиск кратчайших путей ............................................ 170 
2.3.2.2. Алгоритмы управления проектами ............................ 170 
Контрольные вопросы ................................................................. 172 
2.4. Некоторые практические задачи ............................................... 172 
2.4.1. Поиск гамильтонова цикла ................................................ 172 
2.4.2. Раскраска графа .................................................................. 174 
2.4.3. Задача о кратчайшем пути между двумя 
вершинами графа ......................................................................... 176 
2.4.3.1. Алгоритм поиска кратчайшего пути .......................... 176 
2.4.3.2. Алгоритм Прима ......................................................... 179 
2.4.3.3. Задачи с деревьями...................................................... 181 
2.4.4. Использование алгоритма Дейкстры  
при решении задачи оптимизации передачи сообщений 
в коммуникационных сетях ......................................................... 191 


2.4.5. Система ПЕРТ .................................................................... 196 
Литература ........................................................................................ 200 
Часть 3. Элементы алгебры логики ..................................................... 201 
3.1. Введение в алгебру логики ....................................................... 201 
3.2. Основные функции алгебры логики ......................................... 203 
3.3. Формулы алгебры логики ......................................................... 207 
Контрольные вопросы ................................................................. 209 
3.4. Законы алгебры логики  и следствия из них ............................ 209 
Контрольные вопросы ................................................................. 212 
3.5. Логические функции многих переменных ............................... 212 
3.6. Построение формул алгебры логики по заданной 
таблице истинности ......................................................................... 213 
Контрольные вопросы и упражнения ......................................... 221 
3.7. Некоторые замкнутые классы  (классы Поста). 
Понятие базиса ................................................................................. 222 
Контрольные вопросы и упражнения ......................................... 229 
3.8. Методы минимизации логических функций ............................ 229 
Контрольные вопросы ................................................................. 234 
3.9. Неполностью определенные  логические функции ................. 235 
3.10. Формы представления булевых функций ............................... 235 
3.10.1. Семантические деревья .................................................... 235 
3.10.2. Бинарные диаграммы решений (БДР) ............................. 236 
3.11. Построение логических схем .................................................. 237 
Контрольные вопросы ................................................................. 240 
3.12. Логические конечные автоматы ............................................. 240 
3.12.1. Процессы .......................................................................... 240 
3.12.2. Конечные автоматы .......................................................... 241 
3.12.2.1. Конечные автоматы без памяти 
(комбинационные) ................................................................... 244 
3.12.2.2. Конечные автоматы с памятью 
(последовательностные) .......................................................... 247 
Контрольные вопросы ................................................................. 250 
Литература ........................................................................................ 250 


Введение 
Интерес к дискретной математике вполне понятен. Он объясняется постоянно растущей в последние десятилетия потребностью 
в ней в связи с развитием широких областей её применения, повсеместно курсы дискретной математики входят в программы обучения будущих специалистов по информационным технологиям. 
Содержание изучаемого материала ориентировано на студентов, обучающихся по специальности 23010265, содержит 
большое количество примеров. 
В программе курса предусмотрено изучение элементов теории множеств, основных понятий теории графов, переключательных (логических) функций, схем алгоритмов. Предполагается, 
что студент не испытывает затруднений в понимании текстов 
программ, составленных на языках высокого уровня, в частности 
Object Pascal. 
Дискретная математика имеет широкий спектр приложений в областях, связанных с информационными технологиями 
и компьютерами. Самым первоначальным (ныне редко использующимся) названием компьютера было «электронная цифровая 
вычислительная машина». Слово «цифровая» указывает на принципиально дискретный характер работы данного устройства [5]. 
Дискретная 
математика — 
бурно 
развивающаяся 
в XX веке ветвь математики. Её роль и место определяются в основном тремя факторами: 
• дискретную математику можно рассматривать как теоретические основы компьютерной математики; 
• модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей 
в различных науках, включая химию, биологию, генетику, физику, психологию, экологию и другие; 
• язык дискретной математики чрезвычайно удобен и стал
фактически метаязыком всей современной математики. 
Математика как наука, естественно, от рождения делится 
на дискретную и континуальную математику. Что мы относим 
к континуальной математике? Все, что явно или неявно содержит 
идеи теории пределов и непрерывности. Все остальное — дискретная математика (т. е. арифметика, алгебра, теория множеств 


и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и многое другое). 
Предмет дискретная математика 
Дискретная математика (дискретный анализ, конечная 
математика) — это раздел математики, занимающийся изучением свойств объектов конечного характера. К их числу могут 
быть отнесены конечные группы, конечные графы, некоторые математические модели преобразователей информации, такие как 
конечные автоматы.  
Дискретный анализ — раздел математики, занимающийся изучением свойств структур конечного характера, которые возникают как внутри математики, так и в её приложениях. 
В качестве синонима понятий дискретный анализ и дискретной 
математики иногда употребляют термин «конечная математика». 
В отличие от дискретного анализа классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической или дискретной 
математики как аппаратов исследования связано с задачами, которые ставит перед собой исследователь, и с тем, какую модель 
изучаемого явления он рассматривает — дискретную или непрерывную.  
Дискретность (происходит от латинского слова discretus) — «разделённый, прерывистый». Дискретное изменение какой-либо величины во времени — это изменение, происходящее 
через некоторые промежутки времени (скачками).  
Деление математики на классическую и дискретную в значительной мере условно, поскольку, например, с одной стороны, 
происходит активная циркуляция идей и методов между ними, 
а с другой стороны, часто возникает необходимость исследования моделей, обладающих как дискретными, так и непрерывными свойствами одновременно. Следует отметить, что 
в математике существуют направления, использующие средства 
дискретной математики для изучения непрерывных моделей, 
и наоборот, часто средства и постановки задач классического 
анализа используются при исследовании дискретных структур. 
Это указывает на известное слияние рассматриваемых областей. 


(Возьмите множество всех подмножеств эталонного дискретного 
множества — множества натуральных чисел, и вы получите 
мощность базового для традиционного математического анализа 
множества — множества действительных чисел.) 
Специфика методов и задач дискретного анализа обусловлена, в первую очередь, необходимостью отказа от основополагающих понятий классической математики — предела 
и непрерывности — и в связи с этим тем, для многих задач 
дискретного анализа сильные средства классической математики 
оказываются, как правило, мало приемлемыми. 
Некоторые сведения из истории предмета 
Элементы дискретного анализа возникли в глубокой древности и развивались параллельно с другими разделами математики, в значительной мере являлись их составной частью. 
Типичными для этого периода являлись задачи, связанные со 
свойствами целых чисел и приведшие затем к созданию теории 
чисел. К их числу могут быть отнесены задачи отыскания алгоритмов сложения и умножения натуральных чисел у древних 
египтян (2-е тысячелетие до н. э.), задачи суммирования и задачи о делимости натуральных чисел в пифагорейской школе 
(V–IV век до н. э.). Позже появились элементы комбинаторного 
анализа и дискретной теории вероятности, а в связи с общими 
проблемами теории чисел, алгебры и геометрии (XVIII–
XIX век) возникли важнейшие понятия алгебры, определившие 
её развитие, и имевшие дискретную природу. Стремление 
к строгости математических рассуждений и анализ рабочего инструмента математики — логики — привели к выделению ещё 
одного важного раздела в математике — математической логики (XIX век). Однако наибольшего развития дискретная математика достигла в связи с запросами практики, приведшими 
к появлению новой науки — кибернетики и её теоретической 
части — теоретической кибернетики. (Норберт Винер — основоположник кибернетики.) Теоретическая кибернетика широко 
использует результаты дискретного анализа при решении задач. 
Анализ понятий «вычислимость» и «алгоритм» привели 
к созданию раздела математической логики — теории алгоритмов. 


Экономические задачи, задачи электротехники, равно как 
и внутренние задачи математики, потребовали разработки теории графов. Задачи конструирования и описания работы сложных управленческих систем привели к теории функциональных 
систем. 
Наряду с уже отличительными свойствами дискретная математика имеет ещё ряд особенностей. Вместе с задачами, имеющими 
общий 
математический 
характер, 
важное 
место 
в дискретном анализе занимают задачи построения конкретных 
решающих алгоритмов. 
В некоторых параграфах в качестве нотаций для описания алгоритмов будем использовать некоторый не специфицированный язык программирования, похожий по синтаксису на 
Pascal [5]. 
В программах широко используются математические обозначения, которые являются самоочевидными в некотором контексте. 
Например: 
 
For 
M
x ∈
 do  
)
(x
P
 
 
End for 
 
Читаем, как применение какой-то процедуры P ко всем элементам x, принадлежащим множеству М. 
Оператор Select 
M
m∈
 читаем, как выбор произвольного 
элемента m из множества М. Этот оператор часто используется, 
например, в алгоритмах «перебора». 
Оператор Yield x означает возврат значения x, но при этом 
выполнение функции не прекращается, а продолжается со следующего оператора.  
Обозначение : = — «по определению» или «положим». 
В табл. 1 представлены некоторые общепринятые обозначения. 
В настоящее время популярным становится термин компьютерная математика, введённый американскими исследователями 
Куком Д. и Бейзом Г. Многие разделы дискретной математики 
причислены к компьютерной математике. 


Доступ онлайн
344 ₽
В корзину