5. Матричное представление бинарных отношений. Свойства матрицы бинарных отношений.

Бинарное отношение можно задать с помощью матрицы

Рассмотрим конечное множество A и B

A={a₁,a₂,…,a_n}, B={b₁,b₂,…,b_n}

P⊆AxB, P – бинарное отношение

Опр: Матрицей бинарного отношения P называется матрица ||P||=(p_ij) размерности n x m, где n=|A|, m=|B|

Эта матрица содержит полную информацию о связи между элементами множеств A и B и позволяет представить эту информацию в графическом виде.

Заметим, что любая матрица, состоящая из 0 и 1 является матрицей некоторого бинарного отношения

Свойства матриц бинарных отношений

1) P,Q∈AxB, P,Q – бинарные отношения

||P||=(p_ij), ||Q||=(q_ij)

||PUQ||=||P||+||Q||=(p_ij+q_ij)

||P∩Q||=||P||*||Q||=(pij∙qij)

Зам: Сложение элементов матриц осуществляется по правилу

0+0=0, 0+1=1, 1+0=1, 1+1=1

А умножение почленное

0∙0=0, 0∙1=0, 1∙0=0, 1∙1=1

2) P⊆AxB, Q⊆BxC

||P○Q||=||P|∙||Q||

Матрицы перемножаются по обычному правилу умножения матриц, но произведение и сумма при перемножении матриц находится по правилам пункта 1

3) ||P^-1||=||P||^T

4) Если P⊆Q и ||P||=(p_ij), ||Q||=(q_ij) то p_ij<=q_ij ∀i,j

Определение свойств бинарного отношения с помощью матрицы

Пусть P – бинарное отношение на множестве A, P⊆AxA=A²

1) Опр: P – рефлексивно∀x∈A (x,x) ∈P, т.е. тождественное отношение id_A⊆P иликогда главная диагональ ||P|| матрицы бинарного отношения состоит только из единиц

2) Опр: P – симметричноP^-1=P||P||^T=||P||матрица бинарного отношения ||P|| симметрична относительно главной диагонали

3) Опр: P – антисимметричноP∩P^-1⊆id_A||P∩P^-1||=||P||*||P||^T причем ||P∩P^-1|| все элементы вне главной диагонали будут нулевыми, а на главной диагонали могут быть нули

4) Опр: P – транзитивно  P○P⊆P∀i,j q_ij<=p_ij, где ||P○P||=(q_ij), ||P||=(p_ij)

Зам: Свойство не симметричности не совпадает со свойством антисимметричности

6. Отношение Эквивалентности.

Опр. Бинарное отношение на не пустом множестве А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно( ≈,≅,≣,∃)

Примеры:

1) Отношение равенства на числовых множествах

2) Параллельность прямых на плоскости.

3) Подобие треугольника на плоскости

Пусть дано А≠∅, а∊А и задано P-отношение эквивалентности

Опр. Классом эквивалентности порождённым элементом a из множества A называется множество элементов, которые находятся с элементом a в отношением Р

a/p={x|x∊A, x∊PA}=

Def: Множество всех классов эквивалентности, по отношению к Р (отношение эквивалентности) называется фактор-множеством

A/p={x/p|∀x∊A}

Def: Любой элемент класса эквивалентности называется его представителем.

Опр. Разбиением непустого множества А называется совокупность его непустых подмножеств, таких что объединение всех подмножеств есть множество, а пересечение 2 любых различных подмножеств будет пустым

T1 (о разбиение множества на классы)

Пусть Р - отношение эквивалентности на А≠∅. Тогда фактор-множество А\Р является разбиением множества А.

■Т.к Р - отношение эквивалентности, то Р – рефлексивно=> ∀a∊A =>aPa=>(a,a)∊P

a∊a/p={x|x∊A, xPa}=>a/p≠∅

Таким образом =A

Осталось доказать что любые 2 класса эквивалентности не пересекаются.

Достаточно доказать, что если 2 класса имеют хотя бы один общий элемент, то они совпадают.

Пусть c∊a\p, c∊b\p. Возмем ∀x∊a\p. Покажем что x∊b\p

c∊a\p =>cPa, т.к P-симметрично=>aPc

xPa и aPc, т.к. P – транзитивно=>xPc

c∊b/p=>cPb

xPc и cPb, т.к Р транзитивно=>xPb=>x∊b\p

∀x∊a\p=>x∊b\p=>a\p⊆b\p

Аналогично b\p⊆a\p=>a\p≡b\p=>

Таким образом по определению разбиения множествава на классы A\p является разбиением множества А. ■

T2.S-разбиение множества A≠∅

Rs - бинарное отношением на А определенное следующим образом: (x,y)∊Rsкогда эл-ты x,y∊разбиению S.

Тогда Rs соответствующее разбиению S является отношением эквивалентности на А причём А\Rs≡S

■ Необходимо проверить что Rs является отношение эквивалентности, т.е. выполняются 3 свойства.

1)∀a∊A=>∃Mi∊S:a∊Mi=>a, a∊Mi=>(a,a)∊RsилиaRsa=>Rs =>рефлексивно

2)∀a,b∊A и aRsb ∃Mj∊S: a,b∊Mj=>b,a∊Mj=>bRsa=>Rs-симметрично

3)∀a,b,c∊A, aRsb и bRsc∃Mi и Mj∊S: a,b∊Mi, b,c∊ Mj=>b∊Mi∩Mj=>Mi=Mj, т.к Mi и Mj∊S-разбиение Mi∩Mj=∅=>a,c∊Mi=>aRsc=>Rs- транзитивно

Т.о. Rs является отношением эквивалентности => по определению и Т1 фактор множества A/Rs=S■