Тема 5. Відношення. Основні властивості відношень.

Питання теми

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

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

3. Властивості відношень.

Основні терміни теми : відношення, рефлекcивність, симетричність, транзитивність відношень.

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

Означення. Підмножина RMn називають n-містним відношенням на множині M.

Кажуть, що a1, ... , an знаходяться у відношенні R, якщо (a1, ... , an)  R. Одномістне відношення - це просто  підмножина M. Такі відношення називають ознаками: a володіє ознаками R, якщо aR та RM. Властивості одномістних відносин - це властивості підмножин M, ось чому для випадку n=1 термін “відношення” використовується рідко.

Приклади.

1. Підмножина натуральних чисел у множині цілих.

2. Парні числа у множині натуральних та ін.

Найбільш часто зустрічаються та найбільш вивченими є двоомістні, або бінарні відносини. Якщо a та b знаходяться у відношенні R то це часто записують як aRb.

Приклади.

1. Відношення на N.

- відношення  виповнюється для пар ( 7,7 ) , ( 7,9 ), але не виповнюється для пари ( 9,7 ) ;

- відношення  “  мати  загальний дільник “, який відрізняється від 1” виповнюється для пар ( 6,9 ), ( 4,2 ), ( 2,4 ), але не виповнюється для пар ( 7,9 ), ( 11, 23 );

- відношення “ бути дільником” виповнюється для пар ( 4,9 ), ( 7,9 ).

2. Відношення на множені крапок дійсної площини.

- знаходяться на однаковій відстані.

3. Відношення на множині людей.

Хай буде відношення R на M. Для  підмножини М1  М означається відношення  R`, яке зветься звуженням R на М1, яка виходить з R вилученням всіх пар, які мають елементи, що не належать до М1.

 .

Для отримання бінарних відношень можна використовувати різні засоби завдання множин ( наприклад, список пар ). Відношення на скінчених множинах звичайно задаються списком або матрицею С

  порядок матриці - m;

C = 

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

Приклад:

для множини М=  задамо відношення R - “бути більше”.

Тоді R={(2;1),(3;1),(3;2),(4;1),(4;2),(4;3),(5;1),(5;2),(5;3),(5;4),(6;1),(6;2),(6;3),(6;4),(6;5)}

Матриця відношення:

R       1          2          3          4          5          6

1        0          0          0          0          0          0

2        1          0          0          0          0          0

3        1          1          0          0          0          0

4        1          1          1          0          0          0

5        1          1          1          1          0          0

6        1          1          1          1          1          0

Граф відношення:

 

Відношення підкоряються всім операціям на множинах.

Означення .Відношення називають оберненим  до відношення R (R-1), якщо ai R-1 aja  Raj .

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

3. Властивості відношень

Відношення R називається рефлексивним, якщо для  а М має місце aRa. Головна діагональ його матриці має тільки одиниці.

Відношення R називається антирефлексивним, якщо ні для якого а М не виповнюється аRa. Головна діагональ має тільки нолі.

Відношення R називається нерефлексивним (арефлексивним) , якщо воно не рефлексивно та не антирефлексивно.

Відношення R називається симетричним, якщо для пари (a,d) M2 aRddRa. Матриця симетрична відносно головної діагоналі.

Відношення R називається  антисиметричним, якщо з aRd та dRa виходить, що а=d. Матриця трикутна відносно головної діагоналі.

Відношення R називають несиметричним, якщо воно не симетрично та не антисиметричне.

Відношення R називають транзитивним, якщо для  a,d,c  M з aRd та dRc виходить aRc.

Якщо нетранзитивне відношення R на М є RR1 (R1 транзитивне на М) тоді R1 називається транзитивним замиканням на М.

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

Відношення R називають відношенням нестрогого порядку, якщо воно  рефлексивне, антисиметричне та транзитивне.

Відношення R називають відношенням строгого порядку, якщо воно антирефлексивне, антисиметричне та транзитивне.