Бинарные отношения

Теория:

Отношения – один из способов задания взаимосвязей между элементами множества.

Унарные (одноместные) отношения отражают наличие какого-то определенного признака R (свойства и т.п.) у элементов множества M (например, быть «белым» на множестве шаров в урне). Тогда все такие элементы a из множества M, которые отличаются данным признаком R, образуют некоторое подмножество в M, называемое унарным отношением R, т.е. .

Бинарные (двухместные) отношения используются для определения каких-то взаимосвязей, которыми характеризуются пары элементов в множестве M (так на множестве людей могут быть заданы, например, следующие бинарные отношения: «жить в одном городе», «быть моложе», «работать в одной фирме», и т.п.). Тогда все пары (a,b) элементов, между которыми имеет место данное отношение R, образуют подмножество пар из множества всех возможных пар элементов , называемое бинарным отношением R, т.е. , при этом .

Бинарным (двуместным) отношением R называется подмножество пар прямого произведения , т.е. . При этом множество называется областью определения отношения R, множество – областью значений.

Если a,b находятся в отношении R, это записывается как aRb.

Бинарные отношения. Отношения определенные на конечных множествах, задаются:

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

2. Матрицей – где бинарному отношению , где , соответствует квадратная матрица порядка n, в которой элемент , стоящий на пересечении i-той строки и j-того столбца, равен 1, если между и имеет место отношение R, или 0, если оно отсутствует:

Задача 8. Пусть M={1,2,3,4,5,6}. Задать в явном виде (списком) и матрицей отношение , если R означает – «< - быть строго меньше».

Решение:

Отношение R как множество содержит все пары элементов a,b из M такие, для которых a<b:

.

Тогда список будет иметь вид:

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

Матрица отношений будет выглядеть следующим образом:

Задача 9. Пусть M={1,2,3,4,5,6}. Составить матрицы отношения для , если:

а) – «быть делителем»;

б) – «иметь общий делитель, отличный от единицы»;

в) – «иметь один и тот же остаток от деления на 3».

Решение:

а) отношение R₁ б) отношение R₂ в) отношение R₃