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

R_S = {y ç$ x: x S y}.

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

M_S = D_S ÈR_S.

Пример 2.9. Пусть S = {<1, 3>, <3, 3>, <4, 2>}. Тогда D_S = {1, 3, 4}, R_S = {3, 2},
M_S= {1, 2, 3, 4}.

Среди отношений на множествах особую роль играют бинарные отношения между элементами одного множества, т.е. S Í X². Их называют бинарными отношениями на множестве X.

Бинарное отношение для конечного множества может быть задано матрицей бинарного отношения. Пусть А = { a ₁, a ₂, …, a_n } – конечное множество. Матрица бинарного отношения C есть квадратная матрица порядка n, элементы которой c_ij определяются следующим образом:

c_ij =

Пример 2.10. А = {1, 2, 3, 4}. Зададим бинарное отношение S тремя перечисленными способами.

1. S = {<1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>} – отношение задано перечислением всех упорядоченных пар.

2. S = {< a_i, a_j > ç a_i < a_j; a_i, a_j Î А } – отношение задано указанием свойства "меньше" на множестве А.

3. – отношение задано матрицей бинарного отношения C.

Пример 2.11. Рассмотрим некоторые бинарные отношения.

1. Отношения на множестве натуральных чисел.

а) отношение £ выполняется для пар <1,2>, <5,5>, но не выполняется для пары <4,3>;

б) отношение "иметь общий делитель, отличный от единицы" выполняется для пар <3, 6>, <7, 42>, <21, 15>, но не выполняется для пары <3, 28>.

2. Отношения на множестве точек действительной плоскости.

а) отношение "находиться на одинаковом расстоянии от точки (0, 0)" выполняется для точек (3, 4) и (–2, Ö21), но не выполняется для точек (1, 2) и (5, 3);

б) отношение "быть симметричным относительно оси OY " выполняется для всех точек (x, y) и (– x, – y).

3. Отношения на множестве людей.

а) отношение "жить в одном городе";

б) отношение "учиться в одной группе";

в) отношение "быть старше".

Бинарные отношения на плоскости можно отобразить с помощью графов. Элементы множества M_S обозначаются вершинами графов. Если для a Î M_S, bÎ M_S aSb, то вершины а и b соединяются стрелкой (дугой).

Пример 2.12. Графическое изображение отношений из рассмотренных выше примеров приведено на рис. 2.1.

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

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

Отношение S называется рефлексивным на множестве X, если для любого x Î X выполняется x S x, т.е. (" x),(x, x)Î S.

а) Граф отношения из примера 2.9	b) Граф отношения из примера 2.10
с) Граф отношения «быть равными» на множестве {1, 2, 3,4}	d) Граф отношения «иметь общий делитель» на множестве {2, 3,4, 6}

Рис. 2.1. Графы бинарных отношений

В матрицах рефлексивных отношений на главной диагонали стоят единицы. У графа такого отношения все вершины имеют петли.

Пример 2.13. Рефлексивными являются отношения «быть равными» (рис. 2.1 с), «быть не меньше», «иметь общий делитель» (рис. 2.1 d) на множестве чисел; «быть подмножеством» на множестве множеств, «жить в одном городе» на множестве людей.

Отношение S называется нерефлексивным на множестве X, если ($ x),
(x, x)Ï S и антирефлексивным если. (" x),(x, x)Ï S.

Отношение S называется симметричным на множестве X, если для любых x, y Î X из xSy следует yS x.

Матрицы симметричных отношений симметричны (равны транспонированным). У графа такого отношения все дуги имеют встречные.

Пример 2.14. Симметричными являются отношения «быть равными» (рис. 2.1 с), «быть не меньше», «иметь общий делитель» (рис. 2.1 d) на множестве чисел; «быть подмножеством» на множестве множеств, «жить в одном городе» на множестве людей.

Отношение S называется антисимметричным на множестве X, если для любых x, y Î X из x S y и y S x следует x = y.

Отношение S называется асимметричным на множестве X, если ни для одной пары x, y Î X не выполняется одновременно x S y и y S x.

Пример 2.15. а) Пусть X – конечное множество, X = {1, 2, 3} и r = {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>}. Отношение S антисимметрично.

б) Отношение G = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 3>, <3, 3>} не антисимметрично. Например, <1, 2> Î G, и <2, 1> Î G, но 1 ¹2.

в) На множество действительных чисел отношение £ (меньше или равно) антисимметрично.

г) На множество действительных чисел отношение > (больше) асимметрично.

Отношение S называется транзитивным на множестве X, если для любых
x, y, z Î X из xSy и yS z следует xSz.

Одновременное выполнение условий xSy, yS z, xS z означает, что пара
< x, z > принадлежит композиции S S. Поэтому для транзитивности S необходимо и достаточно, чтобы множество S S являлось подмножеством S, т. е. S S Í S.

Пример 2.16. а) Пусть X – конечное множество, X = {1, 2, 3} и S = {<1,1>,
<1 2>,<2,3>, <1, 3>}. Отношение S транзитивно, т. к. наряду с парами < x, y >и < y, z >имеется пара< x, z >. Например, наряду с парами <1,2>, и <2,3> имеется пара <1,3>.

б) На множестве действительных чисел отношение £ (меньше или равно) транзитивно, т.к. если x £ y и y £ z, то x £ z.

в) Пусть X – множество людей, отношение "быть старше" транзитивно, т.к. если x старше y и y старше z, то x старше z.

Отношение S называется отношением эквивалентности на множестве X, если оно рефлексивно, симметрично и транзитивно на множестве X.

Пример 2.17. Отношениями эквивалентности являются отношение равенства на множестве чисел, отношение "учиться в одной группе" на множестве студентов.

Пусть S – отношение эквивалентности на множестве X и x Î X. Классом эквивалентности, порожденным элементом x, называется подмножество множества X, состоящее из тех элементов y Î X, для которых xSy. Класс эквивалентности, порожденный элементом x, обозначается через [ x ].

Классы эквивалентности образуют разбиение множества X, т. е. систему непустых попарно непересекающихся его подмножеств, объединение которых совпадает со всем множеством X.

Пример 2.18. а) Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого элемента x из этого множества [ x ] = { x }, т.е. каждый класс эквивалентности состоит из одного элемента.

б) Класс эквивалентности, порожденный парой < x, y > определяется соотношением: [< x, y >] = . Каждый класс эквивалентности, порожденный парой < x, y >, определяет одно рациональное число.

в) Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы.

Отношение S называется отношением толерантности на множестве X, если оно рефлексивно, симметрично на множестве X.

Отношение S называется отношением частичного порядка (или просто частичным порядком) на множестве X, если оно рефлексивно, антисимметрично и транзитивно на множестве X. Множество X в этом случае называют частично упорядоченным и указанное отношение принято обозначать символом , а, если это не приводит к недоразумениям, то £.

Пример 2.19. а) Пусть X = {1, 2, 3} и S = {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>,
<3, 3>}. Отношение S есть отношение частичного порядка.

б) Отношение А Í В на множестве подмножеств некоторого множества U есть отношение частичного порядка.

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

Примеры тестовых заданий

ЗАДАНИЕ N 2.1 (- введите ответ)
Отображение f множества всех целых чисел в себя определяется формулой . Тогда число элементов образа множества при этом отображении равно …

ВАРИАНТЫ ОТВЕТОВ:

Решение. Найдем образы всех элементов исходного множества:

f (-6)=|-6|-3=3, f (-5)=|-5|-3=2, f (-4)=|-4|-3=1, f (-3)=|-3|-3=0, f (-2)=|-2|-3=-1,
f (-1)=|-1|-3= -2, f (0)=|0|-3= -3, f (1)=|1|-3= -2, f (2)=|2|-3= -1, f (0)=|3|-3= 0.

Т.о. образом заданного множества будет множество {-3, -2, -1, 0, 1, 2, 3}, которое состоит из семи элементов.

Заметим, что можно было учесть четность функции, задающей отображение, и из числа элементов исходного множества (10) вычесть число симметричных относительно нуля элементов в прообразе (-3 и 3б -2 и 2, -1 и 1): 10-3=7.

ЗАДАНИЕ N 2.2 (- выберите один вариант ответа)
Образом отрезка при отображении является…

ВАРИАНТЫ ОТВЕТОВ:

1)	(– 1; 83)		2)	(5; 83)
3)	[– 1; 83]		4)	[9; 81]

Решение. Поскольку f`(x)=(3x<sup>3</sup>+2)`= 6x² ≥0, то функция монотонна на области определения, в т.ч. на [-1; 3]. Из ее непрерывности вытекает, что образом отрезка является отрезок, конца которого являются образами концов заданного отрезка:
f`(-1)=3∙ (-1)<sup>3</sup>+2=-3+2= -1; f`(3)=3∙(3)³+2=81+2= 83. Образом отрезка [-1; 3] является отрезок [-1; 83]. Верный ответ 3).

ЗАДАНИЕ N 2.3 (- выберите несколько вариантов ответа)
Бинарная алгебраическая операция на множестве не обладает свойством коммутативности, если …

ВАРИАНТЫ ОТВЕТОВ:

1)			2)
3)			4)

Решение. Коммутативность бинарной операции по определению состоит в выполнении равенства T(x,y)=T(y,x) для всех x, y из области определения. Проверим выполнение этого равенства для заданных операций:

; ; ; ;

Т.о. 1-я и 2-я из операция не обладает свойством коммутативности, а 3-я и4-я обладают. Верный ответ 1) 2).

ЗАДАНИЕ N 2.4 (- выберите один вариант ответа)
Свойством транзитивности облает бинарное отношение…

ВАРИАНТЫ ОТВЕТОВ:

1)	«иметь разный рост»		2)	«быть перпендикулярными»
3)	«быть параллельными		4)	«быть отцом»

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

1) Если А и В имеют разный рост (например, 179 и 175 см) и В и С имеют разный рост, то в случае, когда рост С 179 см, А и С имеют одинаковый рост. Т.о. отношение 1 нетранзитивно.

2) Рассмотрим прямые L₁, L₂ , L₃ на плоскости. Если L₁ ┴ L₂, а L₂ ┴ L₃, то L₁ || L₃. Т.о. отношение 2 нетранзитивно.

3) Рассмотрим прямые L₁, L₂ , L₃ на плоскости или в пространстве. Если L₁ || L₂, а
L₂ || L₃, то L₁ || L₃. Т.о. отношение 3 транзитивно.

4) Если А отец В, а В отец С, то А -дед С, но не отец. Т.о. отношение 4 нетранзитивно.

Верный ответ 3).

ЗАДАНИЕ N 2.5 (- выберите один вариант ответа)
Бинарное отношение , обладает свойствами …

ВАРИАНТЫ ОТВЕТОВ:

1)	симметричности и транзитивности	2)	рефлексивности и транзитивности
3)	рефлексивности и симметричности	4)	антирефлексивности и симметричности

Решение. Проверим рефлексивность заданного отношения: , т.е. " хÎR xRx, отношение рефлексивно. Проверим симметричность: если , то поскольку получим: , отношение симметрично. Проверим транзитивность: пусть х =4, у =3, z =2. Имеем: , , , т.е. для выбранных значений x, y, z отношение транзитивным не является, т.о. оно нетранзитивно. Верный ответ 3).

ЗАДАНИЕ N 2.6 (- выберите несколько вариантов ответа)
Отношение «быть меньше» на множестве действительных чисел является…

ВАРИАНТЫ ОТВЕТОВ:

1)	симметричным		2)	антирефлексивным
3)	рефлексивным		4)	транзитивным

Решение. Проверим рефлексивность заданного отношения: неравенство x<x неверно " хÎR, отношение антирефлексивно. Проверим симметричность: если x<y, то неравенство y<x неверно " х, yÎR, отношение несимметрично (асимметрично). Проверим транзитивность: пусть x<y, у<z, тогда очевидно, что x<z. Отношение транзитивно. Верный ответ 2) и 4).

Комбинаторика