Содержание
- 2. 2.3. Властивості бінарних відношень рефлексивність антирефлексивність симетричність асиметричність антисиметричність транзитивність антитранзитивність замикання відношень
- 3. Рефлексивність Відношення R на множині X називається рефлексивним, якщо для будь-якого х∈X має місце xRx. E⊆R
- 4. Антирефлексивність Відношення R на множині X називається антирефлексивним, якщо з x1R x2 виходить, що x1≠ x2.
- 5. Симетричність Відношення R на множині X називається симетричним, якщо для пари (x1, х2)∈X2 з x1 R
- 6. Асиметричність Відношення R на множині X називається асиметричним, якщо для пари (x1, х2)∈X2 із x1 R
- 7. Антисиметричність Відношення R на множині X називається антисиметричним, якщо з x1 R x2 і x2 R
- 8. Транзитивність Відношення R на множині X називається транзитивним, якщо з x1 R x2 і x2 R
- 9. Антитранзитивність Відношення R на множині X називається антитранзитивним, якщо з x1 R x2 і x2 R
- 10. Приклад перевірки на транзитивність та антитранзитивність a3 R a1 і a1 R a4 ⇒ a3 R
- 11. Замикання Рефлексивним замиканням RE відношення R називається відношення RE=R∪E, де E – відношення тотожності на X
- 12. Симетричним замиканням RS відношення R називається відношення RS=R∪R-1, тобто якщо (x1, х2)∈R, то (x1, х2)∈RS i
- 13. Транзитивним замиканням Rt відношення R називається відношення Rt=R∪R1∪…∪Rn∪… a1 a2 a3 a4
- 14. Алгоритм Уоршалла побудови транзитивного замикання для відношення R. Нехай відношення задано у вигляді матриці. Присвоювання початкових
- 15. Приклад. Використаня алгоритму Уоршалла для побудови транзитивного замикання. Нехай A={1, 2, 3, 4}, R ⊆ A×А
- 16. W(2)=W(1) бо другий стовпчик нульовий Результат W(4)
- 17. 2.4. Відношення еквівалентності, толерантності, порядку відношення еквівалентності класи еквівалентності відношення толерантності строгий порядок частковий (нестрогий) порядок
- 18. Бінарне відношення, що має властивості рефлексивності, симетричності і транзитивності, називається відношенням еквівалентності (позначається ~). Нехай задана
- 19. Розбиття скінченної множини А на класи еквівалентності за відношенням R. Виберемо елемент а1∈А і утворимо клас
- 20. Система класів С1, С2, … ,Сn називається системою класів еквівалентності і має такі властивості: 1. класи
- 21. Приклад. Нехай A={2, 4, 6, 8, 12, 15}, R1 ⊆ A×А R1 – мати однакову кількість
- 22. Приклад. Нехай A={2, 4, 6, 8, 12, 15}, R2 ⊆ A×А R2 = {(2,2),(2,6),(4,4),(4,8),(4,12),(6,2),(6,6), (8,4),(8,8),(8,12),(12,4),(12,12), (15,15)}
- 23. Бінарне відношення, що має властивості рефлексивності, симетричності і антитранзитивності, називається відношенням толерантності. Толерантність зображує собою формальне
- 24. Відношення порядку Бінарне відношення, що має властивості антирефлексивності (якщо а Приклад. A – множина студентів групи,
- 25. Бінарне відношення, що має властивості рефлексивності, антисиметричності і транзитивності, називається відношенням нестрогого (часткового) порядку (позначається ≤).
- 26. Зображення відношення часткового порядку {a} {∅} {c} {a, b} {b, c} {a, c} {a, b, c}
- 27. діаграма Хассе {a} {∅} {c} {a, b} {b, c} {a, c} {a, b, c} {b}
- 28. Шлях у графі відношення з вершини а до вершини b — це послідовність дуг (а, х1),
- 29. A={2, 4, 6, 8, 12, 24}, В={ 4, 8, 12}, В ⊆ A R ⊆ A×А,
- 30. Мажорантою (найбільшим елементом, верхньою гранню) підмножини В називають такий елемент m∈А, що для будь-якого елемента b∈B
- 31. Якщо верхній конус підмножини В має мінімальний елемент, то він називається точною верхньою гранню В і
- 32. Мінорантою (найменшим елементом, нижньою гранню) підмножини В називають такий елемент n∈А, що для будь-якого елемента b∈B
- 33. Якщо нижній конус підмножини В має максимальний елемент, то він називається точною нижньою гранню В і
- 34. 2.5. Функціональні відношення функціональне відношення області визначення і значень відображення (функція) сюр'єкція, ін'єкція, бієкція
- 35. Відношення R між множинами X і Y (R⊆X×Y) є функціональним, якщо всі його елементи (упорядковані пари)
- 36. Нехай R — деяке відношення, R⊆X×Y. Областю визначення відношення R називається множина DR (DomR), що складається
- 37. Відображення (функція) Функцією f або відображенням f множини X в Y (позначається f: X → Y)
- 38. Види відображень Функція f: X→Y називається сюр'єктивним відображенням, якщо ℜf = Y. На графі, що зображує
- 39. Функція f: X→Y називається ін'єктивним відображенням, якщо з x1≠x2 виходить f(x1)≠f(x2). На графі, що зображує ін'єктивне
- 40. Якщо f: X→Y — ін'єктивне відображення і F={(х,f(х)), ∀х∈X} — відповідне функціональне відношення (F⊂X→Y), то обернене
- 42. Скачать презентацию