Математическая операция
В математике бинарных отношений композиция отношений есть образование нового бинарного отношения R ; S из двух заданных бинарных отношений R и S. В исчислении отношений композиция отношений называется относительным умножением [1] , а ее результат называется относительным произведением . [2] : 40 Композиция функций — это особый случай композиции отношений, когда все задействованные отношения являются функциями .
Слово дядя указывает на сложное отношение: чтобы человек мог быть дядей, он должен быть братом родителя. В алгебраической логике говорят, что отношение дяди ( ) представляет собой композицию отношений «является братом» ( ) и «является родителем» ( ).![{\displaystyle xUz}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle xBy}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle yPz}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle U=BP\quad {\text{эквивалентно: }}\quad xByPz{\text{ тогда и только тогда, когда }}xUz.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Начиная с Огастеса Де Моргана , [3] традиционная форма рассуждения с помощью силлогизма была включена в состав реляционных логических выражений и их композиции. [4]
Определение
Если и — два бинарных отношения, то их композицией является отношение![{\displaystyle R\subseteq X\times Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S\subseteq Y\times Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R;S=\{(x,z)\in X\times Z: {\text{ существует }}y\in Y{\text{ такое, что }}(x,y)\in R{ \text{ и }}(y,z)\in S\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Другими словами, определяется правилом, которое гласит, что тогда и только тогда, когда существует такой элемент, что (то есть и ). [5] : 13 ![{\displaystyle R;S\subseteq X\times Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x,z)\in R;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle y\in Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle х\,R\,y\,S\,z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x,y)\in R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (y,z)\in S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Варианты обозначений
Точка с запятой как инфиксное обозначение состава отношений восходит к учебнику Эрнста Шредера 1895 года. [6] Гюнтер Шмидт возобновил использование точки с запятой, особенно в «Реляционной математике» (2011). [2] : 40 [7] Использование точки с запятой совпадает с обозначением композиции функций, используемым (в основном учёными-компьютерщиками) в теории категорий , [8] , а также обозначением динамического соединения в лингвистической динамической семантике . [9]
Маленький кружок использовался Джоном М. Хоуи для инфиксной записи композиции отношений в его книгах, посвященных полугруппам отношений. [10] Однако маленький кружок широко используется для обозначения композиции функций , которая меняет последовательность текста на последовательность операций. Маленький кружок использовался на вводных страницах книги «Графики и отношения» [5] : 18 , пока от него не отказались в пользу сопоставления (без инфиксной записи). Сопоставление обычно используется в алгебре для обозначения умножения, поэтому оно также может означать относительное умножение.
![{\displaystyle (RS)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Кроме того, при обозначении круга можно использовать индексы. Некоторые авторы [11] предпочитают писать и явно, когда это необходимо, в зависимости от того, какое отношение применяется первым: левое или правое. Еще одним вариантом, встречающимся в информатике, является обозначение Z : используется для обозначения традиционной (правой) композиции, но ⨾ ( U+ 2A3E ⨾ Z NOTATION RELATIONAL COMPOSITION ) обозначает левую композицию. [12] [13]![{\displaystyle \circ _ {l}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \circ _ {r}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Математические обобщения
Бинарные отношения являются морфизмами в категории . В Rel объекты представляют собой множества , морфизмы — это бинарные отношения, а композиция морфизмов — это в точности композиция отношений, как определено выше. Категория Набор множеств и функций — это подкатегория, в которой карты являются функциями .![{\displaystyle R\subseteq X\times Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\to Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f:X\to Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Учитывая регулярную категорию , ее категория внутренних отношений имеет те же объекты, что и , но теперь морфизмы задаются подобъектами в . [14] Формально это совместные монические промежутки между и . Категории внутренних отношений являются аллегориями . В частности . Учитывая поле (или, в более общем случае, область главных идеалов ), категория отношений, внутренних по отношению к матрицам над , имеет морфизмы, линейные подпространства . Категория линейных отношений над конечным полем изоморфна бесфазному кубиту ZX-исчисления по модулю скаляров.![{\displaystyle \mathbb {X} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}(\mathbb {X})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {X} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\to Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\subseteq X\times Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {X} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle n \ to m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {F} _{2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Характеристики
- Состав отношений ассоциативен :
![{\displaystyle R;(S;T)=(R;S);T.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Обратное отношение is Это свойство делает набор всех бинарных отношений на множестве полугруппой с инволюцией .
![{\displaystyle R\,;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (R\,;S)^{\textsf {T}}=S^{\textsf {T}}\,;R^{\textsf {T}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Композиция (частичных) функций (то есть функциональных отношений) снова является (частичной) функцией.
- Если и инъективны , то инъективен, что, наоборот , подразумевает только инъективность
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\,;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Р.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если и сюръективны , то сюръективен, что, наоборот , подразумевает только сюръективность
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\,;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle С.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Набор бинарных отношений на множестве (то есть отношений от до ) вместе с (левой или правой) композицией отношений образует моноид с нулем, где тождественная карта на является нейтральным элементом , а пустое множество — нулевым элементом .
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Композиция в терминах матриц
Конечные бинарные отношения представляются логическими матрицами . Элементы этих матриц равны нулю или единице, в зависимости от того, является ли представленное отношение ложным или истинным для строки и столбца, соответствующих сравниваемым объектам. Работа с такими матрицами включает в себя булеву арифметику с и. Тогда запись в матричном произведении двух логических матриц будет 1, только если умноженные строка и столбец имеют соответствующую 1. Таким образом, можно найти логическую матрицу композиции отношений. путем вычисления матричного произведения матриц, представляющих факторы композиции. «Матрицы представляют собой метод вычисления выводов, традиционно получаемых с помощью гипотетических силлогизмов и соритов ». [15]![{\displaystyle 1+1=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 1\times 1=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Гетерогенные отношения
Рассмотрим гетерогенное отношение , где и — различные множества. Тогда, используя композицию отношения с его обратным, возникают однородные отношения (on ) и (on ).![{\displaystyle R\subseteq A\times B;}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RR^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Если для всех существует такое, что (то есть является (лево-)тотальным отношением ), то для всех так, что это рефлексивное отношение или где I — тождественное отношение . Аналогично, если — сюръективное отношение , то ![{\displaystyle x\in A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle y\in B,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle xRy}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x,xRR^{\textsf {T}}x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RR^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle I\subseteq RR^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{xIx:x\in A\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R\supseteq I=\{xIx:x\in B\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
дифункционального![{\displaystyle R\subseteq RR^{\textsf {T}}R.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Композиция используется для выделения отношений типа Феррера, удовлетворяющих![{\displaystyle {\bar {R}}^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Пример
Пусть { Франция, Германия, Италия, Швейцария } и { французский, немецкий, итальянский } с отношением, заданным условием, когда является национальным языком Поскольку
оба и конечны, могут быть представлены логической матрицей , предполагая строки (сверху вниз) и столбцы (слева направо) расположены в алфавитном порядке:![{\displaystyle A=}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B=}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle aRb}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle б}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle а.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Обратное отношение соответствует транспонированной матрице , а композиция отношения соответствует произведению матрицы , когда суммирование осуществляется посредством логической дизъюнкции . Оказывается, матрица содержит 1 в каждой позиции, а произведение обратной матрицы вычисляется как:![{\displaystyle R^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 3\times 3}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle А.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Соответственно, это универсальное отношение, следовательно , любые два языка принадлежат одной нации, в которой на обоих говорят (фактически: Швейцарии). И наоборот, на вопрос, имеют ли две данные нации общий язык, можно ответить, используя![{\displaystyle R^{\textsf {T}}\,;R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle B,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\,;R^{\textsf {T}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Шредер рулит
Для данного набора совокупность всех бинарных отношений на формирует булеву решетку , упорядоченную по включению . Напомним, что дополнение меняет включение на противоположное:
В исчислении отношений [16] дополнение множества принято представлять через черту:![{\displaystyle V,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (\subseteq).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A\subseteq B{\text{ подразумевает }}B^{\complement }\subseteq A^{\complement }.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\bar {A}}=A^{\complement }.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Если это бинарное отношение, пусть представляет обратное отношение , также называемое транспонированием . Тогда правила Шредера имеют вид![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle QR\subseteq S\quad {\text{эквивалентно }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text { эквивалентно }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
[5] : 15–19 Хотя это преобразование включения композиции отношений было подробно описано Эрнстом Шредером , фактически Огастес Де Морган впервые сформулировал это преобразование как теорему K в 1860 году. [4] Он написал [17]
![{\displaystyle LM\subseteq N{\text{ подразумевает }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
С помощью правил Шредера и дополнений можно найти неизвестное отношение во включениях отношений, таких как ![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
левым остатком от![{\displaystyle RX\subseteq S{\text{ подразумевает }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Коэффициенты
Точно так же, как композиция отношений — это тип умножения, в результате которого получается произведение, так и некоторые операции сравниваются с делением и производят частное. Здесь показаны три фактора: левый остаток, правый остаток и симметричный фактор. Левый остаток двух отношений определяется в предположении, что они имеют один и тот же домен (источник), а правый остаток предполагает один и тот же кодомен (диапазон, цель). Симметричный фактор предполагает, что два отношения имеют общий домен и кодомен.
Определения:
- Левый остаток:
![{\displaystyle A\обратная косая черта B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Правый остаток:
![{\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Симметричный коэффициент:
![{\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Используя правила Шредера, эквивалентно: Таким образом, левый остаток является наибольшим отношением, удовлетворяющим. Аналогично, включение эквивалентно , а правый остаток является наибольшим соотношением, удовлетворяющим [2] : 43–6. ![{\displaystyle AX\subseteq B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\subseteq A\обратная косая черта B.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle AX\subseteq B.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle YC\subseteq D}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y\subseteq D/C,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle YC\subseteq D.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Логику остатков можно практиковать с помощью судоку . [ нужны дальнейшие объяснения ]
Присоединяйтесь: другая форма композиции
Был введен оператор вилки для объединения двух отношений и в . Конструкция зависит от проекций и понимается как отношения, что означает, что существуют обратные отношения и Тогда![{\displaystyle (<)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle c:H\to A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d:H\to B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle c\,(<)\,d:H\to A\times B.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a:A\times B\to A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle b:A\times B\to B,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
развилка иопределяется выражением[18]![{\displaystyle с}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle c\,(<)\,d~\mathrel {:=} ~c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Другой формой композиции отношений, которая применяется к отношениям общего места, является операция соединения реляционной алгебры . Обычную композицию двух бинарных отношений, определенную здесь, можно получить, взяв их соединение, ведущее к тройному отношению, за которым следует проекция, удаляющая средний компонент. Например, в языке запросов SQL есть операция Join (SQL) .![{\displaystyle п}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle n \ geq 2,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Смотрите также
Примечания
- ^ Бьярни Йонссен (1984) «Максимальные алгебры бинарных отношений», в «Вкладах в теорию групп» , редактор К.И. Аппеля ISBN Американского математического общества 978-0-8218-5035-0
- ^ abc Гюнтер Шмидт (2011) Реляционная математика , Энциклопедия математики и ее приложений, том. 132, ISBN издательства Кембриджского университета 978-0-521-76268-7
- ^ А. Де Морган (1860) «О силлогизме: IV и логике отношений»
- ^ ab Дэниел Д. Меррилл (1990) Огастес Де Морган и логика отношений , страница 121, Kluwer Academic ISBN 9789400920477
- ^ abc Гюнтер Шмидт и Томас Стрёлейн (1993) Отношения и графики , книги Springer
- ^ Эрнст Шредер (1895) Алгебра и логика относительности
- ^ Пол Тейлор (1999). Практические основы математики. Издательство Кембриджского университета. п. 24. ISBN 978-0-521-63107-5.Бесплатная HTML-версия книги доступна по адресу http://www.cs.man.ac.uk/~pt/Practical_Foundations/.
- ^ Майкл Барр и Чарльз Уэллс (1998) Теория категорий для ученых-компьютерщиков. Архивировано 4 марта 2016 г. в Wayback Machine , стр. 6, из Университета Макгилла.
- ^ Рик Нувен и другие (2016) Динамическая семантика §2.2, из Стэнфордской энциклопедии философии
- ^ Джон М. Хоуи (1995) Основы теории полугрупп , страница 16, монография LMS № 12, Clarendon Press ISBN 0-19-851194-9
- ^ Килп, Кнауэр и Михалев, с. 7
- ^ ISO/IEC 13568:2002(E), стр. 23
- ^ Символ Юникода: реляционная композиция Z Notation из FileFormat.info
- ^ «Внутренние отношения». нлаб . Проверено 26 сентября 2023 г.
- ^ Ирвинг Копиловиш (декабрь 1948 г.) «Матричное развитие исчисления отношений», Журнал символической логики 13 (4): 193–203 Ссылка на Jstor, цитата со страницы 203
- ^ Вон Пратт. Истоки исчисления отношений, из Стэнфордского университета.
- ^ Де Морган указал противоположное строчными буквами, преобразование как M −1 и включение с помощью )), поэтому его обозначения были
![{\displaystyle нМ^{-1}))\ л.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- ^ Гюнтер Шмидт и Майкл Винтер (2018): Реляционная топология , стр. 26, Конспекты лекций по математике, том. 2208, книги Springer , ISBN 978-3-319-74451-3
Рекомендации
- М. Килп, У. Кнауэр, А. В. Михалев (2000) Моноиды, действия и категории с приложениями к сплетениям и графам , Изложения Де Грюйтера по математике, том. 29, Вальтер де Грюйтер , ISBN 3-11-015248-7 .