Читайте также:
|
|
Підмножина R Í Mn називається n-місцевим відношенням на множину М. Кажуть, що а1, …..., ат знаходиться у відношенні R, якщо (а1, …,аn)ÎR. Одномісне відношення - це просто підмножина М. Такі відношення називають ознаками: а має ознаку R, якщо аÎR і RÍМ. Властивості одномісних відношень - це властивості підмножин М; тому для випадку n=1 термін відношення вживається рідко. Прикладом тримісного відношення є множина трійок нападаючих у хокейній команді. Кожний із нападаючих знаходиться в цьому відношенні з усіма тими гравцями, з якими він грає в трійці.
Найяастіше зустрічаються і найкраще вивчені двомірні або бінарні відношення. Якщо а і в знаходяться в бінарном відношенні R, то записують так а R в.
Приклад 1. Відношення на N (де N - множина позитивних чисел):
1) відношення £ виконується для пар (7, 9) і (7, 7), але не виконується для пар (9, 7);
2) відношення “мати спільний дільник, відмінний від одиниці” виконується для пар (6, 9), (4, 2), (2, 4), (4, 4), але не виконується для пар (7, 9) і (9, 7);
3) відношення “бути дільником” - а R в (а дільник в) - виконується для пар (2, 4) і (4, 4), але не виконується для пар (4, 2) і (7, 9).
Приклад 2. Відношення на множині точок дійсної площини:
1) відношення “знаходитися на однаковій відстані від початку координат” виконується для пар точок, які знаходяться на одному й тому ж колі з центром на початку координат;
2) відношення “знаходитися на різній відстані від початку координат” виконується для тих і тільки тих пар точок, для яких не виконується попереднє відношення;
3) відношення “бути симетричним щодо осі Х” виконується для усіх пар точок (х1, y1) і (x2, y2), що задовольняють умові х1 = х2 і y1 = -y2.
Приклад 3. Відношення на множині людей: “жити в одному місті”, “бути молодше”, “бути сином”, “бути відомим”.
Нехай дане відношення R і М. Для будь-якої підмножини М1 Í М природно визначається відношення R', називане звуженням R на М1, воно утворюється з R видаленням усіх пар, що містять елементи, які не належать множині М1. Іншими словами R’=R Ç M12. Строго кажучи, R і R' - це різні відношення з різними областями визначення. Проте, якщо не виникає протиріч, цей педантизм не дотримується; наприклад, цілком можна говорити “бути дільником” не уточнюючи, задано воно на N або якійсь його підмножині.
Для завдання бінарних відношень можна використовувати будь-які засоби завдання множин, наприклад список пар, для яких дане відношення виконується. Відношення на кінцевих множинах звичайно задаються списком або матрицею. Матриця, що задає бінарні відношення на множині M={a1, …, am}, - це квадратна матриця з порядком m, у якій елемент cij, що стоїть на перетинанні i-го рядка і j-го стовпчика, визначається в такий спосіб:
æ1, якщо ai R aj;
cij = í
è 0 - у протилежному випадку.
Наприклад, для кінцевої множини {1, 2,..., 6} матриці відношень £, “має спільний дільник”, “бути дільником” мають вигляд:
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1
2 0 1 1 1 1 1 2 0 1 0 1 0 1 2 0 1 0 1 0 1
3 0 0 1 1 1 1 3 0 0 1 0 0 1 3 0 0 1 0 0 1
4 0 0 0 1 1 1 4 0 1 0 1 0 1 4 0 0 0 1 0 0
5 0 0 0 0 1 1 5 0 0 0 0 1 0 5 0 0 0 0 1 0
6 0 0 0 0 0 1 6 0 1 1 1 0 1 6 0 0 0 0 0 1
Для будь-якої множини М відношення Е, задане матрицею, у якій по головній діагоналі стоять одиниці, а в інших місцях - нулі, називається відношенням рівності на М.
Оскільки відношення на М задаються підмножинами М2, для них можна визначити ті ж операції, що і над множинами.
Визначимо ще одну операцію над відношеннями. Відношення є зворотним до R (позначається R-1), якщо ai R-1 aj тоді і тільки тоді, коли ai R aj. Так для відношення £ зворотним є ³.
Дата добавления: 2014-12-15; просмотров: 121 | Поможем написать вашу работу | Нарушение авторских прав |