Лабораторна робота №3 на тему Бінарні відношення та їх властивості
« НазадЛАБОРАТОРНА РОБОТА №3ТЕМА РОБОТИ: «БІНАРНІ ВІДНОШЕННЯ ТА ЇХ ВЛАСТИВОСТІ»МЕТА РОБОТИ: набути знань та практичних навичок побудови бінарних відношень та вивчення їх властивостей. ХІД РОБОТИ Збережіть цей файл з ім’ям zvit_lab_3 у своїй папці на сервері. Відкрийте його для роботи. ЗАВДАННЯ 1. Уважно перегляньте методичні рекомендації МЕТОДИЧНІ РЕКОМЕНДАЦІЇ
Підмножина R декартового степеня Mn деякої множини M називається n-місним або n-арним відношенням на множині M. Кажуть, що елементи a1,a2,...,an∈M знаходяться у відношенні R, якщо (a1,a2,...,an)∈R. При n=1 відношення R⊆M називають одномісним або унарним. Найбільш популярними у математиці є двомісні або бінарні відношення. Далі скрізь під словом "відношення" розумітимемо бінарне відношення. Якщо елементи a,b∈M знаходяться у відношенні R, тобто (a,b)∈R, то це часто записують також у вигляді aRb. Відношення можна задавати тими ж способами, що й звичайні множини. Крім того, зручним способом задання бінарного відношення R на скінченній множині M={a1,a2,...,an} є задання за допомогою так званої матриці бінарного відношення. Це квадратна матриця C порядку n, в якій елемент cij, що стоїть на перетині i-го рядка і j-го стовпчика, визначається так: cij = 1, якщо aiRaj, cij = 0 у противному разі. Відношення можна задавати також за допомогою графіків і діаграм. Графік відношення означається й будується так само, як і графік відповідності. Поняття діаграми (або графа) відношення також можна означити аналогічно до відповідності. Однак частіше діаграма (або граф) відношення R на скінченній множині M={a1,a2,...,an} означається таким чином. Поставимо у взаємнооднозначну відповідність елементам множини M деякі точки площини. З точки ai до точки aj проводимо напрямлену лінію (стрілку) у вигляді відрізка або кривої тоді і тільки тоді, коли aiRaj. Зокрема, якщо aiRai, то відповідна стрілка, що веде з ai в ai, називається петлею. Відношення R на множині M називається відношенням еквівалентності (або просто еквівалентністю), якщо воно рефлексивне, симетричне і транзитивне, тобто: а) aRa для всіх a ∈ M (рефлексивність); б) якщо aRb, то bRa для a,b∈M (симетричність); в) якщо aRb і bRc, то aRc для a,b,c∈M (транзитивність). Сукупність множин { Bi | i∈N} називається розбиттям множини A, якщо UBi = A і Bi∩Bj= ∅ для i ≠ j. Відношення R на множині M називається відношенням часткового (нестрогого) порядку, якщо воно рефлексивне, антисиметричне і транзитивне, тобто а) aRa для всіх a∈M (рефлексивність), б) якщо aRb і bRa, то a = b (антисиметричність), в) якщо aRb і bRc, то aRc (транзитивність). Відповідне відношення R, задане на лінійно впорядкованій множині, називається лінійним (досконалим) порядком. Таким чином, відношення R на множині M називається відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне і для будь-якої пари елементів a,b∈M виконується aRb або bRa. Для позначення відношень порядку будемо використовувати знаки ≤ і ≥. Тобто для відношення порядку R замість aRb будемо записувати a ≤ b або b ≥ a і читати "a менше або дорівнює b" або "b більше або дорівнює a" відповідно. Очевидно, що ≤ є оберненим відношенням до відношення ≥. Порядок ≥ іноді називають двоїстим порядком до ≤. За кожним відношенням часткового порядку ≤ на довільній множині M можна побудувати інше відношення < на M, поклавши a < b тоді і лише тоді, коли a ≤ b і a ≠ b. Це відношення називається відношенням строгого порядку на множині M. Зрозуміло, що відношення строгого порядку антирефлексивне, транзитивне, а також задовольняє умову так званої сильної антисиметричності або асиметричності, тобто для жодної пари a,b∈M не може одночасно виконуватись a < b і b < a. З іншого боку, за довільним відношенням строгого порядку < на множині M однозначно можна побудувати відповідне відношення часткового (нестрогого) порядку ≤, поклавши a ≤ b тоді і тільки тоді, коли a < b або a = b, a,b∈M Приклад 1. Нехай М={1,2,3,4,5,6}. Задати переліком та матрицею відношення R⊆MxM, якщо R – «бути строго менше». Відповідь: Відношення R як множина містить всі пари елементів a,b з M таких, що a<b: R={(a,b)| a,b ÎM; a<b }. Тоді. Матриця відношення R має вигляд. ЗАВДАННЯ 2. РОЗВ’ЯЖІТЬ ЗАДАЧІ. 1. Для відношень R1 та відношення R2 на множині М={1,2,3,4} побудуйте матриці відношень та визначте всі елементи відношень, якщо R1 – «ділитися на 2», а R2 - «менше 3». 3. На множині студентів вашої групи побудуйте відношення явним переліком (задаючи ПІБ, наприклад, Петрова Ганна Іванівна – ПГІ) та у вигляді матриці відношення R⊆MxM, якщо: 1) R1 – «бути вищим на зріст»; 2) R2– «народитися на Київщині»; 3) R3 – «мати розмір одягу менший 48». 4.Які з наведених у задачі 4 відношень є: a) рефлексивними; b) антирефлексивними; c) симетричними; d) антисиметричними; e) транзитивними; f) толерантними? 5. Які з відношень задачі 4 є відношеннями часткового, строгого чи лінійного порядку? ПИТАННЯ ДЛЯ САМОКОНТРОЛЮ1. Що є відношення? 2. Які способи визначення відношень існують? 3. Яке відношення називають рефлексивним? 4. Яке відношення називають антирефлексивним? 5. Яке відношення називають симетричним? 6. Яке відношення називають антисиметричним? 7. Яке відношення називають толерантним? 8. Як будується матриця бінарного відношення? 9. Чи можна задати відношення переліком елементів? 10. Яке відношення називають відношенням часткового порядку? 11. Яке відношення називають відношенням строгого порядку? 12. Які властивості має відношення строгого порядку? 13. Яке відношення називають відношенням лінійного порядку? 14. Яке відношення називають відношенням еквівалентності? ПИТАННЯ ДЛЯ САМОКОНТРОЛЮ15. Що є множина, порожня множина і універсум? 16. Які засоби визначення множин існують? 17. Які операції діють над множинами? 18. Як можуть співвідноситися дві множини? 19. Що таке булеана множини? 20. Яке співвідношення між потужністю множини і потужністю її булеана? 21. Що таке потужність множини? 22. Чому дорівнює потужність скінченої множини? 23. Як формулюється теорема Кантора? 24. Чи вірним є твердження, що порожня множина є підмножиною будь-якої множини? 25. Чи вірним є твердження, що порожня множина є елементом будь-якої множини? З повагою ІЦ “KURSOVIKS”! |