Бинарные отношения. Основные понятия

Бинарным отношением R называется подмножество пар (a,b)ÎR прямого произведения M₁ × M₂ , т.е. R Í M₁ × M₂. При этом множество M₁ – называется областью определения отношения R, обозначается D(R):

D(R) = {a : (a,b) Î R}.

Множество M₂ – называется областью значения отношения R, обозначается Q(R):

Q(R) = {b : (a,b) Î R}.

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

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

2. Матрицей – бинарному отношению R M × M , где M = {a₁, ₂, …a_n} соответствует квадратная матрица порядком n, в которой элемент C_ij , стоящий на пересечении i – ой строки и j – ого столбца равен 1, если между a_i и a_j имеет место отношения R, или 0, если оно отсутствует:

Пример:

Задать списком и матрицей отношение RÍ M × M , где M={1, 2, 3, 4, 5}, eсли R означает “ быть не больше “.

R= {a,b) : a,b Î M ; a ≤ b}

R={(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5)}.

Пример:

Пусть M={1, 2, 3, 4, 5, 6}. Составить матрицу отношения RÍ M × M, если R означает “ иметь общий делитель, отличный от единицы “.

R={(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 2), (4, 4), (4, 6), (5, 5), (6, 2), (6, 3), (6, 4), (6, 6)}.