8.11. Симетричне закриття

Означення 10. Нехай R є бінарне відношення в A. Відношення S в A називається симетричним закриттям R якщо S має наступні властивості:

a) R ( S;

b) S симетричне;

c) Для будь якого T в A, якщо R ( T і T симетричне, то S ( T.

Приклад.

A = {1, 2, 3 }, R = { (1, 1), (1, 3), (2, 3), (3, 1)}, тоді симетричне закриття R

S = { (1, 1), (1, 3), (2, 3), (3, 1), (3, 2)}.

Наступна теорема гарантує існування симетричного закриття для будь якого бінарного відношення в A.

Teorema 2. Нехай R є бінарне відношення в A. Тоді, S = R ( R^-1 є симетричне закриття R.

Доведення.

R ( R ( R^-1 = S;

Якщо (a, b) ( R, то (b, a) ( R^-1 ( R ( R^-1 = S ( S є симетричне);

Нехай T ( A A, R ( T і T симетричне. Якщо (a,b) ( S , тоді (a, b) (R або (a, b) (R^-1 . Але R ( T і T є симетричне , значить R^-1 ( T. Звідси слідує, що S ( T.

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

Означення 11. Нехай R є бінарне відношення в A. Відношення S в A називається транзитивним закриттям R якщо S має наступні властивості:

a) R ( S;

b) S транзитивне;

c) Для будь якого T в A, якщо R ( T і T транзитивне, то S ( T.

Приклад.

A = {1, 2, 3 }, R = { (1, 1), (1, 3), (2, 3), (3, 1)}, тоді транзитивне закриття R

S = { (1, 1), (1, 3), (2, 3), (3, 1), (2, 1), (3, 3)}.

Наступна теорема гарантує існування транзитивного закриття для будь якого бінарного відношення в A.

Teorema 3. Нехай R є бінарне відношення в A і F_i = {T( A A: R ( T і T є транзитивне}. Тоді S = є транзитивне закриття R.

Доведення.

a) Очевидно, що R ( F_I , а звідси слідує, що R ( = S;

b) Якщо (a, b) ( R і (b, c) ( R, то (a, c) ( F_I і (a, c) ( = S ( S є транзитивне);

c) Остання умова виконується автоматично, тому що S = ( F_I , де T = F_I є будь яке транзитивне відношення, що містить R.

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

A = { 1, 2, 3, 4} і R = {(1, 2), (1, 3), (2,1), (2, 2), (3, 4)}.

Звідси одержимо:

S_R = {(1, 2), (1, 3), (2,1), (2, 2), (3, 4), (1, 1), (3, 3), (4, 4};

S_S = {(1, 2), (1, 3), (2,1), (2, 2), (3, 4), (4, 3), (3, 1)};

S_T = {(1, 2), (1, 3), (2,1), (2, 2), (3, 4), (1, 1), (2, 4), (2, 3), (1, 4)}.

Вправи на закріплення

Знайти рефлексивне, симетричне і транзитивне закриття для наступних бінарних відношень:

a) A = {a, b, c}, R = {(a, a), (a, b), (b, c), (c, b)};

R = {(x, y) ( R R: x < y };

c) D_r = {(x, y) ( R R: ( r > 0 ( I x – y I < r) };

Текст 2. Відношення еквівалентності і порядку

Відношення еквівалентності

Еквівалентність множин

Класи еквівалентності

Розбиття множин

Модульна арифметика

Відношення порядку

Тотальний і частковий порядок

Перший і останній елементи

Мінімальні і максимальні елементи

Нижня і верхня грані

Подібні множини

10.1. Відношення еквівалентності

Бінарне відношення в A, що має наступні властивості:

рефлексивне - aRa;

симетричне - якщо aRb, то bRa;

транзитивне - якщо aRb і bRc, тo aRc

називається еквівалентністю.

Приклади

Відношення колінеарності векторів є еквівалентність

Рівність двох чисел по модулю a ( b (mod.c) ( a – b = nc є еквівалентність

Звичайна рівність чисел (векторів, матриць) є еквівалентність

Подільність цілих чисел не є еквівалентністю.

Відношення x < y не є еквівалентність.

Завдання 1. Обґрунтуйте правильність наведених вище прикладів