Властивості бінарних відносин - Студопедія
1. Рефлексивність. Ставлення R називаєтьсярефлексивним, якщо (х, х)ÎR для будь-якого хÎA. Приклади рефлексивних відносин: відносини "?", "£" на множині R.
2. Антирефлексивність. Ставлення R називаєтьсяантирефлексивним, якщо (х, х)ÏR для будь-якого хÎA. Приклади антирефлексивних відносин: відносини "" на множині R.
Якщо R – антирефлексивне відношення, то xÏGR(x) та хÏHR(x) для будь-якого хÎA .
3. Симетричність. Відношення R називаєтьсясиметричним, якщо для будь-яких x, yÎA з того, що (x, y)ÎR слідує (y, x)ÎR і назад. Приклади симетричних відносин: відносини "=" та "¹".
Якщо відношення R симетричне, то для будь-якого хÎA
4. Антисиметричність. Відношення R називаєтьсяантисиметричним, якщо для будь-яких x та y з A з одночасного виконання умов (x, y)ÎR та (y, x)ÎR слід, що x = y. Приклад антисиметричного відношення. Нехай А – безліч людей у цій черзі. Відношення R – "не стояти за кимось у черзі" буде антисиметричним.
Нехай х = ВАСЯ, а y = ІВАНОВ. Той факт, що (x, y)ÎR означає, що "ВАСЯ не стоїть у черзі за ІВАНОВИМ", (y, x)ÎR - "ІВАНОВ не стоїть за ВАСЕЙ". Вочевидь, що одночасне виконання обох включень можливе, тільки якщо ВАСЯ і є ІВАНОВ, тобто. x = y.
Відношення "³" також антисиметрично: якщо x ³ y та y ³ x, то x = y.
5. Асиметричність. Відношення Rасиметрично, якщо R R -1 = Æ, тобто. перетин відносини R зі зворотним ставленням порожньо.
Еквівалентне визначення асиметричності: з двох відносин (x, y) R і (y, x) R одне не виконується.
Приклади асиметричних відносин: ">", "s = R ÇR -1 іасиметричної частинивідношення R a = R \ R s. Якщо відношення Rсиметрично, то R= R s якщо відношення R асиметрично, то R = R a .
приклади. Якщо R – "³", то R –1 – "s – "=", R a – ">".
6. Транзитивність. Відношення Rтранзитивно, якщо для будь-яких x, y, zÎA з того, що (x, y)ÎR та (y, z)ÎR випливає (x, z)ÎR.
Властивості транзитивного відношення:
б) для будь-якого хÎA з yÎGR(x) випливає, що GR(y) і GR(x).
Чи не транзитивним є відношення "¹". Нехай x = 2, y = 3, z = 2, тоді справедливо x і y y z, але x = z, тобто. (x, z)ÏR.
Відношення R1 називається транзитивним щодо відношення R2, якщо:
а) з (x, y) R1 і (y, x) R2 випливає, що (x, z) R1;
б) з (x, y) R2 і (y, x) R1 випливає, що (x, z) R1.
7. Негатранзитивність. Відношення R називаєтьсянегатранзитивним, якщо R транзитивно.
Приклади. Відносини R1 - ">" і R2 - "¹" негатранзитивні, так як відносини R1 - "£", R2 - "=" транзитивні. Можливе одночасне виконання властивостей транзитивності та негатранзитивності. Наприклад, відношення R1 одночасно транзитивно і негатранзитивно, а R2 як відомо транзитивним не є.
8. Повнота. Відношення Rповно, якщо для будь-яких x, yÎА або (x, y)ÎR, або (y, x)ÎR, або обидва відносини виконуються одночасно.
Властивості повних відносин:
а) GR(x) È HR(x) = А для будь-якого хÎA;
б) повне ставлення рефлексивне.
9. Слабка повнота. Відношення R називаєтьсяслабко повним, якщо для будь-яких х ¹ y з А або (x, y)ÎR, або (y, x)ÎR.
Приклад слабко повного відношення. Нехай А - безліч підприємств, "неблагополучних" у сенсі свого бюджету. Ставлення R "бути належним" є слабко повним, оскільки кожне з цих підприємств або комусь повинно, або йому хтось повинен, але бути належнимсебе не можна і (x, x)ÏR.
10. Ациклічність. Бінарне відношення Rациклічно, якщо R n ÇR –1 = Æ для будь-якого nÎN. Іншими словами, якщо з будь-якого кінцевого ланцюжка відносин х1Rx2, x2Rx3. xn-1Rxn слід, що x1 ¹ хn, то відношення R ациклічно.
Чи не знайшли те, що шукали? Скористайтеся пошуком:
Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно