Дискретная математика (стр. 1 )

Федеральное агентство по образованию

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

ДИСКРЕТНАЯ МАТЕМАТИКА

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

для студентов заочной формы обучения специальностей

230101 «Вычислительные машины, комплексы, системы и сети»,

230201 «Информационные системы и технологии»

Рекомендовано к изданию научно-методическим советом

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

Псков

Издательство ППИ

2009

Оглавление

Порядок выполнения контрольной работы.. 5

Часть 1. Краткий теоретический материал. 6

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

1.1. Понятие множества. 6

1.2. Объединение, пересечение, дополнение, разность множеств 7

1.3. Прямое произведение множеств. 8

Контрольные вопросы.. 8

2. Отношения. 10

2.1. Понятие бинарного отношения. 10

2.2. Обратное отношение. 10

2.3. Композиция отношений. 10

2.4. Векторы.. 11

Контрольные вопросы.. 11

3. Соответствия. 13

Контрольные вопросы.. 14

4. Виды графов. 16

4.1. Понятие графа. 16

4.2. Связность. 18

4.3. Планарность. 20

4.4. Деревья. 20

Контрольные вопросы.. 21

5. Способы задания графов. 23

5.1. Матрица смежности. 23

5.2. Матрица инциденций. 23

Контрольные вопросы.. 24

6. Маршруты, цепи, циклы.. 25

6.1. Основные определения. 25

6.2. Эйлеровы циклы.. 25

6.3. Гамильтоновы циклы.. 25

Контрольные вопросы.. 26

7. Преобразование логических выражений. 27

7.1. Понятие логической функции. 27

7.2. Тождества булевой алгебры.. 29

7.3. Правила преобразования некоторых логических функций. 30

Контрольные вопросы.. 30

8. Минимизация логических функций. 32

8.1. Минимизация с помощью карт Карно. 32

8.2. Метод Квайна поиска СокДНФ.. 33

8.3. Метод Квайна – Мак-Класки. 36

8.4. Нахождение МКНФ с помощью карты Карно. 37

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

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

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

Контрольные вопросы.. 42

9. Свойства логических функций. 43

Контрольные вопросы.. 46

Часть 2 47

Варианты заданий. 47

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

Задание 2. Отношения. 50

Задание 3. Соответствия. 55

Задание 4. Виды графов. 60

Задание 5. Способы задания графов. 63

Задание 6. Маршруты, цепи, циклы.. 68

Задание 7. Преобразование логических выражений. 73

Задание 8. Минимизация логических функций. 75

Задание 9. Свойства логических функций. 78

Пример оформления контрольной работы.. 79

Рекомендуемая литература. 85

Порядок выполнения контрольной работы

Контрольная работа по дисциплине «Дискретная математика» включает 9 заданий. Первые 3 задания относятся к разделу «Теория множеств», следующие 3 задания – к разделу «Графы» и последние 3 задания – к разделу «Логические функции».

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

Каждое задание контрольной работы представлено двадцатью вариантами. Номер варианта для конкретного студента определяется следующим образом:

·  взять две последние цифры номера зачетной книжки;

·  определить остаток от деления полученного числа на 20, величина остатка и будет соответствовать номеру варианта;

·  если остаток получился равным нулю, то взять вариант 20.

Например, пусть номер зачетной книжки 0701089. Число, образованное двумя последними цифрами, – 89. Остаток от деления 89 на 20 равен 9 (89 = 20 × 4 + 9). Следовательно, студент с номером зачетной книжки 0701089 должен решать задания варианта 9.

Пусть теперь номер зачетной книжки 0751000. В таком случае две последние цифры дадут число 0. Остаток от деления 0 на 20 равен 0 (0 = 20 × 0 + 0). Значит, студент с номером зачетки 0751000 должен выполнять задания варианта 20.

Контрольная работа аккуратно выполняется в отдельной тетради. Решение каждой задачи при этом должно содержать:

·  задание согласно варианту;

·  подробное описание решения или подробное обоснование ответа;

·  ответ.

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

В пособии также предлагается перечень литературы, в которой можно найти дополнительный материал по дисциплине «Дискретная математика».

«Цыфиркин. Задача… Нашли мы трое... на дороге… триста рублев… Дошло дело до дележа. Смекни-тко, по чему на брата?

Митрофан (вычисляя, шепчет). Единожды три — три. Единожды ноль — ноль. Единожды ноль — ноль…

Г-жа Простакова. ..Нашел деньги, ни с кем не делись. Все себе возьми, Митрофанушка. Не учись этой дурацкой науке.»

. «Недоросль». Действие третье. Явление VII.

Часть 1. Краткий теоретический материал

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

1.1. Понятие множества

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

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

Множество, не содержащее элементов, называется пустым (Æ).

Обычно в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества U (своего для каждого случая), которое называется универсальным множеством (или универсумом).

Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами:

·  Перечислением: M = {a1, a2, …, ak}

·  Характеристическим предикатом: M ={x ½ P(x)}

При задании множеств перечислением обозначения элементов обычно заключают в фигурные скобки и разделяют запятыми. Это задание множества в явной форме.

Пример. M0 = {1, 2, 3, 4, 5, 6, 7, 8, 9}

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

Пример. M0 = {n ½ n Î N & n < 10}

(Множество M0 состоит из элементов n таких, которые принадлежат множеству натуральных чисел и меньше 10)

1.2. Объединение, пересечение, дополнение, разность множеств

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

A È B = {x ½ x Î A Ú (или) x Î B}

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

A Ç B = {x ½ x Î A & (и) x Î B}

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

A \ B = {x ½ x Î A & x Ï B}

Симметрическая разность (или кольцевая сумма):

A D B = (А È В) \ (А Ç В) =

= {x ½ (x Î A & x Ï B) Ú (x Ï A & x Î B)}

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

Ā = {x ½ x Ï A}

Ā = U \ A

Пример. Пусть А = {1, 2, 3}, B = {3, 4, 5}.

Определим множества D1 = (A È B) \ (A Ç B) и D2 = A D B.

A È B = {1, 2, 3, 4, 5}

A Ç B = {3}

D1 = (A È B) \ (A Ç B) = {1, 2, 4, 5}

D2 = A D B = {1, 2, 4, 5}

1.3. Прямое произведение множеств

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

A ´ B = {(a, b) ½ a Î A & b Î B}

Степенью множества А называется его прямое произведение самого на себя:

Соответственно, А1 = A, A2 = A ´ A и вообще Аn = A n–1 ´ A.

Пример. А = {a, b}, B = {1, 2, 3}.

A ´ B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}

B ´ A = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}