Бинарные отношения

БИНАРНЫЕ ОТНОШЕНИЯ
в Z: 8>5 – истинно; 5>10 – ложно
На множестве точек плоскости:
Можно сказать, какая из точек плоскости
наиболее удалена от данной прямой
этой плоскости
Различные пары элементов некоторого множества связаны отношением (двуместным или бинарным)

БИНАРНЫЕ ОТНОШЕНИЯ
На множестве X определено бинарное отношение, если задано подмножество R декартова произведения X×X
Бинарное отношение – соответствие из X в X
Если (x,y)∈R, то “x и y связаны отношением R”
R ⊆ X×X
x R y R(x,y)

Способы задания
бинарного отношения
1. Перечисление элементов:
R={(1,1),(2,2),(6,6),(1,2),(1,6),(2,6)} определено на множестве X={1,2,6}
2. Бинарное отношение - область истинности некоторого двухместного предиката
R = IP - область истинности P(x,y): "x делит y"
3. Характеристическое свойство:
R = { (x,y)∈Z×Z | x>3y }

Способы задания
бинарного отношения
4. Граф отношения (рисунок, диаграмма):
R определено на
множестве X={1,2,6}
5. На множестве действительных чисел бинарное отношение может быть изображено точками плоскости

6. Матричный способ: X={1,2,6}
Если (a,b)∈R, то на
пересечении строки
с номером a и столбца
с номером b ставится 1
Способы задания
бинарного отношения

Свойства бинарного отношения
R - бинарное отношение, определенное на множестве X
1. R рефлексивно, если ∀x∈X (x,x)∈R
R1 = { (x,y)∈Z×Z | x≤y }
2. R симметрично, если
∀x,y∈X [ (x,y)∈R ⇒ (y,x)∈R ]
∀x∈Z x≤x
R2 = { (x,y)∈Z×Z | (x-y) кратно 2 }
∀x,y∈Z [ (x-y) кратно 2 ⇒ (y-x) кратно 2 ]

Свойства бинарного отношения
R - бинарное отношение, определенное на множестве X
3. R транзитивно, если
∀x,y,z∈X [ (x,y)∈R & (y,z)∈R ⇒ (x,z)∈R ]
Для R1:
∀x,y,z∈Z [ x≤y & y≤z ⇒ x≤z ]
4. R антирефлексивно, если ∀x∈X (x,x)∉R
R3 = { (x,y)∈Z×Z | x>y }
∀x∈Z ⎤(x>x), т.е. x≤x
R1 = { (x,y)∈Z×Z | x≤y }

R - бинарное отношение, определенное на множестве X
6. R линейно, если
∀x,y∈X [ (x,y)∈R V (y,x)∈R V x=y ]
5. R антисимметрично, если
∀x,y∈X [ (x,y)∈R & (y,x)∈R ⇒ x=y ]
∀x,y∈Z [ x≤y & y≤x ⇒ x=y ]
∀x,y∈Z [ x≤y V y≤x V x=y ]
Свойства бинарного отношения
Для R1:
R1 = { (x,y)∈Z×Z | x≤y }
Для R1:

Отношение порядка
Отношение частичного порядка –
рефлексивное, транзитивное и
антисимметричное бинарное отношение
R1 = { (x,y)∈Z×Z | x≤y }
Отношение строгого порядка –
антирефлексивное, транзитивное,
антисимметричное и линейное
бинарное отношение
R3 = { (x,y)∈Z×Z | x>y }

Частично упорядоченное множество
A≠∅ < A, ≤ > – ЧУМ
Частично упорядоченное множество – множество, на котором задано отношение частичного порядка
1) < Z, ≤ > – ЧУМ
2) < P(A), ⊆ > – ЧУМ
3) На N определим R: x R y ⇔ x | y
Рефлексивность: ∀x∈N (x | x)
Транзитивность: ∀x,y,z∈N (x | y & y | z ⇒ x | z)
Антисимметричность: ∀x,y∈N (x | y & y | x ⇒ x=y)
< N, R > - ЧУМ
< Z, R > - не является ЧУМ

Частично упорядоченное множество
Элемент a∈A частично упорядоченного множества < A, ≤ > называется
наибольшим элементом, если ∀x∈A x ≤ a
Наименьший элемент ???
Элемент a∈A частично упорядоченного множества < A, ≤ > называется
максимальным элементом, если:
∀x∈A (если x сравним с a, то x ≤ a)
Минимальный элемент ???

A = {1, 5, 60, 4, 6, 2}
∀x,y∈A x R y ⇔ x | y
< A, R > - ЧУМ
A = {1, 5, 4, 6, 2}
60 – наибольший и максимальный
Нет наибольшего
4, 6, 5 - максимальные
Частично упорядоченное множество

Отношение эквивалентности
Отношение эквивалентности –
рефлексивное, симметричное и
транзитивное бинарное отношение
R1 = { (x,y)∈Z×Z | x≤y }
R3 = { (x,y)∈Z×Z | x>y }
R2 = { (x,y)∈Z×Z | (x-y) кратно 2 }
- не симметрично
- не рефлексивно
Рефлексивность: ∀x∈Z ( (x-x) кратно 2 )
Симметричность – проверена (см. ранее)
Транзитивность:
∀x,y,z∈Z [ ((x-y) кратно 2) & ((y-z) кратно 2)
⇒ ((x-y)+(y-z)) кратно 2
⇒ (x-z) кратно 2 ]
R3 - отношение эквивалентности

УПРАЖНЕНИЕ
Докажите:
∀m∈Z m>1
R = { (x,y)∈Z×Z | (x-y) кратно m } –
отношение эквивалентности

Классы эквивалентности
Семейство { Xk | k∈K, Xk⊆X } образует разбиение множества X на классы Xk, если:
1) ∀k∈K Xk ≠ ∅
2) ∀m,k∈K [ m≠k ⇒ Xm ∩ Xk = ∅ ]
3) X = U Xk
k∈K
A = {1,2,3,4,5} можно разбить на классы:
A1 = {3}, A2 = {1,4}, A3 = {2,5}

Классы эквивалентности
Всякому разбиению множества X на классы Xk отвечает бинарное отношение R, задаваемое следующим образом:
(x,y)∈R т.т.т., когда ∃k∈K (x∈Xk & y∈Xk)
Упражнение: Покажите, что R – отношение эквивалентности
Любые два элемента одного класса эквивалентны между собой
Никакие два элемента разных классов не эквивалентны между собой

Пусть ~ – отношение эквивалентности, заданное на X, и a∈X
Класс Ka эквивалентности ~
c порождающим элементом a:
Ka = { x∈X | x ~ a }
{ (x,y)∈Z×Z | (x-y) кратно 2 } - отношение эквивалентности ~
K0 = { x∈Z | x ~ 0 }
= { x∈Z | (x-0) кратно 2 }
= 2Z
K1 = { x∈Z | x ~ 1 }
= { x∈Z | (x-1) кратно 2 }
= 2Z+1
Классы эквивалентности

Свойства классов эквивалентности
Пусть ~ – отношение эквивалентности, заданное на X
1) Любой класс Ka не пуст
a ~ a (рефлексивность), т.е. a∈Ka
2) Если x∈Ka и y∈Ka, то x ~ y
x∈Ka и y∈Ka, т.е. x ~ a и y ~ a
По симметричности: y ~ a ⇒ a ~ y
По транзитивности: x ~ a & a ~ y ⇒ x ~ y
3) Если a ~ b, то Ka = Kb
Пусть x∈Ka
Но по условию a ~ b
Аналогично: Kb ⊆ Ka
, тогда x ~ a
⇒ x∈Kb
⇒ Ka ⊆ Kb
Итак, Ka = Kb

Свойства классов эквивалентности
Пусть ~ – отношение эквивалентности, заданное на X
4) Элементы из разных классов не эквивалентны друг другу
Пусть Ka ≠ Kb
5) Различные классы не пересекаются
Пусть Ka∩Kb≠∅, т.е. ∃x∈Ka∩Kb.
, Тогда x∈Ka и x∈Kb
⇒ Kx = Ka и Kx = Kb
⇒ Ka = Kb
Пусть x∈Ka
Если x ~ y, то
⇒ Kx = Ka
⇒ x ~ a
Пусть y∈Kb
⇒ Ky = Kb
⇒ y ~ b
Kx = Ky
ПРОТИВОРЕЧИЕ
Пусть Ka ≠ Kb.
ПРОТИВОРЕЧИЕ

ТЕОРЕМА
Всякое отношение эквивалентности, заданное на множестве X, определяет разбиение множества X на классы эквивалентности
Доказательство: Пусть ~ – отношение эквивалентности на X
{ Xk | k∈K, Xk⊆X } – множество классов эквивалентности по отношению ~
1) По свойству 1: ∀k∈K Xk ≠ ∅
2) По свойству 5: ∀m,k∈K [ m≠k ⇒ Xm ∩ Xk = ∅ ]

Доказательство ТЕОРЕМЫ
Следовательно, { Xk | k∈K, Xk⊆X } образует разбиение множества X на классы Xk
продолжение
∀a∈X ∃k∈K (a∈Xk)
Теорема доказана

Фактор-множество
Фактор-множеством множества X по отношению эквивалентности R называется множество, каждый элемент которого является одним из классов эквивалентности
Обозначение: X / R
Пример 1: R = { (x,y) | (x-y) кратно 2 } на Z
K0 = 2Z
K1 = 2Z+1
X / R = { 2Z, 2Z+1 }