Материал: Методические указания по выполнению лабораторных работ по дисциплине Дискретная математика для студентов специальности 230101. Леденева Т.М., Недикова Т.Н

Таким образом, получаем следующие классы эквивалентности:

,

,

,

,

Заметим, что элементы «похожи» в том смысле, что каждый из них кратен 5. Элементы любого другого класса эквивалентности «похожи» в том смысле, что имеют один и тот же остаток при делении на пять.

Фактор-множество множества целых чисел по отношению эквивалентности имеет вид

.

Задача 3.4. Отношение , задано матрицей, которая имеет вид

Определить классы эквивалентности.

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

Таким образом, . Таким образом, фактор-множество множества по отношению эквивалентности имеет вид

.

Задача 3.5. Определите тип отношения

.

Решение. Элементы этого отношения будут упорядочены включением

.

Проверим, будет ли это отношение частичным порядком. Заметим, что

.

Так как для всех , то отношение рефлексивно. Видно, что отношение не является симметричным. Но если и , то , иначе из следует . Следовательно, антисимметрично. Пусть и , т.е. и . Тогда и и, следовательно, или , а значит . Таким образом, транзитивно. Обобщая, сделаем вывод, что является отношением частичного порядка.

Задачи для самостоятельного решения

1. Пусть , а - отношения на , определенные следующим образом:

,

,

,

.

Какое из отношений является

а) симметричным, б) рефлексивным,

в) транзитивным, г) антисимметричным.

Постройте графы, соответствующие данным отношениям.

2. Определите свойства следующих отношений:

а) ;

б) ;

в) ;

г) .

3. Постройте бинарное отношение на множестве

а) рефлексивное, симметричное, не транзитивное;

б) рефлексивное, антисимметричное, не транзитивное;

в) рефлексивное, не симметричное, транзитивное;

г) не рефлексивное, антисимметричное, транзитивное.

4. Пусть . Опишите наименьшее рефлексивное отношение на множестве .

5. Пусть и бинарное отношение на множестве . Опишите следующие отношения:

а) наименьшее симметричное отношение на , содержащее ,

б) наименьшее симметричное и рефлексивное отношение на , содержащее ,

в) наибольшее симметричное отношение, содержащееся в ,

г) наименьшее транзитивное отношение на , содержащее .

6. Перечислите упорядоченные пары, принадлежащие отношениям, заданным на множестве

а) ; б) ;

в) транзитивное замыкание ,

г) транзитивное замыкание .

7. Пусть бинарные отношения и заданы на одном и том же множестве . Проверьте справедливость утверждения «если отношения и обладают свойством , то отношение также обладает свойством », если отношения заданы в следующей таблице,

а в качестве свойства выступает

а) рефлексивность, б) антирефлексивность,

в) симметричность, г) антисимметичность, д) транзитивность.

8. Установите, является ли каждое из приведенных ниже отношений отношением эквивалентности. Для каждого отношения эквивалентности постройте классы эквивалентности.

а) ,

б) ,

в) на множестве ,

г) на множестве прямых на плоскости,