Теорема об ассоциативности композиции отношений

Пусть даны три множества X, Y, Z и два отношения и . Композиция отношений А и В есть отношение С=А°В, состоящее из всех тех пар , для которых существует такое уÎY, что (х, у) Î А и (у, z) Î В.

Сечение отношения С=А°В по х совпадает с сечением отношения В по подмножеству А(х)Î Y, т. е. С(х) = В (А(х)).

Граф композиции отношений получается из графов исходных отношений заменой двух стрелок, конец одной из которых является началом другой, на стрелку, начало которой совпадает с началом первой, а конец с концом второй.

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

Пример. Пусть ;

Тогда

Граф композиции этих отношений приведен на рис. 2.3.

Рис. 2.3. Граф композиции С=А°В

;

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10661 – | 7824 – или читать все.

Определение:

Композицией (произведением, суперпозицией) бинарных отношений (англ. composition of binary relations) [math]Rsubseteq A imes B[/math] и [math]Ssubseteq B imes C[/math] называется такое отношение [math] (R circ S) subseteq A imes C[/math] , что: [math]forall a in A, c in C : a (R circ S) c iff exists b in B : (a R b) wedge (b S c) [/math] .

Примером такого отношения может служить отношение на некотором множестве [math]A[/math] населенных пунктов [math]Rsubseteq A imes A[/math] — отношение "можно доехать на поезде", а [math]Ssubseteq A imes A[/math] — отношение "можно доехать на автобусе". Тогда отношение [math]Rcirc Ssubseteq A imes A[/math] — отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".

Содержание

Степень отношений [ править ]

Определение:

Степень отношения (англ. power of relation) [math]R^ subseteq A imes A[/math] , определяется следующим образом:

[math] R^

= R^ circ R; [/math]

[math] R^ <1>= R; [/math]

[math] R^ <0>= < (x, x) mid x in A >[/math] ;

В связи с этим понятием, также вводятся обозначения:

[math] R^ <+>= igcuplimits^<infty>_ R^ [/math] — Транзитивное замыкание (англ. transitive closure) отношения [math]R[/math] ;

[math] R^ <*>= igcuplimits^<infty>_ R^ [/math] — Транзитивно-рефлексивное замыкание отношения [math]R[/math]

Обратное отношение [ править ]

Определение:

Отношение [math]R^ <-1>subseteq B imes A[/math] называют обратным (англ. inverse relation) для отношения [math] R subseteq A imes B[/math] , если: [math] bR^<-1>a iff aRb [/math]

Определение:

Ядром отношения (англ. kernel of relation) [math]R[/math] называется отношение [math] Rcirc R^ <-1>[/math]

Свойства [ править ]

Композиция отношений обладает следующими свойствами:

Ядро отношения [math] R [/math] симметрично: [math]a (R circ R^<-1>) b iff b (R circ R^<-1>)a [/math]

Композиция отношений ассоциативна: [math] (R circ S) circ T = R circ (S circ T) [/math]

Обратное отношение для отношения, являющемуся обратным к [math] R [/math] есть само [math] R :[/math] [math] (R^<-1>)^ <-1>= R [/math]

Обратное отношение к композиции отношений [math]R [/math] и [math]S [/math] есть композиция отношений, обратных к [math]R [/math] и [math]S : [/math] [math] (R circ S) ^ <-1>= (S ^ <-1>) circ (R ^ <-1>) [/math]

Обратное отношение к объединению отношений [math]R [/math] и [math]S [/math] есть объединение отношений, обратных к [math]R [/math] и [math]S : [/math] [math] (R cup S) ^ <-1>= (R^<-1>) cup (S^<-1>) [/math]

Обратное отношение к пересечению отношений [math]R [/math] и [math]S [/math] есть пересечение отношений, обратных к [math]R [/math] и [math]S : [/math] [math] (R cap S) ^ <-1>= (R^<-1>) cap (S^<-1>) [/math]

Определение 1
Композицией отображений $f:U o V$ и $g:V o W$ называется такое отображение $ h:U o W $ $ h = g circ f $, что $ forall u in U $ $ h(u)=(g circ f)(u)=g(f(u))=w $.
$circ$ — символ композиции.

Определение 2
Бинарная операция «$*$» на $A$(непустом множестве) обладает свойством ассоциативности, если $forall a,b,c in A$ верно равенство $(a*b)*c=a*(b*c)$.

Лемма
Композиция отображений обладает свойством ассоциативности. То-есть $forall f,g,h (f circ g)circ h= fcirc (gcirc h)$, где $f:W o Q$, $g:V o W$, $h:U o V$, если левая и правая части существуют.

Доказательство
Нужно доказать, что $forall f,g,h $ $ (f circ g)circ h=fcirc (gcirc h)$, где $f:W o Q$, $g:V o W$, $h:U o V$.
$forall u in U $ $ [(fcirc g)circ h](u)=(fcirc g)(h(u))=f(g(h(u)))$ и $forall u in U $ $ [fcirc (gcirc h)](u)=f ((gcirc h)(u))=f(g(h(u)))$, получаем что левая и правая части равны, что и доказывает теорему.

Пример 1
Пусть $f:mathbb^* o mathbb^+$, $g:mathbb^+ o mathbb$ и $f(u)=u^2$, $h(u)=log$, где $uin mathbb^*$, $vin mathbb^+$, тогда $h(u)=(gcirc f)(u)=log$, где $h:mathbb^* o mathbb$.

Пример 2
Пусть $f:mathbb o mathbb$, $g:mathbb o mathbb^*$, $h:mathbb^* o mathbb^+$ и $f(u)=2u, g(v)=v^2, h(w)=2^w$, где $u,v in mathbb$, $w in mathbb^*$, тогда $t_1(u)=(hcirc g)(u)=2^, t_2(u)=((h circ g)circ f)(u)=2^<(2u)^2>$, где $t_2:mathbb o mathbb^+$ и $t_3(u)=(g circ h)(u)=(2u)^2$, $t_4(u)=(hcirc (gcirc f))(u)=2^<(2u)^2>$, где $t_4:mathbb o mathbb^+$. Как видим области определений, области значений и законы отображений совпадают, поэтому они равны, то-есть $t_2=t_4$, $ (h circ g)circ f=hcirc (gcirc f)$.