Дискретная математика. В 2 ч. Ч. 1

Министерство науки и высшего образования Российской Федерации 
Департамент координации деятельности организаций  
в сфере сельскохозяйственных наук 
Федеральное государственное бюджетное образовательное  
учреждение высшего образования 
«Волгоградский государственный аграрный университет» 
 
Электроэнергетический факультет 
 
Кафедра «Высшая математика» 
 
 
 
Т. Р. Ищанов 
 
 
 
ДИСКРЕТНАЯ МАТЕМАТИКА 
 
Учебное пособие 
 
Часть 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Волгоград 
Волгоградский ГАУ 
2024 
 
1 

УДК 517 
ББК 22.1 
И-98 
 
Рецензенты: 
кандидат физико-математических наук, доцент кафедры «Информационная безопасность» ФГАОУ ВО «Волгоградский государственный 
университет» Д. П. Радченко; кандидат педагогических наук, доцент 
кафедры «Высшая математика» ФГБОУ ВО Волгоградский ГАУ       
И. В. Кадина 
 
 
Ищанов, Тлек Рахметолович 
И-98  Дискретная математика: учебное пособие / Т. Р. Ищанов. – Волгоград: ФГБОУ ВО Волгоградский ГАУ, 2024. – Часть 1. – 148 с. 
 
 
ISBN 978-5-4479-0448-7 
 
 
Пособие подробно описывает основные концепции и методы 
дискретной математики, обеспечивая понятное и систематизированное изложение материала. Особое внимание уделяется трѐм ключевым 
разделам: теории множеств, математической логике и комбинаторике. 
Каждый раздел включает в себя обзор основных понятий, примеры и 
задачи для самостоятельного решения. 
Предназначено для студентов, обучающихся по направлению 
подготовки 09.03.03 Прикладная информатика, всех форм обучения. 
 
УДК 517 
ББК 22.1 
 
Рекомендовано методической комиссией Электроэнергетического факультета ФГБОУ ВО Волгоградский ГАУ (протокол № 8 от 
16 апреля 2024 г.). 
 
 
ISBN 978-5-4479-0448-7 
© ФГБОУ ВО Волгоградский 
ГАУ, 2024  
© Ищанов Т. Р., 2024 
 
 
2 

ВВЕДЕНИЕ 
 
Учебное пособие по дискретной математике является важным 
ресурсом для студентов и преподавателей, занимающихся изучением 
этой фундаментальной области математики. Дискретная математика 
охватывает широкий спектр тем, начиная от теории множеств и математической логики, и заканчивая комбинаторикой, графами и алгоритмами. 
В данном пособии особое внимание уделяется трем разделам. 
1. Теория множеств. В этом разделе рассматриваются основные 
концепции теории множеств, включая операции над множествами, 
свойства отношений между множествами и декартово произведение. 
2. Математическая логика. Здесь представлены основные понятия математической логики, логические операции, а также их применения в решении задач и построении математических моделей. 
3. Комбинаторика. Этот раздел посвящен изучению комбинаторных структур, таких как перестановки, сочетания, размещения, а 
также рассмотрены треугольник Паскаля, формула бинома Ньютона и 
полиномиальная формула. 
Пособие разработано с учетом потребностей студентов и преподавателей, стремящихся углубленно изучить дискретную математику 
и ее применение в различных областях науки и техники. Оно предлагает четкие и подробные объяснения основных концепций, многочисленные примеры и задачи для самостоятельного решения, что делает 
его незаменимым ресурсом как для учебы, так и для научной работы в 
области дискретной математики. 
 
 
3 

ТЕОРИЯ МНОЖЕСТВ И ОТНОШЕНИЙ 
 
Теория множеств – это раздел математики, который изучает 
сущность, свойства и отношения множеств. В основе этой теории лежат базовые понятия множества, элемента множества, а также операции, которые можно выполнять над множествами, такие как объединение, пересечение, разность и дополнение. Теория множеств также 
занимается изучением отношений между множествами: включение, 
равенство множеств, подмножества и декартово произведение. 
Важной частью теории множеств является формализация математических концепций с помощью множеств и логических операций. 
Это позволяет строить математические теории и доказательства на 
более строгих основаниях, обеспечивая точность и четкость в математическом рассуждении. 
Теория множеств имеет широкие приложения в различных областях математики, а также в других науках, таких как информатика, 
физика, экономика и теория вероятностей. 
 
1.1 Основные определения теории множеств 
 
Первоначальные идеи о множествах встречаются уже в работах 
древних математиков, таких как Пифагор, Евклид и Архимед. Однако, 
формализация и развитие теории множеств как самостоятельной области математики произошло в XIX веке. 
Считается, что основоположником теории множеств является 
немецкий математик Георг Кантор. Он ввел основные понятия и аксиомы теории множеств и разработал ее математические основы в своих 
работах в конце XIX – начале XX века. В частности, Кантор ввел понятия мощности множества, бесконечности и различных типов бесконечностей. 
Таким образом, Георг Кантор считается первым, кто дал формальное и математически строгое определение множеству и разработал теорию множеств как отдельную область математики. 
Георг Кантор (1845-1918): «Множество есть многое, мыслимое 
нами как единое».  
Множество – одно из фундаментальных понятий математики.  
Множество – это совокупность объектов любой природы, которые объединены на основании какого-то одного общего свойства, 
признака, или их совокупности.  
Входящие во множество объекты, называются элементами множества. 
 
 
4 

Примеры:  
• множество студентов учебной группы;  
• множество прямых, проходящих через данную точку;  
• множество решений системы уравнений.  
 
Примеры математических множеств 
1. Множество натуральных чисел:  
 
𝑵= *1,2,3,4,5, … +. 
 
2. Множество целых чисел: 
 
𝒁= *… , −3, −2, −1,0,1,2,3, … +. 
 
3. Множество рациональных чисел: 
 
𝑸= { 𝑎
𝑏∣
∣
∣𝑎∈𝑍, 𝑏∈𝑍, 𝑏≠0 }. 
 
4. Множество вещественных чисел: 
 
𝑹= все действительные числа. 
 
5. Множество комплексных чисел: 
 
𝑪= *𝑎+ 𝑏𝑖∣𝑎, 𝑏∈𝑅, 𝑖2 = −1+. 
 
6. Множество четных натуральных чисел: 
 
𝟐𝑵 = *2, 4, 6, 8, 10, … +. 
 
7. Множество квадратов натуральных чисел: 
 
   𝑵𝟐 = *1, 4, 9, 16, 25, … +. 
 
8. Множество простых чисел: 
 
𝑷 = *2, 3, 5, 7, 11, … +. 
 
9. Множество дробей с числителем и знаменателем от 1 до 10: 
 
𝑫= { 𝑎
𝑏∣
∣
∣𝑎, 𝑏∈*1,2, … ,10+ }. 
 
Множества принято обозначать большими латинскими или греческими буквами, элементы множества – маленькими буквами.  
Запись 𝑎∈   означает, что элемент 𝑎 принадлежит множеству  .  
Запись 𝛾∉ , означает, что элемент 𝛾 не принадлежит множеству  .  
5 

 
Рисунок 1.1.1 – Множество и его элементы 
 
Способы задания множества. 
1. Перечисление всех элементов множества. 
Определим множество 𝐶 перечислением всех его элементов: 
𝐶= {3,    7,   9}. Данная запись позволяет нам описать множество 𝐶, 
которое состоит из трех элементов: 3, 7, 9.  
Обратите на форму записи, все элементы множества перечисляются в фигурных скобках, через запятую.  
Данная форма записи применима для задания конечных множеств, в остальных случаях удобно описывать множества с помощью 
правила, которое позволит определить принадлежность элемента к 
конкретному множеству. 
2. Образующее правило (характеристическое свойство). 
Описание свойств, общих для всех элементов этого множества, 
и только этого множества. Это свойство называется характеристическим свойством, а такой способ задания множества описанием. Таким 
образом, можно задавать как конечные, так и бесконечные множества. 
Соответствующая запись имеет вид: 𝑀= {𝑥 | 𝑅(𝑥)} (множество 
М состоит из таких элементов 𝑥, для которых образующее множество 
правило 𝑅(𝑥) истинно).  
Пример. Запись вида 𝑀= {𝑥 | 𝑥≥3} означает, что множество 
состоит из элементов, принадлежащих числовому промежутку 
𝑥∈,3; +∞).  
Порядок элементов во множестве несущественен. Множества 
{k, t, r} и {t, k, r} одинаковы. 
Замечание. Элемент а и множество {а} – это не одно и то же, 
они представляют разные математические концепции. Первое – это 
объект, обозначенный а, второе – это множество, состоящее из един6 

ственного элемента а. Следовательно, верное утверждение – "элемент 
a принадлежит множеству {a}". С другой стороны, утверждение 
"множество {a} принадлежит элементу a" является ложным. 
Количество элементов во множестве называется мощностью или 
кардинальным числом. Например, мощность множества  = *𝑑, 𝑚, 𝑐+ равна трем, записывается следующим образом: | | = 3. 
Множество, которое не содержит ни одного элемента, называется пустым и обозначается ∅. Мощность пустого множества ∅ равна    
0: |∅| = 0. Введение понятия пустого множества обосновано. Допустим, у нас есть множество, которое изначально содержало элементы. 
В определенных условиях это множество может оказаться пустым, то 
есть лишенным элементов. Однако важно отметить, что отсутствие 
элементов во множестве не означает отрицание самого множества как 
математического объекта. Пустое множество сохраняет свою сущность, определяемую основными правилами формирования множеств, 
даже если временно лишено конкретных элементов. 
Введение понятия пустого множества является важным шагом в 
теории множеств.  
Понятие пустого множества важно по нескольким причинам. 
1. Универсальность. Пустое множество является подмножеством любого множества. Это универсальное свойство делает пустое 
множество фундаментальным в теории множеств. 
2. Определение через правило. Пустое множество можно определить через отсутствие элементов, удовлетворяющих определенному 
правилу или свойству. Например, множество всех синих роз в комнате, где нет синих роз, будет пустым, но само правило формирования 
множества (наличие синих роз) остается в силе. 
3. Отличие от "ничего". Важно понимать, что пустое множество 
не равно "ничему" или "отсутствию множества". Это скорее множество, в котором просто нет элементов, но само по себе оно существует 
как объект в теории множеств. 
4. Основа для определений и доказательств. Пустое множество 
используется в математике для формулировки определений, теорем и 
доказательств. Например, пересечение любого количества множеств 
можно определить как множество, содержащее только те элементы, 
которые принадлежат всем этим множествам. Если множества не 
имеют общих элементов, их пересечение будет пустым множеством. 
Таким образом, пустое множество – это не просто абстракция 
или математический курьѐз, а важный и необходимый элемент структуры теории множеств. 
 
 
7 

Пример. Рассмотрим пример образования пустого множества на 
основе изменения состава. Предположим, у нас есть множество работников в компании, имеющих доступ к определенному проекту. В 
процессе времени некоторые сотрудники могут получить повышение 
и переместиться на другие проекты, а другие могут покинуть компанию. Изначально это множество может быть наполнено разными работниками, имеющими доступ к проекту. С течением времени, в результате повышений, перемещений и увольнений, множество может 
стать пустым. Тем не менее, само понятие множества работников с 
доступом к проекту сохраняет свой смысл и структуру, и в будущем 
новые сотрудники могут быть добавлены к этому множеству, если им 
будет предоставлен доступ к проекту. 
Замечание. Мощность множества, элементом которого является 
пустое множество, равна единице: если 𝐿= *∅+,  тогда |𝐿| = |*∅+| = 1. 
Множества равномощны, если их мощности равны, т. е. множества содержат одинаковое количество элементов. Например, множества 𝐹= *1, 2, 3+ и 𝐿= *𝑎, 𝑏, 𝑐+ равномощны. 
Упражнение. Равномощны ли множества 𝐹 и 𝐿:  
𝐹= {*клавиатура, монитор, ноутбук+, *книга, тетрадь+,
*авторучка, карандаш+};  𝐿= *𝑎, 𝑏, 𝑐+. 
Если два множества равномощны, это не означает, что множества равны. Равными множества будут только в том случае, если они 
будут содержать одинаковые элементы. 
Определение. Множество называется конечным, если оно состоит из конечного числа элементов. 
Пример. 𝐴 = *1, 2, 3, 4, 5+ – конечное множество.  
Множество называется бесконечным, если оно содержит бесконечное количество элементов. 
Пример. 𝐵 = *1, 2, 3, 4, … + – бесконечное множество натуральных чисел. 
Множество называется счетным, если все его элементы можно 
пронумеровать натуральными числами (каждому элементу поставить 
в соответствие натуральное число; элементы можно упорядочить в 
последовательность, которая соответствует натуральным числам).  
Пример. Множество всех целых чисел Z – счетное, потому что его 
элементы можно упорядочить в последовательность: 0, 1, -1, 2, -2, 3, -3, … . 
Множество называется несчетным, если оно не является счетным. 
Пример. Множество всех действительных чисел R – несчетное. 
Невозможно упорядочить все действительные числа в последовательность, соответствующую натуральным числам, потому что мощность 
множества действительных чисел больше мощности множества натуральных чисел. 
8 

Множество 𝐴 является подмножеством множества 𝐵: 𝐴⊆𝐵, если каждый элемент множества 𝐴 (𝑎𝑖𝜖𝐴), также принадлежит и множеству 𝐵, (𝑎𝑖𝜖𝐵). Если во множестве 𝐵 найдется хотя бы один элемент 
𝑥𝑖, который не принадлежит 𝐴, (𝑥𝑖∈𝐵 и 𝑥𝑖∉𝐴), то множество 𝐴 
называется собственным подмножеством множества 𝐵, 𝐴⊂𝐵. Иными 
словами, если число элементов подмножества 𝐴 меньше числа элементов множества 𝐵, то 𝐴 есть собственное подмножество 𝐵. 
Свойства множеств. 
1. Пустое множество *∅+ всегда является подмножеством любого другого множества. 
2. Любое множество X является подмножеством самого себя: 
𝑋⊆𝑋. 
3. Множества 𝐴 и 𝐵 равны, если являются подмножествами друг 
друга: 𝐴⊆𝐵 и 𝐵⊆𝐴. 
4. Если множество X есть подмножество некоторого множества 
Ү, а множество Y есть подмножество некоторого множества Z, то 
множество X обязательно является подмножеством множества Z: если 
𝑋⊆𝑌, 𝑌⊆𝑍, то 𝑋⊆𝑍. 
Для каждого множества 𝑀 можно построить новое множество, 
элементами которого будут являться все подмножества 𝑀 и только 
они. Тогда множество 𝑀 называют универсальным множеством (универсумом), а множество всех его подмножеств – булеаном. Универсальное множество будем обозначать символом 𝑈. 
Множество всех подмножеств некоторого множества 𝑀, включая пустое подмножество и само множество 𝑀, называется булеаном 
множества и обозначается 𝐵(𝑀). 
Пример. Пусть дано универсальное множество 𝑈= *3, 7, 9+, тогда булеан будет иметь вид: 𝐵(𝑈) = {*∅+, *3+, *7+, *9+, *3,7+, *3,9+,
*7,9+, *3, 7, 9+}. 
Если мощность универсума равна 𝑚, то мощность его булеана 
рассчитывается по формуле |𝐵(𝑈)| = 2𝑚. 
В нашем примере мощность булеана на основании множества из 
трех разных элементов будет равна 8. 
 
1.2 Множества и операции над ними 
 
Для визуализации множеств и отношений между ними будем 
использовать такой инструмент, как круги диаграммы Эйлера-Венна. 
Диаграммы Эйлера-Венна – это графические методы визуализации 
множеств и их взаимосвязей, предложенные Джоном Венном в      
1880-х годах и независимо от него Леонардом Эйлером в XVIII веке. 
9 

Диаграммы Эйлера-Венна – мощный инструмент для визуализации множеств и их отношений, делая абстрактные концепции более 
доступными и понятными. 
Диаграммы Эйлера-Венна широко используются для иллюстрации 
логических отношений между множествами, операций над множествами 
(таких как объединение, пересечение, разность) и других множественных концепций. Они предоставляют интуитивное и наглядное представление сложных структур данных и помогают в понимании абстрактных 
математических концепций для широкой аудитории. 
Над множествами могут предприниматься различные операции по 
их преобразованию. Основные операции над множествами по аналогии 
с операциями над числами получили названия алгебраических. Операции над множествами опишем алгебраической записью и изобразим 
графически с помощью диаграмм Эйлера-Венна: универсальное множество (U) образует прямоугольник, внутри которого находятся круги. 
 
 
 
Рисунок 1.2.1 – Диаграмма Эйлера-Венна 
 
Объединение множеств. Объединением множеств А и В называется новое множество, обозначаемое как 𝐴∪𝐵, все элементы которого являются либо элементами множества А, либо элементами множества В:  
𝐴∪𝐵= *𝑥 | 𝑥∈𝐴  или  𝑥∈𝐵+. 
 
 
 
Рисунок 1.2.2 – Объединение множеств 
10