МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Основні поняття теорії відношень
В загальному випадку відношення визначає який-небудь зв’язок між предметами або поняттями. Відношення між парами об’єктів називають бінарними. Бінарне відношення між елементами двох множин встановлює відповідність елементів однієї множини X елементам іншої множини Y. Таке відношення може бути задане як множина упорядкованих пар (x, y), які є елементами множини X ´ Y. Якщо A − відношення, то співвідношення xAy можна записати також у вигляді (x, y)ÎA, де A Ì X ´ Y. Наприклад, вирази 3 < 7 і (3, 7)Î< означають одне й те ж, однак, перший з них звичніший. В той же час вираз (7, 3)Î< означає 7<3, що неправильно. Таким чином, в загальному випадку переставляти елементи в парі (x, y) не можна, що і підкреслюється назвою пари − упорядкована. Елемент x називається першою координатою, а елемент y− другою координатою упорядкованої пари. Областю визначення відношення A (позначення DВ) називається множина всіх перших координат, а областю значень (позначення DЗ) − множина всіх других координат. Якщо xÎX i yÎY, то DВ (A)ÌX i DЗ (A)ÌY В цьому випадку кажуть, що A є відношення віддо. Якщо Y = X, то будь-яке відношення xAy є підмножиною множини X´X і називається відношенням вX. Окремі випадки відношень в X: 1) повнеабо універсальне відношенняP=X ´X,яке має місце для кожної пари (x1, x2) елементів із X (наприклад, відношення “вчитися в одній групі” на множині студентів даної групи); 2) тотожне(діагональне) відношення E, рівносильне x = x (наприклад, рівність на множині дійсних чисел); 3) порожнє відношення, яке не задовольняє жодна пара елементів з X(наприклад, відношення “бути братом” на множині жінок). Очевидно, для будь-якого відношення A в X справедливо ÆÌ AÌ P. Приклад 1. Нехай X={ 2, 3 } і Y={ 3, 4, 5, 6 }. Декартовий добуток цих множин X´Y ={(2, 3), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6)}. Відношення "бути дільником" є множина A={(2, 4), (2, 6), (3, ), (3, 6)} відношення = є множина B={(3, 3)}, а відношення > є порожня множина Æ. Для відношення A то DВ (A)= {2, 3}= X, DЗ (A)= {3, 4, 6}Ì Y. Нехай X = {1, 2, 3}, Y = {1, 2, 3, 4, 5, 6, 7, 8, 9} і відношення А описується наступним чином: A={(x, y)ÎX´Y | y=x2}. Тоді A={(1, 1), (2, 4) (3, 9)}, DВ (A)= = {1, 2, 3}= X, DЗ (A) = {1, 4, 9}=Y. Нехай A Ì X´Y; якщо xiÎ X, то переріз по xi відношення A, який позначають A(xi), є множина yÎY таких, що (x, y)Î A. Множина всіх перерізів відношення A називається фактор-множиною множини Y по відношенню A і позначається Y/A. Вона цілком визначає відношення A. Приклад 2. Нехай X={x1, x2, x3, x4, x5}; ={y1, y2, y3, y4} i задано відношення A= {(x1, y1), (x1, y3), (x2, y1), (x2, y3), (x2, y4), (x3, y1), (x3, y2), (x3, y4), (x4, y3), (x5, y2), (x5, y4)}. Тоді A(x1)={y1, y3}; A(x2)={y1, y3, y4}; A(x3)={y1, y2, y4}; A(x4)={y3}; A(x5)={y2, y4}. Якщо записати під кожним елементом з X відповідний переріз відношення A, то елементи другого рядка утворюють фактор-множину Y/A:
.
Об'єднання перерізів по елементах деякої підмножини B Ì X є перерізом A (B) цієї підмножини, тобто Так, A(х2,х3) A(х2)Ս A (х3)={y1, y2, y3, y4}. Таким чином, скінченне відношення можна подати за допомогою фактор-множини. Інший спосіб − матричний− оснований на поданні відношення відповідною йому прямокутною таблицею (матрицею). Її стовпці відповідають першим координатам, а рядки− другим координатам. На перетині i-го стовпця і j-го рядка ставиться одиниця, якщо виконується співвідношення xiAyj, і нуль, якщо це співвідношення не виконується (нулеві клітинки можна залишати порожніми). Ця матриця містить всю інформацію про відношенняA. Наприклад, для відношення, розглянутого в прикладі 2, матриця має вигляд:
. Відношення A–1 називається симетричним (оберненим) до відношення AÌX´Y, якщо воно являє собою підмножину множини Y´X, утворену тими парами (y, x)ÎY´X, для яких (x, y)ÎA. Перехід від A до A–1 здійснюється взаємною перестановкою координат кожної упорядкованої пари. Графи повного, тотожного і порожнього відношень зображені на рис. 1.4. Так, обернене відношення для “x є дільник y” буде “y ділиться на x”. При переході від A до A–1 область визначення стає областю значень, і навпаки. Матрицю оберненого відношення одержують транспонуванням початкової матриці. Нехай дано три множини X, Y, Z і два відношення AÌX´Y і BÌY´Z. Композиція відношень A і B є відношення C = BA, що складається із всіх тих пар (x, z)Ì X´Z, для яких існує таке уÎY, що (x, у)Î A і (у, z)Î B. Переріз відношення C по х збігається з перерізом відношення B по підмножині A(х)Ì Y, тобто = B(A(х)). Композиція відношень підпорядкована асоціативному закону, тобто D(BA)) = (DB) A = DBA, але не комутативна, тобто BA ≠ AB. Аналогічно можна одержати матрицю композиції C = BA як добуток матриць відношень матриць В і А, який знаходиться за правилом множення прямокутних матриць з наступною заміною відмінного від нуля елемента матриці одиницею. Приклад 1.5. Нехай X={x1, x2, x3, x4, x5}; Y={y1, y2, y3, y4}; A= {(x1,y1), (x1, y3), (x2, y1), (x2, y3), (x2, y4), (x3, y1), (x3, y2), (x3, y4), (x4, y3), (x5, y2), (x5, y4)}; B= {(y1, z2), (y2, z1), (y2, z2), (y3, z3), (y4, z3)}. Треба знайти матрицю композиції відношень C=BA. Розв’язання. Одержимо матрицю композиції:
Питання для самоперевірки
1.Що таке бінарне відношення? 2.Що таке фактор множина? 3.Що таке повне, тотожне і порожнє відношення? Література: [1], c. 81-86; [2], c. 11-15. Вправи 22. Задані дві множини X = {x1, x2, x3, x4, x5, x6} і Y = {y1, y2, y3, y4 } і визначене бінарне відношення . Треба для відношення A: а) написати область визначення і область значень; б) визначити перерізи по кожному елементу із X; в) написати матрицю і нарисувати граф; г) визначити симетричне відношення. 23. Нехай X − множина студентів; Y – множина дисциплін і співвідношення xAy означає “студент x вивчає дисципліну y”. Треба дати словесний опис областей визначення і значень, перерізів і оберненого відношення, одержаних в задачі 22. 24.За результатами задачі 22 треба визначити множини і дати їм словесний опис у відповідності з умовою задачі 23. 25. Написати композицію C = BA відношень A = {(1, 2), (1, 3),(2, 1), (2, 4), (3, 3)} і B = {(1, 1) (1, 3), (2, 2), (2, 3), (3, 1) (4, 2), (4, 3)}. Перевірити результат за допомогою операцій над матрицями.
Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|