![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Двухместным, или бинарным, отношением R называется подмно-жество пар (a, b)Î R прямого произведения M 1´ M 2, т.е. R Í M 1´ M 2.
Отношения, определенные на конечных множествах, обычно задаются:
1. Списком (перечислением) пар, для которых это отношение выполняется. Например, R ={(a, b), (a, c), (b, d)}.
2. Матрицей – бинарному отношению R Í M ´ M, где M ={ a 1, a 2, …, an }, соответствует квадратная матрица порядка 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 1, R 2, R 3Í M ´ M, если:
1) R 1 – “быть делителем”;
2) R 2 – “иметь общий делитель, отличный от единицы”;
3) R 3 – “иметь один и тот же остаток от деления на 3”.
1) R 1={(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 1 определяют наличие единиц в матрице отношения R 1Í M 2 на пересечении строки элемента а и столбца элемента b; а, b Î M (рис. 2.1, б);
2) R 2={(a, b): a, b Î M; а и b имеют общий делитель c ¹1}.
Матрица отношения R 2 представлена на рис 2.1, в;
3) R 3={(a, b): a, b Î M; а, b имеют один и тот же остаток от деления на 3}. Матрица отношения R 3 приведена на рис. 2.1, г.
Пример 3. Для указанных ниже отношений привести примеры пар, для которых выполняются отношения, и пар, для которых отношения не выполняются.
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 – “быть дополнением к”.
Примеры пар элементов с отношениями между ними без таковых приведены в табл. 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 1 – “пересекаться с” (иметь непустое пересечение);
2) R 2 – “являться строгим включением Ì”;
b(M)={Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }}.
Матрицы отношений R 1 и R 2 представлены на рис. 2.3.
1) R 1 – “быть частью целого”;
2) R 2 – “быть непосредственно связанным с”.
Матрицы отношений R 1 и R 2 приведены на рис. 2.4. (При построении матрицы отношения R 1 предполага-лось, что “целое есть часть самого себя”; аналогично при построении матрицы отношения R 2)
Пример 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 1={(a, d), (a, e), (a, f), (a, g), (a, h)} – “быть дедом”;
R 2={(b, c), (c, b), (d, e), (e, d), (d, f), (f, d), (e, f), (f, e), (g, h), (h, g)} – “быть родным братом или сестрой”;
R 3={(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 4={(b, g), (b, h), (c, d), (c, e), (c, f)} – “быть дядей”;
R 5={(g, b), (h, b), (d, c), (e, c), (f, c)} – “быть племянником или племянницей”;
R 6={(b, a), (c, a), (d, b), (e, b), (f, b), (g, c), (h, c)} – “быть сыном или дочерью”;
Уточним потомков b и c. Пусть d и g – дочери, e, f и h – сыновья для b и с соответственно. Тогда:
R 7={(b, c), (c, b), (e, f), (f, e)} – “быть родным братом” (очевидно, что R 7Í R 2);
R 8={(b, a), (c, a), (e, b), (f, b), (h, c)} – “быть сыном” (очевидно, что R 8Í R 6);
R 9={(d, c), (g, b)} – “быть племянницей” (R 9Í R 5) и т. д.
Пример 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 1, m 2)Î R л тогда и только тогда, когда m 1 и m 2 – элементы M и ладья может пройти от m 1 к m 2 одним ходом на пустой доске (Задать R л описанием его характеристического свойства).
Ладья за один ход на шахматном поле может изменить либо горизонтальную координату, либо вертикальную, но не обе коорди-наты вместе. Обозначим m 1, m 2Î M: m 1=(x 1, y 1), m 2=(x 2, y 2), где x 1, x 2Î X, y 1, y 2Î Y. Тогда
R л={((x 1, y 1), (x 2, y 2)): (x 1= x 2 и y 1¹ y 2) или (x 1¹ x 2 и y 1= y 2)}.
Пример 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). Требуется:
а) Задать характеристическим свойствам отношение Rk Í M ´ M, связывающее клетки m 1, m 2Î M, которые определяются ходом коня (т.е. если конь может перейти с m 1 на m 2 за один шаг);
б) Описать отношение Rp Í M ´ M, область определения D (Rp), область значений Q (Rp), если Rp такое, что (m 1, m 2)Î Rp тогда и только тогда, когда m 1 – начальная позиция белой пешки, а m 2 – клетка, где первый ход игры заканчивается.
Дата публикования: 2015-03-29; Прочитано: 5206 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!