Бинарные отношения. Операции над бинарными отношениями.

Определение. Бинарным отношением R называется подмножество пар (a,b)∈R декартова произведения A×B, т. е. R⊆A×B . При этом множество A называют областью определения отношения R, множество B – областью значений.

Обозначение: aRb (т. е. a и b находятся в отношении R ). /

Замечание: если A = B , то говорят, что R есть отношение на множестве A .

Способы задания бинарных отношений

1. Списком (перечислением пар), для которых это отношение выполняется.

2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a₁ , a₂ ,..., a_n), соответствует квадратная матрица порядка n , в которой элемент c_ij, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между a_i и a_j имеет место отношение R , или 0, если оно отсутствует:

Свойства отношений

Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:

•  рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);

•  антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);

•  симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. c_ij c_ji);

•  антисимметрично, если Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (в матрице такого отношения отсутствуют единицы, симметричные относительно главной диагонали);

•  транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. c_ij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, c_jk = 1 ) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. c_ik = 1 (и, может быть, ещё и в других координатах).

Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.

Решение.

отношение R = {(a,b):a делитель b}:

•  рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;

•  не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;

•  транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.

Задача 3.2. Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.

Отношение R = {(a,b):a - брат b}:

•  не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;

•  не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;

•  не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;

•  транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры

Решение.

Отношение R = {( a,b ) : a - начальник b}:

•  не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
•  не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
•  транзитивно, так как если a начальник b и b начальник c , то a начальник c .

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

Определите свойства отношения R_i , заданного на множестве M_i матрицей, если:

1. R₁ «иметь один и тот же остаток от деления на 5»; M₁ множество натуральных чисел.
2. R₂ «быть равным»; M₂ множество натуральных чисел.
3. R₃ «жить в одном городе»; M₃ множество людей.
4. R₄ «быть знакомым»; M₄ множество людей.
5. R₅ {(a,b):(a-b) - чётное; M₅ множество чисел {1,2,3,4,5,6,7,8,9}.
6. R₆ {(a,b):(a+b) - чётное; M₆ множество чисел {1,2,3,4,5,6,7,8,9}.
7. R₇ {(a,b):(a+1) - делитель (a+b)} ; M₇ - множество {1,2,3,4,5,6,7,8,9}.
8. R₈ {(a,b):a - делитель (a+b),a≠1}; M₈ - множество натуральных чисел.
9. R₉ «быть сестрой»; M₉ - множество людей.
10. R₁₀ «быть дочерью»; M₁₀ - множество людей.

Операции над бинарными отношениями

Пусть R₁, R₁ есть отношения, заданные на множестве A .

• объединение R₁∪ R₂ : R₁ ∪ R₂ = {(a,b) : (a,b) ∈ R₁ или (a,b) ∈ R₂} ;

• пересечение R₁∩ R₂ : R₁ ∩ R₂ = {(a,b) : (a,b) ∈ R₁ и (a,b) ∈ R₂} ;

• разность R₁ \ R₂ : R₁ \ R₂ = {(a,b) : (a,b) ∈ R₁ и (a,b) ∉ R₂} ;

•  универсальное отношение U: = {(a;b)/a ∈ A & b ∈ A}. ;

•  дополнение R₁ U \ R₁, где U = A × A;

• тождественное отношение I : = {(a;a) / a ∈ A};

•  обратное отношение R^-11 : R^-11 = {(a,b) : (b,a) ∈ R₁};

• композиция R₁ º R₂ : R₁ º R₂ : = {(a,b) / a ∈ A&b ∈ B& ∃ c ∈ C : aR₁ c & c R₂b}, где R₁⊂ A × C и R₂⊂ C × B;

Определение. Степенью отношения R на множестве A называется его композиция с самим собой.

Обозначение:

 

Определение. Если R ⊂ A × B , то R º R^-1 называется ядром отношения R .

Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .

Тогда:

1. R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
2. R симметрично ⇔ R = R^-1.
3. R транзитивно ⇔ R º R ⊂ R
4. R антисимметрично ⇔ R ⌒ R^-1 ⊂ I .
5. R антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4. Пусть R - отношение между множествами {1,2,3} и {1,2,3,4}, заданное перечислением пар: R = {(1,1), (2,3), (2,4), (3,1), (3,4)}. Кроме того, S - отношение между множествами S = {(1,1), (1,2), (2,1), (3,1), (4,2)}. Вычислите R^-1, S^-1 и S º R. Проверьте, что ( S º R)^-1 = R^-1, S^-1.

Решение.
R^-1 = {(1,1), (1,3), (3,2), (4,2), (4,3)};
S^-1 = {(1,1), (1,2), (1,3), (2,1), (2,4)};
S º R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)};
(S º R)^-1 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)};
R^-1 º S^-1 = {(1,1), (1,2), (1,3), (2 ,1), (2,2), (2,3)} = (S º R)^-1.

Задача 3.5. Пусть R отношение «...родитель...», а S отношение «...брат...» на множестве всех людей. Дайте краткое словесное описание отношениям:

R^-1, S^-1, R º S, S^-1 º R^-1 и R º R.

Решение.

R^-1 - отношение«...ребёнок...»;

S^-1 - отношение«...брат или сестра...»;

R º S - отношение «...родитель...»;

S^-1 º R^-1 - отношение «...ребёнок...»

R º R - отношение «...бабушка или дедушка...»

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

1) Пусть R - отношение «...отец...», а S - отношение «...сестра...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, R º S, S^-1 º R^-1, R º R.

2) Пусть R - отношение «...брат...», а S - отношение «...мать...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, S º R, R^-1º S^-1, S º S.

3) Пусть R - отношение «...дед...», а S - отношение «...сын...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, R º S, S^-1 º R^-1, S º S.

4) Пусть R - отношение «...дочь...», а S - отношение «...бабушка...» на множе- стве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, S º R, R^-1 º S^-1, R º R.

5) Пусть R - отношение «...племянница...», а S - отношение «...отец...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, S º R, R^-1 º S^-1, R º R.

6) Пусть R - отношение «сестра...», а S - отношение «мать...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, R º S, S^-1 º R^-1, S º S.

7) Пусть R - отношение «...мать...», а S - отношение «...сестра...» на множе- стве всех людей. Дайте словесное описание отношениям:

R^-1, S1, R º S, S1 º R1, S º S.

8) Пусть R - отношение «...сын...», а S - отношение «...дед...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, S º R, R^-1 º S^-1, R º R.

9) Пусть R - отношение «...сестра...», а S - отношение «...отец...» на множе- стве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, R º S, S^-1 º R^-1, S º S.

10) Пусть R - отношение «...мать...», а S - отношение «...брат...» на множестве всех людей. Дайте словесное описание отношениям:

R^-1, S^-1, S º R, R^-1 º S^-1, R º R.