logo
кр одмита

2.2. Бинарные отношения (соответствия)

Бинарным отношением, или соответствием между элементами множеств А и В, называется любое подмножество R  А  В декартова произведения этих множеств. Тот факт, что некоторые a  A и b  В находятся в отношении R, иногда выражают как a R b. В качестве примера бинарного отношения рассмотрим отношение R между элементами множеств А = {1, 2, 3} и B = {1, 2, 3, 4, 5, 6}, которое можно выразить словами так: элемент х  A есть делитель элемента у  В. Тогда имеем R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}.

Бинарное отношение удобно представлять в виде двоичной (булевой) матрицы. При этом элементы множеств А и В должны быть пронумерованы, и если i-й элемент множества А соответствует j-му элементу множества В, то элемент матрицы, расположенный на пересечении i-й строки и j-го столбца, имеет значение 1, в противном случае он имеет значение 0. Например, рассмотренное выше отношение R будет представлено следующей матрицей:

.

Проекция элемента (a, b) множества А  В на множество А есть элемент а. Аналогично элемент b является проекцией элемента (a, b) множества А  В на множество В.

Проекцией множества Е  А  В на А называется множество всех тех элементов из А, которые являются проекциями элементов из Е на множество А. Для множеств А и В, рассмотренных выше, проекцией элемента (2, 4) на множество А является элемент 2, а проекцией множества {(1, 2), (2, 2), (2, 4)} – множество {1, 2}.

Сечением множества R  А  В по а, обозначаемым R(а), называется множество всех тех элементов у  В, для которых (a, у) R.

Сечением R(Х) множества R по Х  А является объединение сечений для всех элементов из Х. Пусть R = {(1, 1), (1, 3) (1, 5), (1, 6), (2, 2), (2, 4), (3, 3), (3, 6)}. Тогда R(2) = {2, 4}, а если Х = {2, 3}, то R(Х) = {2, 3, 4, 6}.

Бинарное отношение можно задавать с помощью сечений. Например, отношение, представленное матрицей

,

можно задать следующим образом: R(a1) = {b1, b3}, R(a2) = {b1, b3, b4}, R(a3) = {b1, b4}, R(a4) = , R(a5) = {b4}. Множество сечений для всех a  A называется фактор-множеством.

Областью определения отношения R  А  В является проекция множества R на А. Для рассматриваемого выше отношения такой областью является {а1, а2, а3, а5}. Областью значений отношения R  А  В является сечение множества R по A. Областью значений рассматриваемого отношения R является {b1, b3, b4}.

Образом множества Х  А относительно R называется множество {b│b  В, х  Х, (х, b)  R}. Прообразом множества Y  В относительно R называется множество {a│a  A, y  Y, (a, y)  R}. В нашем последнем примере образом множества {а1, а3} относительно R является {b1, b3, b4}, а прообразом множества {b3, b4} является {а1, а2, а3, а5}.

Обратным отношением R – 1 для некоторого отношения R  А  В является множество, образованное теми парами (b, а)  В  А, для которых (а, b)  R. Матрица, представляющая отношение R – 1, получается транспонированием матрицы, представляющей R, т. е. заменой строк столбцами и наоборот.

Например, рассмотренному выше отношению R будет соответствовать обратное отношение R  1 , представляемое матрицей

.