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

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

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] складываются и умножаются по правилам из свойства 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 Если - дополнение Р, то [ ] равна матрице отношения Р, в которой нули заменены единицами и единицы нулями.

Пример 1.2.5 -

, , тогда ;

; ;

, .

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

а) рефлексивным a A (a,a) P;

б) антирефлексивным a A (a,a) P или [(a,b) P a≠b];

в) симметричным a,b A (a,b) P (b,a) P;

г) антисимметричным a,b A (a,b) P и (b,a) P a=b;

д) транзитивным a,b,c A (a,b) P и (b,с) P (a,c) P.

Заметим, что если

а) P-рефлексивное I P, [P]= ;

б) P – симметричное P=P^-1, [P]=[P]^T;

в) Р - антисимметричное Р Р^-1 I, [P P^-1]=[P]*[P^-1], все элементы последней матрицы вне главной диагонали равны 0;

г) P- транзитивное P P P, т.е. если [P P]=(a_ij), [P]=(p_ij), то a_ij≤p_ij.

Пример 1.2.6 - Проверим, какими свойствами обладает отношение P = {(1,2),(2,3),(3,2)} A², А = {1,2,3}. Составим матрицу этого отношения [P]= . P не рефлексивное, т.к. на главной диагонали матрицы нет единиц; P не симметричное, т.к. (1;2) P, но (2;1) P или [P]≠[P]^T; P не антисимметричное, т.к. (2;3) P, (3;2) P, но 2≠3, или в матрице не все элементы вне главной диагонали нули; P не транзитивное, т.к., например, (1,2) P, (2,3) P, но (1,3) P.

Пример 1.2.7 - Дано отношение P={(x;y)|x-y<1; x,y Z}.

а) Р рефлексивное, т.к. (x;x) P(x-x=0<1);

б) Р не симметричное, т.к., например, (2;4) P, (4;2) P;

в) P антисимметричное, т.к. из (x-y)<1, y-x<1 следует x=y, потому, что если x≠y, то при x<y→x-y<0, при x>y→x-y>0, т.е. >0→ ≥1;

г) P транзитивное, т.к. x-y<1, y-z<1 →x-z<1, действительно:

x-y<1

⁺y-z<1 x-z=1

x-z<2 x-z<1,

но x-z=1 противоречит условию x-y<1, остаётся x-z<1.

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

Дата добавления: 2014-12-27