1.2. Отношения
Пусть даны два множества – X = {x1, x2, ... , xk, ... ,xn} и
Y = {x1, x2, ... ,xk}.
Самое простое, что можно сказать об элементах этих множеств, — это установить связи между конкретным элементом и конкретным множеством, между двумя данными элементами или множествами.
Мы говорим:
а) элемент x2 принадлежит множеству X, x2 X;
б) элемент x2 принадлежит множеству Y, x2 Y;
в) множество Y является составной частью множества X, Y X, поскольку элементы множества Y и первые k элементов множества X совпадают.
Говорят, что элементы множества могут находиться в некоторых отношениях R между собой, с элементами других множеств или с самими множествами.
В вышеприведенных примерах в первых двух случаях на множествах X и Y задано отношение принадлежности: R = « ».
В последнем примере имеет место отношение включения: R = « ».
Пусть X является множеством целых чисел: X = {1, 2, 3, 4, 5, 6}.
Элементы множества X могут находиться в отношениях: R = « > » — «больше», R = « < » — «меньше», R = « » — «больше или равно», R = « » — «меньше или равно», R = « » — «равно» и R = « » — «не равно».
Другие примеры отношений: «быть братом», «жить в одном доме», «иметь общий делитель, отличный от единицы».
Отношения между парами объектов называют бинарными (двухместными). Они встречаются наиболее часто и хорошо изучены.
В общем виде бинарное отношение может быть записано как xRy, где R – отношение, устанавливающее связь между элементом x X и элементом у Y.
Определение бинарного отношения
Бинарное
отношение R
— это подмножество декартова произведения
множеств X
X, R
X
X, то есть это множество всевозможных
пар (x,x)
между элементами множества X.
Пример. X = {x1, x2, x3} = {1, 2, 3}
X X = {1, 2, 3} {1, 2, 3} = {(x1, x1), (x1, x2), (x1, x3), (x2, x1), (x2, x2), (x2, x3), (x3, x1), (x3, x2), (x3, x3)} = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}.
Отношение R = « » имеет следующий вид:
R = {(x1, x1), (x1, x2), (x1, x3), (x2, x2), (x2, x3), (x3, x3)} = {(1, 1), (1, 2),
(1, 3), (2, 2), (2, 3), (3, 3)}.
Для отношения R = « = » получим:
R = {(x1, x1), (x2, x2), (x3, x3)} = {(1, 1), (2, 2), (3, 3)}.
Часто для задания отношений используют матричный способ.
Матрица бинарного отношения R на множестве X, X = n – это квадратная матрица C порядка n, в которой элемент cij, стоящий на пересечении
i – й строки и j – го столбца, определяется следующим образом:
1, если i R j
Cij =
0, в противном случае
Пример 1. Дано множество X = {1, 2, 3, 4, 5, 6}, на котором задано отношение R = « ».
Для всех x, y X, для которых выполняется x y, матрица C имеет следующий вид:
C
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
2 |
0 |
1 |
1 |
1 |
1 |
1 |
|
3 |
0 |
0 |
1 |
1 |
1 |
1 |
|
4 |
0 |
0 |
0 |
1 |
1 |
1 |
|
5 |
0 |
0 |
0 |
0 |
1 |
1 |
|
6 |
0 |
0 |
0 |
0 |
0 |
1 |
Пример 2. Для отношения R на множестве X: R = «x и y являются чётными числами», x X, y X, матрица C будет иметь следующий вид:
C
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
1 |
0 |
1 |
0 |
1 |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
|
4 |
0 |
1 |
0 |
1 |
0 |
1 |
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
|
6 |
0 |
1 |
0 |
1 |
0 |
1 |