1535
.pdfФГБОУ ВО «Воронежский государственный технический университет»
А.Н. Шелковой Н.А. Ююкин
ДИСКРЕТНАЯ МАТЕМАТИКА
В
ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ
Утверждено Редакционно-издательским советом университета в качестве учебного пособия
Воронеж 2016
УДК 519.17
Шелковой А.Н. Дискретная математика в информационных технологиях: учеб. пособие [Электронный ресурс]. – Электрон. текстовые, граф. данные (736 Кб) / А.Н. Шелковой, Н.А. Ююкин. – Воронеж: ФГБОУ ВО «Воронежский государственный технический университет», 2016. – 1 электрон. опт. диск (CD-ROM). – Систем. требования: ПК 500 и
выше ; 256 Мб ОЗУ ; Windows XP ; Adobe Acrobat ; 1024x768
;CD-ROM ; мышь. – Загл. с экрана.
Впособии рассмотрены вопросы теории множеств, комбинаторики, отношений на множествах, графы и рекуррентные уравнения.
Издание соответствует требованиям Федерального государственного образовательного стандарта высшего образования по направлению 09.03.02 «Информационные системы и технологии», профили «Информационные системы и технологии в машиностроении», «Информационные технологии в дизайне», дисциплине «Дискретная математика».
Табл. 11. Ил. 30. Библиогр.: 10 назв.
Рецензенты: кафедра высшей математики Воронежского института МВД России (начальник кафедры д-р физ.- мат. наук, проф. В.В. Меньших); канд. физ.-мат. наук, доц.
А.В. Ряжских
©Шелковой А.Н., Ююкин Н.А., 2016
©Оформление. ФГБОУ ВО «Воронежский государственный технический университет», 2016
ВВЕДЕНИЕ
Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися на специалиста по направлению 09.03.02 «Информационные системы и технологии», профили «Информационные системы
итехнологии в машиностроении», «Информационные технологии в дизайне».
Дисциплина “Дискретная математика” обеспечивает приобретение знаний и умений в соответствии с Государственным, общеобразовательным стандартом, и при этом содействует повышению уровня образования, формированию мировоззрения и развитию логического мышления.
Дискретная математика является эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Она используется при моделировании систем управления, исследовании автоматов и логических сетей, в системном анализе, автоматизированном управлении производством, при разработке вычислительных
иинформационных сетей и т.п.
Вучебном пособии излагаются основы, базовые методы и алгоритмы теории. В нём нашли отражение основные понятия теории множеств; простейшие комбинаторные комбинации и их объединения; отношения, отображения и алгебраические операции на множествах; неориентированные, ориентированные, эйлеровы, гамильтоновы и планарные графы; потоки в сетях; рекуррентные уравнения и методы их решения. Здесь также отрабатываются практические навыки по использованию вышеприведенных понятий.
Целью курса является формирование у студентов теоретических знаний, практических умений и навыков в области моделирования процессов и явлений в естествознании и технике, с возможностью употребления математических символов для выражения количественных и качественных отношений объектов, необходимых для выполнения служеб-
3
ной деятельности в области разработки информационных систем на высоком профессиональном уровне.
Достижению данной цели служат следующие задачи: изучить максимально широкий круг понятий теории;
получить навыки решения учебных и практических
задач;
выработать навыки постановки и решения информационных задач,
моделирования и анализа информации с помощью методов теории множеств, отношений, комбинаторики и графов.
Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она базируется на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Начала информатики”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении обще профессиональных и специальных дисциплин.
4
1.ТЕОРИЯ МНОЖЕСТВ
1.1.Основные понятия
Вматематике понятие множества принадлежит к числу первичных, то есть неопределяемых через более простые. Это понятие лишь проясняется, то есть даётся описание его основных свойств.
Множеством называется любая совокупность определенных и различимых между собой объектов нашей интуиции и интеллекта, мыслимая, как единое целое. Эти объекты называются элементами множества. Множества обозначаются большими буквами латинского алфавита, а их элементы –
малыми. Запись x X означает, что элемент x принадлежит множеству X, в противном случае пишут x X.
Вэтом “определении” совокупность предметов рассматривается, как один общий объект и при этом предметы как бы собираются в один мешок, а дальше работают с этим мешком, как с единым целым, не задумываясь о его содержании. Такой подход известен в биологии, где растения и животные, классифицируются по видам, классам, отрядам и т. д. При этом внимание переносится с отдельных представителей на общие свойства группы, как совокупности. В языке это отражается в словах “компания”, “стая”, “стадо” и т.д.
В“определении” множества нет никаких ограничений на природу элементов. Это может быть множество студентов первого курса, множество пятен на солнце, множество зелёных яблок, множество звёзд на небе и так далее. Заметим, что в качестве элементов множеств могут быть также множества. Например: с одной стороны, группа студентов – это множество, состоящее из людей, а с другой стороны, эта группа является элементом множества всех групп в институте.
5
В математике часто используют числовые множества, элементами которого являются числа. Некоторые из этих множеств часто используются математиками и имеют стандартные названия и обозначения. К ним относятся множества N – натуральных, Z – целых, Q – рациональных, I – иррациональных, R – действительных чисел.
Геометрически множество действительных чисел изображается точками числовой оси, то есть прямой на которой выбрано: 1) начало отсчёта, 2) положительное направление и 3) единица масштаба.
Между множеством действительных чисел и точками числовой оси существует взаимно однозначное соответствие.
Множества точек X числовой оси называются: a ≤ x ≤ b – отрезком,
a<x<b – интервалом,
a<x ≤ b, a ≤ x<b– полуинтервалом,
Все указанные множества называются промежутками. Всякий интервал, содержащий точку a, называется
окрестностью точки a.
Если множество содержит конечное число элементов, то оно называется конечным, а в противном случае – бесконечным.
Мощностью конечного множества называется число его элементов. Мощность множества X обозначается символом |X|.
Конечное множество обычно задаётся перечислением его элементов с заключением их в фигурные скобки, то есть
X= {x1,x2,,…,xn}.
Здесь порядок, в котором записываются элементы множества, значения не имеет.
Перечисление элементов является громоздким для описания больших множеств и не применимо для бесконечных множеств. Такие множества задаются с помощью характеристических свойств. Пусть P(x)- предикат, т. е. некоторое
6
предложение, зависящее от x. Оно может быть истинным или ложным в зависимости от x. Тогда множество задаётся в виде:
X={x|P(x)}.
Эта запись означает, что x X тогда и только тогда, когда P(x) истинное утверждение.
Например: A= {1,2}={x N | x<3}.
Способ задания множеств с помощью характеристических свойств таит в себе некоторые опасности, которые могут привести к противоречиям. Например, парадокс Рассела заключается в том, что рассматривается множество всех множеств, которые не являются своими собственными подмножествами. То есть, К={М|М М}. Является ли множество К своим элементом? С одной стороны, если К К, то должно выполняться свойство, задающее множество К, т.е. К К, Получили противоречие. С другой стороны, если К К, то исходя из свойства, задающего К, приходим к тому, что К К. А это также противоречит предположению. Таким образом, любое характеристическое свойство, должно всегда приводить к осмысленному заданию множества.
1.2. Операции над множествами
Существует несколько способов конструирования нового множества из некоторого количества исходных множеств. Эти способы представляют собой операции над множествами.
ПодмножествомA множества B (A B) или (A содержится в B) называется множество A, каждый элемент которого принадлежит B. Графически это изображается с помощью кругов Эйлера, как показано на рисунке.
7
А
В
Рис. 1 Пустое множество есть подмножество любого множе-
ства.
Совокупность всех подмножеств множества А называется множеством-степенью и обозначается P(А), то есть
P(А)={В В А}.
Множества A и B называются равными (A=B), если
A B и B A.
Множество, не содержащее ни одного элемента, называется пустым и обозначается Ø. Совокупность всех допустимых объектов в рамках решаемой задачи называется универсальным множеством и обозначается U.
Дополнением множестваA называется множество Ā, состоящее из элементов универсального множества, не являющихся элементами множеством A.
Рис. 2
8
Пересечение множествA B, есть множество элементов принадлежащих A и B.
Рис. 3
ОбъединениеA B есть множество всех элементов принадлежащих A или B. Следует иметь в виду, что существуют два значения союза или:
1)«исключающее или» - либо то, либо другое и третьего не дано;
2)«не исключающее или» - то или другое, или то и другое вместе.
В определении объединения множеств подразумевается второе “не исключающее или”, то есть элемент может принадлежать только A, только B, а также одновременно этим множествам
Рис. 4
РазностьA\B, есть множество, состоящее из элементов A, не входящих в множество В.
Рис. 5
9
Симметричная разность A B
Рис. 6
1.3. Алгебраические свойства операций над множествами
Таблица 1
1. идемпотентность
1.1. A A=A |
|
|
1.2. A A=A |
||||||||||||
|
|
|
2. коммутативность |
||||||||||||
2.1. A B=B A |
|
|
2.2 A B=B A |
||||||||||||
|
|
|
|
3. ассоциативность |
|||||||||||
3.1. |
|
|
|
|
|
3.2 |
|
|
|
|
|||||
A (B C)=(A B) C |
|
|
A (B C)=(A B) C |
||||||||||||
|
|
|
4 дистрибутивность |
||||||||||||
4.1.A (B C)=(A B) ( |
|
4.2 |
|
|
|
|
|||||||||
A C) |
|
|
A (B C)=(A B) (A C) |
||||||||||||
|
|
|
|
5. поглощение |
|||||||||||
5.1. A (A B)=A |
|
|
5.2. A (A B)=A |
||||||||||||
|
|
|
|
6. свойства нуля |
|||||||||||
6.1. A Ø=A |
|
|
6.2. A Ø=A |
||||||||||||
|
|
|
7. свойства единицы |
||||||||||||
7.1. A U= U |
|
|
7.2. A U=A |
||||||||||||
|
|
|
|
8. инволютивность |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
A |
A |
|||||||
|
|
|
9. законы де Моргана |
||||||||||||
9.1. |
A B |
|
A |
|
B |
|
|
|
9.2 |
A B |
|
A |
|
B |
|
|
|
|
10. дополнительность |
||||||||||||
10.1. A Ā=U |
|
|
10.2 A Ā=Ø |
||||||||||||
10 |
|
|
|
|
|
|
|
|
|