Руководство к решению задач по дискретной математике

Министерство сельского хозяйства Российской Федерации

Департамент научно-технологической политики и образования

Федеральное государственное бюджетное 

образовательное учреждение

высшего профессионального образования

«Волгоградский государственный аграрный университет»

Кафедра «Высшая математика»

РУКОВОДСТВО 

К РЕШЕНИЮ ЗАДАЧ 

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Учебно-методическое пособие

Для бакалавров направления подготовки:

09.03.03 «Прикладная информатика»

38.03.05 «Бизнес-информатика»

35.03.06 «Агроинженерия»

13.03.02 «Электроэнергетика и электротехника»

Волгоград

Волгоградский ГАУ

2015

УДК 51
ББК 22.1
Р-85

Рецензент–

кандидат физико-математических наук, доцент кафедры информационных систем и математического моделирования Российской академии народного хозяйства и государственной службы при Президенте 
Российской Федерации (Волгоградский филиал) А.Ю. Савушкин

Р-85
Руководство к решению задач по дискретной математике. 
Для бакалавров по направлению подготовки: 09.03.03 «Прикладная информатика»; 38.03.05 «Бизнес-информатика»; 35.03.06 
«Агроинженерия»; 13.03.02 «Электроэнергетика и электротехника»./ Сост. А.А. Шубович. – Волгоград: ФГБОУ ВПО Волгоградский ГАУ, 2015. – 88 с.

Учебно-методическое пособие предназначено для студентов 

первого курса очной и заочной формы обучения на экологомелиоративном факультете при изучении дисциплины «Дискретная математика», а также для студентов второго курса очной 
формы обучения электроэнергетического факультета при изучении дисциплины «Математика». Построение материала соответствует ФГОС ВПО третьего поколения, а также программе по 
предмету «Дискретная математика» на эколого-мелиоративном 
факультете, и программе по предмету «Математика» на электроэнергетическом факультете. Приведены общепринятые условные 
обозначения, основные понятия и определения по дискретной математике, а также приѐмы и методы решения задач заданий расчѐтно-графической работы по темам: «Элементы теории множеств», «Элементы комбинаторики», «Метод математической индукции», «Отношения и их свойства», «Алгебры», «Многомодульная арифметика», «Графы и действия с ними», «Элементы 
математической логики».

УДК 51

ББК 22.1

Рекомендовано методической комиссией электроэнергетическо-
го факультета Волгоградского ГАУ (протокол № 10 от 17 июня
2015 г.)

©
ФГБОУ ВПО Волгоградский ГАУ, 2015

©
Шубович А.А., 2015

Оглавление

Пояснительная записка.………………………………………………………4
Общепринятые условные обозначения по дискретной математике…….…...6
Элементы теории множеств.…………………………..………………………..7
Математическая индукция.………………………………………………........10
Метод математической индукции ….…………………………………….…..11
Доказательство методом математической индукции.………………….……11
Доказательство 
делимости 
методом 
математической 
индук
ции………………………………………………………………………………11
Доказательство тождеств методом математической индукции.……............12
Доказательство неравенств методом математической индукции…………..13
Элементы математической логики……………………………………………14
Отношения на множестве и их свойства……………………………………..16
Многомодульная арифметика………………………………………………...19
Свойства алгебраических операций…………………………………………..21
Элементы абстрактной алгебры………………………………………………23
Основные определения теории графов……………………………………….25
Основные формулы комбинаторики………………………………………….31
Практические занятия…………………………………………………………32
Занятие 1. Множества и их свойства……….………………………………...32
Занятие 2. Соответствия и их свойства...…………………………………….33
Занятие 3. Отношения и их свойства…………………………………………35
Занятие 4. Операции над множествами...…………………………………….37
Занятие 5. Алгебраические операции и их свойства. Алгебры...…………...39
Занятие 6. Группы, полугруппы, кольца, поля..……………………………..40
Занятие 7. Метод математической индукции………………………………..41
Занятие 8. Элементы многомодульной арифметики………………………..42
Занятие 9. Высказывания. Операции над высказываниями………………...43
Занятие 10. Таблицы истинности высказываний. Равносильность высказываний. Тавтологии……………………………………………………………..44
Занятие 11. Графы. Матрицы графов. Действия с графами………………...45
Занятие 12. Пути и связность в неориентированных графах……………….46
Занятие 13. Пути и связность в ориентированных графах………………….47
Занятие 14. Простейшие комбинаторные задачи……………………………48
Занятие 15. Комбинаторные задачи и уравнения. Реккурентные соотношения………………………………………………………………………………49
Контрольные вопросы по теме «Абстрактная алгебра»…………………….50
Примеры интернет-заданий по дискретной математике……………………53
Контрольная (расчѐтно-графическая) работа……………………………......56
Методические указания по выполнению контрольной работы…………….78
Методические указания по выполнению расчѐтно-графической работы.…79
Экзаменационные билеты по дисциплине «Дискретная математика»……..82
Список литературы………………..………………………………………..….87

Пояснительная записка

Для подготовки высокопрофессиональных специалистов народного 

хозяйства в 2009 году впервые осуществлен прием абитуриентов в Волго
градский государственный аграрный университет в бакалавриат по направ
лению подготовки «Прикладная информатика». Объясняется это тем, что 

особенно высокая потребность существует не просто в программистах, вы
полняющих по сути роль кодировщиков, а в специалистах-информатиках, 

глубоко знающих бухгалтерский учет, налогообложение, банковское дело, 

основы бизнеса, менеджмент, маркетинг и способных к разработке инфор
мационных систем для экономики.

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

и интегрирующие функции во взаимодействии заказчиков автоматизации 

обработки информации и инженерного персонала, решающего технические 

задачи.

Особое место среди дисциплин учебного плана по направлению под
готовки 09.03.03 «Прикладная информатика» профиль «Экономика» зани
мает «Дискретная математика». Дисциплина «Дискретная математика» от
носится к базовой части математического и естественнонаучного цикла.

Для освоения дисциплины обучающиеся используют знания, умения, 

сформированные в ходе изучения дисциплин базовой части математическо
го и естественнонаучного цикла: «Математика». Трудоемкость дисциплины 

составляет 4 зачетных единицы, формой контроля является экзамен.

Процесс изучения дисциплины направлен на формирование элемен
тов следующих компетенций в соответствии с ФГОС ВПО по данному на
правлению: 

- способность использовать основные законы естественнонаучных дисцип
лин в профессиональной деятельности и эксплуатировать современное 

электронное оборудование и информационно-коммуникационные техноло
гии в соответствии с целями образовательной программы бакалавра (ПК-3);

- способность применять к решению прикладных задач базовые алгоритмы 

обработки информации, выполнять оценку сложности алгоритмов, про
граммировать и тестировать программы (ПК-10);

- способность применять системный подход и математические методы в 

формализации решения прикладных задач (ПК-21).

В результате изучения дисциплины студент должен:

а) знать: основные понятия теории множеств, математической логики, ал
гебры высказываний, теории графов, теории автоматов, теории алгоритмов, 

основные методы оценки сложности алгоритмов, основные математические 

методы формализации решения прикладных задач;

б) уметь: применять алгоритмы к решению прикладных задач, вычислять 

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

в) владеть: комбинаторным, теоретико-множественным и вероятностным 

подходами к постановке и решению задач, навыками расчѐта сложности ал
горитмов, навыками моделирования прикладных задач методами дискрет
ной математики.

Общепринятые условные обозначения по дискретной математике

Символ
Расшифровка

𝑁
 1; 2; 3; …  – множество натуральных чисел

𝜔, 𝑍0
 0; 1; 2; 3; …  – множество целых неотрицательных чисел

𝑍
 0; ±1; ±2; ±3 …  – множество целых чисел

𝑄
 𝑝 𝑞
 ;  𝑝, 𝑞 ∈ 𝑍, 𝑞 ≠ 0 – множество рациональных чисел

𝑅
множество вещественных чисел

𝐶
множество комплексных чисел

𝑈, 𝐼
универсальное множество, универсум

 𝐴 
мощность множества 𝐴

𝑖𝑛𝑓
точная нижняя грань

𝑠𝑢𝑝
точная верхняя грань

∥
параллельность

⊥
перпендикулярность

∈
квантор принадлежности, читается «принадлежит»

∉
«не принадлежит»

∀
квантор всеобщности, читается «любой, всякий, для любого, всякого»

∃
квантор существования, читается «существует»

∄
«не существует»

!
квантор единственности, читается «единственный»

∃!
существует и единственный

⊐
пусть

:
такой, что

∅
пустое множество

∞
бесконечность

⊂
включение

°
произведение бинарных отношений

~;⇔;↔
эквивалентность

∪
объединение

∩
пересечение

\
разность

∆
симметрическая разность

⋁
логическое сложение, логическое «или», читается «дизъюнкция»

∧
логическое умножение, логическое «и», читается «конъюнкция»

→;⇒
импликация, читается «если первое, то второе»

Σ
сигнатура

𝔄; 𝔅
алгебраические системы

𝑎 𝑚𝑜𝑑 𝛽 
остаток от деления числа 𝑎 на число 𝛽

⊕
кольцевая сумма, логическое сложение, сложение по модулю 2, исключающее «или»

×
декартово произведение


отрицание, читается «не»

↓
стрелка Пирса, читается «ни первое, ни второе»

 
 
штрих Шеффера

Элементы теории множеств

Объекты любой природы, составляющие множество, называют его 

элементами. Отношение между множеством и его элементами, выражают и 
при помощи слова принадлежит.

Множество ∅, не содержащее ни одного элемента, называется пустым. 

Существует лишь одно пустое множество.

Два множества 𝑋 и 𝑌 называются равными 𝑋 = 𝑌, если каждый эле
мент 𝑥 первого множества является одновременно элементом 𝑦 второго, и наоборот. Равенство возможно тогда и только тогда, когда ∀𝑥 ∈ 𝑌 и ∀𝑦 ∈ 𝑋.

Множества могут содержать как конечное число элементов, так и бес
конечное. Множество может содержать и один элемент. Элементами множества могут быть множества.

Пусть каждый элемент 𝑦 множества 𝑌 является элементом множества 

𝑋, т.е. ∀𝑦 ∈ 𝑋. Тогда множество 𝑌 называется подмножеством множества 
𝑋 и записывается 𝑌 ⊂ 𝑋. Это означает, что множество 𝑌 является частью 
множества 𝑋. 

Для ∀𝑋 множество ∅ ∈ 𝑋.
Два множества 𝑋 = 𝑌 тогда и только тогда, когда 𝑋 ⊂ 𝑌 и 𝑌 ⊂ 𝑋.
Подмножество 𝑌 множества 𝑋 называется собственным (истинным) 

подмножеством множества 𝑋, если существует элемент 𝑥′ ∈ 𝑋, такой, что 
𝑥′ ∉ 𝑌.

Краткая запись: ∀𝑦 ∈ 𝑌: 𝑦 ∈ 𝑋
и ∃𝑥′ ∈ 𝑋: 

𝑥′ ∉ 𝑌.
Если 𝑌 является собственным подмножеством 
множества 𝑋, получается ситуация на рисунке. 
Такие рисунки называются диаграммами Эйлера-Венна.

Два множества 𝑋 и 𝑌 являются эквива
лентными 𝑋~𝑌, если между их элементами 
можно установить однозначное соответствие 
𝑥 ↔ 𝑦. Этот значит, что из элементов множеств 𝑋 и 𝑌 можно сконструировать пары 

 𝑥, 𝑦 , такие, что для каждого элемента 𝑥 ∈ 𝑋 существует один и только 
один элемент 𝑦 ∈ 𝑌, и наоборот.

Множество называется конечным, если оно эквивалентно отрезку  

натурального ряда чисел. В противном случае оно называется бесконечным. Множество 𝑋 называется счетным, если оно эквивалентно натуральному ряду чисел, т.е. элементы счетного множества можно пронумеровать. 
Счетное множество можно записать в виде 𝑋 =  𝑥1, 𝑥2, 𝑥3, …  . 

Объединением (суммой) двух множеств 𝐴 и 𝐵 называется множест
во 𝐶 = 𝐴 ∪ 𝐵, элементы которого принадлежат множеству 𝐴 или множеству 
𝐵.

𝐶 = 𝐴 ∪ 𝐵 =  𝑥: 𝑥 ∈ 𝐴⋁𝑥 ∈ 𝐵 .

𝑋

𝑌

𝑥′

В объединение входят все элементы, принадлежащие хотя бы одному из 
множеств.

Пересечением (произведением) двух множеств 𝐴 и 𝐵 называется 

множество 𝐷 = 𝐴 ∩ 𝐵, элементы которого принадлежат множеству 𝐴 и 𝐵
одновременно.

𝐷 = 𝐴 ∩ 𝐵 =  𝑥: 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵 .

Пересечение образовано всеми общими элементами данных множеств.

Разностью двух множеств 𝐴 и 𝐵 называется множество 𝐶 = 𝐴\𝐵, со
стоящее из элементов, принадлежащих множеству 𝐴, но не принадлежащих 
𝐵.

𝐶 = 𝐴\𝐵 =  𝑥: 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵 .

Из множества 𝐴 достаточно удалить общие элементы множеств 𝐴 и 𝐵, т.е. 
все элементы множества 𝐴 ∩ 𝐵, чтобы получить разность 𝐴\𝐵.

Симметрической разностью 𝐴𝛥𝐵 множеств 𝐴 и 𝐵 называется объе
динение множества 𝐴\𝐵 и множества 𝐵\𝐴, т.е.

𝐴𝛥𝐵 =  𝐴\𝐵 ∪  𝐵\𝐴 =  𝐵\𝐴 ∪  𝐴\𝐵 .

Пример 1. Доказать тождество 𝐴 ∪  𝐵\𝐶 =  𝐴 ∪ 𝐵 \ 𝐶\𝐴 ,

𝐴, 𝐵 ≠ ∅, используя диаграммы Эйлера-Венна.
Доказательство. Каждое множество изображается в виде круга Эйлера и 

над множествами выполняются указанные операции.

Последовательно изображается множество 𝐴 ∪  𝐵\𝐶 :

 𝐵\𝐶 

𝐴 ∪  𝐵\𝐶 

Последовательно изображается множество  𝐴 ∪ 𝐵 \ 𝐶\𝐴 правой части ра
венства.

𝐴 ∪ 𝐵
𝐶\𝐴
 𝐴 ∪ 𝐵 \ 𝐶\𝐴 

Результирующие множества 𝐴 ∪  𝐵\𝐶  и  𝐴 ∪ 𝐵 \ 𝐶\𝐴  совпадают, что оз
начает, что тождество 𝐴 ∪  𝐵\𝐶 =  𝐴 ∪ 𝐵 \ 𝐶\𝐴 , 𝐴, 𝐵 ≠ ∅ верно, что и 

требовалось доказать.

Пример 2. Доказать, что множества точек двух окружностей эквивалентны.

Доказательство. Пусть даны два множества 𝑀1 =  𝑂1, 𝑟 , 𝑀2 =  𝑂2, 𝑅 , оп
ределяющие две окружности с центрами в точках 𝑂1, 𝑂2 и радиусами 𝑟, 𝑅

соответственно. Пусть для определѐнности, 𝑟 ≠ 𝑅, 𝑟 < 𝑅. Отметим на 

плоскости произвольную точку 𝑂, и параллельным переносом изобразим 

данные окружности с общим центром. Во множестве 𝑀2 проведѐм радиус 

𝑂𝐵. Отрезок 𝑂𝐵 = 𝑅 пересечѐт множество 𝑀1 в точке 𝐴. Тогда между эле
ментами 𝐴 и 𝐵 множеств 𝑀1 и 𝑀2 будет установлено однозначное соответ
ствие 𝐴 ↔ 𝐵. Это доказывает, что 𝑀1~𝑀2.

Пример 3. Доказать утверждение:  0,  1  ~ 0, +∞ .

Доказательство. Требуется подобрать такую функцию, у которой область 

определения 𝐷 𝑦 =  0,  1  , а множество значений есть множество всех не
отрицательных чисел 𝐸 𝑦 =  0, +∞ . Рассмотрим функцию 𝑦 =  

1−𝑥

𝑥 . 

𝑂1
𝑂2

𝑂
𝑟
𝑅

𝐴

𝐵