4. Основные свойства матриц бинарных отношений. Свойства бинарных отношений (рефлексивность, симметричность, антисимметричность, транзитивность).

1. Пусть P,Q A×B, [P]=(p_i,j), [Q]=(q_i,j).

[P Q]=(p_ij+q_ij)=[P]+[Q], где элементы матриц складываются по правилам:

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

[P Q]=(p_ij*q_ij)=[P]*[Q], где умножение элементов матриц происходит по правилам: 0*0=0*1=0*1=0, 1*1=1.

2 Если P A×B, Q B×C, то [P Q]=[P]•[Q] - обычное умножение матриц, но элементы матриц [P] и [Q] складываются и умножаются по правилам из св-ва 1.

3 Если P^-1 – обратное P, то [P^-1]=[P]^T.

4 P Q и [P]=(p_ij), [Q]=(q_ij), тогда p_ij≤q_ij.

5 I–тождественное отношение, то - единичная матрица.

6 - дополнение Р, то [ ] равна матрице отношения Р, в которой нули заменены единицами и единицы нулями.

Свойства отношений

Пусть P A². Отношение Р называется:

а) рефлексивным  aЄA, (a,a)ЄP; {единицы на главной диагонали}

б) симметричным  (a,b)ЄP,=> (b,a)ЄP; {[P]=[P]^T}

в) антисимметричным  (a,b)ЄP и (b,a)ЄP=>a=b; {все элементы вне главной диагонали равны 0}

г) транзитивным  (a,b)ЄP и (b,с)ЄP=> (a,c)ЄP.

{P P P т.е. если [P P]=(a_ij), [P]=(p_ij), то a_ij≤p_ij.}

5. Отношение эквивалентности. Классы эквивалентности. Фактор-множество

Определение. P называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (обозначается ~, E, ≡).

 Примеры отношений эквивалентности: а) отношение равенства на любом множестве: 1)x=x; 2) x=y→y=x; 3) x=y; y=z → x=z; б) отношение подобия на множестве треугольников.

Определение. Пусть Е – отношение эквивалентности на множестве А и хЄА. Подмножество элементов множества А, эквивалентных x, называется классом эквивалентности элемента х. Обозначается: [x]_E; E(x). Таким образом, E(x)={y | yEx}.

Определение. Множество классов эквивалентности называется фактор – множеством множества А относительно эквивалентности Е, обозначается А/Е: А/Е={E(x)| xЄA}. Фактор – множество  является подмножеством булеана.

Пример. А – множество студентов в институте. Е – отношение принадлежности  к одной группе. [x]_E- студенты одной группы. А/Е – множество студенческих групп института.

Из определений ясно, что 1) любой элемент класса эквивалентности порождает класс эквивалентности, т.е. bЄ[a]→[a]=[b]; 2) каждый класс эквивалентности содержит хотя бы один элемент, т.е. аЄА  [a]≠Ø; 3) никакой элемент множества А не может принадлежать двум различным классам: aEb => [a]=[b].

Теорема. Фактор – множество А/Е является разбиением множества А. Обратно, если А={Ai} какое-то разбиение множества А, то ему соответствует некоторое отношение эквивалентности Е: xEyx, yЄA_i  для некоторого i.

Таким образом, существует взаимно однозначное соответствие между множеством всех разбиений множества А и множеством всех отношений эквивалентности на множестве А.

Пример. А={1,2,3,4}.А ={{1},{2,3,4}}={A₁,A₂}-разбиение А.

E={(x;y)|x,yЄA_i,i=1,2}={(1,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,2),(4,3),(4,4)}- отношение эквивалентности, соответствующее данному разбиению.  

Пример 1.3.3 - A={1,2,3,4,5,6}, P A², P={(1;1);(2;2);(3;3);(4;4);(5;5);(6;6); (1;2);(1;4);(2;1);(2;4);(3;5);(5;3);(4;1);(4;2)}. Покажем, что данное отношение является отношением эквивалентности. По его матрице [P]= определяем, что P-рефлексивно, симметрично, транзитивно (см. выше),  следовательно, Р есть отношение эквивалентности на множестве А. Построим классы эквивалентности и фактор – множество: [1]_P={x | (x;1)ЄP}={1,2,4}; [2]_P={x | (x;2)ЄP}={1,2,4}; [3]_P={x | (x;3) ЄP}={3,5}; [4]_P={x | (x;4)ЄP}={1,2,4}; [5]_P={x | (x;5) ЄP}={3,5}; [6]_P={x | (x;6)ЄP}={6}.

Таким образом, имеется только три различных класса эквивалентности [1]=[2]=[4]={1,2,4}, [3]=[5]={3,5}, [6]={6}. Фактор – множество A/Р= {[1],[3],[6]}= {{1,2,4},{3,5},{6}} является разбиением множества А, которое  соответствует данному отношению эквивалентности.