Бинарные отношения и их свойства. Специальные бинарные отношения

Бинарным отношением на множестве А называется подмножество его квадрата RÍ A². Бинарным отношением между множествами А и В называются подмножество принадлежащее декартовому произведению 2-х множеств: RÍ АхВ.

Если упорядоченная пара (а1, а2) принадлежит отношению R, то говорят что а1 R а2, то есть между элементом а1 и а2 уст-но отношение R.

Областью определения бинарного отношения называется множество элементов а, в котором в принадлежит бинарному отношению: þ_R={a|bÎ aRb}.

Областью значения бинарного отношения называют множество b, в котором а принадлежит бинарному значению:

P_R={b|aÎ aRb }.

Обратное отношение для отношения R называется отношение: R^-1={(b,a)|(a,b) Î R }.

Отношение можно задать:

- с помощью любого способа задания множеств

- С помощью матрицы бинарного отношения. Матрица бинарного отношения это квадратная матрица R элементы которой определяются следующим образом rij=1, (ai,aj)Î R, 0 – в противном случае.

- С использованием графа. Каждому бинарному отношению можно подставить в соответствие граф G(X,U), содержащий множество вершин Х, и множество ребер U. При этом вершины aj ai соединяются дугой если упорядоченная пара aj ai Î R. Так как отношения являются множеством упорядоченных пар, то для отношения можно определить те же операции, что и для множеств (объединение, пересечение, разность, дополнение, симметрическая разность).

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

1 ) Рефлексивность. Пусть на множестве А задано бинарное отношение R. Бинарное отношение называется рефлексивным, если для любого элемента А упорядоченная пара из этого элемента принадлежит R: для любого A(a,a) Î R. Т.е. бинарное отношение на множестве называется рефлексивным, если всякий элемент этого множества находится в отношении с самим собой.

Матрица рефлексивного отношения на диагонали содержит 1, а граф бинарного отношения имеет петли.

2) Антирефлексивность. Бинарные отношения являются антирефлексивными, если: для любого A(a,a) Ï R.

Матрица антирефлексивного отношения на диагонали содержит 0, а граф не имеет петель.

3) Симметричность. Бинарное отношение на множестве X называется симметричным, если для каждой пары элементов множества выполнение отношения влечёт выполнение отношения . Отношение симметрично, если .

Матрица симметричного бинарного отношения симметрична относительно главной диагонали. В графе все пары вершин соединены 2-мя противоположно направленными дугами.

4) Антисимметричночть. В математике бинарное отношение на множестве X называется антисимметричным, если для каждой пары элементов множества выполнение отношений и влечёт , или, что то же самое, выполнение отношений и возможно только для равных и .

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

5) Транзитивность. Бинарное отношение называют транзитивным, если:

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

Специальные бинарные отношения:

1) Отношение Эквивалентности на множестве А это отношение, обладающее свойством рефлекисвности, симметричности и транзитивности. (Отношение равенства, отношение параллельности).

2) Отношения строгого порядка: это бинарное отношение на множестве А, обладающее свойствами антирефлексивности, антисимметричности и транзитивности.

3) Отношения нестрого порядка- бинарные отношения, обладающие свойствами рефлексивности. Антисимметричности и транзитивности.