Задание отношений.

Формально бинарное отношение можно определить, как подмножество декартова произведения: R Í X Y, то есть как множества пар xy между элементами x Î X и y Î Y.

Для задания отношений можно использовать все способы, приведенные выше (перечисление, описание свойств, процедура). Кроме того, для задания отношений используют матричный способ.

Матрица бинарного отношения на множестве X, ÷ X÷ = n - это квадратная матрица C порядка n, в которой элемент c_ij, стоящий на пересечении i - й строки и j - го столбца, определяется следующим образом:

1, если x_i Rx_j

C_ij=

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

Пример 1 .

X = {1,2,3,4,5,6}

Для отношения x < y, x Î X, y Î X матрица 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.

Для отношения "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 1 0 0 1

4 0 1 0 1 0 1

5 0 0 0 0 1 0

6 0 1 1 1 0 1