Предмет дискретной математике

ВВЕДЕНИЕ

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

В данном учебном пособии содержание разделов дискретной математики определяются требованиями государственного образовательного стандарта профессионального образования, предъявляемыми к дисциплине «Дискретная  математика» специальности «Прикладная  информатика в экономике» и родственных специальностей. К этим разделам относятся: элементы теории множеств, математической логики, теории графов.

По программе курса выполняется  контрольная работа и расчетно-графическое  задание. Студенты обучающиеся по ускоренной программе (3,5 года) выполняют только контрольную работу.

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

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

Дискретная математика, или  дискретный анализ – область математики, которая занимается исследованием структур и задач на конечных множествах. Поэтому в качестве синонима иногда используется термин «конечная математика». Можно считать общепринятым деление математики на непрерывную и дискретную. Последняя представляет собой важное направление, имеющее характерные для него предмет исследований, методы и задачи. Специфика задач дискретной математики в первую очередь предполагает отказ от основных понятий классической математики – предела и непрерывности. Поэтому для задач дискретной математики обычные средства классического анализа являются вспомогательными.

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

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

Дискретная математика  предлагает:

• универсальные средства (языки) формализованного представления;
• способы корректной переработки информации, представленной на этих языках;
• возможности и условия перехода с одного языка описания явлений на другой с сохранением содержательной ценности моделей.

Сегодня дискретная математика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов –  обязательное квалификационное требование к специалистам в области информатики.

 

 

 

 

1. НАЧАЛЬНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

1. 1. Элементы и множества

Человеческое мышление устроено так, что мир представляется состоящим  из отдельных «объектов». Философам  давно ясно, что мир – единое неразрывное целое, и выделение  в нем объектов – это не более чем произвольный акт нашего мышления, позволяющий сформировать доступную для рационального анализа картину. Но как бы там ни было, выделение объектов и их совокупностей – естественный способ организации нашего мышления, поэтому не удивительно, что он лежит в основе главного инструмента описания точного знания – математики.

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

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

Определение. Под множеством понимают объединение в единое целое определенных вполне различаемых предметов (объектов), которые при этом называются элементами образуемого ими множества.

Обычно множества обозначают прописными буквами латинского алфавита: A, B, C, …; а элементы множеств – строчными буквами: a, b, c, … .

Если объект х является элементом множества М, то говорят, что х принадлежит М: хÎМ. В противном случае говорят, что х не принадлежит М: хÏМ.

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

Пример 1. Это может быть множество студентов, присутствующих на лекции, множество четных чисел и т. д.

Определение. Множество А называется подмножеством множества В, если всякий элемент из А является элементом В. Если А является подмножеством В и В не является подмножеством А, то говорят, что А является строгим (собственным) подмножеством В.

В первом случае обозначают , во втором случае   .

Определение. Множество, не содержащее элементов, называется пустым Æ, оно является подмножеством любого множества. Множество U называется универсальным, то есть все рассматриваемые множества являются его подмножеством.

Рассмотрим два определения  равенства множеств.

Определение. Множества А и В считаются равными, если они состоят из одних и тех же элементов, пишут А=В, А¹В – в противном случае.

Определение. Множества А и В считаются равными, если

Способы задания множеств:

• перечислением элементов: М={a₁, a₂, …, a_k}, т. е. списком своих элементов;
• характеристическим предикатом: М={x | P(x)}(описанием характеристических свойств, которыми должны обладать его элементы);
• порождающей процедурой: M={ x | x=f}, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. В таком случае элементами множества являются все объекты, которые могут быть построены с помощью такой процедуры. Например, множество всех целых чисел, являющихся степенями двойки.

Замечание. При задании множеств перечислением обозначения элементов обычно заключают в фигурные скобки и разделяют запятыми. Перечислением можно задавать только конечные множества (число элементов множества конечно, в противном случае множество называется бесконечным). Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае – не принадлежит. Порождающая процедура – это процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определяемого множества. Бесконечные множества задаются характеристическим предикатом или порождающей процедурой.

Пример 2.

1. М={1, 2, 3, 4} – перечисление  элементов множества.

2. - характеристический предикат.

3. Числа Фибоначчи задаются условиями  (порождающей процедурой):

а₁=1, а₂=2, a_n=a_n-1+a_n-2 для n>2.

Определение. Мощность конечного множества А - это число его элементов.

Мощность множества обозначают |A|.

Пример 3.

|Æ|=0, |{Æ}|=1.

Определение. Множества называются равномощными, если их мощности совпадают.

Определение. Множество всех подмножеств множества А называется булеаном P(A).

Известно, что если множество А содержит n элементов, то множество P(A) содержит 2ⁿ элементов. В связи с этим используется также обозначение множества-степени множества А в виде 2^А.

Пример 4.

А={0, 1, 2}, P(A)={ Æ, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.

 

1.2. Операции  над множествами. Диаграммы Эйлера-Венна

Диаграммы Эйлера-Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

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

 

 

Определение. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):

 

Определение. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 2):

 

Определение. Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):

 

 

Определение. Симметрической разностью множеств А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):

 

Определение. Абсолютным дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А (рис. 5):

 

 

Пример 5. С помощью диаграмм Эйлера – Венна проиллюстрируем справедливость соотношения (рис. 6).

 

 

Убедились, что в обоих случаях  получаем равные множества. Следовательно, исходное соотношение справедливо.

 

1.3. Основные  тождества алгебры множеств

Для произвольных множеств А, В, и С  справедливы следующие соотношения (табл. 1):

Таблица 1

1. Коммутативность объединения	1’. Коммутативность пересечения
2. Ассоциативность объединения	2’. Ассоциативность пересечения
3. Дистрибутивность объединения  относительно пересечения	3’. Дистрибутивность пересечения  относительно объединения
4. Законы действия с пустым  и универсальным множествами	4’. Законы действия с пустым  и универсальным множествами
5. Закон идемпотентности объединения	5’. Закон идемпотентности пересечения
6. Закон де Моргана	6’. Закон де  Моргана
7. Закон поглощения	7’. Закон поглощения
8. Закон склеивания	8’. Закон склеивания
9. Закон Порецкого	9’. Закон Порецкого
10. Закон двойного дополнения

 

Пример 6.

Доказать следующее тождество  .

Решение.

Докажем это тождество двумя  способами: аналитически (используя равносильности алгебры множеств) и конструктивно (используя диаграммы Эйлера-Венна).

1.

2. Построим соответствующие диаграммы  Эйлера-Венна (рис. 7).

 

 

1.4. Прямое  произведение множеств. Отношения  и функции

Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов х и у, расположенных в определенном порядке. Две пары <x, y>, <u, v> считаются равными тогда и только тогда, когда x=u, y=v.

Упорядоченная n-ка элементов х₁, …, х_n обозначается <x₁, …, x_n>.

Определение. Прямым произведением  множеств X и Y называется множество , элементами которого являются все возможные упорядоченные пары <x, y>, такие, что .

Определение. Прямым произведением  множеств Х₁, Х₂, …, Х_n называется совокупность всех упорядоченных n-ок <x₁, …, x_n> таких, что . Если Х₁=Х₂=…Х_n, то пишут .

Пример 7.

1. Пусть X={1, 2, 3}, Y={0, 1}. Тогда ; .

2. Пусть Х – множество точек отрезка [0, 1], а Y – множество точек отрезка [1, 2]. Тогда - множество точек квадрата с вершинами в точках (0, 1), (0, 2), (1, 1), (1,2).

Определение. Бинарным (или двуместным) отношением r называется множество упорядоченных пар.

Если r есть отношение и пара <x, y> принадлежит этому отношению, то наряду с записью <x, y>Îr употребляется запись xry. Элементы х и у называются координатами (или компонентами) отношения r.

Определение. N-арным отношением называется множество упорядоченных n-ок.

Определение. Областью определения бинарного отношения r называется множество

Определение. Областью значений бинарного отношения r называется множество

Пусть rÍ X´Y определено в соответствии с изображением на рисунке 8 . Область определения D_r и область значений E_r определяются соответственно:

D_r={x: (x, y) Î r}, E_r={y: (x,y)Î r}.

Бинарное отношение можно  задать любым из способов задания  множеств. Помимо этого отношения, определенные на конечных множествах обычно задаются:

1. списком (перечислением) пар, для которых это отношение выполняется.
2. матрицей – бинарному отношению соответствует квадратная матрица порядка n, в которой элемент c_ij, стоящий на пересечении i-той строки и j-го столбца, равен 1, если a_i и a_j имеет место отношение, или 0, если оно отсутствует.