рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Математика
- /
- Операції над відношеннями
Реферат Курсовая Конспект
Операції над відношеннями
Операції над відношеннями - раздел Математика, Основи Дискретної математики Нехай R1, R2 – Відношення...
Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2 (позначається R1ÈR2) називається множина R1ÈR2={<a1,…,an>| <a1,…,an>ÎR1 або <a1,…,an>ÎR2}. Перетином відношень R1 та R2 (позначається R1ÇR2) називається множина R1ÇR2={<a1,…,an>| <a1,…,an>ÎR1, <a1,…,an>ÎR2}. Різницею відношень R1 та R2 (позначається R1R2) називається множина R1R2={<a1,…,an>| <a1,…,an>ÎR1, <a1,…,an>ÏR2}. Доповненням відношення R1 (позначається R1¢) називається множина R1¢=А1´…´AnR1, тобто R1¢={<a1,…,an>| <a1,…,an>ÎА1´…´An, <a1,…,an>ÏR1}. Вираз <a1,…,an>ÎR1¢ означає, що <a1,…,an>ÏR1 (при цьому, звичайно, <a1,…,an>ÎА1´…´An, але для скорочення запису це твердження опускають).
Нехай, наприклад, A1={1,2,3}, A2={a,b,c}, R1, R2 – відношення, задані на множинах А1 та А2, й R1={<1,a>,<1,b>,<2,b>,<3,c>}, R2={<1,b>, <3,c>,<3,a>}. Тоді:
R1ÈR2={<1,a>,<1,b>,<2,b>,<3,c>,<3,a>},
R1ÇR2={<1,b>,<3,c>},
R1R2={<1,a>,<2,b>},
R1¢={<1,c>,<2,a>,<2,c>,<3,a>,<3,b>}.
Розглянемо дві операції, визначені для відношень, заданих на двох множинах. Нехай відношення R задано на множинах А та В. Відношенням, оберненим до R (позначається R-1), називається відношення, задане на множинах В та А, виду R-1={<x,y>| <y,x>ÎR}.
Нехай, наприклад, А={а,с,е}, В={1,3,5}, RÍА´В й R={<a,1>, <a,3>,<c,3>,<c,5>,<e,5>}. Тоді R-1={<1,a>,<3,a>,<3,c>,<5,c>,<5,e>}. Відношен-ням, оберненим до відношення Í, заданого на булеані деякої множини А, є відношення, задане на булеані множини А, виду {<S,T>| <T,S>ÎÍ}, тобто множина упорядкованих пар <S,T> підмножин множини А таких, що ТÍS, або SÊТ. Отже, відношенням, оберненим до Í, є відношення Ê.
Нехай R1 – відношення, задане на множинах А та В, а R2 – відношення, задане на множинах В та С. Добутком (або композицією) відношень R1 та R1 (позначається R1*R2 або R1○R2) називається відношення, задане на множинах А та С, виду R1*R2={<x,y>| для деякого z з B <x,z>ÎR1, <z,y>ÎR2}. Іншими словами, добуток відношень R1 та R2 складається з таких упорядкованих пар <x,y>, які «побудовані» з пар виду <x,z> та <z,y>, що належaть відповідно відношенням R1 та R2.
Наприклад, нехай А={a,b,c,d}, B={1,2,3}, C={2,4,6}, R1ÍA´B, R2ÍB´C, R1={<a,3>,<a,2>,<b,1>,<c,2>}, R2={<2,2>,<3,6>}. Тоді добуток R1 та R2 – це відношення, задане на множинах А та С, виду R1*R2={<a,6>,<a,2>,<c,2>}. Розглянемо тепер відношення R3={<a,1>, <b,1>,<d,1>}, задане на множинах А та В, й обчислимо R3*R2. Оскільки відношення R3 та R2 не містять пар виду <x,z> та <z,y>, тобто таких пар, що другий компонент першої пари (тієї, що належить відношенню R3) збігається з першим компонентом другої пари (тієї, що належить відношенню R2), пар виду <x,y> утворити не можна, отже, R3*R2=Æ.
Теорема 5. Нехай R, R1, R2, R3 – бінарні відношення на множині А. Тоді:
1) (R-1)-1=R, 2) (R1ÈR2)-1=R1-1ÈR2-1,
3) (R1ÇR2)-1=R1-1ÇR2-1, 4) (R-1)¢=(R¢)-1,
5) (R1R2)-1=R1-1R2-1, 6) RÈR=RÇR=R,
7) R1*(R2ÈR3)=(R1*R2)È(R1*R3), 8) (R1ÈR2)*R3=(R1*R3)È(R2*R3).
9) (R1*R2)*R3=R1*(R2*R3), 10) (R1*R2)-1=R2-1*R1-1.
Доведемо рівність 4. Використовуючи означення доповнення відно-шення та означення відношення, оберненого до даного, маємо: <x,y>Î(R-1)¢ Þ <x,y>ÏR-1 Þ <y,x>ÏR Þ <y,x>ÎR¢ Þ <x,y>Î(R¢)-1. Отже, (R-1)¢Í(R¢)-1. Покажемо, що (R¢)-1Í(R-1)¢. <x,y>Î(R¢)-1 Þ <y,x>ÎR¢ Þ <y,x>ÏR Þ <x,y>ÏR-1 Þ <x,y>Î(R-1)¢. Отже, показали, що (R-1)¢=(R¢)-1.
Доведемо останню рівність. Використовуючи означення відношення, оберненого до даного, та означення добутку відношень, маємо: <x,y>Î(R1*R2)-1 Þ <y,x>Î(R1*R2) Þ існує такий елемент z з множини A, що <y,z>ÎR1 тa <z,x>ÎR2 Þ <x,z>ÎR2-1, <z,y>ÎR1-1 Þ <x,y>ÎR2-1*R1-1. Отже, (R1*R2)-1 Í R2-1*R1-1. Покажемо, що R2-1*R1-1 Í (R1*R2)-1. <x,y>ÎR2-1*R1-1 Þ існує такий елемент z з множини A, що <x,z>ÎR2-1 та <z,y>ÎR1-1 Þ <z,x>ÎR2, <y,z>ÎR1 Þ <y,x>ÎR1*R2 Þ <x,y>Î(R1*R2)-1. Таким чином, доведено, що R2-1*R1-1 Í (R1*R2)-1, отже, рівність 10 доведено.
– Конец работы –
Эта тема принадлежит разделу:
Основи Дискретної математики
Київський національний університет технологій та дизайну... М К МОРОХОВЕЦЬ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Операції над відношеннями
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.029 сек.
Новости и инфо для студентов