Операції над бінарними відношеннями

Тому що відношення на М задаються підмножинами, (або якщо для них визначні ті ж операції, що й над множинами:

1. Об'єднання

або

2. Перетинання

і

3. Різниця

і

4. Доповнення R :

де (або

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

5. Зворотне відношення існує тоді й тільки тоді, коли існує bRа:

Наприклад, якщо R - "бути молодше", то - "бути старше", якщо R - "бути сином", то - "бути батьком (або матір'ю)".

6. Складене відношення (композиція)

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

 

 

Рис.1.8

 

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

Зокрема, якщо відношення R визначене на множині то складене відношення

Наприклад, якщо R - "бути сином", те - "бути онуком".

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

і

7. Транзитивне замикання

Транзитивне замикання складається з таких і тільки таких пар елементів а,b з М, тобто для яких у М існує ланцюжок з (k+2)елементів між сусідніми елементами якої виконується R: тобто:

(визначення I).

Унарна операція транзитивного замикання може бути також визначена як нескінченне об'єднання:

(визначення II).

Наприклад, для відношення R - "бути сином" складене відношення (композиція) - "бути онуком", - "бути правнуком" і т.д. Тоді об'єднання всіх цих відношень є транзитивне замикання - "бути прямим нащадком".

Якщо відношення R транзитивно, то Наприклад, транзитивне замикання відношення R - "бути більше" збігається із цим відношенням, тобто

8. Рефлексивне замикання

Нехай тотожне відношення Тоді

Якщо R транзитивно й рефлексивно, то

Процедура обчислення транзитивного замикання для відношення

1) привласнити

2) обчислити привласнити

3) зрівняти: Якщо то привласнити й перейти до кроку 2. У противному випадку - до кроку 4;

4) кінець:

Функція як бінарне відношення. Часткові і повні функції. Відображення. Класифікація функцій. Зворотна функція. Композиція функцій

 

Якщо відомо, що А і В — упорядковані множини з відношеннями порядку, аналогічними « » і « », і то можна дати визначення для монотонних функцій: функція називається монотонної \ строго монотонної, якщо із випливає, що

На множині пар дійсних чисел (множина точок площини) частковий порядок можна задати за допомогою покоординатного попередування, а повний - якщо поставити порядок однієї з координат як пріоритетний.

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

a) Відношення називається функціональним, якщо для кожного перетин R по х містить не більше одного елемента).

Приклад. Задамо таблицею на рис. 10.3 деяке відношення яке повністю задовольняє умові функціональності, оскільки на кожній вертикалі перебуває жирна точка, і притім єдина. Побудуємо стрілочне подання цього відношення (рис. 10.3): як видно з рисунка, з кожної точки виходить стрілка, і притім тільки одна (включаючи цикли).

Якщо перетин R по будь-якому елементі з А містить один (і тільки один) елемент, то функціональне відношення називається всюди певним.

 

Приклад. Відношення, представлене на рис. 10.3.

Якщо відношення ,симетричне до функціонального відношення теж функціонально, то відношення R називається взаємно однозначним.

Рис. 10.3.

Приклад. Зображена нижче таблиця, у якої в кожному рядку й у кожному стовпці рівно одна жирна точка, представляє взаємно однозначне відношення. Подання цього відношення за допомогою перетинів має вигляд:

d) Для всякого функціонального відношення, взаємно однозначного чи ні, визначимо функцію, пов'язану із цим відношенням, як функцію, перетин якої по кожному або порожньо, або є той елемент множини В, що є елементом R(x).

Перетин R(x) множини R по називають образом аргументу х для функції й позначають Аргумент також називають змінною, а — значенням функції. Перетин множини R по називають прообразом у для функції

Множина , таких, що існує є область визначення.

Якщо образ всієї множини А дорівнює В, інакше кажучи, якщо кожен елемент із В є образ принаймні одного елемента з А, то говорять, що має місце відображення А на В; говорять також, що є сюр¢єктівне відображення функції, пов'язаної з R. Якщо всюди визначена, тобто якщо область визначення збігається з А, то говорять, що є відображення множини А в В і пишуть Якщо А і В збігаються, тобто відображення множини А в А, елемент х, що задовольняє відношенню називається нерухомою точкою відображення

Якщо -функція, пов'язана з R, то, коли R — взаємно днозначне відношення, функція, пов'язана з позначається В цьому випадку називається ін¢єктивної (говорять також однозначної) функцією, а — оберненною функцією.

Якщо, крім того, R усюди визначено, тобто ін¢єктивне відображення, або ін'єкція . Тоді

Бієктивними відображеннями, або бієкціями, називаються відображення одночасно сюр¢єктивні й ін¢єктивні.

Приклади. а) (Відображення множини А на множину В.)Нехай — множина дійсних чисел. Функція яка визначена формулою —2 (читається: х переходить в y = 3х — 2), задає відображення множини А на множину В.

b) (Відображення множини А в множину В.) Нехай знову . Функція така, що є відображення множини А в В. Тут знову -множина дійсних чисел. Це відображення не сюр¢єктивне, тому що негативні числа із множини В не є образами елементів з А при відображенні f.

c) Нехай А — множина R дійсних чисел, і В - множина позитивних дійсних чисел, відображення яке ставить у відповідність кожному елементу з А деякий елемент із В, взаємно однозначно; дійсно кожному у відповідає

Отже маємо ін¢єктивне відображення.
Оберненне відображення до відображення буде відображення

d) Нехай функція визначена на множині А, і функція визначена на множині якщо для кожного то називається обмеженням функції а — продовженням функції Якщо дані множини А, і задані на , то повністю визначено. Зворотне невірно: так, симетрію щодо точки М у площини Р можна розглядати як обмеження різних перетворень простору в себе, наприклад симетрії простору щодо крапки М або симетрії відносно прямій, ортогональної до Р у точки М.

 

Таблиця 1.6.

Властивості бінарних відношень

Множина Відношення Рефлек- тивність Симет- ричність Асиметрич- ність Антисиме-тричність Транзити- вність Антитран- зитивність
Будь-які + - - + + -
Будь-які не порожні + + - - - -
Будь-які - + - - - -
Будь-які + + - - + -
Будь-які - + - - - +
N + - - + + -
R - - + - + +
R + - - + + +
R - - + - + +
R + - - + + +
Прямі площини + + - - + -
  Прямі площини - + - - - -
Вектори Колінеар-ність + + - - + -
  окружність дотик + + - - - -
окружність концент-ричність + + - - + -
N Взаємна простота - + - - - -
N (порівняня за модулем m) + + - - + -