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

Двухместным, или бинарным, отношением R называется подмно-жество пар (a, b)Î R прямого произведения M ₁´ M ₂, т.е. R Í M ₁´ M ₂.

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

1. Списком (перечислением) пар, для которых это отношение выполняется. Например, R ={(a, b), (a, c), (b, d)}.

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

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

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

R ={(a, b): 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)}.

Матрица отношения приведена на рис 2.1, a.

Пример 2. Пусть M ={1, 2, 3, 4, 5, 6}. Составить матрицы отношения R ₁, R ₂, R ₃Í M ´ M, если:

1) R ₁ – “быть делителем”;

2) R ₂ – “иметь общий делитель, отличный от единицы”;

3) R ₃ – “иметь один и тот же остаток от деления на 3”.

1) R ₁={(a, b): a, b Î M; а – делитель b } и выполнятся для пар {1, 1}, (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6)}. Эти пары (а, b)Î R ₁ определяют наличие единиц в матрице отношения R ₁Í M ² на пересечении строки элемента а и столбца элемента b; а, b Î M (рис. 2.1, б);

2) R ₂={(a, b): a, b Î M; а и b имеют общий делитель c ¹1}.

Матрица отношения R ₂ представлена на рис 2.1, в;

3) R ₃={(a, b): a, b Î M; а, b имеют один и тот же остаток от деления на 3}. Матрица отношения R ₃ приведена на рис. 2.1, г.

Пример 3. Для указанных ниже отношений привести примеры пар, для которых выполняются отношения, и пар, для которых отношения не выполняются.

1. Отношения, заданные на множестве точек действительной плоскости:

а) R ₁ – “находиться на одинаковом расстоянии от начала координат”;

б) R ₂ – “находиться на разном расстоянии от начала координат”;

в) R ₃ – “находиться на одной и той же окружности с центром в начале координат”;

г) R ₄ – “быть симметричным относительно оси X ”.

2. Отношения, заданные на множестве элементов структуры, изображен-ной на рис. 2.2:

а) R ₅ – “быть частью целого”;

б) R ₆ – “быть непосредственно связанным с”;

в) R ₇ – “быть начальником”;

г) R ₈ – “быть непосредственным начальником”.

3. Отношения, заданные на системе мно-жеств b(M), M ={ a, b, c }:

а) R ₉ – “пересекаться с” (иметь непустое пересечение);

б) R ₁₀ – “являться строгим включением Ì”;

в) R ₁₁ – “ являться нестрогим включением Í”;

г) R ₁₂ – “быть дополнением к”.

Примеры пар элементов с отношениями между ними без таковых приведены в табл. 2.1.

Таблица 2.1

Отношение	Примеры пар, для которых отношение
выполняется	невыполняется
1. Отношения, заданные на множестве точек действительной плоскости: R 1 – “находиться на одинаковом рас-стоянии от начала координат” R 2 – “находиться на разном расстоянии от начала координат” R 3 – “находиться на одной и той же окруж-ности с центром в начале координат” R 4 – “быть симметричным относительно оси X ” 2. Отношения, заданные на множестве элементов структуры (рис. 2.2): R 5 – “быть частью целого” R 6 – “быть непосредственно связанным с” R 7 – “быть начальником” R 8 – ‘быть непосредственным начальником” 3. Отношения, заданные на системе множеств b(M), M ={ a, b, c }: R 9 – “пересекаться с” (иметь непустое пересечение)   R 10 – “являться строгим включением Ì”     R 11– “ являться нестрогим включением Í”     R 12 – ‘быть дополнением к”	((3, 4), (–3, 4)), ((3, 4), (0, –5)), ((3, 4), (1, 6))   ((3, 4), (–3, 4)), ((3, 4), (0, –5)) ((3, 4), (3, –4)), ((–3, 4), (–3, –4))     (b, a), (d, a), (c, a) (d, b), (b, d), (c, a) (b, d), (a, d), (a, c) (b, d), (a, b)   ({ a }, { a, c }), ({ a, c }, { a, b }), ({ a, c }, { a, b, c }) ({ a }, { a, c }), ({ a, c }, { a, b, c })   ({ a }, { a, c }), ({ a, c }, { a, b, c }), ({ a, c }, { a, c }) ({ a }, { b, c }), (Æ, { a, b, c })	((3, 4), (1, 6))   ((3, 4), (–3, 4)), ((3, 4), (0, –5)) ((3, 4), (1, 6))   ((3, 4), (–3, 4)), ((3, 4), (–3, –4))     (d, f), (a, b), (g, b) (d, f), (g, b), (d, a) (d, b), (b, g) (d, b), (a, d), (b, g)   ({ a }, { b }), ({ a }, { b, c })   ({ a, c }, { a, b }), ({ a, c }, { a, c }), ({ a }, { b, c }) ({ a, c }, { a, b }), ({ a }, { b, c })   ({ a }, { a, c }), ({ a, b }, { a, c })

Пример 4. Составить матрицы отношений, заданных на системе множеств b(M), M ={ a, b, c }:

1) R ₁ – “пересекаться с” (иметь непустое пересечение);

2) R ₂ – “являться строгим включением Ì”;

b(M)={Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }}.

Матрицы отношений R ₁ и R ₂ представлены на рис. 2.3.

1) R ₁ – “быть частью целого”;

2) R ₂ – “быть непосредственно связанным с”.

Матрицы отношений R ₁ и R ₂ приведены на рис. 2.4. (При построении матрицы отношения R ₁ предполага-лось, что “целое есть часть самого себя”; аналогично при построении матрицы отношения R ₂)

Пример 5. Пусть отношение R – “быть отцом”, определенное на множестве людей M ={ a, b, c, d, e, f, g, h }, представлено схемой на рис. 2.2. Задать списком отношение R. Определить (назвать) родственные отношения между следующими парами: (a, b), (a, d), (b, c), (b, d), (b, h), (c, d).

1) R ={(a, b), (a, c), (b, d), (b, e), (b, f), (c, g), (c, h)} – “быть отцом”.

2) a – отец для b; a – дед для d; b – родной брат для c; b – отец для d; b – дядя для h; с – дядя для d.

В целом заданная матрица отношения R – “быть отцом” – позволяет установить новые отношения между элементами множества M, в том числе:

R ₁={(a, d), (a, e), (a, f), (a, g), (a, h)} – “быть дедом”;

R ₂={(b, c), (c, b), (d, e), (e, d), (d, f), (f, d), (e, f), (f, e), (g, h), (h, g)} – “быть родным братом или сестрой”;

R ₃={(d, g), (g, d), (d, h), (h, d), (e, g), (g, e), (e, h), (h, e), (f, g), (g, f), (f, h), (h, f)} – “быть двоюродным братом или сестрой”;

R ₄={(b, g), (b, h), (c, d), (c, e), (c, f)} – “быть дядей”;

R ₅={(g, b), (h, b), (d, c), (e, c), (f, c)} – “быть племянником или племянницей”;

R ₆={(b, a), (c, a), (d, b), (e, b), (f, b), (g, c), (h, c)} – “быть сыном или дочерью”;

Уточним потомков b и c. Пусть d и g – дочери, e, f и h – сыновья для b и с соответственно. Тогда:

R ₇={(b, c), (c, b), (e, f), (f, e)} – “быть родным братом” (очевидно, что R ₇Í R ₂);

R ₈={(b, a), (c, a), (e, b), (f, b), (h, c)} – “быть сыном” (очевидно, что R ₈Í R ₆);

R ₉={(d, c), (g, b)} – “быть племянницей” (R ₉Í R ₅) и т. д.

Пример 6. Пусть M – множество клеток шахматной доски, M = X ´ Y, где X ={ a, b, c, d, e, f, g, h }, Y ={1, 2, 3, 4, 5, 6, 7, 8}.

Определить бинарное отношение R _л на M для ладьи так, что (m ₁, m ₂)Î R _л тогда и только тогда, когда m ₁ и m ₂ – элементы M и ладья может пройти от m ₁ к m ₂ одним ходом на пустой доске (Задать R _л описанием его характеристического свойства).

Ладья за один ход на шахматном поле может изменить либо горизонтальную координату, либо вертикальную, но не обе коорди-наты вместе. Обозначим m ₁, m ₂Î M: m ₁=(x ₁, y ₁), m ₂=(x ₂, y ₂), где x ₁, x ₂Î X, y ₁, y ₂Î Y. Тогда

R _л={((x ₁, y ₁), (x ₂, y ₂)): (x ₁= x ₂ и y ₁¹ y ₂) или (x ₁¹ x ₂ и y ₁= y ₂)}.

Пример 7. Пусть некоторая программа читает два числа из мно-жества M ={1, 2, 3, 4, 5}, обозначаемых x и y, и, если x < y, печатает число z (также из M) такое, что x £ z < y. В любом случае программа останавливается после считывания всех чисел на множестве M. Чему равны области определения и значений отношений?

При поступлении на вход программы двух чисел x, y Î M таких, что x < y, программа выдает результат z такой, что x £ z < y, т.е. устанавливает отношение R Í M ´ M такое, что R ={((x, y), z): x < y, x £ z < y)}:

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

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

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

Вопросы для самопроверки и упражнения:

1. Пусть M =b(A), A ={1, 2, 3, 4}. Найти все элементы (пары) отно-шения R на M, если R означает:

а) Ì; в) “пересекаться с”;

б) Í; г) “быть дополнением к”.

Задать R описанием его характеристического свойства.

2. Пусть отношение R задано на M ={1, 2, 3, …, 9}. Выписать все элементы R, если:

а) R ={(a, b): a, b Î M; (a +1) – делитель (a + b)};

б) R ={(a, b): a, b Î M; a – делитель (a + b), a ¹1}.

3. Пусть М – множество клеток шахматной доски (см. пример 6). Требуется:

а) Задать характеристическим свойствам отношение R_k Í M ´ M, связывающее клетки m ₁, m ₂Î M, которые определяются ходом коня (т.е. если конь может перейти с m ₁ на m ₂ за один шаг);

б) Описать отношение R_p Í M ´ M, область определения D (R_p), область значений Q (R_p), если R_p такое, что (m ₁, m ₂)Î R_p тогда и только тогда, когда m ₁ – начальная позиция белой пешки, а m ₂ – клетка, где первый ход игры заканчивается.