- •Псковский государственный политехнический институт
- •Н.В. Мотина
- •Дискретная математика
- •Методические указания по выполнению контрольных работ
- •230101 «Вычислительные машины, комплексы, системы и сети»,
- •230201 «Информационные системы и технологии»
- •Псков Издательство ппи
- •Часть 1. Краткий теоретический материал 6
- •Часть 2 47
- •Порядок выполнения контрольной работы
- •Часть 1. Краткий теоретический материал
- •1. Операции над множествами
- •1.1. Понятие множества
- •1.2. Объединение, пересечение, дополнение, разность множеств
- •1.3. Прямое произведение множеств
- •Контрольные вопросы
- •2. Отношения
- •2.1. Понятие бинарного отношения
- •2.2. Обратное отношение
- •2.3. Композиция отношений
- •2.4. Векторы
- •Контрольные вопросы
- •3. Соответствия
- •Контрольные вопросы
- •4. Виды графов
- •4.1. Понятие графа
- •4.2. Связность
- •4.3. Планарность
- •4.4. Деревья
- •Контрольные вопросы
- •5. Способы задания графов
- •5.1. Матрица смежности
- •5.2. Матрица инциденций
- •Контрольные вопросы
- •6. Маршруты, цепи, циклы
- •6.1. Основные определения
- •6.2. Эйлеровы циклы
- •6.3. Гамильтоновы циклы
- •Контрольные вопросы
- •7. Преобразование логических выражений
- •7.1. Понятие логической функции
- •Продолжение табл.2
- •7.2. Тождества булевой алгебры
- •7.3. Правила преобразования некоторых логических функций
- •Контрольные вопросы
- •8. Минимизация логических функций
- •8.1. Минимизация с помощью карт Карно
- •8.2. Метод Квайна поиска СокДнф
- •8.3. Метод Квайна – Мак-Класки
- •8.4. Нахождение мкнф с помощью карты Карно
- •8.5. Минимизация логических функций, представленных в конъюнктивной форме, с использованием правил, аналогичных правилам минимизации логических функций в дизъюнктивной форме
- •8.6. Минимизация неполностью определенных логических функций с помощью карты Карно
- •8.7. Минимизация неполностью определенных логических функций без использования карты Карно
- •Контрольные вопросы
- •9. Свойства логических функций
- •Контрольные вопросы
- •Часть 2 Варианты заданий Задание 1. Операции над множествами
- •Задание 2. Отношения
- •Задание 3. Соответствия
- •Задание 4. Виды графов
- •Задание 5. Способы задания графов
- •Задание 6. Маршруты, цепи, циклы
- •Задание 7. Преобразование логических выражений
- •Задание 8. Минимизация логических функций
- •Задание 9. Свойства логических функций
- •Пример оформления контрольной работы
- •Рекомендуемая литература
- •Мотина Надежда Владимировна
Задание 3. Соответствия
Вариант 1
A = {a, b, c, d, e}; B = {a, b, c, d, e};
R A B = {(a, a), (a, b), (b, c), (b, d), (c, e), (e, d), (c, a)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента a;
г) прообраз элемента a;
д) является ли соответствие R всюду определенным? почему?
Вариант 2
A = {1, 2, 4, 5, 6}; B = {5, 6, 7, 8, 10};
R A B = {(1, 7), (4, 6), (5, 6), (2, 8), (6, 5)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 5;
г) прообраз элемента 6;
д) является ли соответствие R всюду определенным? почему?
Вариант 3
A = {6, 7, 8, 9, 10, 11, 12, 13}; B = {10, 11, 12, 13};
R A B = {(6, 10), (6, 11), (7, 10), (8, 13), (13, 11)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 6;
г) прообраз элемента 13;
д) является ли соответствие R всюду определенным? почему?
Вариант 4
A = {10, 11, 12, 13}; B = {, , , *};
R A B = {(11, ), (10, ), (13, *), (12, ), (13, )}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 10;
г) прообраз элемента ;
д) является ли соответствие R всюду определенным? почему?
Вариант 5
A = {a, b, c, d}; B = {1, 2, 3, 4};
R A B = {(a, 2), (a, 3), (a, 4), (b, 3), (c, 1), (c, 4)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента c;
г) прообраз элемента 1;
д) является ли соответствие R всюду определенным? почему?
Вариант 6
A = {a, b, c}; B = {1, 2, 3, 4};
R A B = {(b, 2), (a, 3), (b, 1), (b, 4), (c, 1), (c, 2), (c, 4)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента a;
г) прообраз элемента 2;
д) является ли соответствие R сюръективным? почему?
Вариант 7
A = {a, b, c, d, f, g, h}; B = {a, b, c, d, e, i, o, u};
R A B = {(b, a), (c, e), (d, i), (f, o), (g, u), (c, d), (a, c)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента c;
г) прообраз элемента c;
д) является ли соответствие R сюръективным? почему?
Вариант 8
A = {u, v, w, x, y, z}; B = {a, e, i, o, y, u};
R A B = {(v, a), (w, e), (x, i), (y, o), (z, u), (x, o), (v, y)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента y;
г) прообраз элемента o;
д) является ли соответствие R сюръективным? почему?
Вариант 9
A = {a, b, c}; B = {a, b, c, d};
R A B = {(a, c), (b, c), (c, d), (a, d), (b, d)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента a;
г) прообраз элемента d;
д) является ли соответствие R сюръективным? почему?
Вариант 10
A = {a, b, c, d}; B = {b, c, d};
R A B = {(a, b), (b, c), (a, c), (a, d), (b, d), (c, d)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента c;
г) прообраз элемента c;
д) является ли соответствие R сюръективным? почему?
Вариант 11
R = {(a, c), (b, c), (c, b), (a, b)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента a;
г) прообраз элемента b;
д) является ли соответствие R функциональным? почему?
Вариант 12
R = {(a, с), (a, d), (b, d), (b, e), (d, b)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента d;
г) прообраз элемента d;
д) является ли соответствие R функциональным? почему?
Вариант 13
R = {(1, 2), (1, 3), (2, 3)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 1;
г) прообраз элемента 2;
д) является ли соответствие R функциональным? почему?
Вариант 14
R = {(2, 1), (3, 1), (3, 2)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 2;
г) прообраз элемента 2;
д) является ли соответствие R функциональным? почему?
Вариант 15
R = {(1, 2), (2, 3), (3, 2), (2, 1)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 2;
г) прообраз элемента 1;
д) является ли соответствие R функциональным? почему?
Вариант 16
R = {(1, x), (1, y), (3, x)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 3;
г) прообраз элемента x;
д) является ли соответствие R инъективным? почему?
Вариант 17
R = {(x, ), (x, ), (y, ), (y, *)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента y;
г) прообраз элемента *;
д) является ли соответствие R инъективным? почему?
Вариант 18
R = {(1, ), (1, ), (1, ), (1, *), (3, ), (3, )}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 3;
г) прообраз элемента ;
д) является ли соответствие R инъективным? почему?
Вариант 19
R = {(a1, a2), (a1, a3), (a2, a5), (a4, a2), (a5, a2)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента a1;
г) прообраз элемента a2;
д) является ли соответствие R инъективным? почему?
Вариант 20
R = {(1, 3), (1, 4), (3, 2), (4, 2)}.
Найти:
а) OOR (область определения соответствия R);
б) ОЗR (область значений соответствия R);
в) образ элемента 4;
г) прообраз элемента 3;
д) является ли соответствие R инъективным? почему?