Оглавление [Скрыть]
- 1 Бинарное отношение
- 1.1 Определение бинарного отношения
- 1.2 Примеры бинарных отношений
- 1.3 Свойства бинарных отношений
- 1.4 Операции с бинарными отношениями
- 1.5 Бинарные отношения и их дополнения
- 1.6 Ограничения бинарных отношений
- 1.7 Содержания и равенства бинарных отношений
- 1.8 Матричное представление бинарных отношений
- 1.9 Примеры бинарных отношений
- 1.10 Визуализация отношений
- 1.11 Гиперболическая ортогональность
- 1.12 Геометрические конфигурации
- 1.13 Структура заболеваемости
- 1.14 Типы бинарных отношений
- 1.15 Свойства совокупности
- 1.16 Свойства уникальности и совокупности
- 1.17 Отношения над соответствующими классами
- 1.18 Наборы в сравнении с классами
- 1.19 Однородное отношение
- 1.20 Основные понятия отношений
- 1.21 Частичный и полный порядок
- 1.22 Операции с отношениями
- 1.23 Индуцированная концептуальная решетка
- 1.24 Особые отношения
- 1.25 Предварительный заказ R\R
- 1.26 Транзитивность и наибольшие соотношения
- 1.27 Отношение включения и граница отношения
- 1.28 Математические кучи
- 1.29 Дополнительные темы
- 1.30 Полный текст статьи:
- 2 Бинарное отношение – Arc.Ask3.Ru
Бинарное отношение
-
Определение бинарного отношения
- Бинарное отношение связывает элементы одного множества с элементами другого множества.
- Бинарное отношение над множествами X и Y представляет собой набор упорядоченных пар (x, y), где x в X и y в Y.
- Бинарное отношение кодирует общее понятие отношения: элемент x связан с элементом y, если пара (x, y) принадлежит набору упорядоченных пар.
-
Примеры бинарных отношений
- Отношение “деления” на множество простых чисел P и множество целых чисел Z.
- Отношение “соответствует” в геометрии.
- Отношение “находится рядом с” в теории графов.
- Отношение “ортогонально к” в линейной алгебре.
-
Свойства бинарных отношений
- Бинарное отношение является элементом силового набора X × Y.
- Бинарное отношение называется однородным, если X = Y.
- Бинарное отношение также называется гетерогенным, если X ≠ Y.
-
Операции с бинарными отношениями
- Союз: объединение двух бинарных отношений.
- Пересечение: объединение двух бинарных отношений.
- Композиция: композиция двух бинарных отношений.
- Преобразование: обратное отношение к бинарному отношению.
-
Бинарные отношения и их дополнения
- Бинарное отношение равно обратному тогда и только тогда, когда оно симметрично.
- Дополнение отношения R над множествами X и Y — это отношение, обратное R, обозначаемое ¬R.
- Примеры дополнений: = и ≠, ⊆ и ⊈, ⊇ и ⊉, ∈ и ∉, < и ≥, > и ≤.
- Дополнение к обратному отношению R^T является обратным дополнением: R^T¯ = R¯T.
-
Ограничения бинарных отношений
- Ограничение отношения R к подмножеству S множества X — это отношение, где xRy и x ∈ S и y ∈ S.
- Ограничение отношения R к подмножеству S множества X и Y — это отношение, где xRy и x ∈ S.
- Ограничения рефлексивных, нерефлексивных, симметричных, антисимметричных, асимметричных, транзитивных, тотальных, трихотомических, частичных порядков, полных порядков, строгих слабых порядков, полных предварительных порядков и отношений эквивалентности также являются рефлексивными, нерефлексивными, симметричными, антисимметричными, асимметричными, транзитивными, тотальными, трихотомическими, частичными порядками, полными порядками, строгими слабыми порядками, полными предварительными порядками и отношениями эквивалентности.
- Транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания.
-
Содержания и равенства бинарных отношений
- Бинарное отношение R над множествами X и Y содержится в отношении S над X и Y, если R является подмножеством S.
- Если R и S содержатся друг в друге, то они равны.
- Если R содержится в S, но S не содержится в R, то R меньше, чем S.
-
Матричное представление бинарных отношений
- Бинарные отношения над множествами X и Y могут быть представлены алгебраически логическими матрицами.
- Сложение матриц соответствует объединению отношений, умножение матриц — композиции отношений, произведение Адамара — пересечению отношений, нулевая матрица — пустому отношению, матрица единиц — универсальному отношению.
- Однородные отношения образуют матричное полукольцо, где единичная матрица соответствует отношению тождества.
-
Примеры бинарных отношений
- Пример отношения: океаны и континенты, где aRb означает, что океан a граничит с континентом b.
- Логическая матрица для этого отношения: R = (0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1).
- Взаимосвязанность планеты Земля можно увидеть с помощью RR^T и R^T R, где RR^T является универсальным отношением, а R^T R — нет.
-
Визуализация отношений
- Для отношений на множестве ориентированный граф иллюстрирует отношение, а граф — симметричное отношение.
- Для гетерогенных отношений гиперграф имеет ребра с более чем двумя узлами и может быть проиллюстрирован двудольным графом.
- Биклики используются для описания разнородных отношений.
-
Гиперболическая ортогональность
- Время и пространство — это разные категории, и временные свойства отделены от пространственных свойств.
- Герман Минковский сформулировал понятие относительной одновременности, когда пространственные события нормальны по отношению ко времени.
- Неопределенное внутреннее произведение в композиционной алгебре задается формулой ⟨x, z⟩ = xz¯ + x¯z, где верхняя черта обозначает спряжение.
- Гиперболическая ортогональность — это гетерогенное отношение.
-
Геометрические конфигурации
- Геометрическую конфигурацию можно рассматривать как отношение между ее точками и линиями.
- Это отношение выражается в виде частоты встречаемости.
- Якоб Штайнер каталогизировал конфигурации с помощью систем Steiner systems S(t, k, n), которые имеют набор из n элементов и набор подмножеств из k элементов.
- Матрица инцидентности, используемая в геометрических контекстах, соответствует логической матрице, обычно используемой с бинарными отношениями.
-
Структура заболеваемости
- Структура заболеваемости — это тройная D = (V, B, I), где V и B — любые два непересекающихся множества, а I — бинарное отношение между V.
-
Типы бинарных отношений
- Инъективный: каждый элемент кодовой области содержит не более одного элемента прообраза
- Функциональный: каждый элемент домена содержит не более одного элемента изображения
- Один к одному: инъективный и функциональный
- Один ко многим: инъективный и нефункциональный
- Соотношение “много к одному”: функциональный, а не инъективный
- Многие-ко-многим: не инъективный и не функциональный
-
Свойства совокупности
- Итого: для всех элементов домена существует элемент изображения
- Сюръектив: для всех элементов кодовой области существует элемент прообраза
-
Свойства уникальности и совокупности
- Функция: функциональное и полное
- Инъекция: функция, которая является инъекционной
- Сюръекция: функция, которая является сюръективной
- Биекция: функция, которая является инъективной и сюръективной
-
Отношения над соответствующими классами
- Заданный: для всех элементов домена класс всех элементов кодовой области, таких что элемент домена связан с элементом кодовой области, является множеством
-
Наборы в сравнении с классами
- Некоторые математические отношения, такие как “равно”, “подмножество” и “член”, не могут быть поняты как бинарные отношения
- Решение: использование теории множеств с соответствующими классами или ограничение отношений на определенные множества
-
Однородное отношение
- Однородное отношение над множеством X является подмножеством декартова произведения X × X
- Однородное отношение может быть отождествлено с направленным простым графом
- Совокупность всех однородных отношений над X образует булеву алгебру с инволюцией
- Важные свойства однородного отношения: рефлексивный, нерефлексивный, симметричный, антисимметричный
-
Основные понятия отношений
- Отношение R является антисимметричным, если xRy и yRx, но x ≠ y.
- Отношение является асимметричным, если xRy, но yRx.
- Отношение транзитивно, если xRy и yRz, то xRz.
- Отношение связно, если x ≠ y, то xRy или yRx.
- Отношение плотно, если xRy, то существует z, что xRz и zRy.
-
Частичный и полный порядок
- Частичный порядок: рефлексивный, антисимметричный и транзитивный.
- Полный порядок: рефлексивный, антисимметричный, транзитивный и связанный.
- Строгий частичный порядок: нерефлексивный, асимметричный и транзитивный.
- Строгий полный порядок: нерефлексивный, асимметричный, транзитивный и связанный.
-
Операции с отношениями
- Операции с отношениями включают включение, составление отношений и манипулирование операторами.
- Составление отношений является частичной функцией.
- Изучение разнородных отношений связано с теорией категорий.
-
Индуцированная концептуальная решетка
- Бинарные отношения описываются с помощью индуцированных концептуальных решеток.
- Концепция C удовлетворяет двум свойствам: логическая матрица C является внешним произведением логических векторов и C является максимальным.
- Теорема о завершении Макнейла утверждает, что любой частичный порядок может быть встроен в полную решетку.
-
Особые отношения
- Дифункциональное отношение разделяет объекты по различным признакам.
- Дифункциональные отношения удовлетворяют включению и могут быть записаны как объединение декартовых произведений.
- Тип Феррерса: строгий порядок на множестве, удовлетворяющий алгебраической формулировке.
- Контактное отношение: отношение, удовлетворяющее трем свойствам, включая установленное отношение членства.
-
Предварительный заказ R\R
- Каждое отношение R создает предварительный заказ R\R, который является левым остатком.
- R\R эквивалентно R^T R^\overline.
-
Транзитивность и наибольшие соотношения
- Для транзитивности требуется, чтобы (R ∖ R)(R ∖ R) ⊆ R ∖ R.
- X = R ∖ R является наибольшим соотношением, таким что RX ⊆ R.
-
Отношение включения и граница отношения
- Отношение включения Ω на множестве степеней U может быть получено из отношения принадлежности ∈ о подмножествах U.
- Граница отношения R определяется как бахрома(R) = R ∩ R¯T R¯.
- Для отношений частичной идентичности, дифункциональных или блочно-диагональных бахрома(R) = R.
- В противном случае бахрома(R) выбирает граничное подчиненное отношение.
-
Математические кучи
- Даны два набора A и B, совокупность бинарных отношений между ними может быть оснащена троичной операцией [a, b, c] = abT c.
- Виктор Вагнер использовал эту операцию для определения полугрупп, куч и обобщенных куч.
- Различные типы полугрупп возникают при рассмотрении бинарных отношений между различными наборами A и B.
-
Дополнительные темы
- Система переписывания рефератов
- Аддитивное отношение, многозначный гомоморфизм между модулями
- Аллегория (теория категорий)
- Категория отношений, категория, имеющая множества в виде объектов и бинарные отношения в виде морфизмов
- Слияние (переписывание термина), обсуждает несколько необычных, но фундаментальных свойств бинарных отношений
- Соответствие (алгебраическая геометрия) – бинарное отношение, определяемое алгебраическими уравнениями
- Диаграмма Хассе – графическое средство отображения соотношения заказов
- Структура инцидентности, неоднородное соотношение между множеством точек и линий
- Логика родственников, теория взаимоотношений Чарльза Сандерса Пирса
- Теория порядка, исследующая свойства отношений порядка