2 Способи задання бінарних відношень

Якщо R – бінарне відношення на множинах X, Y, то факт (x, y)R часто записується xRy, і говорять, що елемент xX знаходиться у відношенні R з елементом yY.

1. Будь-яке бінарне відношення може бути задане у вигляді списку, елементами якого є пари, з якого складається відношення.

Приклад. На множинах А={1, 2, 3, 4, 5, 6, 7, 8, 9}; B={24, 25, 26} побудуємо відношення «дільник», яке складається з упорядкованих пар (x, y), де х – дільник у, xА, yВ. Позначимо це відношення через R:

R={(1,24), (1,25), (1, 26), (2, 24), (2, 26), (3, 24), (4, 24), (5, 25), (6, 24), (8, 24)}.

2. А\В	24	25	26
   1	1	1	1
   2	1	0	1
   3	1	0	0
   4	1	0	0
   5	0	1	0
   6	1	0	0
   7	0	0	0
   8	1	0	0
   9	0	0	0

   Бінарне відношення R на множинах X, Y може бути задане за допомогою матриці W=W(R), рядки якої відповідають елементам множини Х, а стовпці – елементам множини Y. Кожен елемент цієї матриці w_ij відповідає парі (x_i, y_j) А В, причому w_ij=0, якщо (x_i, y_j) R, і w_ij=1, якщо (x_i, y_j) R.

3. Бінарне відношення R на множинах X, Y може бути задане графічно. Позначимо на площині точками елементи множин X і Y, якщо пара (x_i, y_j) R, поєднаємо відповідні точки лінією, що спрямована від x_i до y_j. Лінії називаються дугами, а точки – вершинами графа.

Приклад. Як приклад графічного задання відношення зобразимо генеалогічне дерево деякої родини:

Розглянемо деякі часткові випадки відношень. Нехай задане бінарне відношення R на множині А: R  A². Можливий випадок, коли R = A², - таке відношення називається повним.

Відношення називається порожнім при R=. Якщо відношення містить всі можливі пари виду (а, а), і не містить інших пар елементів, то таке відношення називається тотожним.

Якщо повне відношення задане за допомогою матриці, то всі елементи цієї матриці дорівнюють одиниці. Матриця порожнього відношення складається з нульових елементів.

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

Запитання.

1. Як зв’язані теорія відношень та теорія множин?

2. Нехай А – деяка множина. Що означає запис А², А³, Aⁿ?

3. Нехай А і В – множини. Поясніть, чому А В ≠ B A?

4. Які способи задання відношення вам відомі?

5. Пояснити поняття «граф», «вершина», «дуга».

6. Що таке тотожне відношення, повне відношення, порожнє відношення?

 Завдання.

1. Побудуйте матрицю і граф для таких відношень, визначених на множині A={1, 2, 3}:

   1. {(1,1), (1,2), (1,3)};

   2. {(1,1), (2,1), (2,2), (2,3)};

   3. {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)};

   4. {(1,3), (3,1)}.

2. Побудуйте граф і список елементів для таких відношень, визначених на множині A={a, b, c} матрицями:

	a	b	c			a	b	c			a	b	c			a	b	c
a	1	0	1		a	0	1	0		a	1	1	1		a	1	0	0
b	0	1	0		b	0	1	0		b	1	0	1		b	0	1	0
c	1	0	1		c	0	1	0		c	1	1	1		c	0	0	1

a) b) c) d)

3. Побудуйте матрицю і список елементів для таких відношень, що задані графами:

a) b) c)

4. Запишіть список елементів для 3-арного відношення R, що задане на множині натуральних чисел (a, b, c)R, якщо 0<a<b<c<5.

5. Запишіть список елементів для 4-арного відношення R, що задане на множині натуральних чисел (a, b, c, d)R, якщо abcd = 6.

Самостійна робота №4

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

Мета: Засвоїти нові знання, закріпити їх при виконанні практичних завдань.

Завдання

1. Засвоїти теоретичний матеріал згідно теми;

2. Дати відповіді на поставлені питання;

3. Виконати письмово приведені завдання;

4. Випишіть питання, що виникли в ході засвоєння матеріалу;

5. Зробіть висновки.

Рекомендована література:

1. Бондаренко М.Ф. Комп’ютерна дискретна математика – Х: Компанія СМІТ, 2004р.

2. Новіков Ф.А. Дискретна математика для програмістів – К: Питер, 2006р