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

• Название: Лекция. Бинарные отношения и операции над ними
• Дата: 07.02.2022
• Размер: 109.5 Kb.
• Имя файла: бинарные отношения.doc
• Тип: Лекция; #353648

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

Ключевые слова: бинарное отношение, пересечение, объединение, произведение бинарных отношений.
1 Понятие бинарного отношения

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

Определение. Бинарным отношением, определенным на паре множеств А и В, называется любое подмножество их декартова произведения А × В.

Если — бинарное отношение, а упорядоченная пара (а, b), где , , принадлежит R, то это записывают либо (согласно определе­нию), либо R(а, b), либо aRb. Обозначение aRb исхо­дит из обозначений вида а = b, а < b, и др.

Если — бинарное отношение и А = В, то R называют бинарным отношением, определенным на множестве А.

Два бинарных отношения R₁ и R₂ равны тогда и только тогда, когда любая пара (а, b) из R₁ принадлежит вместе с тем и R₂, и обратно: любая пара (а, b) из R₂ принадлежит и R₁. Аналогично, тогда и только тогда, когда любая пара (а, b) из R₁ принадлежит вместе с тем и R₂.

Определение. Пусть — бинарное отношение, определенное на паре множеств А, В. Областью определения отношения R называется совокупность всех таких , что хотя бы для одного . Областью значений отношения R называют множество всех таких , что хотя бы для одного элемента .

Пусть А — произвольное множество. Множество А×A называют универсальным отношением, определенным на множестве А; любая пара (a₁, a₂), где , находится в этом отношении, поэтому его называют иногда всюду истинным отношением. Пустое подмножество множества А² называют пустым отношением; ни одна из пар множества А² не находится в этом отношении, поэтому оно называется еще всюду ложным отношением. Отношение равенства, определенное на множестве А, совпадает с множеством так называемых диагональных пар: (а, а), где , и обозначается е_A или просто е, если ясно, какое множество А рассматривается.

По аналогии с понятием бинарного отношения вводится и понятие n-арного (n-местного) отношения.

Определение. Пусть A₁, …, A_n — непустые множества. Всякое подмножество R их декартового произведения А₁×A_n называется отношением, определен­ным на системе множеств A₁, …, A_n.

Если A₁ = … = A_n = А, то отношение R, определен­ное на системе множеств A₁, …, A_n, называют n-арным (n-местным) отношением, определенным на множестве А.

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

Так как бинарные отношения, определенные на фиксированной паре множеств А, В, являются подмножествами А×В, то над ними можно производить операции объединения, пересечения и дополнения (в множестве А×В). Так, если R, S — два бинарных отношения, опре­деленных па паре множеств А, В, то для любых , тогда и только тогда, когда aRb или aSb; тогда и только тогда, когда aRb и aSb; тогда и только тогда, когда не aRb.

Помимо теоретико-множественных операций над отношениями важное значение имеют еще две операции над ними: обращение и умножение отношений.

Определение. Пусть — бинарное отношение, определенное на паре множеств А, В. Отношением, обратным к бинарному отношению R, называется отношение, определенное на паре множеств В и А и состоящее из всех тех и только тех пар (b, а), для ко­торых ( , ).

Бинарное отношение, обратное к отношению R, обозначается R^–1. Таким образом, .

Если R — бинарное отношение «х является родителем у», то R^–1 — отношение «х является ребенком (сыном или дочерью) у».

Определение. Пусть — бинарное отношение, определенное на паре множеств А, В, а — бинарное отношение, определенное на паре множеств В, С. Произведением отношений R и Sназывается бинарное отношение, определенное на паре множеств А и С и состоящее из всех тех и только тех пар (а, с) ( , ), для которых существует элемент х из В такой, что aRx и xSc.

Произведение бинарных отношений и обозначим через RS. Таким образом, и a(RS)c тогда и только тогда, когда существует элемент такой, что aRx и xSc.

Теорема 1. Пусть , , — бинарные отношения. Тогда произведения (RS)T и R(ST)определены и (RS)T = R(ST). То есть умножение бинарных отношений ассоциативно.

Теорема 2. Пусть , — бинарные отношения. Тогда выражения (RS)^–1 и S^–1R^–1 определены и имеет место равенство (RS)^–1 = S^–1R^–1.

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

Бинарное отношение R, определенное на множестве А, называется:

- рефлексивным, если для любого aRa;

- антирефлексивным, если для любого не выполняется aRa;

-симметричным, если для любых из аRb следует bRa;

- антисимметричным, если аRb и bRa влекут a=b.

- транзитивным, если для любых из aRb и bRс следует аRс.

Например, отношение ≤ на множестве R действительных чисел, а также отношение включения подмножеств некоторого множества являются рефлексивными и транзитивными, но не являются симметричными. Отношение < на множестве действительных чисел транзитивно, но не рефлексивно, не симметрично. Отношение «х является матерью у» не рефлексивно, не симметрично, не транзитивно.
2 Виды бинарных отношений

Определение. Бинарное отношение R, определенное на множестве А, называется отношением эквивалентности или просто эквивалентностью на множестве А, если R рефлексивно, симметрично и транзитивно.

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

1. 
   отношение равенства в произвольной системе множеств;
   
2. 
   отношение равночисленности, т.е. иметь одинаковое число элементов, в системе конечных множеств;
   
3. 
   отношение «учиться в одной группе» в множестве студентов лесопромышленного факультета;
   
4. 
   пусть F: A → B — отображение. Отношение σ, определяемое следующим образом: , является отношением эквивалентности на А. Оно называется ядерной эквивалентностью отображения F.