Практическая работа 1. Отношения на множествах
 Скачать 15.01 Kb.
|
|
ПРЗ №1. Решение задач по теме 2. Отношения на множествах (практикум по решению задач) Задача 1. Доказать, что бинарное отношение на множестве целых чисел ρ = {(x, y ) ∈ Ζ × Ζ : x = y} является отношением эквивалентности, и построить соответствующее ему фактор-множество Ζ / ρ. Решение. Проверку рефлексивности, симметричности и транзитивности данного бинарного отношения выполните самостоятельно. Построим классы эквивалентности для данного отношения эквивалентности. Класс эквивалентности, порожденный любым элементом x ∈ Ζ , имеет вид [x] = {y ∈ Ζ : x ≈ y} = {y ∈ Ζ : x = y} = {x}. Таким образом, для данного отношения эквивалентности класс эквивалентности, порожденный элементом x ∈ Ζ , состоит только из этого элемента x и фактор-множество Ζ / ρ имеет вид Ζ / ρ = {{x}: x ∈ Ζ }. Задача 2. На плоскости Ρ выбрана некоторая декартова прямоугольная система координат. На Ρ заданы три отношения эквивалентности: ρ1 = {((a1 , a 2 ), (b1 , b2 )) ∈ Ρ × Ρ : a1 = b1 , a 2 − b2 ∈ Ζ }; ρ 2 = {((a1 , a 2 ), (b1 , b2 )) ∈ Ρ × Ρ : a1 − b1 ∈ Ζ , a 2 − b2 ∈ Ζ }; ρ 3 = {((a1 , a 2 ), (b1 , b2 )) ∈ Ρ × Ρ : a1 − b1 + a 2 − b2 ∈ Ζ }. Найдите фактор-множества для данных отношений эквивалентности. Решение. Построим фактор-множество для отношения ρ1 . Класс эквивалентности, порожденный произвольным элементом (a1 , a 2 )∈ Ρ, имеет вид [(a1 , a 2 )] = {(x, y )∈ Ρ : ((a1 , a 2 ), (x, y ))∈ ρ1} = {(x, y )∈ Ρ : x = a1 , a 2 − y ∈ Ζ } = = {(x, y ) ∈ Ρ : ∃k ∈ Ζ x = a1 , a 2 − y = k } = = {(x, y ) ∈ Ρ : ∃k ∈ Ζ x = a1 , y = a 2 − k } = = {(a1 , a 2 − k ) ∈ Ρ : k ∈ Ζ }. Таким образом, в класс эквивалентности, порожденный элементом (a1 , a 2 )∈ Ρ a1 ∈ R, 0 ≤ a 2 < 1 , попадают вместе с элементом (a1 , a 2 )∈ Ρ элементы, у которых первая координата равна a1 , а вторая координата отличается от a 2 на целое число. Классы эквивалентности, порожденные элементами с a1 ∈ R, 0 ≤ a 2 < 1 , не пересекаются и в объединении дают все множество Ρ . Следовательно, фактор-множество Ρ / ρ1 можно записать в виде Ρ / ρ1 = { (α , β + k ) : k ∈ Ζ } : α ∈ R, β ∈ [0,1)}. Фактор-множество для отношений ρ 2 , ρ 3 постройте самостоятельно. Задача 3. Покажите, что объединение двух отношений эквивалентности может не являться отношением эквивалентности. Решение. На множестве Α = { ,2,3,4,5} рассмотрим два отношения эквивалентности ρ1 = {(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (1,2 )(2,1)}; ρ1 = {(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (3,2 )(2,3)}. Объединение данных отношений эквивалентности ρ1 ∪ ρ 2 = {(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (1,2 )(2,1), (3,2 ), (2,3)} не является отношением эквивалентности, так как для него не выполнено свойство транзитивности ( (3,2 ) ∈ ρ1 ∪ ρ 2 , (2,1) ∈ ρ1 ∪ ρ 2 , а (3,1) ∉ ρ1 ∪ ρ 2 ). Задачи для самостоятельного решения Задание 1. На R задано бинарное отношение ρ = (x, y ) ∈ R × R : x 2 + x = y 2 + y . Докажите, что ρ - отношение эквивалентности. Сколько элементов может содержать класс эквивалентности? Существует ли класс эквивалентности, состоящий из одного элемента? Задание 2. Покажите, что пересечение отношений эквивалентности, определенных на некотором множестве Α , является отношением эквивалентности. Задание 3. Докажите, что если ρ - отношение эквивалентности, то ρ −1 – также отношение эквивалентности. |