Рішення задач по темі бінарні відносини

3) Уявімо відносини і з допомогою дводольних графів.

Завдання 12. На безлічі задані бінарні відносини: і. Потрібно визначити, яке з них є транзитивним.

Запишемо матриці інціденцій відносин:

Ставлення транзитивно, якщо квадрат його матриці інціденцій не більш самої матриці:.

Будемо будувати в квадрат матриці інціденцій відносин і та порівнювати отримані результати з самими матрицями інціденцій.

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

Оскільки, ставлення транзитивно.

Завдання 13. Для відносини в задачі 12 виявити непрямі зв'язки між елементами безлічі.

Віднімемо з матриці матрицю:

У матриці ненульовими є елементи і. Отже, ставлення не враховує зв'язку між елементами (2,3) і (4,1).

Розглянемо опосередковані зв'язки між елементами 2 і 3. Для цього запишемо, як був отриманий елемент, тобто процес множення другого рядка матриці на її третій стовпець.

Спочатку випишемо другий рядок і третій стовпець матриці і покажемо зміст кожного елемента.

Тепер розпишемо процес отримання, вказуючи сенс чисел, над якими виконуються операції мінімум і максимум.

З малюнка видно, що опосередкований зв'язок між елементами 2 і 3 відносно здійснюється елементами 1 або 3.

Таким чином, елементи-посередники, які здійснюють опосередковану зв'язок між 2 і 3 відносно, - це елементи 1 або 3.

Розглянемо опосередковані зв'язки між елементами 4 і 1. Запишемо, як був отриманий елемент.

Випишемо четвертий рядок і перший стовпець матриці і покажемо зміст кожного елемента.

Розпишемо процес отримання, вказуючи сенс чисел, над якими виконуються операції мінімум і максимум.

З малюнка видно, що опосередкований зв'язок між елементами 4 і 1 в відношенні здійснюється елементом 2.

Таким чином, елемент-посередник, що здійснює опосередкований зв'язок між 4 і 1 в відношенні, - це елемент 2.

Завдання 14. Бінарне відношення на множині задано матрицею інціденцій:

1) Знайти транзитивне замикання відношення.

2) Знайти евклідова відстань між ставленням і його транзитивним замиканням.

3) Побудувати графи всіх отриманих відносин.

1) Для отримання транзитивного замикання будемо отримувати послідовність ступенів матриці.

Подальше множення матриць не дасть нових результатів.

Висновок: транзитивним замиканням відношення є відношення.

2) Знайдемо евклідова відстань між відносинами і.

3) Побудуємо графи відносин і.

Завдання 15. На площині задано п'ять прямих:

На безлічі прямих задано відношення: "пряма паралельна або збігається з прямою",.

1) Довести, що є відношенням еквівалентності.

2) Записати фактор безліч /.

3) Записати характеристичні функції кожного класу.

1) Нагадаємо, що дві прямі паралельні або збігаються тоді і тільки тоді, коли їх кутові коефіцієнти рівні.

Перепишемо рівняння прямих,,,, у вигляді рівнянь прямих з кутовим коефіцієнтом і початкової ординатою:

Порівняння кутових коефіцієнтів прямих дозволяє записати графік відносини:

Запишемо матрицю відносини:

а) Всі елементи головної діагоналі матриці одиниці, отже, - рефлексивне відношення.

б) Матриця симетрична відносно головної діагоналі, отже, - симетричне відношення.

в) Для перевірки транзитивності відносини знайдемо матрицю:

, отже, - транзитивне відношення.

Ставлення рефлексивно, симетрично і транзитивній, отже - відношення еквівалентності.

2) Ставлення еквівалентності розбиває безліч на непересічні класи еквівалентності, об'єднання яких становить все безліч. В один клас потрапляють елементи, пов'язані один з одним відношенням, в різні класи - цим ставленням не зв'язані.

Перебираючи елементи безлічі, і записуючи їх образи і прообрази в відношенні, отримаємо класи еквівалентності:

3) Характеристичні функції кожного класу запишемо у вигляді мірних довічних векторів:

Завдання 16. На безлічі задано відношення:

Визначити, якими властивостями володіє відношення.

а) Ставлення рефлексивно, так як на головній діагоналі матриці все числа - одиниці.

б) Відношення не є симетричним, тому що матриця не симетрична щодо головної діагоналі.

Перевіримо виконання ознаки антисиметричність відносини:.

Перетин матриць інціденцій знаходимо за правилом логічного твори:, де,,.

Оскільки рівність виконується, ставлення антисиметрично.

в) Для перевірки транзитивності знайдемо матрицю:

Оскільки, ставлення не є транзитивним.

Отже, ставлення має властивості рефлексивності і антисиметричність.

Завдання 17. Задані числа й. Запишіть всі функціональні відповідності на безлічі за допомогою двустрочним матриць і матриць інціденцій. Вкажіть, які з них є ін'єкційних, сюр'ектівнимі, взаємно однозначними.

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

На безлічі існує 2 4 = 16 різних функціональних відповідностей. Ін'єкційних і взаємно однозначних відповідностей серед них немає, так як число елементів множини менше числа елементів множини.

Відповідності є сюр'ектівнимі, оскільки кожен елемент безлічі має в цих відповідностях не менше одного прообразу.

Відповідності і не відносяться ні до якого виду відповідностей. оскільки деякі елементи безлічі мають в цих відповідностях більше одного прообразу, а інші - ні одного прообразу.

Завдання 18. В умовах задачі 17 запишіть всі функціональні відповідності на множині. Виділіть серед них ін'єкційних, сюр'ектівние і взаємно однозначні.

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

Дворядковий матриці будемо складати за таким правилом. Виберемо образ нуля. Для обраного способу нуля виберемо образ одиниці.

Оскільки чином одиниці може бути будь-який з чотирьох елементів безлічі, то при кожному фіксованому образі елемента нуль, будемо отримувати чотири різних відповідності. Чином нуля також може бути будь-який з чотирьох елементів множини. Отже, існує 4 4 = 16 різних функціональних відповідностей на множині.

Серед функціональних відповідностей на безлічі не може бути сюр'ектівних і взаємно однозначних, так як число елементів множини більше числа елементів множини.

Відповідності, і не відносяться ні до якого виду відповідностей, оскільки деякі елементи безлічі мають в цих відповідностях більше одного прообразу, а інші - ні одного прообразу.

Решта 12 відповідностей є ін'єкційних, так як кожен елемент безлічі має в них не більше одного прообразу.

Завдання 19. Дано безлічі,. На безлічі задано функціональне відповідність, графік якого має вигляд:. потрібно:

1. Записати графіки і матриці інціденцій відносин,,.

2. Записати графіки відносин і.

1. а) є доповнення безлічі до декартова твори множин.

Запишемо матриці інціденцій відносин і:

б) Відносини і є відносно на множині.

Щоб отримати, треба в графіку поміняти місцями елементи у всіх парах:

Матриця інціденцій відносини:

Примітка 1. Звернемо увагу на те, що.

Примітка 2. Ставлення не є функціональним відповідністю на безлічі, оскільки елемент має два образи і ().

в) є доповнення безлічі до декартова твори множин:

Матриця інціденцій відносини:

2. Знайдемо композиції відносин і.

Відносини і є відносини на множині.

Примітка 3. Звернемо увагу на те, що є додаток відносини до безлічі.