Page 16 - 4570

15

універсальної множини. Нехай універсальна множина U містить n елементів,
тоді:
U = {а 1, а 2, а 3, . . ., а n-1, а n}.
Множину A  U подають у комп'ютері рядком із 0 та 1 довжиною n
наступним чином: якщо a i  А, то i-й біт дорівнює 1, в іншому випадку – 0.
Приклад 1.19. Нехай U = {a, b, c, d, e, f, m, n, p, q), A = {b, m, n, q), В = {a,
b, f, m, q). Тоді множину А можна представити рядком 0100001101, а множину
В – рядком 1100011001.
Тепер на комп'ютері легко виконати операції над множинами А та В.
Неважко переконатись, що об'єднанню множин відповідає порозрядне OR над
бітовими рядками, які представляють множини А та В, а перетину множин –
порозрядне AND над відповідними бітовими рядками.
Виконаємо операції об’єднання та перетину над бітовими рядками, які
представляють множини А та В.
Бітовий рядок, який відповідає об'єднанню цих множин АВ = {а, b, f, m,
n, q}, знаходимо як результат виконання операції порозрядного OR:
0100001101
OR
1100011001
1100011101
Бітовий рядок, який відповідає перетину множин AB = {b, m, q},
знаходимо як результат виконання операції порозрядного AND:
0100001101
AND
1100011001
0100001001
Якщо універсальна множина U має велику потужність, а її підмножини не
дуже потужні, то подання за допомогою бітових рядків неефективне щодо
витрат пам'яті. У такому разі доцільно використовувати інші структури даних –
зазвичай зв'язані списки та хеш-таблиці. У певних задачах потрібні спеціальні
методи подання множин, які ґрунтуються на використанні дерев.

ЛЕКЦІЯ 4. ВІДНОШЕНЬ МІЖ МНОЖИНАМИ

1. Поняття відношення

Поняття відношення є фундаментальним поняттям не тільки дискретної
математики, але й в інших теоретичних та прикладних дисциплінах.
Відношення визначається як будь-яка підмножина впорядкованих кортежів,
побудованих з елементів абстрактних множин, і реалізують зв’язки між
реальними об’єктами. При цьому під кортежем розуміють просто набір
впорядкованих елементів.
Приклад 1.20: 1) a  A − зв’язок між елементом та множиною; 2) A  B −
зв’язок між множинами; 3) <, ≤ , ≠ − нерівності; 4) = − рівність; 5) «бути
братом»; 6) ділення без остачі.
Приклади 1-6 – приклади відношень.
Введемо поняття впорядкованої множини.