Пусть r задано на множестве X, r Í Х2
- Рефлексивность: " х Î Х (x, x) Î r.
- Антирефлексивность: " х Î Х (x, x) Ï r.
- Нерефлексивность: $ х Î Х (x, x) Ï r.
- Симметричность: " х, y Î Х (x, y) Î r => (y, x) Î r.
- Антисимметричность: " х, y Î Х (x, y) Î r, (y, x) Î r => x = y.
- Транзитивность: " х, y, z Î Х (x, y) Î r, (y, z) Î r => (x, z) Î r.
- Отношение порядка: антисимметрично, транзитивно.
Отношение нестрого порядка - рефлексивно, антисимметрично, транзитивно.
Отношение строгого порядка – антирефлексивно, антисимметрично, транзитивно.
В отношениях полного порядка все элементы сравнимы между собой, а в отношениях частичного порядка не все элементы сравнимы между собой.
- Отношение эквивалентности (~) - рефлексивно, симметрично, транзитивно.
Класс эквивалентности для х: [ x ] = { yÎ Х | x ~ y }
- Обратное отношение получается путём перестановки значений в парах исходного отношения.
- Композиция отношений r и g -отношение, состоящее из пар r ○ g = {(x, z)| х r у, y g z }
Пример1:
|
|
Отношения r и g заданы на множестве Х = {1, 2, 3, 4, 5, 6,}.
r = {(1,4), (2,5), (3,6), (4,1), (6,3)},
g = {(1,1), (2,3), (3,4), (4,5), (5,6), (6,6)}.
Область определения Dom(r) = {1, 2, 3, 4, 6}.
Область значений Im ( r) = {1, 3, 4, 5, 6}.
Обратное отношение r-1 = {(4,1), (5,2), (6,3), (1,4), (3,6)}.
Отношение r - антирефлексивно, не симметрично, не транзитивно.
Область определения Dom(g)= {1, 2, 3, 4, 5, 6}.
Область значений Im ( g) = {1, 3, 4, 5, 6}.
Отношение g - не рефлексивно, антисимметрично, не транзитивно.
Композиция r ○ g = {(1,5), (2,6), (3,6), (4,1), (6,4)}.
Пример2:
Отношение r= { (x, y) | сравнение по модулю m, x,y Î N }.
Отношение сравнения по модулю m на множестве натуральных чисел:
x = y mod m,
что означает, что x и y имеют одинаковый остаток при делении на m
(классы вычетов по модулю m).
Отрезок натурального ряда N4={1,2,3,4}.
Отношение сравнения по модулю 2 на N4 :
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 заданы на множестве N4.
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 }.