Бинарные операции обозначения

План
лекции

Понятие бинарного отношения

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

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

1 Понятие бинарного отношения

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

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

Если

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

Если

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

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

тогда и только тогда, когда любая пара
(а,
b)
из R1
принадлежит вместе с тем и
R2.

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

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

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

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

Если
A1
= … = An
= А,
то отношение
R, определен­ное
на системе множеств A1,
…, An,
называют 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.