ОСНОВНЫЕ ТИПЫ (СВОЙСТВА) БИНАРНЫХ ОТНОШЕНИЙ

Пусть задано бинарное отношение R на множестве А²: R Í A ´ A = {(a, b) | a ÎA, b ÎA, (a, b)ÎR}

1. Бинарное отношение R на множестве А называется рефлексивным, если для любого a ÎАвыполняется a R a, то есть (а, а)ÎR. Главная диагональ матрицы рефлексивного отношения состоит из единиц. Граф рефлексивного отношения обязательно имеет петли у каждой вершины.

Примеры рефлексивных отношений: £, =, ³ на множестве действительных чисел, «не быть начальником» на множестве сотрудников.

2. Бинарное отношение R на множестве А называется антирефлексивным (иррефлексивным), если для любого a ÎА не выполняется отношение a R a, то есть (а, а)ÏR. Главная диагональ матрицы иррефлексивного отношения состоит из нулей. Граф иррефлексивного отношения не имеет петель.

Примеры антирефлексивных отношений: <, > на множестве действительных чисел, перпендикулярность прямых на множестве прямых.

3. Бинарное отношение R на множестве Aназывается симметричным, если для любых a, b Î А из a R b следует b R a, то есть если (a, b)Î R, то и(b, a)Î R. Матрица симметричного отношения симметрична относительно своей главной диагонали (σ_ij = σ_ji). Граф симметричного отношения не является ориентированным (рёбра изображаются без стрелок). Каждая пара вершин здесь соединена неориентированным ребром.

Примеры симметричных отношений: ¹ на множестве действительных чисел, «быть родственником» на множестве людей.

4. Бинарное отношение R на множестве Aназывается:

а) антисимметричным, если для любых a, b Î А из a R b и b R a следует, что a = b. То есть, если (a, b)Î R и(b, a)Î R, то отсюда вытекает, что a = b. Матрица антисимметричного отношения вдоль главной диагонали имеет все единицы и не имеет ни одной пары единиц, расположенных на симметричных местах по отношению к главной диагонали. Иными словами, все σ_ii =1, и если σ_ij =1, то обязательно σ_ji =0. Граф антисимметричного отношения имеет петли у каждой вершины, а вершины соединяются только одной направленной дугой.

Примеры антисимметричных отношений:, £, ³ на множестве действительных чисел; Í, Ê на множествах;

б) асимметричным, если для любых a, b Î А из a R b следует невыполнение b R a, то есть если (a, b)Î R, то (b, a)Ï R. Матрица асимметричного отношения вдоль главной диагонали имеет нули (σ_ij =0) все и ни одной симметричной пары единиц (если σ_ij =1, то обязательно σ_ji =0). Граф асимметричного отношения не имеет петель, а вершины соединены одной направленной дугой.

Примеры асимметричных отношений: <, > на множестве действительных чисел, «быть отцом» на множестве людей.

5. Бинарное отношение R на множестве Aназывается транзитивным, если для любых a, b, с Î А из a R b и b R a следует, что и a R с. То есть если (a, b)Î R и(b, с)Î R вытекает, что (а, с)Î R. Матрица транзитивного отношения характеризуется тем, что если σ_ij =1 и σ_jm =1, то обязательно σ_im =1. Граф транзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно есть дуги из первой в третью вершину.

Примеры транзитивных отношений: <, £, =, >, ³ на множестве действительных чисел; «быть начальником» на множестве сотрудников.

6. Бинарное отношение R на множестве Aназывается антитранзитивным, если для любых a, b, с Î А из a R b и b R a следует, что не выполняется a R с. То есть если (a, b)Î R и(b, с)Î R вытекает, что (а, с)Ï R. Матрица антитранзитивного отношения характеризуется тем, что если σ_ij =1 и σ_jm =1, то обязательно σ_im =0. Граф антитранзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно нет дуги из первой в третью вершину.

Примеры антитранзитивных отношений: «несовпадение чётности» на множестве целых чисел; «быть непосредственным начальником» на множестве сотрудников.

Если отношение не обладает некоторым свойством, то, добавив недостающие пары, можно получить новое отношение с данным свойством. Множество таких недостающих пар называют замыканием отношения по данному свойству. Обозначают его как R*. Так можно получить рефлексивное, симметричное и транзитивное замыкание.

Задача 4.10.1. На множестве А = {1, 2, 3, 4} задано отношение R={(a, b)| a, b ÎA, a + b -чётное число}. Определить тип данного отношения.

Решение. Матрица данного отношения:

. Очевидно, что отношение является рефлексивным, так как вдоль главной диагонали расположены единицы. Оно симметрично: σ₁₃ = σ₃₁, σ₂₄ = σ₄₂. Транзитивно: (1,3)ÎR, (3,1)ÎR и (1,1)ÎR; (2,4)ÎR, (4,2)ÎR и (2,2)ÎR и т.д.

Задача 4.10.2. Какими свойствами на множестве А = { a, b, c, d } обладает бинарное отношение R = {(a, b), (b, d), (a, d), (b, a), (b, c)}?

Решение. Построим матрицуданного отношения и его граф:

Отношение иррефлексивно, так как все σ _ii = 0. Оно несимметрично, так как σ₂₃=1, а σ₃₂=0, однако σ₁₂=σ₂₁=1. Отношение нетранзитивно, поскольку σ₁₂=1, σ₂₃=1 и σ₁₃=0; σ₁₂=1, σ₂₁=1 и σ₁₁=0; но при этом σ₁₂=1, σ₂₄=1 и σ₁₄=1.

Задача 4.10.3. На множестве А = {1,2,3,4,5} задано отношение R = {(1,2), (2,3), (2,4), (4,5)}. Определить тип отношения и найти следующие замыкания для R:

а) рефлексивное;

б) симметричное;

в) транзитивное.

Решение. Отношение иррефлексивно, поскольку нет ни одного элемента вида (а, а). Асимметрично, так как не содержит пар вида (a, b) и (b, a) и все диагональные элементы равны 0. Антитранзитивно, поскольку (1,2)ÎR, (2,3)ÎR, но (1,3)ÏR. Аналогично (2,4)ÎR, (4,5)ÎR, а (2,5)ÏR и т.д.

а) рефлексивное замыкание данного отношения R^*={(1,1), (2,2), (3,3), (4,4), (5,5)};

б) симметричное замыкание: R*={(2,1), (3,2), (4,2), (5,4)};

в) транзитивное замыкание: R*={(1,3), (1,4), (2,5)}. Рассмотрим граф исходного отношения и полученного транзитивного.

Задачи для самостоятельного решения.

1. Задано отношение R = {(1,1), (1,2), (1,3), (3,1), (2,3)}. Определить его тип и найти замыкания по рефлексивности, симметричности и транзитивности.

2.Отношение на множестве слов русского языка определено следующим образом: а R b тогда и только тогда, когда они имеют хоть одну общую букву. Определить тип отношения на множестве А = {корова, вагон, нить, топор}.

3. Указать примеры бинарных отношений на множестве А = {1, 2) и В = {1, 2, 3}, которые были бы:

а) не рефлексивное, не симметричное, не транзитивное;

б) рефлексивное, не симметричное, не транзитивное;

в) симметричное, но не рефлексивное и не транзитивное;

г) транзитивное, но не рефлексивное и не симметричное;

д) рефлексивное, симметричное, но не транзитивное;

е) рефлексивное, транзитивное, но не симметричное;

ж) не рефлексивное, симметричное, транзитивное;

з) рефлексивное, симметричное, транзитивное.