Пример. 2.10. Матрица бинарного отношения на множестве

а) Отношения на множестве натуральных чисел :

1) отношение выполняется для пар (7, 9) и (7,7), но не выполняется для пары (9, 7);

2) отношение «иметь общий делитель, отличный от единицы» выполняется для пар (6, 9), (4, 2), (2, 4), (5, 5), но не выполняется для пар (3, 7) и (9, 11);

3) отношение «быть делителем» (означает « – делитель » то есть ) выполняется для пар (12, 24), (17, 17), но не выполняется для пар (24, 12) и (11, 17).

б) Отношение на множестве точек действительной плоскости:

1) отношение «находиться на одинаковом расстоянии от начала координат» выполняется для пары точек с координатами (3, 4) и (-2, ), но не выполняется для пары точек (3, 4) и (1, 6). Отметим, что это отношение совпадает с отношением «находиться на одной и той же окружности с центром в начале координат»;

2) отношение «находиться на разном расстоянии от начала координат» выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение;

3) отношение «быть симметричным относительно оси » выполняется для всех пар точек и , удовлетворяющих условию и .

в) Отношения на множестве людей могут быть такими:

1) «жить в одном городе»;

2) «быть моложе»

3) «быть сыном»;

4) «быть знакомым» и т.д.

Пусть дано отношение на . Для любого подмножества можно определить отношение , которое называется сужением на , которое получается из удалением всех пар, содержащих элементы, не принадлежащие . Это можно записать следующим образом . Строго говоря, и – это разные отношения, с разными областями определения. Однако, если не возникает разночтений, эта строгость не соблюдается: например, вполне можно говорить об отношении «быть делителем», не уточняя, задано оно на или каком-либо его подмножестве».

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

Матрица бинарного отношения на множестве – это квадратная матрица порядка , строки и столбцы которой соответствуют элементам множества, а каждый элемент , стоящий на пересечении -й строки и –го столбца определяется следующим образом

Например, для конечного множества матрицы отношений 1-3 из примера 2.10, а приведены рис. 2.5.

На пересечении i -й строки и j -го столбца ставится 1 или 0 или элементы i и j, находящиеся в заданном отношении. Необходимо отметить, что в записи отношения через соответствие может использоваться одно и то же множество: .

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

1) «» 2) «общий делитель ≠1» 3) «быть делителем»

Рис. 2.5. Матрицы отношений для примера 2.10, а

Поскольку отношения на задаются подмножествами , для них можно определить те же операции, что и над множествами. Например, отношение 2 из примера 2.10, б является дополнением отношения 1, отношение является объединением отношений < и равенства.

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