1. Відношення: визначення і приклади. Почнемо з базового визначення.
Визначення. Бінарним відношенням a між елементами множин S і R назвемо будь-яку підмножину декартового добутку S ´ R, тобто a Í S´R.
Якщо (х,у) Î a, то говорять, що х знаходиться у відношенні a до у і пишуть хaу.
Далі будемо розглядати відношення aÍ R´R, причому R={r1,r2,...,rn}.
Бінарне відношення може бути задане:
· графіком відношення, тобто множиною пар (ri,rj)Îa;
· матрицею N, елемент i,j якої дорівнює 1, якщо (ri,rj)Îa і 0, якщо (ri,rj)Ïa.
Приклад. Нехай R={1,2,3,4,5,6}. Тоді бінарними відношеннями на R є:
a1 = {(1,1),(1,2),(2,3),(3,1),(4,5),(5,2),(6,6)};
a2 = {(1,1),(5,1),(6,2),(6,6)};
a3 = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)};
a4 = {(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)};
a5 = {(1,2),(2,1),(3,2),(2,3)};
a6 = {(1,2),(2,3),(1,3),(3,4),(1,4),(2,4)}.
Зверніть увагу, що деякі з цих відношень вже нам знайомі, зокрема відношення a3 можна назвати «ri дорівнює rj», а відношення a4 - «ri поділяється без остатку на rj». Цей приклад підкреслює, яке значення для формалізації має поняття «відношення».
Надалі будемо використовувати деякі корисні відношення, які можуть бути визначені для довільної множини.
Визначення. Тотожним відношенням для довільної множини R назвемо відношення IR = {(ri,ri): riÎR}. Універсальним відношенням для довільної множини R назвемо відношення UR = {(ri,rj): riÎR, rjÎR}.
З усіх бінарних відношень виділимо класи, що мають корисні властивості.
Визначення. Бінарне відношення aÍR´R назвемо рефлексивним, якщо для кожного riÎR справедливо (ri,ri)Îa, інакше - антирефлексивним. Бінарне відношення назвемо іррефлексивним, якщо для кожного riÎR справедливо (ri,ri)Ïa. Зокрема, a3, a4 - приклади рефлекссивних відношень, a1, a2 – антирефлексивних, a5, a6 – іррефлексивних.
Визначення. Бінарне відношення a Í R ´ R назвемо симетричним, якщо з (ri,rj)Îa випливає (rj,ri)Îa. Якщо з (ri,rj) Î a і (rj,ri) Î a випливає ri = rj, то відношення назвемо антисиметричним. Зокрема, a5 – приклад симетричного відношення. Якщо з aab випливає (b,a) Ï a, то відношення назвемо асиметричним.
Зазначимо, що властивості симетричності і антисиметричності не є взаємно виключними. Легко пересвідчитись, що для будь-якої множини R відношення IRє симетричним і антисиметричним. Ми можемо також визначити відношення, які не є ні симетричними, ні антисиметричними.
Приклад. Нехай маємо множину всіх людей. Визначимо відношення В таке, що x Вy тоді і тільки тоді, коли xє братом у. В сім’ї, що складається з двох братів рі qта сестри г, ми отримуємо відношення В,яке не є симетричним, тому що p В r,але не r В p. Це відношення також не є антисиметричним, тому що p B qі q B p, хочр і q різні.
Визначення. Бінарне відношення a Í R ´ R назвемо транзитивним, якщо з (ri,rj) Î a і (rj,rl) Î a випливає (ri,rl) Î a, ri ¹ rj, ri ¹ rl, rl ¹ rj. Зокрема, a4 і a6 – приклади транзитивного відношення.
Існує багато інших властивостей відношень, які можна було б розглянути. Однак наведені вище властивості є найважливішими і будуть часто використовуватися в подальшому.
2. Відношення часткового порядку. Для дискретної математики характерне використання класів відношень, що визначені на різних множииах, але володіють тим ж набором властивостей.
Визначення. Бінарне відношення на множини R, що має властивості рефлексивності, антисиметричності і транзитивності, назвемо відношенням часткового порядку і будемо позначати £.
Приклади відношення часткового порядку: a4 ; відношення £ на множині позитивних цілих чисел, тобто a7 = (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 ³ ri для будь-якого riÎR; нижня універсальна границя О, якщо О £ ri для будь-якого riÎR.
Говорять ще, що О – найменший, а I – найбільший елемент множини R.
