Відношення.
Властивості відношень (реферат)
Найбільш популярними в математиці є двомісні або бінарні відношення, на вивченні властивостей яких ми зупинимось детальніше. Далі скрізь під словом «відношення» розумітимемо бінарне відношення. Якщо елементи a, bзнаходяться у відношенні R (тобто (a, b) то це часто записують у вигляді aRb. Зауважимо, що бінарні відношення іноді розглядають, як окремий випадок відповідностей, а саме — як… Читати ще >
Відношення. Властивості відношень (реферат) (реферат, курсова, диплом, контрольна)
Реферат на тему:
Відношення. Властивості відношень
Підмножина R декартового степеня Mn деякої множини M називається n-місним або n-арним відношенням на множині M. Кажуть, що елементи a1, a2,…, anзнаходяться у відношенні R, якщо (a1,a2,…, an)/p>
При n=1 відношення Rназивають одномісним або унарним. Таке відношення часто називають також ознакою або характеристичною властивістю елементів множини M. Кажуть, що елемент aмає ознаку R, якщо aі RНаприклад, ознаки «непарність» і «кратність 7» виділяють із множини N натуральних чисел унарні відношення R{2k-1 | k і R = {7k | k, відповідно.
Найбільш популярними в математиці є двомісні або бінарні відношення, на вивченні властивостей яких ми зупинимось детальніше. Далі скрізь під словом «відношення» розумітимемо бінарне відношення. Якщо елементи a, bзнаходяться у відношенні R (тобто (a, b) то це часто записують у вигляді aRb. Зауважимо, що бінарні відношення іноді розглядають, як окремий випадок відповідностей, а саме — як відповідності між однаковими множинами.
Приклад 1.13. Наведемо приклади бінарних відношень на різних множинах.
1. Відношення на множині N натуральних чисел:
R1 — відношення «менше або дорівнює», тоді 4R19, 5R15, 1R1m для будь-якого m.
R2 — відношення «ділиться на», тоді 4R23, 49R27, mR21 для будь-якого m.
R3 — відношення «є взаємно простими», тоді 15R38, 366R3121, 1001R3612;
R4 — відношення «складаються з однакових цифр», тоді 127R4721, 230R 4 302, 3231R 43 213 311.
2. Відношення на множині точок координатної площини R2:
R5 — відношення «знаходяться на однаковій відстані від початку координат», тоді (3,2) R5 ( , — ), (0,0)R 5 (0,0) ;
R6 — відношення «симетричні відносно осі ординат», тоді (1,7)R6(-1,7) і взагалі (a, b) R6(-a, b) для будь-яких a, b.
R7 — відношення «менше або дорівнює». Вважаємо, що (a, b) R7(c, d), якщо a і b Зокрема, (1,7)R7(20,14), (-12,4)R7(0,17).
3. Відношення на множині студентів даного вузу:
R8 — відношення «є однокурсником» ,.
R9 — відношення «є молодшим за віком від» .
Для задання відношень можна користуватись тими ж способами, що і при заданні множин. Наприклад, якщо множина M скінченна, то довільне відношення R на M можна задати списком пар елементів, які знаходяться у відношенні R.
Зручним способом задання бінарного відношення R на скінченній множині M = {a1,a2,…, an} є задання за допомогою так званої матриці бінарного відношення. Це квадратна матриця C порядку n, в якій елемент cij, що стоїть на перетині i-го рядка і j-го стовпчика, визначається так.
якщо aiRaj,.
cij = >
в противному разі.
Приклад 1.14. Для скінченної множини M = {2,7,36,63,180} матриці наведених вище відношень R1, R2, R3 мають такий вигляд.
.
Рис. 1.5.
Відношення можна задавати також за допомогою графіків і діаграм. Графік відношення означається й будується так само, як і графік відповідності. Поняття діаграми (або графа) відношення також можна означити аналогічно до відповідності. Однак частіше діаграма (або граф) відношення R на скінченній множині M={a1,a2,…, an} означається таким чином. Поставимо у взаємно однозначну відповідність елементам множини M деякі точки площини. З точки ai до точки aj проводимо напрямлену лінію (стрілку) у вигляді відрізка або кривої тоді і тільки тоді, коли aiRaj. Зокрема, якщо aiRai, то відповідна стрілка, що веде з ai в ai, називається петлею.
Оскільки відношення на M є підмножинами множини M 2, то для них означeні всі відомі теоретико-множинні операції. Наприклад, перетином відношень «більше або дорівнює» і «менше або дорівнює» є відношення «дорівнює», об'єднанням відношень «менше» і «більше» є відношення «не дорівнює», доповненням відношення «ділиться на» є відношення «не ділиться на» тощо.
Аналогічно відповідностям для відношень можна означити поняття оберненого відношення і композиції відношень.
Відношення R-1 називається оберненим до відношення R, якщо bR-1a тоді і тільки тоді, коли aRb. Очевидно, що (R-1)-1=R. Наприклад, для відношення «більше або дорівнює» оберненим є відношення «менше або дорівнює», для відношення «ділиться на» — відношення «є дільником» .
Композицією відношень R1 і R2 на множині M (позначається R1) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент cдля якого виконується aR1c і cR2b. Наприклад, композицією відношень R1 — «є сином» і R2 — «є братом» на множині чоловіків є відношення R1 — «є небожем» .
Наведемо список важливих властивостей, за якими класифікують відношення.
Нехай R — деяке відношення на множині M.
а). Відношення R називається рефлексивним, якщо для всіх aмає місце aRa.
Очевидно, що відношення R1, R2,R4,R5,R7 — рефлексивні.
б). Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного aне виконується aRa.
Відношення «більше», «менше», «є сином» антирефлексивні. В той же час, відношення R6 не є ні рефлексивним, ні антирефлексивним.
Всі елементи головної діагоналі матриці C для рефлексивного відношення на скінченній множині M дорівнюють 1, а для антирефлексивного відношення дорівнюють 0.
в). Відношення R називається симетричним, якщо для всіх a, bтаких, що aRb маємо bRa.
г). Відношення R називається антисиметричним, якщо для всіх a, bтаких, що aRb і bRa маємо a = b.
Наприклад, відношення R3, R4,R5,R6,R8 — симетричні, а відношення R1, R2,R7 — антисиметричні.
Неважко переконатись, що відношення R симетричне тоді і тільки тоді, коли R=R-1.
д). Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.
Наприклад, відношення R1, R2,R4,R5,R7,R8,R9 — транзитивні, а відношення R3, R6 — не транзитивні.
Неважко переконатись, що відношення R транзитивне тоді і тільки тоді, коли R/p>
Зауважимо, якщо відношення R має будь-яку з перерахованих вище властивостей, то обернене відношення R-1 також має ту саму властивість. Таким чином, операція обернення зберігає всі п’ять властивостей відношень.
Для довільного відношення R означимо нову операцію. Відношення R* називається транзитивним замиканням відношення R на M, якщо aR*b, a, bтоді і тільки тоді, коли у множині M існує послідовність елементів a1, a2,…, an така, що a1 = a, an = b і a1Ra2, a2Ra3,…, an-1Ran.
Наприклад, нехай M — це множина точок на площині і aRb, a, bякщо точки a і b з'єднані відрізком. Тоді cR*d, c, dякщо існує ламана лінія, яка з'єднує точки c і d.
Можна довести, що відношення R транзитивне тоді і тільки тоді, коли R*=R.
Деякі відношення займають особливе місце в математиці. Розглянемо ці відношення окремо.