- •Методические указания по выполнению контрольной работы по дисциплине «Дискретная математика»
- •050100.62 Педагогическое образование
- •Рекомендации по выполнению и оформлению контрольной работы
- •Контрольные задания по курсу "Дискретная математика "
- •Раздел1. Множества
- •Раздел 2. Отношения
- •Раздел 3 Булевы функции
- •Раздел 4 «Элементы комбинаторики»
- •Раздел 5 «Графы»
- •Содержание разделов, изучаемых в семестре
- •Материалы для самоподготовки
- •Тема 1. Множества
- •1.1.Основные понятия
- •1.2. Операции над множествами
- •1.3. Геометрическое моделирование множеств. Диаграммы Венна
- •1.4. Алгебра множеств. Основные тождества алгебры множеств
- •Основные тождества алгебры множеств
- •1.5. Эквивалентность множеств
- •1.6. Счетные множества
- •1.7. Множества мощности континуума
- •Тема 2. Отношения. Функции
- •2.1. Отношения. Основные понятия и определения
- •2.2. Операции над отношениями
- •2.3. Свойства отношений
- •2.4. Функции. Основные понятия и определения
- •Тема 3. Графы
- •3.1. Основные характеристики графов
- •3.2. Матричные способы задания графов
- •3.3. Изоморфизм графов
- •3.4. Маршруты, циклы в неориентированном графе
- •3.5. Пути, контуры в ориентированном графе
- •3.6. Связность графа
- •3.7. Экстремальные пути в нагруженных ориентированных графах
- •3.8 Алгоритм Форда – Беллмана нахождения минимального пути
- •3.9. Алгоритм нахождения максимального пути
- •3.10. Деревья.. Основные определения
- •3.11. Минимальные остовные деревья нагруженных графов
- •Тема 4. Булевы функции
- •4.1. Определение булевой функции
- •4.2. Формулы логики булевых функций
- •4.3. Равносильные преобразования формул
- •Основные равносильности булевых формул.
- •4.4. Двойственность. Принцип двойственности.
- •4.5. Булева алгебра (алгебра логики). Полные системы булевых функций
- •4.6. Нормальные формы
- •4.7. Разложение булевой функции по переменным
- •4.8. Минимизация формул булевых функций в классе дизъюнктивных нормальных форм
- •4.9. Применение алгебры булевых функций к релейно-контактным схемам
- •Раздел 5 «Элементы комбинаторики»
- •5.1 Основные определения комбинаторного анализа
- •5.2 Правило суммы и правило произведения
- •5.3 Формулы для расчета перестановок и сочетаний без повторений и с повторениями
- •5.4 Бином Ньютона и полиномиальная теорема.
- •Вопросы для самоконтроля
- •Раздел 1 Множества
- •Раздел 2 Отношения и функции
- •Раздел 3 Логика высказываний
- •Раздел 4 Булевы функции
- •Раздел 5. Основы комбинаторного анализа
- •Раздел 6. Графы и сети.
- •Тесты для самоконтроля
- •Список литературы Основная литература
- •Дополнительная литература
- •Приложение 1
- •Контрольная работа
- •Вариант№____
Раздел 2. Отношения
Вариант № 1.
Задано бинарное отношение = {<1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 4>}.
Найти D(),
R(),
,
-1. Проверить, будет ли отношение
рефлексивным, симметричным, антисимметричным,
транзитивным?
2. Привести пример отношения не рефлексивного, не симметричного и не транзитивного.
3. Дана функция f(x) = x3ex, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 2.
Задано бинарное отношение = {<1, 3>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка на множестве треугольников на плоскости.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и не являющейся сюръективной, инъективной, биективной.
Вариант № 3.
Задано бинарное отношение = {<1, 2>, <2, 2>, <2, 1>, <2, 3>, <3, 2>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xy, задаваемое равенством x = – y?
3. Дана функция f(x) = lnx
+
,
отображающая множество положительных
действительных чисел во множество всех
действительных чисел. Является ли эта
функция сюръективной, инъективной,
биективной? Почему?
Вариант № 4
Задано бинарное отношение = {<1, 1>, <2, 2>, <2, 1>, <2, 3>, <3, 2>, <3, 3>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением частичного полрядка на множестве действительных чисел отношение xy, задаваемое неравенством x 2 – y2 0?
3. Дана функция f(x) = ex + , отображающая множество положительных действительных чисел на множество положительных действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 5.
Задано бинарное отношение = {<1, 1>, <1, 2>, <2, 1>, <3, 1>, <3, 2> <1, 3>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество неотрицательных действительных чисел, R® [0, ) и являющейся сюръективной, но не инъективной.
Вариант № 6
Задано бинарное отношение = {<1, 2>, <2, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xy, задаваемое неравенством x y?
3. Дана функция f(x) = lnx + 2x, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 7.
Задано бинарное отношение = {<2, 2>, <2, 4>, <1, 4>, <4, 1>, <4, 2>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и не симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и являющейся сюръективной и неинъективной.
Вариант № 8.
Задано бинарное отношение = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xy, задаваемое равенством xy = 100?
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и не являющейся сюръективной, инъективной, биективной.
Вариант № 9.
Задано бинарное отношение = {<1, 1>, <2, 2>, <3, 3>, <3, 1>, <1, 3>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и являющейся сюръективной, но не инъективной.
Вариант № 10.
Задано бинарное отношение = {<1, 1>, <2, 2>, <4, 4>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(), R(), , -1. Проверить, будет ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка.
3. Дана функция f(x) = x 2 , отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
