Лекція 5

4 Властивості бінарних відношень

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

Р

	a	b	c
a	1	…	…
b	…	1	…
c	…	…	1

ефлексивність. Відношення R на множині Х називається рефлексивним, якщо для буд-якого хХ має місце xRx, тобто кожен елемент хХ знаходиться у відношенні R до самого себе.

А

	a	b	c
a	0	…	…
b	…	0	…
c	…	…	0

нтирефлексивність. Відношення R на множині Х називається антирефлексивним, якщо для має місце x₁Rx₂, і при цьому x₁≠x₂.

Матриця рефлексивного відношення на головній діагоналі містить одиниці, а для анти рефлексивного – нулі.

Симетричність. Відношення R на множині Х називається симетричним, якщо для пари (х₁, х₂)  R² маємо x₁Rx₂, і x₂Rx₁, тобто відношення виконується в обидва боки.

Асиметричність. Відношення R на множині Х називається асиметричним, якщо для пари (х₁, х₂)  R² існує x₁Rx₂, то не існує x₂Rx₁.

Антисиметричність. Відношення R на множині Х називається антисиметричним, якщо для пари (х₁, х₂)  R² існує x₁Rx₂ і x₂Rx₁, то x₂=x₁.

Приклад. Множина симетричних точок відносно осі a. Якщо точка А симетрична точці В, то і точка В симетрична точці А. тобто відношення симетричності точок відносно осі – симетричне.

Приклад. Відношення порівняння 2х дійсних чисел на знак : якщо a  b і b  a , то a = b, тобто відношення – антисиметричне.

П риклад. Відношення порівняння 2х дійсних чисел на знак >: якщо a > b і b > a , то a ≠ b, тобто відношення – асиметричне.

Транзитивність. Відношення R називається транзитивним, якщо з x₁Rx₂, і x₂Rx₃ виходе x₁Rx₃.

Антитранзитивність. Відношення R називається антитранзитивним, якщо з x₁Rx₂, і x₂Rx₃ не виходе x₁Rx₃.

Приклад. Відношення порівняння 2х дійсних чисел на знак  або >: якщо a  b і b  с , то a  с, тобто відношення – транзитивне.

Приклад. Розглянемо відношення m – дільник числа n: якщо 3 – є дільник числа 12, а 12 – є дільник числа 48, то 3 – є дільник числа 48. Тобто відношення транзитивне.

Приклад. Відношення «Батько» розглянуте раніше – антитранзитивне.

 Завдання

1. Визначте, які властивості має кожне з наведених відношень. Відношення задані на множині А={1, 2, 3, 4}:

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

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

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

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

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

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

2. Визначте, які властивості має кожне з відношень, що зображені такими графами:

a) b) c) d)

3. Визначте, які властивості мають такі відношення, що задані на множині людей. Нехай (a, b)R, якщо:

1. а вище на зріст ніж b;

2. a і b народились в один день;

3. а є родичем b;

4. а знайомий з b;

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

Тема: Відношення еквівалентності, порядку, толерантності

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

Завдання

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

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

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

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

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

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

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

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