Практикум по дискретной математике (стр. 1 )

,

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

МАТЕМАТИКЕ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ГОУ ВПО «ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

,

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

Учебное пособие

Рекомендовано учебно-методическим объединением Совета директоров средних специальных учебных заведений Волгоградской области в качестве учебного пособия для образовательных учреждений среднего профессионального образования Волгоградской области

Волгоград

2010

УДК 51/3)

П 69

Рецензенты: старший преподаватель Камышинского филиала СГА ; профессор кафедры ТОИ ГОУ «СПбГПУ», д. т. н.

Кухарева, по дискретной математике: учеб. пособие / , ; ВолгГТУ, Волгоград, 2010. – 68 с.

ISBN 0387-5

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

Предназначено для студентов специальности 230103 «Автоматизированные системы обработки информации и управления (по отраслям)» и может использоваться студентами направления 552800 «Информатика и вычислительная техника».

Ил. 37. Табл. 5. Библиогр.: 9 назв.

Печатается по решению редакционно-издательского совета

Волгоградского государственного технического университета

ISBN 0387-5 Ó Волгоградский

государственный

технический

университет, 2010

СОДЕРЖАНИЕ

Предисловие.......................................................................................	5
Порядок выполнения практических заданий..................................	6
1. Практическое занятие № 1. Тема: «Начальные понятия теории множеств. Операции над множествами. Применение диаграмм Эйлера-Венна при решении практических задач»...............	7
1.1. Начальные понятия теории множеств.............................	7
1.2. Операции над множествами.............................................	9
1.3. Применение диаграмм Эйлера-Венна при решении практических задач....................................................................................	10
Задания................................................................................................	12
Литература..........................................................................................	14
2. Практическое занятие № 2. Тема: «Бинарные отношения»	15
2.1. Бинарные отношения. Прямое произведение множеств...	15
2.2. Свойства отношений..........................................................	17
Задания................................................................................................	17
Литература..........................................................................................	19
3. Практическое занятие № 3. Тема: «Отношения эквивалентности и отношения порядка».............................................................	20
3.1. Отношения эквивалентности. Отношения порядка.......	20
Задания................................................................................................	21
Литература..........................................................................................	23
4. Практическое занятие № 4. Тема: «Функции и отображения»..	24
4.1. Функции и отображения....................................................	24
Задания................................................................................................	25
Литература..........................................................................................	27
5. Практическое занятие № 5. Тема: «Элементы графа. Способы задания графа. Подграфы. Изоморфизм».................................	28
5.1. Элементы графа...................................................................	28
5.2. Способы задания графов....................................................	29
5.3. Подграфы.............................................................................	31
5.4. Изоморфизм графов..........................................................	31
5.5. Степени вершин графа.......................................................	32
Задания................................................................................................	32
Литература..........................................................................................	33
6. Практическое занятие № 6. Тема: «Путь в графе. Поиск путей (маршрутов)».................................................................................	34
6.1. Маршруты, цепи, циклы....................................................	34
6.2. Поиск путей (маршрутов) с минимальным числом дуг..	35
6.3. Эйлеровы графы..................................................................	36
Задания................................................................................................	37
Литература..........................................................................................	38
7. Практическое занятие № 7. Тема: «Связность, компоненты связности»...........................................................................................	39
7.1. Связность, компоненты связности...................................	39
7.2. Матрица связности.............................................................	41
Задания................................................................................................	41
Литература..........................................................................................	43
8. Практическое занятие № 8. Тема: «Планарные графы».......	44
8.1. Планарные графы................................................................	44
8.2. Эйлерова характеристика...................................................	45
8.3. Задача о плоской укладке...................................................	46
8.4. Гамма-алгоритм..................................................................	46
Задания................................................................................................	48
Литература..........................................................................................	50
9. Практическое занятие № 9. Тема: «Деревья».........................	51
9.1. Основные определения.......................................................	51
9.2. Ориентированные деревья.................................................	52
Задания................................................................................................	53
Литература...........................................................................................	54
10. Практическое занятие № 10 Тема: «Переключательные (булевы) функции»............................................................................	55
10.1. Основные определения....................................................	55
10.2. Формулы логики булевых функций.................................	56
10.3. Фиктивные и существенные переменные.......................	57
10.4. Полные системы булевых функций.................................	58
Задания.................................................................................................	60
Литература...........................................................................................	61
11. Практическое занятие № 11. Тема: «Предикаты. Кванторы. Предикатные формулы».....................................................................	62
11.1. Предикаты..........................................................................	62
11.2. Кванторы...........................................................................	63
11.3. Предикатные формулы....................................................	64
Задания................................................................................................	65
Литература...........................................................................................	67

Предисловие

В настоящее время в связи с широким использованием вычислительной техники в различных сферах человеческой деятельности все большее значение приобретают вычисления на дискретных структурах. Решением задач реальной размерности с учетом ограниченности временных и емкостных ресурсов ЭВМ занимается дискретная математика.

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

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

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

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

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

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

Использовать математический аппарат дискретной математики при решении типовых задач в предметной области. Рассмотреть конкретные примеры выполнения заданий.

Выполнить задания, предложенные для самостоятельной работы.

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

1. Практическое занятие № 1

Тема: «Начальные понятия теории множеств. Операции над

множествами. Применение диаграмм Эйлера-Венна при

решении практических задач»

Цель занятия:

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

Пояснение к работе

Время выполнения практического задания – 4 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Как обозначаются множества и элементы множеств?

Какое множество называется конечным?

Какие существуют способы задания множеств?

Как определяется мощность множества?

2. Дать определение следующих понятий:

– множество и элементы множества;

– операции разности и объединения множеств;

– операции пересечения и дополнения;

– универсальное множество и булеан.

3. Перечислить основные тождества алгебры множеств.

4. Представить операции над множествами в виде диаграмм.

5. Выполнить задания для аудиторных занятий.

6. Выполнить задания для самостоятельной работы.

1.1. Начальные понятия теории множеств

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

Множество и его элементы обозначаются следующим образом:

А = { a1, a2, a3} – множество, состоящее из трех элементов;

А = {a1, a2, …} – множество, состоящее из бесконечного числа элементов. Множество может состоять из элементов, которые сами являются множествами. Нужно различать элемент a и множество, состоящее из единственного элемента a.

Пример. Множество А = {1, 2} состоит из двух элементов 1, 2; но множество {А} состоит из одного элемента А.

Если элемент a принадлежит множеству А, это записывается следующим образом: a Î А. Если элемент a не принадлежит множеству А, то записывают так: a Ï А. Если какое-либо множество А включено в другое множество В, то используется запись А Ì В. Множество, содержащее конечное число элементов, называется конечным, если множество не содержит ни одного элемента, то оно называется пустым и обозначается Æ. Принято считать, что пустое множество является подмножеством любого множества: Æ Í А, где А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя.

Пример. 1. Множество корней уравнения sin x = 2 является пустым.

2. Пусть А1 – множество простых чисел, А2 – множество целых чисел, a = 4. Тогда a Î А2, a Ï А1.

Множество считается заданным, если каким-либо образом указано некоторое свойство, которым обладают все его элементы и не обладают никакие другие объекты.

Множество может быть задано различными способами: перечислением элементов (конечные множества) или указанием их свойств (при этом в обоих случаях при задании множеств используют фигурные скобки).

Примеры задания множеств. 1. Множество M цифр десятичного алфавита можно задать в виде: M = {0, 1, ..., 9} или M = {х│х – целое, 0 £ х £ 9}, где справа от вертикальной черты указывают свойство элементов этого множества. Множество M чётных чисел можно записать в виде: M = {х│х – чётное число}.

2. Если R – множество точек числовой прямой, то Rn – множество точек n-мерного арифметического пространства; в частности, R2 – множество точек плоскости, R3 – множество точек пространства трех измерений.

Для каждого множества М существует множество, элементами которого являются подмножества множества М и только они. Такое множество будем называть семейством множества М или булеаном этого множества и обозначать В(М), а множество М будем называть универсальным (универсумом или пространством) и обозначать 1 или U. Множество М (универсальное) не должно быть ýже объединения рассматриваемых множеств, т. е. оно должно быть равно или содержать объединение рассматриваемых множеств.

Пример. Пусть множество А = {1, 2} состоит из двух элементов 1, 2. Тогда множество В(A) включает в себя пустое множество Æ, два одноэлементных множества {1} и {2} и само множество А = {1, 2}, т. е.

В(A) = {Æ, {1}, {2}, {1, 2}}. Мы видим, что множество В(A) состоит из четырех элементов (4 = 22).

Приведем стандартные обозначения для некоторых наиболее употребительных числовых множеств:

N – множество натуральных чисел (иногда его начинают с 1, иногда с 0; обычно это оговаривается);

Р – простые числа;

Z – множество целых чисел (положительные, отрицательные и 0);

R – множество действительных чисел.

Очевидное соотношение: N Í Z Í R.

Рассмотрим методы получения новых множеств из уже существующих на примере пространства или множества U, определив в нём 4 операции над множествами A и B: объединение, пересечение, разность, дополнение.

1.2. Операции над множествами

Объединением А и В называется множество А È В, все элементы которого являются элементами хотя бы одного из множеств А или В:

А È В = {x ç x Î А и / или x Î В}.

Из определения следует, что А Í А È В и В Í А È В. Аналогично определяется объединение нескольких множеств.

Пример. 1. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А È В = {2, 4, 5, 6}.

2. Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А È В – множество чисел, которые делятся на 2 или на 3: А È В = {2, 3, 4, 6, 8, 9, 10, …}.

Пересечением множеств А и В называется множество А Ç В, все элементы которого являются элементами обоих множеств А и В: А Ç В = {x ç x Î А и x Î В}. Из определения следует, что А Ç В Í А, А Ç В Í В и А Ç В Í А È В. Аналогично определяется пересечение нескольких множеств.

Пример. 1. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А Ç В = {4, 6}.

2. Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А Ç В – множество чисел, которые делятся и на 2, и на 3: А È В = {6, 12, 18, …}.

Может оказаться, что множества не имеют ни одного общего элемента. Тогда говорят, что множества не пересекаются или что их пересечение – пустое множество.

Пример. Пусть А = {1, 2}, В = {2, 3}, C = {3, 4}. Тогда А Ç В Ç C = Æ.

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

А \ В = {x ç x Î А и x Ï В}.

Пример. 1. А = {4, 5, 6}, В = {2, 4, 6}. А \ В = {5}, В \ А= {2}.

2. А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А \ В – множество чисел, которые делятся на 2, но не делятся на 3, а В \ А – множество чисел, которые делятся на 3, но не делятся на 2: А \ В = {2, 4, 8, 10, 14, …}. В \ А = {3, 9, 15, 21, 27, …}.

Симметрической разностью множеств А и В называется множество А + В: А + В = (А \ В) È (В \ А).

Пример.1. А = {4, 5, 6}, В = {2, 4, 6}. А \ В = {5}, В \ А= {2}, А + В = {2, 5}.

2. А = {2, 4, 6, …}, В = {3, 6, 9, …}, А \ В = {2, 4, 8, 10, 14, …}.

В \ А = {3, 9, 15, 21, 27, …}, А + В = {2, 3, 4, 8, 9, …}.

Дополнением`М множества М является множество

`М = {mi│mi Ï M}.

Пример. Заданы множества А = {1, 2, 5, 6} и В = {2, 3, 4, 6} на универсальном множестве U = {1, 2, 3, 5, 6, 7}. Выполнить операции`А,`В.

Решение. В результате выполнения заданных операций получим следующие множества: `А = {3, 7};`В = {1, 5, 7}.

Для конечных множеств существует понятие: мощность множества А – число его элементов. Обозначают мощность множества |А|.

Пример. А = {1, 2, 5, 6}, тогда мощность множества |А| = n(А) = 4; |Æ| = 0; |{Æ}| = 1.

Также справедливы следующие формулы: для любых множеств А и В Þ |А È В| = |А| + |В| – |А Ç В|, то есть учитываются общие для обоих множеств элементы.

Пример. А = {1, 2, 3} |А| = 3; В = {1, 2, 3, 4, 5} |В| = 5, тогда А È В = {1, 2, 3, 4, 5} |А È В| = 5; А Ç В = {1, 2, 3} |А Ç В| = 3, то есть получим равенство: |А È В| = |А| + |В| – |А Ç В| 5 = 3 + 5 – 3.

Для конечного множества М мощность его булеана |В(М)| равна 2|М|.

1.3. Применение диаграмм Эйлера-Венна при решении практических задач

Для наглядного представления множеств и отношений между ними используются диаграммы Эйлера-Венна. Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга (рис. 1).

С помощью диаграмм Эйлера-Венна удобно иллюстрировать операции над множествами. Результирующее множество каждой операции выделено штриховкой.

MA	MAÈMB	MAÇMB
MB\MA	MA\MB	`МA

Рис. 1. Представление операций над множествами с помощью диаграмм Эйлера-Венна