4.4. Основные свойства специальных отношений

Отношение  = < Ф, М > называется отношением рефлексивности, если

(хМ)(х  х).

Другими словами, если для любого элемента хМ истинно высказывание х  х, то  - отношение рефлексивности. Это отношение является унарной операцией, т.е. операцией над одним элементом. Примерами отношения рефлексивности являются отношение равенства и отношение параллельности (x = x, x || x). Очевидно, что отношение перпендикулярности между прямыми х и у не является отношением рефлексивности. Отношение  рефлексивно тогда и только тогда, когда МФ, т.е. когда все точки диагонали принадлежат графику отношений.

Отношение  = < Ф, М > называется отношением антирефлексивности, если

(хМ)(х  х),

т.е. МФ = .

Например, выражения x > x, x  x, x  x являются отношениями антирефлексивности.

Отношение  = < Ф, М > называют отношением симметричности, если

(х,уМ)(х  у  у  х).

Отношение симметричности является бинарной операцией. Например, выражения х=у, ху являются отношением симметричности.

Для графика отношения симметричности справедливо Ф = Ф^-1. Например, a = b  b = a, a b  b  a.

Отношение  = < Ф, М >, Ф  МхМ называется отношением антисимметричности, если

х  у  х  у  (у  х).

Очевидно, что отношение  = < Ф, М > антисимметрично тогда и только тогда, когда

ФФ^-1  М.

Например, высказывания больше, меньше, неравно являются примерами отношений антисимметричности (x > y, x  y).

Отношение  = < Ф, М > называется отношением транзитивности, если

(х,у,zM)( х  у & у  z  x  z).

Например, если х = у & y = z  x = z, то  - отношение транзитивности. Для отношения параллельности справедливо: x  y & y  z  x  z, следовательно, оно является отношением транзитивности.

Для отношения транзитивности (иногда говорят транзитивное отношение) справедливо:

Ф • Ф  Ф.

Примеры:

1. Полное отношение  =<М², М> является транзитивным отношением. Пусть М = <1, 2>, тогда M² = {<1, 2>, <2, 1>, <1, 1>, <2, 2>} и M² • M² = {<1, 1>, <1, 2>, <2, 2>, <2, 1>}, M² • M²  M².

2. Пустое отношение является носителем всех свойств.

Интерес в задачах построенеия информационно-коммуникационных технологий представляют отношения, которые обладают комбинациями свойств.

Отношение  называется отношением эквивалентности, если оно рефлексивно (М  Ф), симметрично (Ф = Ф^-1) и транзитивно (Ф•Ф = Ф). Иногда имея в виду отношения рефлексивности, симметричности, транзитивности и т.п., говорят, что эти отношения соответственно рефлексивности, симметричности, транзитивности и т.п.

    — знак эквивалентности.

Отношение равенства является отношением эквивалентности, т.к. оно рефлексивно(a = a), симметрично (a = b  b = a) и транзитивно (a = b & b = c  a = c) на множестве M={a,b,c}. Отношение параллельности является отношением эквивалентности, т.к. оно рефлексивно (a  a), симметрично (a  b  b  a) и транзитивно (a  b & b  c  a  c) на множестве M={a,b,c}. Отношения больше, меньше, неравно, перпендикулярности и т.п. не являются отношениями эквивалентности, т.к. не обладают в совокупности тремя свойствами рефлексивности, симметричности и транзитивности.

Отношение эквивалентности связано с понятием разбиения множеств.