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

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

Н.В. Мотина

Дискретная математика

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

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

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

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

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

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

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

2009

Оглавление

Н.В. Мотина 2

Порядок выполнения контрольной работы 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

Продолжение табл.2 28

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

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

Контрольные вопросы 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

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

Часть 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.