Бинарное отношение. Бинарные отношения — MT1102: Линейная алгебра (введение в математику) — Бизнес-информатика Отношения на множестве графы отношений свойства отношений

Определение . Бинарным отношением 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 1 , a 2 ,..., 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 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
2. R 2 «быть равным»; M 2 множество натуральных чисел.
3. R 3 «жить в одном городе»; M 3 множество людей.
4. R 4 «быть знакомым»; M 4 множество людей.
5. R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
6. R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
7. R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
8. R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
9. R 9 «быть сестрой»; M 9 - множество людей.
10. R 10 «быть дочерью»; M 10 - множество людей.

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

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

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

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

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

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

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

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

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

композиция R 1 º R 2: R 1 º R 2: = {(a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b}, где R 1 ⊂ A × C и R 2 ⊂ 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 - отношение «...сын...» на множестве всех людей. Дайте словесное описание отношениям:

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

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.

Основы дискретной математики.

Понятие множества. Отношение между множествами.

Множество – совокупность объектов, обладающих определенным свойством, объединенных в единое целое.

Объекты, составляющие множество называются элементами множества. Для того чтобы некоторую совокупность объектов можно было называть множеством должны выполняться следующие условия:

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

· Должно существовать правило, по которому элементы можно отличить друг от друга.

Множества обозначаются заглавными буквами, а его элементы маленькими. Способы задания множеств:

· Перечисление элементов множества. - для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A .

Например: , B =>

Свойство:

Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.

Операции над множествами.

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

Свойство: операции объединения и пересечения.

· Коммутативность.

· Ассоциативность. ;

· Дистрибутивный. ;

Бинарные отношения и их свойства.

Пусть А и В это множества производной природы, рассмотрим упорядоченную пару элементов (а, в) а ϵ А, в ϵ В можно рассматривать упорядоченные «энки».

(а 1 , а 2 , а 3 ,…а n) , где а 1 ϵ А 1 ; а 2 ϵ А 2 ; …; а n ϵ А n ;

Декартовым (прямым) произведением множеств А 1 , А 2 , …, А n , называется мн-во, которое состоит из упорядоченных n k вида .

Н-р: М = {1,2,3}

М× М= М 2 = {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Подмножества декартова произведения называется отношением степени n или энарным отношением. Если n =2, то рассматривают бинарные отношения. При чем говорят, что а 1 , а 2 находятся в бинарном отношении R , когда а 1 R а 2.

Бинарным отношением на множестве M называется подмножество прямого произведения множества n самого на себя.

М× М= М 2 = {(a, b )| a, b ϵ M } в предыдущем примере отношение меньше на множестве М порождает следующее множество: {(1,2);(1,3); (2,3)}

Бинарные отношения обладают различными свойствами в том числе:

· Рефлексивность: .

· Антирефлексивность (иррефлексивность): .

· Симметричность: .

· Антисимметричность: .

· Транзитивность: .

· Асимметричность: .

Виды отношений.

· Отношение эквивалентности;

· Отношение порядка.

v Рефлексивное транзитивное отношение называется отношением квазипорядка.

v Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.

v Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

v Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

Декартовым произведением двух множеств X и Y называется множество всех упорядоченных пар (x , y ) таких, что
, а
.

Пример 1 . Пусть .

Тогда , .

Очевидно, что
, т.е. операция декартова произведения множеств не является коммутативной.

Декартовым произведением множеств
называется множество
всех упорядоченных наборов
таких, чтоЕсли
, то декартово произведение обозначают
.

Будем говорить, что задано соответствие q между множествами X и Y , если задана упорядоченная тройка
, где
.Множество X называется областью отправления, а Y – областью прибытия соответствия q (обозначают
). Каждый элементy в паре
называется образом элементаx (x – прообразом элемента y ) при данном соответствии q .

Соответствие
называетсяотображением множества X во множество Y , если каждый элемент
имеет образ
, т.е..

Отображение
называетсяфункциональным , если каждый элемент
имеетединственный образ
:. Множество образов при данном отображении
обозначается
:.

Если множество
совпадает с множествомY , то говорят, что
осуществляет отображениена множество Y .

Соответствие
называетсявзаимно однозначным (биекцией) , если а) является отображением; б) функционально; в) отображает X «на» множество Y ; г) из условия
следует
.

Другими словами,
является биекцией, если каждый элемент
имеет единственный образ
, а каждый элемент
имеет единственный прообраз
при данном отображении:

(1.2)

1.2.2 Определение бинарного отношения

Определение. Говорят, что на множестве X задано бинарное отношение R , если задано подмножество декартова произведения
(т.е.
).

Пример 2 . Пусть
Зададим наХ следующие отношения:

–отношение равенства;

–отношение предшествования;

делится на – отношение делимости.

Все эти отношения заданы с помощью характеристического свойства. Ниже перечислены элементы этих отношений:

Тот факт, что пара (x , y ) принадлежит данному отношению R , будем записывать:
или xRy . Например, для отношения Q запись 4Q 2 означает, что 4 делится на 2 нацело, т.е.

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

Так, для отношения Р из примера 2 областью определения является множество
, а областью значений –
.

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

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

График отношения изображается в декартовой системе координат; на горизонтальной оси отмечается область определения, на вертикальной – множество значений отношения; элементу отношения (х,у ) соответствует точка плоскости с этими координатами. На рис. 1.7,а) приведен график отношения Q примера 2.

Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент (х,у ) принадлежит отношению R , то соответствующие точки из
и
соединяются отрезком прямой. На рис. 1.7,б) приведена схема отношения Q из примера 2.

Граф отношения
строится следующим образом. На плоскости в произвольном порядке изображаются точки – элементы множестваХ . Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х,у ) принадлежит отношению R . На рис. 1.8,а) приведен граф отношения Q примера 2.

Пусть
. Матрица отношения
имеет n строк и n столбцов, а ее элемент определяется по правилу:

На рис.1.8,б) приведена матрица отношения Q примера 2.

Пусть задано некоторое непустое множество А и R – некоторое подмножество декартова квадрата множества А: R  A  A .

Отношением R на множестве А называют подмножество множества А  А (или А 2 ). Таким образом отношение есть частный случай соответствия, где область прибытия совпадает с областью отправления. Так же, как и соответствие, отношение – это упорядоченные пары, где оба элемента принадлежат одному и тому же множеству.

R  A  A = {(a, b) | aA, bA, (a, b)R}.

Тот факт, что (a , b )R можно записать так: a R b . Читается: «а находится в отношении R к b » или «между а и b имеет место отношение R». В противном случае записывают: (a , b )R или a R b .

Примером отношений на множестве чисел являются следующие: «=», «», «», «>» и т.д. На множестве сотрудников какой-либо фирмы ‑ отношение «быть начальником» или «быть подчинённым», на множестве родственников – «быть предком», «быть братом», «быть отцом» и т.д.

Рассмотренные отношения носят название бинарных (двухместных) однородных отношений и являются важнейшими в математике. Наряду с ними рассматривают также п -местные или п -арные отношения:

R  A  A … A = A n = {(a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n  A}.

Поскольку отношение есть частный случай соответствия, для их задания могут быть использованы все ранее описанные способы.

Очевидно, что задавая отношение матричным способом, мы получим квадратную матрицу.

При геометрическом (графическом) изображении отношения мы получим схему, включающую:

вершины, обозначаемые точками или кружочками, которые соответствуют элементам множества,

и дуги (линии), соответствующие парам элементов, входящих в бинарные отношения, обозначаемые линиями со стрелками, направленными от вершины, соответствующей элементу a к вершине, соответствующей элементу b , если a R b .

Такая фигура называется ориентированным графом (или орграфом) бинарного отношения.

Задача 4.9.1 . Отношение R «быть делителем на множестве M = {1, 2, 3, 4 }» может быть задано матрицей :

перечислением: R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4)};

геометрически (графически) :

1. Выписать упорядоченные пары, принадлежащие следующим бинарным отношениям на множестве А = {1, 2, 3, 4, 5, 6, 7}:

R1 = {(x, y)| x, yA; x + y = 9};

R2 = {(x, y)| x, yA; x < y}.

2. Отношение R на множестве X = {a, b, c, d} задано матрицей

,

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

3. Отношение на множестве А = {1, 2, 3, 4} представлено графом. Необходимо:

перечислить упорядоченные пары, принадлежащие R;

выписать соответствующую матрицу;

определить это отношение с помощью предикатов.

(ответ: a-b= 1).

4.10. Основные типы (свойства) бинарных отношений

Пусть задано бинарное отношение R на множестве А 2 : R  A  A = {(a , b ) | a A, b A, (a , b )R}

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

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

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

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

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

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

Бинарное отношение 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). Граф асимметричного отношения не имеет петель, а вершины соединены одной направленной дугой.

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

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

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

Бинарное отношение 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 чётное число}. Определить тип данного отношения.

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

. Очевидно, что отношение является рефлексивным , так как вдоль главной диагонали расположены единицы. Оно симметрично : σ 13 = σ 31 , σ 24 = σ 42 . Транзитивно : (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. Оно не симметрично , так как σ 23 =1, а σ 32 =0, однако σ 12 =σ 21 =1. Отношение не транзитивно , поскольку σ 12 =1, σ 23 =1 и σ 13 =0; σ 12 =1, σ 21 =1 и σ 11 =0; но при этом σ 12 =1, σ 24 =1 и σ 14 =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.Отношение на множестве слов русского языка определено следующим образом: а Rb тогда и только тогда, когда они имеют хоть одну общую букву. Определить тип отношения на множестве А = {корова, вагон, нить, топор}.

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

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

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

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

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

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

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

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

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

Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями,

т.е. рассмотрим сначала конкретный пример. Пусть на множестве X = {2, 4, 6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества X можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.

Вообще бинарные отношения на множестве X определяют следующим способом:

Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения X х X.

Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.

Условимся отношения обозначать буквами R, S, Т, Р и др.

Если R - отношения на множестве X, то, согласно определению, R X х X. С другой стороны, если задано некоторое подмножество множества X х X, то оно определяет на множестве X некоторое отношение R.

Утверждение о том, что элементы х и у находятся в отношении R, можно записывать так: (х, у) R или x R y. Последняя запись читается: «Элемент х находится в отношении R с элементом у».

Отношения задают так же, как соответствия. Отношение можно задать, перечислив пары элементов множества X, находящиеся в этом отношении. Формы представления таких пар могут быть различными - они аналогичны формам задания соответствий. Отличия касаются задания отношений при помощи графа.

Построим, например, граф отношений «меньше», заданного на множестве Х= (2, 4, 6, 8}. Для этого элементы множества X изобразим точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 1).

На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 2).

Отношение можно задать при помощи предложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «х<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).

Для отношения R, заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «х меньше у», то обратным ему будет отношение «у больше х».

Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько карандашей у Бори?» - ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что переформулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».

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

Мы установили, что бинарное отношение на множестве X представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению ХхХ. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые. Рассмотрим на множестве отрезков, представленных на рис. 3, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 4) и будем их сравнивать.

Видим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли - результат того, что отношение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлексивности или просто, что оно рефлексивно .

Определение. Отношение R на множестве X называется рефлексивным, если о каждом элементе множества X можно сказать, что он находится в отношении R с самим собой.

R рефлексивно на Х <=> xRx для любого х X

Если отношение R рефлексивно на множестве X, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.

Примеры рефлексивных отношений:

Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);

Отношение подобия треугольников (каждый треугольник подобен самому себе).

Существуют отношения, которые свойством рефлексивности на обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе. Поэтому на графе отношения перпендикулярности (рис. 4) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.

Обратим теперь внимание на графы отношений перпендикулярности и равенства отрезков. Они «похожи» тем, что если есть одна стрелка, соединяющая пару элементов, то обязательно есть и другая, соединяющая те же элементы, но идущая в противоположном направлении. Эта особенность графа отражает те свойства, которыми обладают отношения параллельности и равенства отрезков:

Если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;

Если один отрезок равен другому отрезку, то этот «другой» равен первому.

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

Определение. Отношение R на множестве X называется симметричным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у, следует, что и элемент у находится в отношении R с элементом х.

Используя символы, это отношение можно записать в таком виде:

R симметрично на X <=> (xRy => yRx)

Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к х. Справедливо и обратное утверждение. Граф, содержащий вместе с каждой стрелкой, идущей от х к у, и стрелку, идущую от у к х, является графом симметричного отношения.

В дополнение к рассмотренным двум примерам симметричных отношений присоединим еще такие:

Отношение параллельности на множестве прямых (если прямая х параллельна прямой у, то и прямая у параллельна прямой х);

Отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

Существуют отношения, которые свойством симметричности не обладают. Таким, например, является отношение «длиннее» на множестве отрезков. Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Про отношения «длиннее» говорят, что оно обладает свойством антисимметричности или просто антисимметрично.

Определение. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится .

антисимметрично на X <=> (xRy и х≠у => )

Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого соединены только одной стрелкой, есть граф антисимметричного отношения.

Кроме отношения «длиннее» на множестве отрезков свойством антисимметричности, например, обладают:

Отношение «больше» для чисел (если х больше у, то у не может быть больше х);

Отношение «больше на 2» для чисел (если х больше у на 2, то у не может быть больше на 2 числа х).

Существуют отношения, не обладающие ни свойством симметричности, ни свойством антисимметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 5. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.

Обратим внимание еще раз на одну особенность графа отношения «длиннее» (рис. 4). На нем можно заметить: если стрелки проведены от е к а и от а к с , то есть стрелка от е к с ; если стрелки приведены от е к b и от b к с , то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй - длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.

Определение. Отношение R на множестве X называется транзитивным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z.

Используя символы, это определение можно записать в таком виде:

R транзитивно на X <=> (xRy и yRz => xRz)

Граф транзитивного отношения с каждой парой стрелок, идущих от х к у и у к z , содержит стрелку, идущую от х к z . Справедливо и обратное утверждение.

Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z , то отрезок х равен отрезку z . Это свойство отражено и на графе отношения равенства (рис. 4)

Существуют отношения, которые свойством транзитивности не обладают. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку d, а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!

Рассмотрим еще одно свойство отношений, которое называют свойством связанности, а отношение, обладающее им, называют связанным.

Определение. Отношение R на множестве X называется связанным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находится в отношении R с элементом у, либо элемент у находится в отношении R с элементом х.

Используя символы, это определение можно записать в таком виде:

R связанно на множестве X <=> (х≠у xRy или yRx)

Например, свойством связанности обладают отношения «больше» для натуральных чисел: для любых различных чисел х и у можно утверждать, что либо х> у, либо у > х.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые свойством связанности не обладают. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа хну, что ни число х не является делителем числа у, ни число у не является делителем числа х.

Выделенные свойства позволяют анализировать различные отношения с общих позиций - наличия (или отсутствия) у них тех или иных свойств.

Так, если суммировать все сказанное об отношении равенства, заданном на множестве отрезков (рис. 4), то получается, что оно рефлексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности-симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве

отрезков связанными не являются.

Задача 1. Сформулировать свойства отношения R, заданного при помощи графа (рис. 6).

Решение. Отношение R- антисимметрично, так как вершины графа соединяются только одной стрелкой.

Отношение R - транзитивно, так как с парой стрелок, идущих от b к а и от а к с , на графе есть стрелка, идущая от b к с .

Отношение R - связанно, так как любые две вершины соединены стрелкой.

Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет.

Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

Решение. «Больше в 2 раза» - это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число у не больше числа х в 2 раза.

Данное отношение не обладает свойством рефлексивности, потому что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.

Заданное отношение не транзитивно, так как из того, что число х больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.

Это отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у, что ни число не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3,5 и 8 и др.