Тема 1.3 Відношення

Відношення - один із способів завдання взаємозв'язків між елементами множин. Найбільш вивченими і найчастіше використовуваними є унарні та бінарні відносини.

Унарні (одномісні) відношення відбивають наявність якогось визначеної ознаки R (властивості і т.п.) в елементів множини М (наприклад, "бути білим" на безлічі куль в урні). Тоді всі такі елементи а з множини, що відрізняються даною ознакою R, утворять деяку підмножину в М, називану унарним відношенням R, тобто та .

Бінарні (двомісні) відносини використовуються для визначення якихось взаємозв'язків, якими характеризуються пари елементів у множині М (так, на множині людей можуть бути задані, наприклад, бінарні відносини: "жити в одному місті", "бути молодшим", "бути сином", "працювати в одній організації" і т.п.). Тоді усі пари елементів з М, між якими має місце дане відношення R, утворять підмножину пар з безлічі всіх можливих пар елементів , називане бінарним відношенням R, тобто , при цьому (рис.5).

У загальному випадку можуть розглядатися п-місні відносини, наприклад відносини між трійками елементів - тримісні (тернарні) відносини і т.д.

Під п-місним відношенням розуміють підмножину R прямого добутку множин: . Говорять, що елементи а₁, а₂, ..., а_n ( ) знаходяться у відношенні R, якщо . Якщо n-місцеве відношення R задане на множині М своїх елементів, тобто М₁=М₂ = ... = М_n , то .

Способи завдання бінарних відносин - будь-які способи завдання множин (тому що відносини визначені вище як підмножини деяких множин - прямих добутків). Відносини, визначені на кінцевих множинах, звичайно, задаються:

1. Списком (перерахуванням) пар, для яких це відношення виконується. Наприклад, R = {( а₁, b₁), (а₁, b₃), (а₂, b₂), (а₂, b₃), (а₂, b₄), (а₃, b₁)}.

2. Матрицею - бінарному відношенню , де М= {a₁ a₂,..., а_п}, відповідає квадратна матриця порядку п, у якій елемент с_ij, що стоїть на перетинанні і-тої строки та j-того стовпця дорівнює 1, якщо між a_i a_j має місце відношення R, та 0, якщо воно відсутнє.

Наприклад,

3. За допомогою орієнтованого графу. Граф це фігура, що складається з точок та стрілок. Вершини графа (точки) відповідають елементами множин, дуга, що направлена від елемента a_i до a_j означає, що a_i R a_j. Наприклад: