Метод доведення в алгебрі множин з застосуванням основних властивостей операцій над множинами.
Декартовий добуток множин. Приклади.
теорії множин, дека́ртів добу́ток (прями́й добу́ток) двох множин X та Y — це множина усіх можливих впорядкованих пар, у яких перша компонента належить множині X, а друга — множині Y. Це поняття названо на честь відомого французького математика Рене Декарта.
Декартів добуток двох множин X та Y позначають як X×Y:
Наприклад, якщо множина X складається з 13 елементів { A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2 }, а множина Y — з 4 елементів {червоний, чорний, блакитний, зелений}, то декартів добуток цих множин є 52-елементною множиною (оскільки 13×4=52) {(A, червоний), (K, червоний), ... , (2, червоний), (A, чорний), ... , (3, зелений), (2, зелений)}.
Бінарні відношення на множинах. Основні поняття та означення.
інарне відношення (бінарне відношення на множині) — в математиці окремий випадок відношення на множині, яке встановлюється між двома елементами множини.
Кажуть також, що елементи a,b ∈ M знаходяться у бінарному відношенні R (часто записують у вигляді aRb), якщо впорядкована пара (a,b) ∈ R. Отже, R є підмножиною декартового квадрата: R ⊆ M×M.
Іноді розрізняють поняття бінарного відношення на множині та бінарного відношення між множинами, яке в цій енциклопедії називається відповідністю між множинами.
Представлення відношення за допомогою матриці і графа. Приклади.
A={1,2,3,4,5,6,7,8}
B={14,15,16}
q = {(a,b) є AxB | b ⁞ a}
AxB =…..
|
14 |
15 |
16 |
1 |
1 |
1 |
1 |
2 |
1 |
0 |
1 |
3 |
0 |
1 |
0 |
4 |
0 |
0 |
1 |
5 |
0 |
1 |
0 |
6 |
0 |
0 |
0 |
A B
1
2 14
3
4 15
5
6 16
14.Композицією відношень R1 і R2 на множині M (позначається R1°R2 ) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент cÎM, для якого виконується aR1c і cR2b. Наприклад, композицією відношень R1 - "є сином" і R2 - "є братом" на множині чоловіків є відношення R1°R2 - "є небожем".
15. Відношення R-1 називається оберненим до відношення R, якщо bR-1a тоді і тільки тоді, коли aRb. Очевидно, що (R-1)-1=R.
Наприклад, для відношення "більше або дорівнює" оберненим є відношення "менше або дорівнює", для відношення "ділиться на" — відношення "є дільником".
16. Функціональне бінарне відношення
Бінарне відношення Γ називається функціональним, якщо воно не містить упорядкованих пар з однаковими першими елементами.
17.Властивості бінарних відношень.
Наведемо список важливих властивостей, за якими класифікують відношення.
Нехай R - деяке відношення на множині M.
а). Відношення R називається рефлексивним, якщо для всіх aÎM має місце aRa.
Очевидно, що відношення R1,R2,R4,R5,R7 - рефлексивні.
б). Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного aÎM не виконується aRa.
Відношення "більше", "менше", "є сином" антирефлексивні. В той же час, відношення R6 не є ні рефлексивним, ні антирефлексивним.
Всі елементи головної діагоналі матриці C для рефлексивного відношення на скінченній множині M дорівнюють 1, а для антирефлексивного відношення дорівнюють 0.
в). Відношення R називається симетричним, якщо для всіх a,bÎM таких, що aRb маємо bRa.
г). Відношення R називається антисиметричним, якщо для всіх a,bÎM таких, що 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°RÍR.