Задание бинарных отношений

Для задания бинарных отношений используются любые способы задания множеств (например, список пар, для которых данное отношение выполняется). Отношения на конечных множествах обычно задаются списком или таблицей. Бинарное отношение на множестве А=(а₁, а₂, …, а_n) – это квадратная таблица с m строками и m столбцами, в которой элемент, стоящий в i-той строке и j-том столбце

Пример. На множестве М₆ ={1, 2, 3, 4, 5, 6} задать отношения: “£”, “быть делителем”. Решение представлено в таблицах (по строкам записаны первые элементы, по столбцам – вторые).

Отношение “иметь общий

Отношение “£” делитель, отличный от единицы”

М6 М6

М6 М6

Отношение “Быть делителем” {(x, y) | x делит y}

Графическое задание бинарных отношений было разъяснено при графическом изображении прямого произведения двух множеств. Стрелочное задание бинарных отношений – элементы X и Y – изображаются в виде точек плоскости, которые соединяются стрелками, направленными от х к у только для тех хÎ Х и уÎ Y, для которых (х, у) Î R. Например, отношение “x делит y “ изобразится графом:

Можно изобразить М₆ один раз, тогда граф упростится и примет вид:

Сечением х=а множества R называется множество элементов yÎ Y, для которых (а, у) Î R. Множество сечений отношения R Î X´Y, обозначаемое Y|R, называется фактормножеством множества Y по отношению R и полностью определяет R.

Рассмотрим некоторое отношение RÌ X´Y, задаваемое графиком.

Сечение по а₁ множества R есть {b₁, b₃}, сечение по а₂ – {b₁, b₃, b₄} и т.д.

Напишем под каждым элементом Х соответствующее сечение. Тогда вторая строка дает фактормножество множества Y по R.

а₁ а₂ а₃ а₄ а₅

b1
b2
b3
b4

а₁ а₂ а₃ а₄ а₅

{b₁ b₃} {b₁, b₃, b₄} {b₁, b₂, b₄} {Æ} {b₂, b₄}

Этими сечениями полностью определяется отношение R.

Вместо одного элемента хÎХ можно рассматривать подмножество АÌХ. Сечение R(A) множества по АÌХ есть объединение сечений R(x) по всем хÎА. Таким образом, R(A) есть подмножество множества Y, образуемое всеми теми элементами yÎY, для которых (x, y) Î R, xÎA.

Пример. R(a₂)= {b₁, b₃, b₄}; R(a₃)= {b₁, b₂, b₄}; R({a₂, a₃})={{b₁, b₂, b_3, b₄}=B.

Отношения называется обратным к отношению R (обозначается R^-1), если . Или: . Из определения непосредственно следует, что .

Пример. Пусть S={(b₁, c₂), (b₂, c₁), (b₂, c₂), (b₃, c₃), (b₄, c₃)}. Тогда обратное отношение .

Поскольку в общем случае отношения представляют собой множества, элементами которого являются кортежи, то, естественно, к ним применимы и соответствующие операции над множествами. И вполне очевидно, что:

;

;

ÏY;

ÏF.

Поиск по сайту: