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

Пусть P задано на множестве X, P Í Х²

- Рефлексивность: " х Î Х (x, x) Î P.

- Антирефлексивность: " х Î Х (x, x) Ï P.

- Нерефлексивность: $ х Î Х (x, x) Ï P.

- Симметричность: " х, y Î Х (x, y) Î P => (y, x) Î P.

- Антисимметричность: " х, y Î Х (x, y) Î P, (y, x) Î P => x = y.

- Транзитивность: " х, y, z Î Х (x, y) Î P, (y, z) Î P => (x, z) Î P.

- Отношение порядка: антисимметрично, транзитивно.

Отношение нестрого порядка - рефлексивно, антисимметрично, транзитивно.

Отношение строгого порядка – антирефлексивно, антисимметрично, транзитивно.

В отношениях полного порядка все элементы сравнимы между собой, а в отношениях частичного порядка не все элементы сравнимы между собой.

- Отношение эквивалентности (~) - рефлексивно, симметрично, транзитивно.

Класс эквивалентности для х: [ x ] = { yÎ Х | x ~ y }

- Обратное отношение получается путём перестановки значений в парах исходного отношения.

- Композиция отношений P и Q -отношение, состоящее из пар P ○ Q = {(x, z)| х P у, y Q z }

Пример1:

Отношения P и Q заданы на множестве Х = {1, 2, 3, 4, 5, 6,}.

P = {(1,4), (2,5), (3,6), (4,1), (6,3)},

Q = {(1,1), (2,3), (3,4), (4,5), (5,6), (6,6)}.

Область определения Dom(P) = {1, 2, 3, 4, 6}.

Область значений Im ( P) = {1, 3, 4, 5, 6}.

Обратное отношение P^-1 = {(4,1), (5,2), (6,3), (1,4), (3,6)}.

Отношение P - антирефлексивно, не симметрично, не транзитивно.

Область определения Dom(Q)= {1, 2, 3, 4, 5, 6}.

Область значений Im ( Q) = {1, 3, 4, 5, 6}.

Отношение Q - не рефлексивно, антисимметрично, не транзитивно.

Композиция P ○ Q = {(1,5), (2,6), (3,6), (4,1), (6,4)}.

Пример2:

Отношение P= { (x, y) | сравнение по модулю m, x,y Î N }.

Отношение сравнения по модулю m на множестве натуральных чисел:

x = y mod m,

что означает, что x и y имеют одинаковый остаток при делении на m

(классы вычетов по модулю m).

Отрезок натурального ряда N₄={1,2,3,4}.

Отношение сравнения по модулю 2 на N₄ :

d = { (1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)}.

Область определения Dom(d)= {1, 2, 3, 4}.

Область значений Im(d)= {1, 2, 3, 4}.

Отношение d - рефлексивно, симметрично, транзитивно.

Отношение d - отношение эквивалентности.

Классы эквивалентности: [ 1 ]={ 1,3 }=[ 3 ]

[ 2 ]={ 2,4 }=[ 4 ].

Пример3:

Отношения j и n заданы на множестве N_4.

j ={ (1,2), (2,3), (1,3), (3,4), (2,4), (1,4) }

n={ (1,1),(2,2),(3,3),(4,4) }.

Область определения Dom(j) = { 1, 2, 3 }.

Область значений Im(j) = { 2, 3, 4 }.

Отношение j - антирефлексивно, антисимметрично, транзитивно.

Отношение j - отношение строгого порядка.

Область определения Dom(n) = { 1, 2, 3,4 }.

Область значений Im(n) = { 1, 2, 3, 4 }.

Отношение n - рефлексивно, симметрично, антисимметрично, транзитивно.

Отношение n - отношение нестрогого частичного порядка.

Отношение n - отношение эквивалентности.

Классы эквивалентности: [ 1 ]={ 1 }

[ 2 ]={ 2 }

[ 3 ]={ 3 }

[ 4 ]={ 4 }.