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

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

Покупка
Основная коллекция
Артикул: 640605.01.99
Учебно-методическое пособие предназначено для студентов первого курса очной и заочной формы обучения на эколого-мелиоративном факультете при изучении дисциплины «Дискрет-ная математика», а также для студентов второго курса очной формы обучения электроэнергетического факультета при изуче-нии дисциплины «Математика». Построение материала соответ-ствует ФГОС ВПО третьего поколения, а также программе по предмету «Дискретная математика» на эколого-мелиоративном факультете, и программе по предмету «Математика» на электро-энергетическом факультете. Приведены общепринятые условные обозначения, основные понятия и определения по дискретной ма-тематике, а также приѐмы и методы решения задач заданий рас-чѐтно-графической работы по темам: «Элементы теории мно-жеств», «Элементы комбинаторики», «Метод математической ин-дукции», «Отношения и их свойства», «Алгебры», «Многомо-дульная арифметика», «Графы и действия с ними», «Элементы математической логики».
Руководство к решению задач по дискретной математике / Шубович А.А. - Волгоград:Волгоградский ГАУ, 2015. - 88 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/615250 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Министерство сельского хозяйства Российской Федерации

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

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

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

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

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

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

РУКОВОДСТВО 

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

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

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

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

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

𝑂
𝑟
𝑅

𝐴

𝐵

Область определения функции можно получить в результате решения нера
венства 

1−𝑥

𝑥 ≥ 0. Нули функции 𝑓 𝑥 =

1−𝑥

𝑥
находятся из равенства 1 − 𝑥 =

0, откуда 𝑥 = 1. Функция не существует при 𝑥 = 0, следовательно, соглас
но методу интервалов, 𝑓 𝑥 ≥ 0 при 𝑥 ∈  0,  1  . 

Множество значений функции определяется неравенством 𝑦 ≥ 0, или 

𝑦 ∈  0, +∞ . 

Значит  0,  1  ~ 0, +∞ , что и требовалось доказать.

Математическая индукция 

В основе всякого научного исследования, в том числе и математиче
ского, лежат дедуктивный и индуктивный подходы. 

Дедукция (от латинского слова «deductio» - выведение) – переход от 

общего к частному, индукция (от латинского «inductio» - наведение) – вид 
обобщений, связанных с предвосхищением результатов наблюдений и экспериментов на основе прошлых лет. 

В математике дедуктивный метод мы применяем, например, в рас
суждениях такого типа: данная фигура – прямоугольник; у каждого прямоугольника диагонали равны, следовательно, и у данного прямоугольника 
диагонали равны. 

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

данных наблюдений или эксперимента. Многократность повторения какого-либо факта приводит к индуктивному обобщению. Индуктивный подход люди, часто сами того не замечая, применяют почти во всех сферах 
деятельности. Так, например, рассуждения, с помощью которых суд приходит к решению, можно сравнить с индуктивными рассуждениями. Такие 
сравнения уже предполагались и обсуждались авторитетами по судебной 
практике. На основании некоторых известных фактов выдвигается какоелибо предположение (гипотеза). Если все вновь выявленные факты не противоречат этому предположению и являются следствием его, то это предположение становится более правдоподобным. Конечно, для практики повседневного и научного мышления характерны обобщения на основе исследования не всех случаев, а только некоторых, поскольку число всех случаев, как правило, практически необозримо. Такие обобщения называются 
неполной индукцией.

𝑥
0
1

−
+
−
𝑓 𝑥 

Если же общее утверждение удается доказать во всех возможных 

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

Метод математической индукции

Многие интересные математические утверждения охватывают беско
нечное число частных случаев, а провести проверку для бесконечного числа случаев человек не может. 

Во многих случаях выход из такого рода затруднений заключается в 

обращении к особому методу рассуждений, называемому методом математической индукции. Доказательства этим методом опираются на следующую аксиому, называемой аксиомой индукции, пятой из аксиом Пеано, 
которые определяют натуральные числа.

Аксиома индукции. Если известно, что некоторое утверждение вер
но для 1, и из предположения, что утверждение верно для некоторого 𝑛, 
вытекает его справедливость для 𝑛 + 1, то это утверждение верно для всех 
натуральных чисел.

Доказательство методом математической индукции

Утверждение, зависящее от натурального числа 𝑛, справедливо для 

любого 𝑛, если выполнены условия:
1) Проверяется справедливость утверждения при 𝑛 = 1.
2) Предполагается, что утверждение справедливо при 𝑛 = 𝑘, где 𝑘 ∈ 𝑁.
3) Доказывается справедливость утверждения при 𝑛 = 𝑘 + 1. На основании 
метода математической индукции делается вывод о справедливости утверждения при любом 𝑛 ∈ 𝑁.

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

Доказательство делимости методом математической индукции

Пример 1. Доказать, что при любых 𝑛 ∈ 𝑁 число 𝑛2 − 𝑛 четное.
Доказательство. 1) При 𝑛 = 1 получим 12 − 1 = 0 - четное число.

2) Предположим, что при 𝑛 = 𝑘, где 𝑘 ∈ 𝑁 число 𝑘2 − 𝑘 четное.
3) Докажем, что при 𝑛 = 𝑘 + 1 число  𝑘 + 1 2 −  𝑘 + 1 четное.
Преобразуем выражение