На головну

 Основні позначення |  Діаграми (кола) Ейлера-Венна |  докази |  Еквівалентність і порядок |  Операції над бінарними відносинами |  Відповідності та їх властивості. Основні визначення |  Функції та відображення |  операції |  Гомоморфізми і ізоморфізми |  Підручники і навчальні посібники |

Бінарні відносини. Основні визначення

  1.  B.1.1 Основні положення
  2.  ER-модель бази даних. Основні нотації зображення ER-моделі.
  3.  I Основні категорії педагогіки
  4.  I Розрахунок витрат для визначення повної собівартості вироби (роботи, послуги), визначення рентабельності його виробництва
  5.  I. Основні положення
  6.  I. Основні принципи
  7.  I. ОСНОВНІ СТРАХОВІ ПОНЯТТЯ

двомісним, або бінарним, ставленням R називається подмн-дружність пар (a, b) IR прямого твори M1?M2, Тобто RIM1?M2.

Відносини, певні на кінцевих множинах, зазвичай задаються:

1. списком (перерахуванням) пар, Для яких це відношення виконується. наприклад, R= {(a, b), (a, c), (b, d)}.

2. матрицею - Бінарним відношенню RIM?M, де M= {a1, a2, ..., an}, Відповідає квадратна матриця порядку n, В якій елемент  , Що стоїть на перетині iго рядка і j-го стовпчика, дорівнює 1, якщо між и  має місце відношення R, Або 0, якщо воно відсутнє:

Приклад 1.нехай M= {1, 2, 3, 4, 5, 6}. Задати в явному вигляді (списком) і матрицею відносини RIM?M, якщо R означає - "бути строго менше".

ставлення R як безліч містить всі пари елементів a, b з M такі, що a<b:

R= {(a, b): a,bIM; 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}. Скласти матриці відносини R1, R2, R3IM?M, Якщо:

1) R1 - "Бути дільником";

2) R2 - "Мати спільний дільник, відмінний від одиниці";

3) R3 - "Мати один і той же залишок від ділення на 3".

1) R1= {(a, b): a,bIM; а - дільник 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) IR1 визначають наявність одиниць в матриці відносини R1IM2 на перетині рядка елемента а і стовпці елемента b; а,bIM (Рис. 2.1, б);

2) R2= {(a, b): a,bIM; а и b мають спільний дільник c?1}.

матриця відносини R2 представлена ??на рис 2.1, в;

3) R3= {(a, b): a,bIM; а, b мають один і той же залишок від ділення на 3}. матриця відносини R3 приведена на рис. 2.1, р

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

1. Відносини, задані на множині точок дійсної площини:

а) R1 - "Перебувати на однаковій відстані від початку координат";

б) R2 - "Перебувати на різній відстані від початку координат";

в) R3 - "Перебувати на одній і тій же окружності з центром на початку координат";

г) R4 - "Бути симетричним щодо осі X".

2. Відносини, задані на множині елементів структури, зображений-ної на рис. 2.2:

а) R5 - "Бути частиною цілого";

б) R6 - "Бути безпосередньо пов'язаним з";

в) R7 - "Бути начальником";

г) R8 - "Бути безпосереднім начальником".

3. Відносини, задані на системі мно-дружність b (M), M= {a, b, c}:

а) R9 - "Перетинатися з" (мати непорожнє перетин);

б) R10 - "Бути строгим включенням I";

в) R11 - "Бути нестрогим включенням I";

г) R12 - "Бути доповненням до".

Приклади пар елементів з відносинами між ними без таких наведені в табл. 2.1.

Таблиця 2.1

 ставлення  Приклади пар, для яких відношення
 виконується  не виконується
 1. Відносини, задані на множині точок дійсної площини: R1 - "Перебувати на однаковій рас-стоянні від початку координат"R2 - "Перебувати на різній відстані від початку координат"R3 - "Перебувати на одній і тій же окруж-ності з центром на початку координат"R4 - "Бути симетричним щодо осі X"2. Відносини, задані на множині елементів структури (Мал. 2.2):R5 - "Бути частиною цілого"R6 - "Бути безпосередньо пов'язаним з"R7 - "Бути начальником"R8 - 'Бути безпосереднім начальником "3. Відносини, задані на системі множин b (M), M= {a, b, c}:R9 - "Перетинатися з" (мати непорожнє перетин)R10 - "Бути строгим включенням I"R11- "Бути нестрогим включенням I"R12 - 'Бути доповненням до "  ((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) R1 - "Перетинатися з" (мати непорожнє перетин);

2) R2 - "Бути строгим включенням I";

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

матриці відносин R1 и R2 представлені на рис. 2.3.

1) R1 - "Бути частиною цілого";

2) R2 - "Бути безпосередньо пов'язаним з".

матриці відносин R1 и R2 наведені на рис. 2.4. (При побудові матриці відносини R1 предполага-лось, що "ціле є частина самого себе"; аналогічно при побудові матриці відносини R2)

Приклад 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, в тому числі:

R1= {(a, d), (a, e), (a, f), (a, g), (a, h)} - "Бути дідом";

R2= {(b, c), (c, b), (d, e), (e, d), (d, f), (f, d), (e, f), (f, e), (g, h), (h, g)} - "Бути рідним братом або сестрою";

R3= {(d, g), (g, d), (d, h), (h, d), (e, g), (g, e), (e, h), (h, e), (f, g), (g, f), (f, h), (h, f)} - "Бути двоюрідним братом або сестрою";

R4= {(b, g), (b, h), (c, d), (c, e), (c, f)} - "Бути дядьком";

R5= {(g, b), (h, b), (d, c), (e, c), (f, c)} - "Бути племінником або племінницею";

R6= {(b, a), (c, a), (d, b), (e, b), (f, b), (g, c), (h, c)} - "Бути сином або дочкою";

уточнимо нащадків b и c. нехай d и g - Дочки, e, f и h - Сини для b и с відповідно. тоді:

R7= {(b, c), (c, b), (e, f), (f, e)} - "Бути рідним братом" (очевидно, що R7IR2);

R8= {(b, a), (c, a), (e, b), (f, b), (h, c)} - "Бути сином" (очевидно, що R8IR6);

R9= {(d, c), (g, b)} - "Бути племінницею" (R9IR5) і т.д.

Приклад 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 для човна так, що (m1, m2) IRл тоді і тільки тоді, коли m1 и m2 - елементи M і тура може пройти від m1 к m2 одним ходом на порожній дошці (Задати Rл описом його характеристичного властивості).

Тура за один хід на шаховому полі може змінити або горизонтальну координату, або вертикальну, але не обидві коорди-нати разом. позначимо m1,m2IM: m1= (x1, y1), m2= (x2, y2), Де x1, x2IX, y1,y2IY. тоді

Rл= {((x1, y1), (x2, y2)): (x1=x2 и y1?y2) Або (x1?x2 и y1=y2)}.

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

При надходженні на вхід програми двох чисел x,yIM таких, що x<y, Програма видає результат z такий, що x?z<y, Тобто встановлює відношення RIM?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 означає:

а) I; в) "перетинатися з";

б) I; г) "бути доповненням до".

задати R описом його характеристичного властивості.

2. нехай відношення R задано на M= {1, 2, 3, ..., 9}. Виписати всі елементи R, Якщо:

а) R= {(a, b): a,bIM; (a+1) - Дільник (a+b)};

б) R= {(a, b): a,bIM; a - Дільник (a+b), a?1}.

3. нехай М - Безліч клітин шахової дошки (див. Приклад 6). потрібно:

а) Поставити характеристичним властивостям відношення RkIM?M, Що зв'язує клітини m1,m2IM, Які визначаються ходом коня (тобто якщо кінь може перейти з m1 на m2 за один крок);

б) Описати ставлення RpIM?M, область визначення D(Rp), Область значень Q(Rp), Якщо Rp таке, що (m1, m2) IRp тоді і тільки тоді, коли m1 - Початкова позиція білої пішаки, а m2 - Клітина, де перший хід гри закінчується.

 



 Вектори, прямі твори, проекції векторів |  Властивості бінарних відносин
© um.co.ua - учбові матеріали та реферати