- •Методические указания
- •Часть 1
- •Содержание
- •Введение
- •Операции над множествами и их свойства
- •Операции над отношениями
- •Задачи для самостоятельного решения
- •Основные типы отношений
- •Задачи для самостоятельного решения
- •Элементы комбинаторики
- •Задачи для самостоятельного решения
- •Библиографический список
- •Часть 1
- •3 94026 Воронеж, Московский просп., 14
Операции над отношениями
Ключевые слова: область отпределения отношения, область значения отношения, обратное отношение, композиция отношений.
Задача 2.1. Для данного отношения
найдите .
Решение. По определению инверсии, .
По определению композиции, , так как существует элемент такой, что и . Рассуждая аналогично, получим, что . Таким же образом можно получить . Используя определение проекций, найдем , , тогда .
Задача 2.2. Пусть
. Найдите для этого отношения .
Решение. Очевидно, что . По определению
.
Композиция отношений и определяет отношение
которое в данном случае примет вид
,
где .
Далее таким же образом получим
.
.
Задача 2.3. Докажите, что .
Решение. Пусть
,
что и требовалось доказать.
Задача 2.4. Для отношений и из уравнения найдите наименьшее отношение , если , и .
Решение. Искомое отношение должно быть наименьшим, т.е. иметь минимальную мощность. Найдем , Из определения композиции отношений и минимальности следует, что . Найдем композицию отношения с левой и правой частями равенства . Получим
или
,
откуда
.
Из равенств и определения композиции отношений следует, что Следовательно, верно равенство
.
Итак, отношение кроме пар отношения может содержать также пары отношения , не попавшие в . Выпишем все пары попавшие в
.
Выберем из этого отношения пары, образующие . Для этого построим таблицу, в столбцах которой выпишем пары, образующие отношение , а в строках – пары отношения . Для каждой пары звездочкой отметим пары из , попавшие в композицию . В результате получим следующую таблицу.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выберем наименьшее число столбцов таблицы так, чтобы для любой строки в выбранном наборе нашелся столбец, имеющий символ в данной строке, причем отношение не должно иметь пар, не входящих в . Видно, что такой набор образуют столбцы , , , поэтому .
Задачи для самостоятельного решения
Для каждого из следующих отношений, заданных на множестве натуральных чисел перечислите упорядоченные пары, принадлежащие отношениям:
а) ,
б) ,
в) .
Пусть - отношение на множестве , определенное условием: тогда и только тогда, когда - нечетное число. Представьте каждым из способов:
а) как множество упорядоченных пар,
б) в виде матрицы,
в) соответствующим графом.
Определите область определения и множество значений отношений
а) ,
б) ,
в) .
Найдите , если
а) ,
б) .
Пусть заданы следующие бинарные отношения и . Найдите отношения .
Пусть , а - отношения на множестве , определенные следующим образом:
,
,
,
.
Найдите , .
Пусть бинарные отношения определены следующим образом , . Опишите отношения
а) , б) , в) , г) .
Для отношений и из уравнения найдите наименьшее отношение , если и
|
|
|
|
|
|
|
|
|
|
|
|