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

Министерство сельского хозяйства Российской Федерации 
Департамент научно-технологической политики и образования 
Федеральное государственное бюджетное  
образовательное учреждение 
высшего профессионального образования 
«Волгоградский государственный аграрный университет» 
 
Кафедра «Высшая математика» 
 
 
 
 
 
 
РУКОВОДСТВО  
К РЕШЕНИЮ ЗАДАЧ  
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ 
  
Учебно-методическое пособие 
 
Для бакалавров направления подготовки: 
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 
𝑂 
𝑟 
𝑅 
𝐴 
𝐵