Лекція 2. Бінарні відношення і їхні властивості

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

Визначення. Бінарним відношенням a між елементами множин S і R назвемо будь-яку підмножину декартового добутку S ´ R, тобто a Í S´R.

Якщо (х,у) Î a, то говорять, що х знаходиться у відношенні a до у і пишуть хaу.

Далі будемо розглядати відношення aÍ R´R, причому R={r₁,r₂,...,r_n}.

Бінарне відношення може бути задане:

· графіком відношення, тобто множиною пар (r_i,r_j)Îa;

· матрицею N, елемент i,j якої дорівнює 1, якщо (r_i,r_j)Îa і 0, якщо (r_i,r_j)Ïa.

Приклад. Нехай R={1,2,3,4,5,6}. Тоді бінарними відношеннями на R є:

a₁ = {(1,1),(1,2),(2,3),(3,1),(4,5),(5,2),(6,6)};

a₂ = {(1,1),(5,1),(6,2),(6,6)};

a₃ = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)};

a₄ = {(1,1),(2,1),(2,2),(3,1),(4,1),(4,2),(5,1),(3,3),(4,4),(5,5,),(6,1),(6,2),(6,3), (6,6)};

a₅ = {(1,2),(2,1),(3,2),(2,3)};

a₆ = {(1,2),(2,3),(1,3),(3,4),(1,4),(2,4)}.

Зверніть увагу, що деякі з цих відношень вже нам знайомі, зокрема відношення a₃ можна назвати «r_i дорівнює r_j», а відношення a₄ - «r_i поділяється без остатку на r_j». Цей приклад підкреслює, яке значення для формалізації має поняття «відношення».

Надалі будемо використовувати деякі корисні відношення, які можуть бути визначені для довільної множини.

Визначення. Тотожним відношенням для довільної множини R назвемо відношення I_R = {(r_i,r_i): r_iÎR}. Універсальним відношенням для довільної множини R назвемо відношення U_R = {(r_i,r_j): r_iÎR, r_jÎR}.

З усіх бінарних відношень виділимо класи, що мають корисні властивості.

Визначення. Бінарне відношення aÍR´R назвемо рефлексивним, якщо для кожного r_iÎR справедливо (r_i,r_i)Îa, інакше - антирефлексивним. Бінарне відношення назвемо ірре­флек­сивним, якщо для кожного r_iÎR справедливо (r_i,r_i)Ïa. Зокрема, a₃, a₄ - приклади ре­флекс­сивних відношень, a₁, a₂ – антирефлексивних, a₅, a₆ – іррефлексивних.

Визначення. Бінарне відношення a Í R ´ R назвемо симетричним, якщо з (r_i,r_j)Îa випливає (r_j,r_i)Îa_. Якщо з (r_i,r_j) Î a і (r_j,r_i) Î a випливає r_i = r_j, то відношення назвемо антисиметричним. Зокрема, a₅ – приклад симетричного відношення. Якщо з aab випливає (b,a) Ï a, то відношення назвемо асиметричним.

Зазначимо, що властивості симетричності і антисиметричності не є взаємно вик­люч­ними. Легко пересвідчитись, що для будь-якої множини R відношення I_Rє симетричним і антисиметричним. Ми можемо також визначити відношення, які не є ні симетрич­ними, ні анти­сим­ет­ричними.

Приклад. Нехай маємо множину всіх людей. Визначимо відношення В таке, що x Вy тоді і тільки тоді, коли xє братом у. В сім’ї, що складається з двох братів рі qта сестри г, ми отримуємо відношення В,яке не є сим­етричним, тому що p В r,але не r В p. Це відношення також не є антисиметричним, тому що p B qі q B p, хо­чр і q різні.

Визначення. Бінарне відношення a Í R ´ R назвемо транзитивним, якщо з (r_i,r_j) Î a і (r_j,r_l) Î a випливає (r_i,r_l) Î a, r_i ¹ r_j, r_i ¹ r_l, r_l ¹ r_j. Зокрема, a₄ і a₆ – приклади транзитивного відношення.

Існує багато інших властивостей відношень, які можна було б розглянути. Однак наведені вище властивості є найважливішими і будуть ча­сто використовуватися в подальшому.

2. Відношення часткового порядку. Для дискретної математики характерне викори­стан­ня класів відношень, що визначені на різних множииах, але володіють тим ж набором властивостей.

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

Приклади відношення часткового порядку: a₄ ; відношення £ на множині позитивних цілих чисел, тобто a₇ = (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6), (4,4), (4,5), (4,6), (5,5), (5,6), (6,6)}; відношення включення R Í S на булеані P(U) і ін.

Визначення. Множина R, на якій задане відношення часткового порядку називається частково упорядкованою.

Для такої множини важливими характеристиками є: верхня універсальна границя I, якщо I ³ r_i для будь-якого r_iÎR; нижня універсальна границя О, якщо О £ r_i для будь-якого r_iÎR.

Говорять ще, що О – найменший, а I – найбільший елемент множини R.