Математика | Замыкание отношений и отношения эквивалентности

Предпосылки: Введение в отношения, представление отношений

Объединение отношений:

Поскольку мы знаем, что отношения - это просто наборы упорядоченных пар, поэтому все операции над наборами применимы и к ним. Два отношения можно комбинировать несколькими способами, например:

• Союз - состоит из всех упорядоченных пар из обоих отношений. Повторяющиеся упорядоченные пары удалены из Union.
• Пересечение - состоит из упорядоченных пар, находящихся в обоих отношениях.
• Разница - состоит из всех упорядоченных пар только в , но не в .
• Симметричная разница - состоит из всех упорядоченных пар, находящихся либо в или но не то и другое одновременно.

Есть еще один способ объединения двух отношений, аналогичный композиции функций.

Композиция - Пусть быть родственником из к а также быть родственником из к , то композиция а также , обозначаемый , - отношение, состоящее из упорядоченных пар куда и для которого существует элемент такой, что а также .

• Пример - Какова композиция отношений а также куда это отношение из к с участием а также это отношение из к с участием ?
• Решение - вычисляя все упорядоченные пары, в которых первый элемент принадлежит а второй элемент принадлежит , мы получаем -
  

Состав отношения к себе:

Отношение может быть составлено с самим собой, чтобы получить степень разделения между элементами множества, на котором определено.

Позволять  отношение на множестве  .
Полномочия  куда  определяются рекурсивно:
 а также  .

Теорема - Пусть - отношение на множестве A, представленное ди-графом. Есть путь длины , куда положительное целое число, от к если и только если .

Важное примечание: отношение на съемочной площадке транзитивен тогда и только тогда, когда для

Завершение отношений:

Рассмотрим отношение на съемочной площадке . может иметь или не иметь собственность , например рефлексивность, симметрия или транзитивность.

Если есть отношение с собственностью содержащий такой, что это подмножество
всякого отношения к собственности содержащий , тогда называется закрытием
относительно .

Мы можем получить замыкания отношений по свойству следующими способами -

1. Рефлексивное закрытие - диагональное отношение на множестве . Рефлексивное завершение отношения на съемочной площадке является .
2. Симметричное замыкание - Пусть быть отношением на множестве , и разреши быть инверсией . Симметричное замыкание отношения на съемочной площадке является .
3. Переходное замыкание - Пусть быть отношением на множестве . Отношение связности определяется как - . Переходное замыкание является .

Пример - Пусть быть отношением на множестве с участием . Найдите рефлексивное, симметричное и транзитивное замыкание R.

Решение -
Для данного набора . Итак, рефлексивное закрытие является

Для симметричного замыкания нам понадобится обратное к , который
.
Симметричное замыкание является-

Для транзитивного замыкания нам нужно найти .
нам нужно найти до . Мы останавливаемся, когда это условие достигнуто, так как находим более высокие степени будет то же самое.



С, мы останавливаем процесс.
Переходное закрытие, -

Отношения эквивалентности:

Позволять быть отношением на множестве . Если рефлексивно, симметрично и транзитивно, то называется отношением эквивалентности.
Следовательно, два элемента а также связанные отношением эквивалентности, называются эквивалентными.

Пример - Покажите, что отношение
является отношением эквивалентности. сравнение по модулю функция. Это верно тогда и только тогда, когда разделяет .

Решение. Чтобы показать, что отношение является отношением эквивалентности, мы должны доказать, что отношение рефлексивно, симметрично и транзитивно.

1. Reflexive - для любого элемента , делится на .
   . Итак, сравнение по модулю рефлексивно.
2. Симметричный - для любых двух элементов а также , если или т.е. делится на , тогда также делится на .
   . Так что по модулю сравнения симметрично.
3. Переходный - для любых трех элементов , , а также если тогда-
   
   
   Сложив оба уравнения,

   

   . Так, транзитивен.

   Поскольку отношение рефлексивно, симметрично и транзитивно, заключаем, что является отношением эквивалентности.

   Классы эквивалентности:

   Позволять - отношение эквивалентности на множестве .
   Мы знаем, что если тогда а также называются эквивалентными относительно .

   Набор всех элементов, связанных с элементом из называется
   класс эквивалентности . Обозначается он или просто если есть только один
   отношение к рассмотрению.
   Формально,
   

   Любой элемент считается представителем .
   Важное примечание: все классы эквивалентности отношения на съемочной площадке либо равны, либо не пересекаются, и их объединение дает множество .
   
   Классы эквивалентности также называются разбиениями, поскольку они не пересекаются, и их объединение дает набор, на котором определено отношение.

   • Пример: каковы классы эквивалентности отношения Congruence Modulo ?
   • Решение: пусть а также быть двумя числами такими, что . Это означает, что остаток, полученный от деления а также с участием та же.
     Возможные значения остатка -
     Следовательно, есть классы эквивалентности -
     
     
     
     
     

   Вопросы по GATE CS Corner

   Выполнение следующих вопросов поможет вам проверить свои знания. Все вопросы задавались в GATE в предыдущие годы или в пробных тестах GATE. Настоятельно рекомендуется попрактиковаться в них.

   1. GATE CS 2013, вопрос 1
   2. GATE CS 2005, вопрос 42
   3. GATE CS 2001, вопрос 2
   4. GATE CS 2000, вопрос 28

   Использованная литература -
   Состав отношений - Википедия
   Дискретная математика и ее приложения, Кеннет Х. Розен

   Эта статья предоставлена Чирагом Манвани . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью с помощью provide.geeksforgeeks.org или отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

   Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.