Page 21 - 4570

20

Приклад 1.27. Перерізом x = a 1 множини R з попереднього прикладу буде
множина {b 2, b 4}.
Проекція відокремлює елементи у множині A, а переріз − елементи у
множині В.
Означення 1.17. Множина перерізів R(a) відношення R (R  A  B) по
всім a  A називається фактор-множиною множини B за відношенням R
(позначається через B / R).
B / R = {R(a), a  A}.
Фактор-множина B / R повністю визначає відношення R.

ЛЕКЦІЯ 5. ТИПИ ВІДНОШЕНЬ ТА ЇХ КОМПОЗИЦІЯ

1. Композиція відношень

Нехай задано три множини A, B, C і два відношення R та S між ними: R 
A  B, S  B  C.
Означення 1.18. Композицією двох відношень R та S називається
відношення SR (іноді позначають як SR) яке задано на декартовому добутку А
 С та визначене як таке, що переріз SR по всіх a  A збігається з перерізом S
по підмножині R(a) (R(a)  B), тобто:
(SR)(a) = S (R(a)), (1.1)
або
SR = {(a, c) | a  A, c  C, якщо b  B, що aRb та bSc}.
Операцію композиції бінарних відношень іноді ще називають добутком
відношень.
При визначенні композиції відношень використано символ , який
називається квантором існування і читається «існує, знайдеться хоча б один».
Окрім квантора існування ще є двоїстий до нього квантор  , який називається
квантором загальності, який читається «для будь-якого, для кожного, для
всіх». Застосування кванторів спрощує формальні записи.
Приклад 1.28. Розглянемо відношення R, яке визначене в попередньому
прикладі і відношення S, яке задане наступною таблицею:

Тоді відношення SR визначається таблицею: