Дискретні структури. Бінарні відношення. Лекція 2
Визначення. Декартовим добутком множин X і Y називається множина X*Y всіх впорядкованих пар (x, у) таких, що x X, у Y. Визначення. Відношенням між множинами X і Y (або відношенням з X в Y) називається будь-яка підмножина R декартового добутку X*Y. Якщо множини X і Y збігаються, то відношення між множинами X і Y називають бінарним відношенням на множині X. Приклад. Нехай X = {а, b, с, d}, Y = {1, 2, 3, 4, 5}. Тоді множина комбінацій R={(а, 1), (b, 2), (с, 3), (d, 4)} є відношенням з X в Y. Зазвичай відношення задаються не шляхом задання підмножини R декартового добутку X*Y, а шляхом задання властивості пар (x, у), що належать цій підмножині R. Приклад. Відношення R = {(4, 4), (3, 3), (2, 2), (4, 2)} на множині X = {4, 3, 2} можна визначити як властивість "Ділиться" на цій підмножині цілих чисел. 2.1. Поняття бінарного відношення Приклади відношень з курсу математики є: на множині цілих чисел Z - відношення "ділиться", "ділить", "рівно", "більше", "менше", "взаємно прості"; на множині прямих простору - відношення "паралельні", "взаємно перпендикулярні", "схрещуються", "перетинаються", "збігаються"; на множині окружності площини - відношення "перетинаються", "торкаються", "концентричні".