6 Отношения

Определение 17 Подмножество R ? Mn

называется n-местным отношением на

множестве M. Говорят, что a1, . . . , an находятся в отношении R, если (a1, . . . , an) ? R.

Наиболее часто встречаются двухместные отношения, называемые бинарными. Далее

речь будет идти только о них, поэтому слово "бинарные" будем опускать. Если a и b нахо-

дятся в отношении R, то это часто записывается aRb.

Пример 20 Отношение <. Выполняется для пары (2, 5) и не выполняется для (4, ?1).

Отношение "иметь общий делитель, отличный от 1"выполняется для (9, 27), не вы-

полняется для (2, 3).

Отношение среди людей "жить в одном городе" "быть сыном".

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

Для задания отношений можно пользоваться любым способом задания множеств.

Отношения на конечных множествах обычно задаются:

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

2. Матрицей бинарного отношения. Для отношения R, заданного на множестве M =

{a1, a2, . . . , an} это квадратная матрица C порядка m, элементы которой находянтся

по правилу:

cij =

(

1, если aiRaj

0 в противном случае

Задание 8 Задать с помощью матрицы отношение ? на множестве A = {1, 2, 3}

C =

?

?

1 0 0

1 1 0

1 1 1

?

?

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

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

ство

?R = {a|?b(a, b) ? R}.

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

?R = {b|?a(a, b) ? R}

Т.к. отношения являются множествами, то над ними можно проводить все те же операции,

что и над множествами (объединение, пересечение, дополнение, разность).

Пример 21 Отношение "=" является пересечением отношений "?" и "?".

Другие операции над отношениями:

1. Обратное отношение.

R

?1

= {(b, a)|(a, b) ? R}14 Кустицкая Т.А. Дискретная математика

2. Суперпозиция (или произведение) отношений. Пусть R1 ? M2

, R2 ? M2

.

R1 ? R2 = {(a, c)|?b : (a, b) ? R1, (b, c) ? R2}

Пример 22 R1 = {(1, 2), (1, 4), (6, 2)}, R2 = {(2, 3), (4, 5)}

?R1 = {1, 6} ?R1 = {2, 4}

R

?1

1 = {(2, 1), (4, 1), (2, 6)}

R1 ? R2 = {(1, 3), (1, 5), (6, 3)}

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

Бинарное отношение R ? M2

называется:

• полным, если ?a, b ? M, a =6 b aRb или bRa;

• рефлексивным, если ?a ? M aRa

Если M - конечно, то в матрице бинарного отношения по главной диагонали стоят

единицы;

• антирефлексивным, если 6 ?a ? M| aRa

В матрице бинарного отношения по главной диагонали - нули;

• симметричным, если ?a, b ? M aRb ? bRa

Матрица отношения симметрична относительно главной диагонали

• антисимметричным, если aRb, bRa ? a = b

• транзитивным, если ?a, b, c ? M| aRb, bRc ? aRc

Пример 23 Отношение ? на R:

- полное,

- рефлексивно,

- антисимметричное,

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

Задание 9 Исследовать свойства отношений: > на R, "быть сыном", "иметь общий

делитель"на Z

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

Определение 19 Бинарное отношение называется отношением эквивалентности, ес-

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

Если элемент a эквивалентен b, это обозначается a ? b.

Пример 24 •

• Отношение равенства на R.

• Отношение на R: aRb, если f(a) = f(b), где f(x) = x

2

.Кустицкая Т.А. Дискретная математика 15

Определение 20 Пусть на множестве M задано отношение эквивалентности ?. Тогда

множество

C(a) = {x ? M|x ? a}

называется классом эквивалентности элемента a.

Отнесем каждый элемент M к какому-то классу эквивалентности. Совокупность

всех классов эквивалентности на M назовем фактор-множеством M по отношению

эквивалентности

M/ ?= {Ki

, i ? I}

Утверждение 2 Фактор-множество M образует разбиение M

Доказать самостоятельно, пользуясь определениями.

Пример 25 Введем отношение эквивалентности на Z следующим образом: m ? n, если

m?n делится на 2. Множество Z разбирается на 2 класса эквивалентности - множество

четных и множество нечетных чисел.

Пример 26 Отношение эквивалентности на множестве

R2

(т.е. на плоскости), заданное следующим образом: a1 ?

a2, если d(a1) = d(a2), где d(a) - расстояние от точки a до

начала координат. Геометрически классы эквивалентности

представляют собой окружности разных радиусов с центром

в начале координат.